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

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

3、，同時(shí)考慮重量或面積、 體積 etc . 即二維、三維、裝箱問題；,2、對(duì)每個(gè)箱子的負(fù)荷限制不是常數(shù) C ; 而是,最優(yōu)目標(biāo)可如何提？,3、物品J1，J2，Jn 的負(fù)荷事先并不知道，來貨是 隨到隨裝；即 在線（On-Line）裝箱問題；,4、由于場(chǎng)地的限制，在同一時(shí)間只能允許一定數(shù)量的 箱子停留現(xiàn)場(chǎng)可供使用, etc .,5,學(xué)習(xí)交流PPT,1 裝箱問題的描述,BP 的應(yīng)用舉例：,1、下料問題 軋鋼廠生產(chǎn)的線材一般為同一長(zhǎng)度, 而用 戶所需的線材則可能具有各種不同的尺寸, 如何根據(jù)用 戶提出的要求，用最少的線材截出所需的定貨；,2、 二維 BP 玻璃廠生產(chǎn)出長(zhǎng)寬一定的大的平板玻璃, 但用戶所需

4、玻璃的長(zhǎng)寬可能有許多差異，如何根據(jù)用 戶提出的要求，用最少的平板玻璃截出所需的定貨;,3、計(jì)算機(jī)的存貯問題 如要把大小不同的共 10 MB 的 文件拷貝到磁盤中去，而每張磁盤的容量為 1. 44 MB , 已知每個(gè)文件的字節(jié)數(shù)不超過 1.44 MB , 而且一個(gè)文件 不能分成幾部分存貯，如何用最少的磁盤張數(shù)完成 .,4、生產(chǎn)流水線的平衡問題 給定流水節(jié)拍 C , 如何設(shè)置 最少的工作站，（按一定的緊前約束）沿著流水線將任 務(wù)分配到各工作站上 . 稱為帶附加優(yōu)先約束的 BP .,BP 是容量限制的工廠選址問題的特例之一.,Go back,6,學(xué)習(xí)交流PPT,第三章 裝箱問題,2 裝箱問題的最優(yōu)解

5、值下界,由于 BP 是 NP-C 問題，所以求解考慮 一是盡可能 改進(jìn)簡(jiǎn)單的窮舉搜索法，減少搜索工作量 . 如: 分支 定界法；二是啟發(fā)式（近似）算法 .,顯然 是它的一個(gè)最優(yōu)解 .,7,學(xué)習(xí)交流PPT,2 裝箱問題的最優(yōu)解值下界,Theorem 3.1,BP 最優(yōu)值的一個(gè)下界為,表示不小于 a 的最小整數(shù).,Theorem 3.2,設(shè) a 是任意滿足 的整數(shù),對(duì) BP 的任一實(shí)例 I ,記,則,是最優(yōu)解的一個(gè)下界 .,8,學(xué)習(xí)交流PPT,第三章 裝箱問題,a,C,C/2,C-a,I1,I2,I3,Proof :,僅考慮對(duì) I1,I2,I3中物品的裝箱 .,中物品的長(zhǎng)度大于C/2 ,每個(gè)物品需

6、單獨(dú)放入一個(gè)箱子， 這就需要 個(gè)箱子 .,又 中每個(gè)物品長(zhǎng)度至少為 a ,但可能與 I2 中的 物品共用箱子，,它不能與 I1 中的物品共用箱子,與 I2 中的物品如何？,由于放 I2 中物品的 個(gè)箱子的剩余 總長(zhǎng)度為,在最好的情形下， 被 I3 中的物品全部充滿，故剩 下總長(zhǎng)度 將另外至少 個(gè)附加的箱子 .,Note: 可能小于零,是最優(yōu)解的一個(gè)下界 .,9,學(xué)習(xí)交流PPT,2 裝箱問題的最優(yōu)解值下界,問 ？,未必！,如,Corollary 3.1,記,則 L2 是裝箱問題的最優(yōu)解的一個(gè)下界，且 .,Proof :,L2 為最優(yōu)解的下界是顯然的 .,(若證明 ，則可得 ),當(dāng) a = 0 時(shí)

7、， 是所有物品 .,Go back,10,學(xué)習(xí)交流PPT,第三章 裝箱問題,3 裝箱問題的近似算法,一、NF ( Next Fit ) 算法,設(shè)物品 J1，J2,，Jn 的長(zhǎng)度分別為 w1，w2,，wn 箱子 B1，B2，的長(zhǎng)均為 C ，按物品給定的順序裝箱 .,先將 J1 放入 B1, 如果 則將 J2 放入 B1 ,如果 而,則 B1 已放入 J1，J2,，Jj，將其關(guān)閉，將 Jj+1 放入 B2 .,同法進(jìn)行，直到所有物品裝完為止 .,特點(diǎn)：,1、按物品給定的順序裝箱；,2、關(guān)閉原則 .,對(duì)當(dāng)前要裝的物品 Ji 只關(guān)心具有最大下標(biāo)的已使 用過的箱子 Bj 能否裝得下？ 能. 則 Ji 放

8、入 Bj ；否 . 關(guān)閉 Bj ，Ji 放入新箱子 Bj+1 .,計(jì)算復(fù)雜性為 O(n).,11,學(xué)習(xí)交流PPT,3 裝箱問題的近似算法,Example 1,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 中放不下, 所 以關(guān)閉 B1 , 將 J2 放入 B2 , J3 在 B2 中放不下(不考慮 B1 是否能裝), 所以關(guān)閉 B2 將 J3 放入 B3，,解為:,其余為零，,12,學(xué)習(xí)交流PPT,第三章 裝箱問題,Theorem 3.3,Pro

9、of :,先證 再說明不可改進(jìn),設(shè) I 為任一實(shí)例，,(要證 ),顯然，由 得,反證,如果 ,則 對(duì)任意 i = 1, 2, k,由于起用第 2i 個(gè)箱子是因?yàn)榈?2i -1 個(gè)箱子放不下第2i 個(gè)箱子中第一個(gè)物品,因此這兩個(gè)箱子中物品的總長(zhǎng)度 大于 C ，所以前 2k 個(gè)箱子中物品的總長(zhǎng)度大于 Ck .,這與 矛盾 .,考慮實(shí)例 I : C = 1,13,學(xué)習(xí)交流PPT,3 裝箱問題的近似算法,二、FF ( First Fit ) 算法,設(shè)物品 J1，J2,，Jn 的長(zhǎng)度分別為 w1，w2,，wn 箱子 B1，B2，的長(zhǎng)均為 C ，按物品給定的順序裝箱 .,I : C = 10,用 NF 算

10、法裝 箱, 當(dāng)放入 J3 時(shí), 僅看 B2,是否能放入，因 B1 已關(guān)閉,參見 EX .1,但事實(shí)上，B1 此時(shí)是能放得下 J3 的 .,如何修正 NF 算法,先將 J1 放入 B1，若 ,則 J2 放入 B1 , 否,則，J2 放入 B2 ; 若 J2 已放入 B2，對(duì)于 J3 則依次檢查,B1、B2 , 若 B1 能放得下, 則 J3 放入 B1 , 否則查看 B2 ,若 B2 能放得下，則 J3 放入 B2 , 否則啟用 B3, J3 放入 B3.,14,學(xué)習(xí)交流PPT,第三章 裝箱問題,一般地，J1,，Jj 已放入 B1,，Bi 箱子，對(duì)于 Jj+1, 則依次檢查 B1，B2,，Bi，

11、將 Jj+1 放入首先找到的能 放得下的箱子，如果都放不下，則啟用箱子 Bi+1 ，將 Jj+1 放入 Bi+1 ，如此繼續(xù)，直到所有物品裝完為止 .,計(jì)算復(fù)雜性為 O(nlogn).,特點(diǎn)：,1、按物品給定的順序裝箱；,2、對(duì)于每個(gè)物品 Jj 總是放在能容納它的具 有最小標(biāo)號(hào)的箱子 .,但精度比NF 算法更高,15,學(xué)習(xí)交流PPT,3 裝箱問題的近似算法,Theorem 3.4,Theorem 3.5,對(duì)任意實(shí)例 I ，,而且存在 任意大的實(shí)例 I ，使,因而,16,學(xué)習(xí)交流PPT,第三章 裝箱問題,Example 2,I : C = 10,J1,J5,J6,J4,J3,J2,B1,B2,B

12、3,B4,B5,J1,J2,J3,J4,J5,J6,Solution :,首先，將 J1 放入 B1;,由于 J2 在 B1 中放不下, 所 以將 J2 放入 B2 , 對(duì)于 J3 , 先檢查 B1 是否能 容納下, 能 . 所以將 J3 放 入 B1，,解為:,其余為零，,17,學(xué)習(xí)交流PPT,3 裝箱問題的近似算法,Example 3,I : C = 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 .

13、3 用 FF 算法裝箱, 當(dāng)放入 J4 時(shí), B1 能容納 J4 就放入 B1 ，而事實(shí)上，放入 B2 更好 .,18,學(xué)習(xí)交流PPT,第三章 裝箱問題,三、BF ( Best Fit ) 算法,與 FF 算法相似，按物品給定的順序裝箱，區(qū)別在 于對(duì)于每個(gè)物品 Jj 是放在一個(gè)使得 Jj 放入之后，Bi 所 剩余長(zhǎng)度為最小者 .,即在處理 Jj 時(shí)，若 B1，B2,，Bi 非空，而 Bi+1 尚 未啟用，設(shè) B1，B2,，Bi 所余的長(zhǎng)度為,若,則將 Jj 放入 Bi+1 內(nèi);,否則，從 的 Bk 中，選取 一個(gè) Bl,使得 為最小者 .,BF 算法的絕對(duì)性能比、計(jì)算復(fù)雜性與 FF 算法相同

14、.,19,學(xué)習(xí)交流PPT,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)解.,20,學(xué)習(xí)交流PPT,第三章 裝箱問題,四、FFD ( First Fit Decreasing ) 算法,FFD 算法是先將物品按長(zhǎng)度從大到小排序，然后用 FF 算法對(duì)物品裝箱 .,該算法的計(jì)算復(fù)雜性為 O(nlogn).,Example 5,I : C = 10,J1,J5,J6,J4,J3,J2,Solution :,已知

15、：,B1,B2,B3,B4,B5,J1,J2,J3,J4,J5,J6,是最優(yōu)的 .,NFD 算法？ BFD 算法？,21,學(xué)習(xí)交流PPT,3 裝箱問題的近似算法,Theorem 3.6,Proof :,顯然對(duì)任意實(shí)例 I ，有,記,首先證明兩個(gè)結(jié)論：,(1) FFD 算法所用的第 個(gè)箱子中每個(gè)的 長(zhǎng)度不超過,記 wi 是放入第 個(gè)箱子中的第一個(gè)物品,只需證,用反證法，若不然，則有 ，因此 FFD,算法中前 個(gè)箱子中, 每個(gè)箱子至多有兩個(gè)物品 .,22,學(xué)習(xí)交流PPT,第三章 裝箱問題,可證明存在 使前 k 個(gè)恰各含一個(gè)物品，后 個(gè)箱子各含兩個(gè)物品.,因?yàn)槿舨蝗唬瑒t存在兩個(gè)箱子 使 Bp有兩 個(gè)

16、物品 , Bq 有一個(gè)物品 因物品已從大到 小排列，故 , 因此 從 而可以將wi 放入 Bq 中，矛盾.,23,學(xué)習(xí)交流PPT,3 裝箱問題的近似算法,因?yàn)?FFD 未將 wk+1,，wi 放入前 k 個(gè)箱子，說明 其中任一個(gè)箱子已放不下, 故在最優(yōu)解中也至少有 k 個(gè) 箱子不含 wk+1,，wi 中任一個(gè)物品 . 假設(shè)就是前 k 個(gè) 箱子，因此在最優(yōu)解中， wk+1,，wi-1 也會(huì)兩兩放入第,個(gè)箱子中，且因?yàn)檫@些物品長(zhǎng)度大于 , 所以,每個(gè)箱子中只有兩個(gè)物品，且 已放不下 . 但最 優(yōu)解中 wi 必須放入前 個(gè)箱子中，矛盾. 故,(2) FFD 算法放入第 個(gè)箱子中物品數(shù)不超過,而如果至

17、少有 個(gè)物品放入第,個(gè)箱子中，記前 個(gè)物品的長(zhǎng)度為 .,24,學(xué)習(xí)交流PPT,第三章 裝箱問題,記 FFD 算法中前 個(gè)箱子中每個(gè)箱子物品總長(zhǎng)為,顯然，對(duì)任意,否則長(zhǎng)為 的物品可放入第 j 個(gè)箱子中，因此,矛盾 .,所以 (2) 結(jié)論成立 .,由(1)、(2) 知FFD 算法比最優(yōu)算法多用的箱子是用 來放至多 個(gè)物品，而每個(gè)物品長(zhǎng)不超過 ，因此,25,學(xué)習(xí)交流PPT,3 裝箱問題的近似算法,因此,因?yàn)?如果 ，則 ，故不妨設(shè),考慮實(shí)例 I ：物品集長(zhǎng)度為 , C 為箱長(zhǎng).,說明 是不可改進(jìn)的 .,26,學(xué)習(xí)交流PPT,第三章 裝箱問題,比較 NF 算法、FF ( BF ) 算法、FFD 算法，

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

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