第四節裝載問題.ppt

第四節　裝載問題 若有 n 項貨物須裝載於貨輪上，第 i 項貨物之單位重量為 wi，其單位價值為 vi，i = 0,1,2, … n，而貨輪所能裝載的最大總重量為W。在最大總重量的限制條件下，如何裝載總價值最大的貨物項目，係為裝載問題，亦稱行囊問題。 設 xi 為第 i 項貨物的裝載單位數，則裝載問題的數學模式為 　Max　 v1x1+v2x2+…＋vｎxn 　 s.t. 　 w1x1＋w2x2＋…＋wnxn ≦ W 　　　 xi ≧ 0 且為整數 它是一個整數規劃問題，亦可使用動態規劃的方法求解。首先將 n 項貨物分為 n 個階段，階段編號由前至後；狀態 sk 表示用於裝載「累積至」第 k 項貨物的總重量；決策變數 xi 表示裝載第 i 項貨物的件數，則 xi 的範圍為 令　(sk) 為由第一階段至第 k 階段(即裝載第一項貨物至第 k 項貨物 ) 所獲得裝載總價值為最佳之分配，即 以順向計算程序可寫出遞迴關係為 第一階段： s1 為分配至第一階段的裝載重量，因裝載有最大總重量之限制，所以 s1≦W，其裝載件數 x1 值可為 0,1…,　　，而 　 最大值可至　　之最大整數，因此只考慮一個階段時，x1的最大值應為　　之最大整數值。 若考慮兩個階段，令 s2 表示分配於第一和第二階段之裝載重量，且 s2 ≦W，　(s2) 表示至第二階段之最佳分配，得 此時，若 s2＝W，即全部裝載第 2 項貨物，則最大裝載件數為 x2 = 。又若 0≦ s2 ≦W，其裝載第 2 項貨物的件數可為 x2 = 0,1,…, 中任挑選一數值，則第 1 項貨物可裝載重為 s1 = s2－ w2x2，故上式可改寫為： 同理 亦即可得 可由 逐步順向計算獲得　　 。 現假設有一個人帶著一個背包登山，它可攜帶物品重量的限度為11公斤，若有三項物品可供他選擇裝入背包中，已知各物品的每件重量 wi 及在登山過程中的價值 vi 如下表所示，試問此人應如何選擇攜帶物品各幾件，才能獲使總價值最大？ 因總重量限制W =11，因此第一階段 s1 分配值可為0,1,2…,11，其可攜帶第 1項物品件數最多為 故 x1 值可為 0、1、2，可將第一階段列表如下 第二階段時，將第 2 項物品考慮進來，s2 值為 1至11，其可攜帶第 2 項物品件數最多為 故 x2 值可為 0、1、2，將第二階段全部列表如下 故 x3 值可為0、1、2、3，將第三階段列表如下 動態規劃和線性規劃都屬於數學規劃的範圍，其所研究的對象本質上均是一個求極值(最大值或最小值)的問題，皆利用逐步求解。 線性規劃所研究的問題，通常與時間無關，故又稱靜態規劃。 動態規劃所研究的問題與時間有關，主要探討具有多階段決策過程的一類問題，將問題的整體特(時間或空間)，分成若干前後銜接，具有連貫性的問題，將前後有關聯的一系列單階段決策問題，一個一個予以解決，最後求出整個問題的最佳決策序列。 作業研究．Chapter 13　動態規劃 13-* 作 業 研 究 陳坤茂　著 13 動態規劃 8 10 5 4 5 3 1 2 3 價值vi 重量wi 物品編號