包裝物流系統(tǒng)優(yōu)化方法-全文預(yù)覽
【正文】 ???????niiiniiiniii xvxvxvyvxv1211211 0/1背包問題可以看作是決策一個序列 (x1, x2, …, x n)，對任一變量 xi的決策是決定 xi=1還是 xi=0。 ）（ 2 }),1(),1( m ax{),1(),(???????????iiiiwjvwjiVjiVwjjiVjiV第一個式子表明：如果第 i個物品的重量大于背包的容量，則裝入前 i個物品得到的最大價值和裝入前 i1個物品得到的最大價值是相同的，即物品 i不能裝入背包；第二個式子表明：如果第 i個物品的重量小于背包的容量，則會有以下兩種情況：（ 1）如果把第 i個物品裝入背包，則背包中物品的價值等于把前 i1個物品裝入容量為 jwi的背包中的價值加上第 i個物品的價值 vi；（ 2）如果第 i個物品沒有裝入背包，則背包中物品的價值就等于把前 i1個物品裝入容量為 j的背包中所取得的價值。為了確定裝入背包的具體物品，從 V(n,C)的值向前推，如果 V(n,C)V(n1,C)，表明第 n個物品被裝入背包，前 n1個物品被裝入容量為 Cwn的背包中；否則，第 n個物品沒有被裝入背包，前 n1個物品被裝入容量為 C的背包中。 ）（ 2 }),1(),1( m ax{ ),1(),(???????????iiiiwjvwjiVjiVwjjiVjiV0/1背包求解 （ 填表 ） 過程 x5=1 x4=0 x3=0 x2=1 x1=1 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 w1=2 v1=6 1 0 0 6 6 6 6 6 6 6 6 6 w2=2 v2=3 2 0 0 6 6 9 9 9 9 9 9 9 w3=6 v3=5 3 0 0 6 6 9 9 9 9 11 11 14 w4=5 v4=4 4 0 0 6 6 9 9 9 10 11 13 14 w5=5 v5=6 5 0 0 6 6 9 9 9 12 15 15 15 }),1(),1( m ax{ ),1(),(???????????iiiiwjvwjiVjiVwjjiVjiV??????????),1(),(,1),1(),(0jiVjiVwjjjiVjiVxii可以看到 ， 裝入背包的物品的最大價值是 15， 裝入背包的物品為 X={1, 1, 0, 0, 1}。由此，得到如下函數(shù)： ??????????),1(),(,1),1(),(0jiVjiVwjjjiVjiVxii例如，有 5個物品，其重量分別是 {2, 2, 6, 5, 4}，價值分別為 {6, 3, 5, 4, 6}，背包的容量為 10，求裝入背包的物品和獲得的最大價值。 第一階段，只裝入前 1個物品，確定在各種情況下的背包能夠得到的最大價值； 第二階段，只裝入前 2個物品，確定在各種情況下的背包能夠得到的最大價值；依此類推，直到第 n個階段。 這兩種情況下背包價值的最大者應(yīng)該是對 xi決策后的背包價值。 設(shè) (x1, x2, … , xn)是所給 0/1背包問題的一個最優(yōu)解 ， 則 ( x2, … , xn)是下面一個子問題的最優(yōu)解： ????????????)2(}1,0{112nixxwCxwiniii如若不然，設(shè) (y2, …, yn)是上述子問題的一個最優(yōu)解，則 ， 且 。 背包問題是如何選擇裝入背包的物品 ， 使得裝入背包中物品的總價值最大 ?如果在選擇裝入背包的物品時 ， 對每種物品 i只有兩種選擇：裝入背包或不裝入背包 ， 即不能將物品 i裝入背包多次 ， 也不能只裝入物品 i的一部分 ， 則稱為 0/1背包問題 。 背包問題（貨物配載問題） 設(shè) xj 為第 j 種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)學(xué)模型如下： ?????????????)..(0max1njxaxaxcZjnijjjnjjj? 且為整數(shù)用動態(tài)規(guī)劃方法求解，令 fk(y) = 總重量不超過 y 公斤，包中只裝有前 k 種物品時的最大使用價值。 （ 3）節(jié)約法計算的配送路線并不一定是總路程最短。 總路徑： DC— 3— 4— DC DC— 1— 2— DC DC— 5— DC DC— 6— DC 總路程： 7+3+8=18 5+6+6=17 6+6=12 5+5=10 節(jié)約里程： 12 5 0 0 序號 路徑 節(jié)約里程 序號 路徑 節(jié)約里程 1 3~4 12 9 1~5 2 2 56 8 10 1~3 2 3 2~3 6 11 3~5 1 4 4~5 6 12 4~6 0 5 1~2 5 1~4 6 2~6 5 2~5 7 1~6 4 3~6 8 2~4 3 第三步 根據(jù)節(jié)約里程順序表和配送中心的約束條件 ， 繪制配送路線。 1 2 3 4 5 8 7 6 11 10 9 12 s t 9 7 3 2 4 2 2 7 1 11 11 8 6 5 4 3 5 6 5 2 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1