一維裝箱問題典型算法PPT學(xué)習(xí)教案

1、會計學(xué)1一維裝箱問題典型算法一維裝箱問題典型算法第1頁/共33頁 裝箱問題（Bin Packing）是一個經(jīng)典的組合優(yōu)化問題，有著廣泛的應(yīng)用，在日常生活中也屢見不鮮 . 設(shè)有許多具有同樣結(jié)構(gòu)和負(fù)荷的箱子 B1，B2，其數(shù)量足夠供所達(dá)到目的之用 . 每個箱子的負(fù)荷（可為長度、重量 etc.）為 C ,今有 n 個負(fù)荷為 wj，0 wj C j = 1，2，n 的物品 J1，J2，Jn 需要裝入箱內(nèi). 是指尋找一種方法，使得能以最小數(shù)量的箱子數(shù)將J1，J2，Jn 全部裝入箱內(nèi)第2頁/共33頁1 裝箱問題的描述由于 wi C，所以 BP 的最優(yōu)解的箱子數(shù)不超過 n設(shè)11;0iyin箱子 Bi 被使用

2、否則1,1.0ijxi jn物品 Jj 放入箱子 Bi 中否則則裝箱問題的整數(shù)線性規(guī)劃模型為：1minniizy1. .1(1)njijijstw xCyin01,01,1.iijyorxori jn ()BP約束條件（1）表示：一旦箱子 Bi 被使用，放入 Bi 的物品總負(fù)荷不超過 C ；約束條件（2）表示：每個物品恰好放入一個箱子中 .11(2)nijix1jn 第3頁/共33頁第三章 裝箱問題 上述裝箱問題是這類問題最早被研究的，也是提法上最簡單的問題，稱為一維裝箱問題但.BPNP C裝箱問題的其他一些提法：1、在裝箱時，不僅考慮長度，同時考慮重量或面積、 體積 etc . 即二維、三維

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

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

5、索工作量 . 如: 分支定界法；二是啟發(fā)式（近似）算法 .1minniizy1. .1(1)njijijstw xCyin01,01,1.iijyorxori jn ()BP01, 01,1.iijyxi jn ()C BP 顯然 是它的一個最優(yōu)解 . 1,0 (),1.iiiijiwxxijyi jnC 1niioptwzC11(2)nijix1jn 第6頁/共33頁2 裝箱問題的最優(yōu)解值下界Theorem 3.1BP 最優(yōu)值的一個下界為11.niiwLCa 表示不小于 a 的最小整數(shù).Theorem 3.2 設(shè) a 是任意滿足 的整數(shù),對 BP 的任一實例 I ,02Ca記1,jIj wC

6、a物品2,2jCIj Caw物品3,2jCIjwa物品則32212()( )max 0,jjj Ij IwI CwL aIIC是最優(yōu)解的一個下界第7頁/共33頁第三章 裝箱問題aCC/2C-aI1I2I3Proof :僅考慮對 I1,I2,I3中物品的裝箱 .中物品的長度大于C/2 ,12II每個物品需單獨放入一個箱子，這就需要 個箱子 .12II又 中每個物品長度至少為 a ,3I 但可能與 I2 中的物品共用箱子，它不能與 I1 中的物品共用箱子,與 I2 中的物品如何？ 由于放 I2 中物品的 個箱子的剩余總長度為 2I22jj ICI Cw 在最好的情形下， 被 I3 中的物品全部充滿

7、，故剩下總長度 將另外至少 個附加的箱子 .C3jjIwwCwCNote: 可能小于零w32212()( )max 0,jjj Ij IwI CwL aIIC是最優(yōu)解的一個下界 .第8頁/共33頁2 裝箱問題的最優(yōu)解值下界問 ？1( )L aL未必！(,1)jwajn 如Corollary 3.1記2max( ) 0,2CLL aaa為整數(shù)則 L2 是裝箱問題的最優(yōu)解的一個下界，且 .21LLProof :L2 為最優(yōu)解的下界是顯然的 .若證明 ，則可得1(0)LL21LL32212()( )max 0,jjj Ij IwI CwL aIIC當(dāng) a = 0 時， 是所有物品 .123,III

8、212()(0)0max 0,njjwI CLIC212max 0,ILI21max,IL1L21(0)LLLGo back第9頁/共33頁第三章 裝箱問題一、NF ( Next Fit ) 算法 設(shè)物品 J1，J2,，Jn 的長度分別為 w1，w2,，wn箱子 B1，B2，的長均為 C ，按物品給定的順序裝箱 . 先將 J1 放入 B1, 如果 則將 J2 放入 B1 12wwC如果 而12121jjjwwwCwwwwC則 B1 已放入 J1，J2,，Jj，將其關(guān)閉，將 Jj+1 放入 B2 .同法進(jìn)行，直到所有物品裝完為止 .特點：1、按物品給定的順序裝箱；2、關(guān)閉原則 . 對當(dāng)前要裝的物

9、品 Ji 只關(guān)心具有最大下標(biāo)的已使用過的箱子 Bj 能否裝得下？能. 則 Ji 放入 Bj ；否 . 關(guān)閉 Bj ，Ji 放入新箱子 Bj+1 .計算復(fù)雜性為 O(n).第10頁/共33頁3 裝箱問題的近似算法Example 1物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution :首先，將 J1 放入 B1由于 J2 在 B1 中放不下, 所以關(guān)閉 B1 , 將 J2 放入 B2 ,J3 在 B2 中放不下(不考慮B1 是否能裝), 所以關(guān)閉 B2將 J3 放入 B3，解為:112233344

10、5561xxxxxx其余為零，( )5.NFzI 第11頁/共33頁第三章 裝箱問題Theorem 3.32NFRProof :先證再說明不可改進(jìn)2NFR設(shè) I 為任一實例，( ).optzIk(要證 )( )2NFzIk顯然，由 得1( )niioptwkzIC1niiwCk反證如果 ,( )2NFzIk則 對任意 i = 1, 2, k由于起用第 2i 個箱子是因為第 2i -1 個箱子放不下第2i個箱子中第一個物品,因此這兩個箱子中物品的總長度大于 C ，所以前 2k 個箱子中物品的總長度大于 Ck .這與 矛盾 .1niiwCk( )2,2.( )NFNFoptzIRzI從而考慮實例

11、I : C = 1,124111111,2 22 22 2Nw wwNNN( )1( )2optNFzINzIN易證( )22 ()2( )1NFNFoptzINNRzIN 得第12頁/共33頁3 裝箱問題的近似算法二、FF ( First Fit ) 算法 設(shè)物品 J1，J2,，Jn 的長度分別為 w1，w2,，wn箱子 B1，B2，的長均為 C ，按物品給定的順序裝箱 .物品物品J1J2J3J4J5J6wj674283I : C = 10 用 NF 算法裝箱, 當(dāng)放入 J3 時, 僅看 B2是否能放入，因 B1 已關(guān)閉,參見 EX .1但事實上，B1 此時是能放得下 J3 的 .如何修正

12、NF 算法先將 J1 放入 B1，若 ,12wwC則 J2 放入 B1 , 否則，J2 放入 B2 ; 若 J2 已放入 B2，對于 J3 則依次檢查B1、B2 , 若 B1 能放得下, 則 J3 放入 B1 , 否則查看 B2 , 若 B2 能放得下，則 J3 放入 B2 , 否則啟用 B3, J3 放入 B3.第13頁/共33頁第三章 裝箱問題 一般地，J1,，Jj 已放入 B1,，Bi 箱子，對于 Jj+1,則依次檢查 B1，B2,，Bi，將 Jj+1 放入首先找到的能放得下的箱子，如果都放不下，則啟用箱子 Bi+1 ，將 Jj+1 放入 Bi+1 ，如此繼續(xù)，直到所有物品裝完為止 .

13、計算復(fù)雜性為 O(nlogn).特點：1、按物品給定的順序裝箱；2、對于每個物品 Jj 總是放在能容納它的具 有最小標(biāo)號的箱子 .但精度比NF 算法更高第14頁/共33頁3 裝箱問題的近似算法Theorem 3.4( )7.( )4FFoptzIzITheorem 3.5對任意實例 I ，17( )( ) 110FFoptzIzI而且存在 任意大的實例 I ，使( )optzI17( )( ) 1)10FFoptzIzI因而17.10FFR717141020第15頁/共33頁第三章 裝箱問題Example 2物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J

14、3J2B1B2B3B4B5J1J2J3J4J5J6Solution :首先，將 J1 放入 B1由于 J2 在 B1 中放不下, 所以將 J2 放入 B2 , 對于 J3 , 先檢查 B1 是否能容納下, 能 . 所以將 J3 放入 B1，解為:1122132435461xxxxxx其余為零，( )4.FFzI 第16頁/共33頁3 裝箱問題的近似算法Example 3物品物品J1J2J3J4J5J6wj678324I : C = 10J1J4J3J2Solution :用 NF 算法B1B2B3B4B5J1J2J6J5J3J4B1B2B3B4B5J1J2J6J5J3J4J6J5( )4NFz

15、I 用 FF 算法( )4FFzI 參見 EX .3 用 FF 算法裝箱, 當(dāng)放入 J4 時, B1 能容納J4 就放入 B1 ，而事實上，放入 B2 更好 .第17頁/共33頁第三章 裝箱問題三、BF ( Best Fit ) 算法 與 FF 算法相似，按物品給定的順序裝箱，區(qū)別在于對于每個物品 Jj 是放在一個使得 Jj 放入之后，Bi 所剩余長度為最小者 . 即在處理 Jj 時，若 B1，B2,，Bi 非空，而 Bi+1 尚未啟用，設(shè) B1，B2,，Bi所余的長度為12,iwww若1maxjkk iww 則將 Jj 放入 Bi+1 內(nèi);否則，從 的 Bk 中，選取 一個 Bl jkww(

16、1)li 使得為最小者min()kjljkjwwwwwwBF 算法的絕對性能比、計算復(fù)雜性與 FF 算法相同 .第18頁/共33頁Example 4物品物品J1J2J3J4J5J6wj678324I : C = 103 裝箱問題的近似算法J1J4J3J2J6J5B1B2B3B4B5J1J2J6J5J3J4Solution :用 BF 算法解為:1122332435161xxxxxx其余為零，( )3.BFzI 611310jjwL1( ),BFzIL第19頁/共33頁第三章 裝箱問題四、FFD ( First Fit Decreasing ) 算法FFD 算法是先將物品按長度從大到小排序，然后

17、用FF 算法對物品裝箱 .該算法的計算復(fù)雜性為 O(nlogn).Example 5物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2Solution :已知：( )4FFzI 物品物品J5J2J1J3J6J4wj876432B1B2B3B4B5J1J2J3J4J5J6( )3FFDzI 是最優(yōu)的NFD 算法？ BFD 算法？第20頁/共33頁3 裝箱問題的近似算法Theorem 3.63( ).2FFDRI Proof :顯然對任意實例 I ，有( )( )FFDoptzIzI記*( )( )FFDoptzIlzIl首先證明兩個結(jié)論：(1) FFD

18、算法所用的第 個箱子中每個的長度不超過*1,2,.,lll;3C記 wi 是放入第 個箱子中的第一個物品,只需證*1l 3iCw 用反證法，若不然，則有 ，因此 FFD11,.,3iCww算法中前 個箱子中, 每個箱子至多有兩個物品 .*l第21頁/共33頁C3C23C第三章 裝箱問題 可證明存在 使前 k 個恰各含一個物品，后 個箱子各含兩個物品0k *lk 因為若不然，則存在兩個箱子 使 Bp有兩個物品 , Bq 有一個物品 因物品已從大到小排列，故 , 因此 從而可以將wi 放入 Bq 中，矛盾.,pqBBpq1221,()ttwwtt3tw132,tttiwwww123.tttiCww

19、ww第22頁/共33頁3 裝箱問題的近似算法 因為 FFD 未將 wk+1,，wi 放入前 k 個箱子，說明其中任一個箱子已放不下, 故在最優(yōu)解中也至少有 k 個箱子不含 wk+1,，wi中任一個物品 . 假設(shè)就是前 k 個箱子，因此在最優(yōu)解中， wk+1,，wi-1也會兩兩放入第個箱子中，且因為這些物品長度大于 , 所以*1,.,kl3C每個箱子中只有兩個物品，且 已放不下 . 但最優(yōu)解中 wi 必須放入前 個箱子中，矛盾. 故3iCw *l.3iCw (2) FFD 算法放入第 個箱子中物品數(shù)不超過*1,.,ll*1l *1,niiwl C而如果至少有 個物品放入第*l*1,.,ll個箱子

20、中，記前 個物品的長度為 .*1,.,laa*l第23頁/共33頁第三章 裝箱問題記 FFD 算法中前 個箱子中每個箱子物品總長為 *l*,1jbjl 顯然，對任意*1,jjjlbaC否則長為 的物品可放入第 j 個箱子中，因此ja*1111()nllljjjjjjjjjwbabal C矛盾 .所以 (2) 結(jié)論成立 . 由(1)、(2) 知FFD 算法比最優(yōu)算法多用的箱子是用來放至多 個物品，而每個物品長不超過 ，因此*1l 3C第24頁/共33頁3 裝箱問題的近似算法( ) 1( )( ) 13( )411( )( )3( )33( )optoptoptFFDoptoptoptoptzIz

21、IzIzIzIzIzIzI 因此因為 如果 ，則 ，故不妨設(shè) ( )1optzI ( )1FFDzI ( )2optzI ( )413( )362FFDoptzIzI考慮實例 I ：物品集長度為 , C 為箱長. ,233344C C C C C C( )2,( )3optFFDzIzI說明 是不可改進(jìn)的 .32第25頁/共33頁第三章 裝箱問題 比較 NF 算法、FF ( BF ) 算法、FFD 算法，它們的近似程度一個比一個好，但這并不是說 NF、FF(BF)就失去了使用價值 .1、FF(BF)、FFD 算法都要將所有物品全部裝好后 , 所有箱子才能一起運走，而 NF 算法無此限制，很適合

22、裝箱場地小的情形；FFD 算法要求所有物品全部到達(dá)后才開始裝箱, 而 NF、FF(BF) 算法在給某一物品裝箱時，可以不知道下一個物品的長度如何，適合在線裝箱第26頁/共33頁存儲罐注液問題第三章 裝箱問題 某化工廠有 9 個不同大小的存儲罐，有一些已經(jīng)裝某液體 . 現(xiàn)新到一批液體化工原料需要存儲，這些液體不能混合存儲，它們分別是 1200 m3 苯，700 m3 丁醇，1000 m3 丙醇，450 m3 苯乙醇和1200 m3 四氫呋喃 . 下表列出每個存儲罐的屬性(單位: m3), 問應(yīng)如何將新到的液體原料裝罐, 才能使保留未用的存儲罐個數(shù)最多?存儲罐編號存儲罐編號123456789容容

23、量量500400400600600900800800800當(dāng)前內(nèi)容當(dāng)前內(nèi)容-苯苯-四氫呋喃四氫呋喃-體體 積積100300第27頁/共33頁第三章 裝箱問題Solution :存儲罐編號存儲罐編號123456789容容 量量500400400600600900800800800當(dāng)前內(nèi)容當(dāng)前內(nèi)容-苯苯-四氫呋喃四氫呋喃-體體 積積100300 分別記苯、丁醇、丙醇、苯乙醇、四氫呋喃為第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個空罐 .令10ijx