一維裝箱問題典型算法.ppt

1、第三章 裝箱問題,信息處理中的組合優(yōu)化,Combinatorial Optimization in Information Processing,第三章 裝箱問題,1 裝箱問題的描述,2 裝箱問題的最優(yōu)解值下界,3 裝箱問題的近似算法,第三章 裝箱問題,裝箱問題（Bin Packing）是一個經(jīng)典的組合優(yōu)化 問題，有著廣泛的應用，在日常生活中也屢見不鮮 .,1 裝箱問題的描述,設(shè)有許多具有同樣結(jié)構(gòu)和負荷的箱子 B1，B2， 其數(shù)量足夠供所達到目的之用 . 每個箱子的負荷（可為 長度、重量 etc.）為 C ,今有 n 個負荷為 wj，0 wj C j = 1，2，n 的物品 J1，J2，Jn

2、需要裝入箱內(nèi).,裝箱問題：,是指尋找一種方法，使得能以最小數(shù)量的箱子數(shù)將 J1，J2，Jn 全部裝入箱內(nèi).,1 裝箱問題的描述,由于 wi C，所以 BP 的最優(yōu)解的箱子數(shù)不超過 n .,設(shè),則裝箱問題的整數(shù)線性規(guī)劃模型為：,約束條件（1）表示：一旦箱子 Bi 被使用，放入 Bi 的物品總負荷不超過 C ；,約束條件（2）表示：每個物品恰好放入一個箱子中 .,第三章 裝箱問題,上述裝箱問題是這類問題最早被研究的，也是提 法上最簡單的問題，稱為一維裝箱問題 . 但,裝箱問題的其他一些提法：,1、在裝箱時，不僅考慮長度，同時考慮重量或面積、 體積 etc . 即二維、三維、裝箱問題；,2、對每個箱

3、子的負荷限制不是常數(shù) C ; 而是,最優(yōu)目標可如何提？,3、物品J1，J2，Jn 的負荷事先并不知道，來貨是 隨到隨裝；即 在線（On-Line）裝箱問題；,4、由于場地的限制，在同一時間只能允許一定數(shù)量的 箱子停留現(xiàn)場可供使用, etc .,1 裝箱問題的描述,BP 的應用舉例：,1、下料問題 軋鋼廠生產(chǎn)的線材一般為同一長度, 而用 戶所需的線材則可能具有各種不同的尺寸, 如何根據(jù)用 戶提出的要求，用最少的線材截出所需的定貨；,2、 二維 BP 玻璃廠生產(chǎn)出長寬一定的大的平板玻璃, 但用戶所需玻璃的長寬可能有許多差異，如何根據(jù)用 戶提出的要求，用最少的平板玻璃截出所需的定貨;,3、計算機的存

4、貯問題 如要把大小不同的共 10 MB 的 文件拷貝到磁盤中去，而每張磁盤的容量為 1. 44 MB , 已知每個文件的字節(jié)數(shù)不超過 1.44 MB , 而且一個文件 不能分成幾部分存貯，如何用最少的磁盤張數(shù)完成 .,4、生產(chǎn)流水線的平衡問題 給定流水節(jié)拍 C , 如何設(shè)置 最少的工作站，（按一定的緊前約束）沿著流水線將任 務(wù)分配到各工作站上 . 稱為帶附加優(yōu)先約束的 BP .,BP 是容量限制的工廠選址問題的特例之一.,Go back,第三章 裝箱問題,2 裝箱問題的最優(yōu)解值下界,由于 BP 是 NP-C 問題，所以求解考慮 一是盡可能 改進簡單的窮舉搜索法，減少搜索工作量 . 如: 分支

5、定界法；二是啟發(fā)式（近似）算法 .,顯然 是它的一個最優(yōu)解 .,2 裝箱問題的最優(yōu)解值下界,Theorem 3.1,BP 最優(yōu)值的一個下界為,表示不小于 a 的最小整數(shù).,Theorem 3.2,設(shè) a 是任意滿足 的整數(shù),對 BP 的任一實例 I ,記,則,是最優(yōu)解的一個下界 .,第三章 裝箱問題,a,C,C/2,C-a,I1,I2,I3,Proof :,僅考慮對 I1,I2,I3中物品的裝箱 .,中物品的長度大于C/2 ,每個物品需單獨放入一個箱子， 這就需要 個箱子 .,又 中每個物品長度至少為 a ,但可能與 I2 中的 物品共用箱子，,它不能與 I1 中的物品共用箱子,與 I2 中的

6、物品如何？,由于放 I2 中物品的 個箱子的剩余 總長度為,在最好的情形下， 被 I3 中的物品全部充滿，故剩 下總長度 將另外至少 個附加的箱子 .,Note: 可能小于零,是最優(yōu)解的一個下界 .,2 裝箱問題的最優(yōu)解值下界,問 ？,未必！,如,Corollary 3.1,記,則 L2 是裝箱問題的最優(yōu)解的一個下界，且 .,Proof :,L2 為最優(yōu)解的下界是顯然的 .,(若證明 ，則可得 ),當 a = 0 時， 是所有物品 .,Go back,第三章 裝箱問題,3 裝箱問題的近似算法,一、NF ( Next Fit ) 算法,設(shè)物品 J1，J2,，Jn 的長度分別為 w1，w2,，wn

7、 箱子 B1，B2，的長均為 C ，按物品給定的順序裝箱 .,先將 J1 放入 B1, 如果 則將 J2 放入 B1 ,如果 而,則 B1 已放入 J1，J2,，Jj，將其關(guān)閉，將 Jj+1 放入 B2 .,同法進行，直到所有物品裝完為止 .,特點：,1、按物品給定的順序裝箱；,2、關(guān)閉原則 .,對當前要裝的物品 Ji 只關(guān)心具有最大下標的已使 用過的箱子 Bj 能否裝得下？ 能. 則 Ji 放入 Bj ；否 . 關(guān)閉 Bj ，Ji 放入新箱子 Bj+1 .,計算復雜性為 O(n).,3 裝箱問題的近似算法,Example 1,I : C = 10,J1,J5,J6,J4,J3,J2,B1,B

8、2,B3,B4,B5,J1,J2,J3,J4,J5,J6,Solution :,首先，將 J1 放入 B1;,由于 J2 在 B1 中放不下, 所 以關(guān)閉 B1 , 將 J2 放入 B2 , J3 在 B2 中放不下(不考慮 B1 是否能裝), 所以關(guān)閉 B2 將 J3 放入 B3，,解為:,其余為零，,第三章 裝箱問題,Theorem 3.3,Proof :,先證 再說明不可改進,設(shè) I 為任一實例，,(要證 ),顯然，由 得,反證,如果 ,則 對任意 i = 1, 2, k,由于起用第 2i 個箱子是因為第 2i -1 個箱子放不下第2i 個箱子中第一個物品,因此這兩個箱子中物品的總長度

9、大于 C ，所以前 2k 個箱子中物品的總長度大于 Ck .,這與 矛盾 .,考慮實例 I : C = 1,3 裝箱問題的近似算法,二、FF ( First Fit ) 算法,設(shè)物品 J1，J2,，Jn 的長度分別為 w1，w2,，wn 箱子 B1，B2，的長均為 C ，按物品給定的順序裝箱 .,I : C = 10,用 NF 算法裝 箱, 當放入 J3 時, 僅看 B2,是否能放入，因 B1 已關(guān)閉,參見 EX .1,但事實上，B1 此時是能放得下 J3 的 .,如何修正 NF 算法,先將 J1 放入 B1，若 ,則 J2 放入 B1 , 否,則，J2 放入 B2 ; 若 J2 已放入 B2

10、，對于 J3 則依次檢查,B1、B2 , 若 B1 能放得下, 則 J3 放入 B1 , 否則查看 B2 ,若 B2 能放得下，則 J3 放入 B2 , 否則啟用 B3, J3 放入 B3.,第三章 裝箱問題,一般地，J1,，Jj 已放入 B1,，Bi 箱子，對于 Jj+1, 則依次檢查 B1，B2,，Bi，將 Jj+1 放入首先找到的能 放得下的箱子，如果都放不下，則啟用箱子 Bi+1 ，將 Jj+1 放入 Bi+1 ，如此繼續(xù)，直到所有物品裝完為止 .,計算復雜性為 O(nlogn).,特點：,1、按物品給定的順序裝箱；,2、對于每個物品 Jj 總是放在能容納它的具 有最小標號的箱子 .,

11、但精度比NF 算法更高,3 裝箱問題的近似算法,Theorem 3.4,Theorem 3.5,對任意實例 I ，,而且存在 任意大的實例 I ，使,因而,第三章 裝箱問題,Example 2,I : C = 10,J1,J5,J6,J4,J3,J2,B1,B2,B3,B4,B5,J1,J2,J3,J4,J5,J6,Solution :,首先，將 J1 放入 B1;,由于 J2 在 B1 中放不下, 所 以將 J2 放入 B2 , 對于 J3 , 先檢查 B1 是否能 容納下, 能 . 所以將 J3 放 入 B1，,解為:,其余為零，,3 裝箱問題的近似算法,Example 3,I : C =

12、 10,J1,J4,J3,J2,Solution :,用 NF 算法,B1,B2,B3,B4,B5,J1,J2,J6,J5,J3,J4,B1,B2,B3,B4,B5,J1,J2,J6,J5,J3,J4,J6,J5,用 FF 算法,參見 EX .3 用 FF 算法裝箱, 當放入 J4 時, B1 能容納 J4 就放入 B1 ，而事實上，放入 B2 更好 .,第三章 裝箱問題,三、BF ( Best Fit ) 算法,與 FF 算法相似，按物品給定的順序裝箱，區(qū)別在 于對于每個物品 Jj 是放在一個使得 Jj 放入之后，Bi 所 剩余長度為最小者 .,即在處理 Jj 時，若 B1，B2,，Bi 非

13、空，而 Bi+1 尚 未啟用，設(shè) B1，B2,，Bi 所余的長度為,若,則將 Jj 放入 Bi+1 內(nèi);,否則，從 的 Bk 中，選取 一個 Bl,使得 為最小者 .,BF 算法的絕對性能比、計算復雜性與 FF 算法相同 .,Example 4,I : C = 10,3 裝箱問題的近似算法,J1,J4,J3,J2,J6,J5,B1,B2,B3,B4,B5,J1,J2,J6,J5,J3,J4,Solution :,用 BF 算法,解為:,其余為零，,而 此為最優(yōu)解.,第三章 裝箱問題,四、FFD ( First Fit Decreasing ) 算法,FFD 算法是先將物品按長度從大到小排序，然

14、后用 FF 算法對物品裝箱 .,該算法的計算復雜性為 O(nlogn).,Example 5,I : C = 10,J1,J5,J6,J4,J3,J2,Solution :,已知：,B1,B2,B3,B4,B5,J1,J2,J3,J4,J5,J6,是最優(yōu)的 .,NFD 算法？ BFD 算法？,3 裝箱問題的近似算法,Theorem 3.6,Proof :,顯然對任意實例 I ，有,記,首先證明兩個結(jié)論：,(1) FFD 算法所用的第 個箱子中每個的 長度不超過,記 wi 是放入第 個箱子中的第一個物品,只需證,用反證法，若不然，則有 ，因此 FFD,算法中前 個箱子中, 每個箱子至多有兩個物品

15、 .,第三章 裝箱問題,可證明存在 使前 k 個恰各含一個物品，后 個箱子各含兩個物品.,因為若不然，則存在兩個箱子 使 Bp有兩 個物品 , Bq 有一個物品 因物品已從大到 小排列，故 , 因此 從 而可以將wi 放入 Bq 中，矛盾.,3 裝箱問題的近似算法,因為 FFD 未將 wk+1,，wi 放入前 k 個箱子，說明 其中任一個箱子已放不下, 故在最優(yōu)解中也至少有 k 個 箱子不含 wk+1,，wi 中任一個物品 . 假設(shè)就是前 k 個 箱子，因此在最優(yōu)解中， wk+1,，wi-1 也會兩兩放入第,個箱子中，且因為這些物品長度大于 , 所以,每個箱子中只有兩個物品，且 已放不下 .

16、但最 優(yōu)解中 wi 必須放入前 個箱子中，矛盾. 故,(2) FFD 算法放入第 個箱子中物品數(shù)不超過,而如果至少有 個物品放入第,個箱子中，記前 個物品的長度為 .,第三章 裝箱問題,記 FFD 算法中前 個箱子中每個箱子物品總長為,顯然，對任意,否則長為 的物品可放入第 j 個箱子中，因此,矛盾 .,所以 (2) 結(jié)論成立 .,由(1)、(2) 知FFD 算法比最優(yōu)算法多用的箱子是用 來放至多 個物品，而每個物品長不超過 ，因此,3 裝箱問題的近似算法,因此,因為 如果 ，則 ，故不妨設(shè),考慮實例 I ：物品集長度為 , C 為箱長.,說明 是不可改進的 .,第三章 裝箱問題,比較 NF

17、算法、FF ( BF ) 算法、FFD 算法，它們 的近似程度一個比一個好，但這并不是說 NF、FF(BF) 就失去了使用價值 .,1、FF(BF)、FFD 算法都要將所有物品全部裝好后 , 所 有箱子才能一起運走，而 NF 算法無此限制，很適合裝 箱場地小的情形；,2、FFD 算法要求所有物品全部到達后才開始裝箱, 而 NF、FF(BF) 算法在給某一物品裝箱時，可以不知道 下一個物品的長度如何，適合在線裝箱 .,存儲罐注液問題,第三章 裝箱問題,某化工廠有 9 個不同大小的存儲罐，有一些已經(jīng)裝 某液體 . 現(xiàn)新到一批液體化工原料需要存儲，這些液體 不能混合存儲，它們分別是 1200 m3

18、苯，700 m3 丁醇， 1000 m3 丙醇，450 m3 苯乙醇和1200 m3 四氫呋喃 . 下表列出每個存儲罐的屬性(單位: m3), 問應如何將新到 的液體原料裝罐, 才能使保留未用的存儲罐個數(shù)最多?,第三章 裝箱問題,Solution :,分別記苯、丁醇、丙醇、苯乙醇、四氫呋喃 為第1，2，3，4，5種液體 . 顯然，新到液體應盡可能 裝入已存有此種液體的罐中 .,所以余下液體為：900 m3 苯，700 m3 丁醇，1000 m3 丙醇，450 m3 乙醇和700 m3 四氫呋喃 . 剩余空罐 為1，3，4，5，6，8，9 . 由于不允許混合，每種液體 至少需要1個空罐 .,令,記第 j 個空罐的容量為 cj ，j = 1, 3, 4, 5, 6, 8, 9,第 i 種剩余液體的體積為 li , i = 1, 2, 3, 4, 5 .,第三章 裝箱問題,整數(shù)規(guī)劃模型：,表示第j 個 空罐被使用,每個罐子至多 裝一種液體,每種液體的體積不