1、1例例1 背包問題背包問題 有有n件物品，編號為件物品，編號為 1，2，n。第。第 件重為件重為 kg，價值為，價值為 元。今一裝包者欲將這些物品裝入元。今一裝包者欲將這些物品裝入一包，其質量不能超過一包，其質量不能超過 kg，問應裝入哪幾件價值最大？，問應裝入哪幾件價值最大？iipaia0-1規劃應用背景2 解解 引入變量引入變量 將將 物品裝包物品裝包 不將不將 物品裝包物品裝包 于是得問題的模型為于是得問題的模型為 取取0或或1，i=1，2，n 背包問題看似簡單，但應用很廣，例如某些投資問題即可歸入背包問題背包問題看似簡單，但應用很廣，例如某些投資問題即可歸入背包問題模型。此類問題可以模

2、型。此類問題可以1,0iixxii11 1max. .niiinnp xsta xa xaix3 描述為：設有總額為描述為：設有總額為 元的資金，投資幾項事業，第元的資金，投資幾項事業，第 項副業需投資項副業需投資 元，元，利潤為利潤為 元元,問應選擇哪些項總利潤為最大？問應選擇哪些項總利潤為最大？ 例例2 某鉆井隊要從以下某鉆井隊要從以下10個可供選擇的井位中確定個可供選擇的井位中確定5個鉆井探油，使總個鉆井探油，使總的鉆探費用為最小。若的鉆探費用為最小。若10個井位的代號為個井位的代號為 ，相應的鉆探費，相應的鉆探費用為用為 ，并且井位選擇要滿足下列限制條件：，并且井位選擇要滿足下列限制條

3、件： （1）或選）或選 和和 ，或選，或選 ； （2）選擇了）選擇了 或或 就不能選就不能選 ，反之亦然；，反之亦然； （3）在）在 中最多只能選兩個。中最多只能選兩個。 試建立其數學模型：試建立其數學模型：aiiaib1210,s ss1210,c cc1s7s8s3s4s5s5678,s s s s4 解解 引入變量引入變量 選擇選擇 不選擇不選擇 于是以上問題的數學模型為：于是以上問題的數學模型為：1,0iixxisis101miniiic x5 101187835455678511. .11201iiixxxxxstxxxxxxxxx6 例例3 指派問題。有指派問題。有 項任務，由項任

4、務，由 個人來完成，每人只能干一件，第個人來完成，每人只能干一件，第 個人完成第個人完成第 項任務需要的時間為項任務需要的時間為 小時，問怎樣安排能使總用時最少？小時，問怎樣安排能使總用時最少？ 解解 引入引入0-1型變量型變量 人完成人完成 任務任務 人不去完成人不去完成 任務任務 于是該問題的數學模型為于是該問題的數學模型為nnijijc1,0ijijxxiij11minnnijijijzc xj7 111,1,2,1,1,2,01nijinijjijxjnxinxS.t.8 0-1規劃模型因其特殊性，不同于整數規劃的解法。如一般0-1規劃的隱枚舉法，指派問題中的匈牙利法，背包問題則可以用動態規劃的方法求解。01規劃解法91011121314151617181920212223242526272829303132333435363738394041。4243444