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

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

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

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

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

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

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

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

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

9、品 Ji 只關(guān)心具有最大下標(biāo)的已使用過(guò)的箱子 Bj 能否裝得下？能. 則 Ji 放入 Bj ；否 . 關(guān)閉 Bj ，Ji 放入新箱子 Bj+1 .計(jì)算復(fù)雜性為 O(n).第10頁(yè)/共33頁(yè)3 裝箱問(wèn)題的近似算法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頁(yè)/共33頁(yè)第三章 裝箱問(wèn)題Theorem 3.32NFRProof :先證再說(shuō)明不可改進(jìn)2NFR設(shè) I 為任一實(shí)例，( ).optzIk(要證 )( )2NFzIk顯然，由 得1( )niioptwkzIC1niiwCk反證如果 ,( )2NFzIk則 對(duì)任意 i = 1, 2, k由于起用第 2i 個(gè)箱子是因?yàn)榈?2i -1 個(gè)箱子放不下第2i個(gè)箱子中第一個(gè)物品,因此這兩個(gè)箱子中物品的總長(zhǎng)度大于 C ，所以前 2k 個(gè)箱子中物品的總長(zhǎng)度大于 Ck .這與 矛盾 .1niiwCk( )2,2.( )NFNFoptzIRzI從而考慮實(shí)例

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

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

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

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

15、I 用 FF 算法( )4FFzI 參見(jiàn) EX .3 用 FF 算法裝箱, 當(dāng)放入 J4 時(shí), B1 能容納J4 就放入 B1 ，而事實(shí)上，放入 B2 更好 .第17頁(yè)/共33頁(yè)第三章 裝箱問(wèn)題三、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)度為12,iwww若1maxjkk iww 則將 Jj 放入 Bi+1 內(nèi);否則，從 的 Bk 中，選取 一個(gè) Bl jkww(

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

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

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

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

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

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

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

23、量量500400400600600900800800800當(dāng)前內(nèi)容當(dāng)前內(nèi)容-苯苯-四氫呋喃四氫呋喃-體體 積積100300第27頁(yè)/共33頁(yè)第三章 裝箱問(wèn)題Solution :存儲(chǔ)罐編號(hào)存儲(chǔ)罐編號(hào)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個(gè)空罐 .令10ijx