數(shù)學(xué)建模-第八章裝箱問題

1、 Combinatorial Optimization Theory第八章第八章 裝箱問題裝箱問題 裝箱問題（裝箱問題（Bin Packing）是一個經(jīng)典的組合優(yōu)化）是一個經(jīng)典的組合優(yōu)化問題，有著廣泛的應(yīng)用，在日常生活中也屢見不鮮問題，有著廣泛的應(yīng)用，在日常生活中也屢見不鮮 . 設(shè)有許多具有同樣結(jié)構(gòu)和負(fù)荷的箱子設(shè)有許多具有同樣結(jié)構(gòu)和負(fù)荷的箱子 B1，B2，其數(shù)量足夠供所達(dá)到目的之用其數(shù)量足夠供所達(dá)到目的之用 . 每個箱子的負(fù)荷（可為每個箱子的負(fù)荷（可為長度、重量長度、重量 etc.）為為 C ,今有今有 n 個負(fù)荷為個負(fù)荷為 wj，0 wj C j = 1，2，n 的物品的物品 J1，J2，J

2、n 需要裝入箱內(nèi)需要裝入箱內(nèi). 是指尋找一種方法，使得能以最小數(shù)量的箱子數(shù)將是指尋找一種方法，使得能以最小數(shù)量的箱子數(shù)將J1，J2，Jn 全部裝入箱內(nèi)全部裝入箱內(nèi)1 1 裝箱問題的描述裝箱問題的描述由于由于 wi C，所以，所以 BP 的最優(yōu)解的箱子數(shù)不超過的最優(yōu)解的箱子數(shù)不超過 n設(shè)設(shè)11;0iyin箱子箱子 Bi 被使用被使用否則否則1,1.0ijxi jn物品物品 Jj 放入箱子放入箱子 Bi 中中否則否則則裝箱問題的整數(shù)線性規(guī)劃模型為則裝箱問題的整數(shù)線性規(guī)劃模型為：1minniizy1. .1(1)njijijstw xCyin01,01,1.iijyorxori jn()BP約束條件

3、（約束條件（1）表示：一旦箱子）表示：一旦箱子 Bi 被使用，放入被使用，放入 Bi 的物品總負(fù)荷不超過的物品總負(fù)荷不超過 C ；約束條件（約束條件（2）表示：每個物品恰好放入一個箱子中）表示：每個物品恰好放入一個箱子中 .11(2)nijix1jn第八章第八章 裝箱問題裝箱問題 上述裝箱問題是這類問題最早被研究的，也是提上述裝箱問題是這類問題最早被研究的，也是提法上最簡單的問題，稱為一維裝箱問題法上最簡單的問題，稱為一維裝箱問題 但但.BPNP C裝箱問題的其他一些提法裝箱問題的其他一些提法：1、在裝箱時(shí)，不僅考慮長度，同時(shí)考慮重量或面積、在裝箱時(shí)，不僅考慮長度，同時(shí)考慮重量或面積、 體積體

4、積 etc . 即二維、三維、即二維、三維、裝箱問題裝箱問題；2、對每個箱子的負(fù)荷限制不是常數(shù)、對每個箱子的負(fù)荷限制不是常數(shù) C ; 而是而是,1.iCin最優(yōu)目標(biāo)可如何提？最優(yōu)目標(biāo)可如何提？3、物品、物品J1，J2，Jn 的負(fù)荷事先并不知道，來貨是的負(fù)荷事先并不知道，來貨是 隨到隨裝；即隨到隨裝；即 在線（在線（On-Line）裝箱問題；）裝箱問題；4、由于場地的限制，在同一時(shí)間只能允許一定數(shù)量的、由于場地的限制，在同一時(shí)間只能允許一定數(shù)量的 箱子停留現(xiàn)場可供使用箱子停留現(xiàn)場可供使用, etc .1 1 裝箱問題的描述裝箱問題的描述BP 的應(yīng)用舉例的應(yīng)用舉例：1、下料問題下料問題 軋鋼廠生產(chǎn)

5、的線材一般為同一長度軋鋼廠生產(chǎn)的線材一般為同一長度, 而用而用戶所需的線材則可能具有各種不同的尺寸戶所需的線材則可能具有各種不同的尺寸, 如何根據(jù)用如何根據(jù)用戶提出的要求，用最少的線材截出所需的定貨；戶提出的要求，用最少的線材截出所需的定貨；2、 二維二維 BP 玻璃廠生產(chǎn)出長寬一定的大的平板玻璃玻璃廠生產(chǎn)出長寬一定的大的平板玻璃,但用戶所需玻璃的長寬可能有許多差異，如何根據(jù)用但用戶所需玻璃的長寬可能有許多差異，如何根據(jù)用戶提出的要求，用最少的平板玻璃截出所需的定貨戶提出的要求，用最少的平板玻璃截出所需的定貨;3、計(jì)算機(jī)的存貯問題計(jì)算機(jī)的存貯問題 如要把大小不同的共如要把大小不同的共 10 M

6、B 的的文件拷貝到磁盤中去，而每張磁盤的容量為文件拷貝到磁盤中去，而每張磁盤的容量為 1. 44 MB ,已知每個文件的字節(jié)數(shù)不超過已知每個文件的字節(jié)數(shù)不超過 1.44 MB , 而且一個文件而且一個文件不能分成幾部分存貯，如何用最少的磁盤張數(shù)完成不能分成幾部分存貯，如何用最少的磁盤張數(shù)完成 .1.44 710.08104、生產(chǎn)流水線的平衡問題生產(chǎn)流水線的平衡問題 給定流水節(jié)拍給定流水節(jié)拍 C , 如何設(shè)置如何設(shè)置最少的工作站，（按一定的緊前約束）沿著流水線將任最少的工作站，（按一定的緊前約束）沿著流水線將任務(wù)分配到各工作站上務(wù)分配到各工作站上 . 稱為帶附加優(yōu)先約束的稱為帶附加優(yōu)先約束的 B

7、P . BP 是容量限制的工廠選址問題的特例之一是容量限制的工廠選址問題的特例之一.Go back第八章第八章 裝箱問題裝箱問題由于由于 BP 是是 NP-C 問題，所以求解考慮問題，所以求解考慮 一是盡可能一是盡可能改進(jìn)簡單的窮舉搜索法，減少搜索工作量改進(jìn)簡單的窮舉搜索法，減少搜索工作量 . 如如: : 分支分支定界法；二是啟發(fā)式（近似）算法定界法；二是啟發(fā)式（近似）算法 .1minniizy1. .1(1)njijijstw xCyin01,01,1.iijyorxori jn()BP01, 01,1.iijyxi jn()C BP 顯然顯然 是它的一個最優(yōu)解是它的一個最優(yōu)解 . 1,0

8、(),1.iiiijiwxxijyi jnC1niioptwzC11(2)nijix1jn2 2 裝箱問題的最優(yōu)解值下界裝箱問題的最優(yōu)解值下界Theorem 3.1BP 最優(yōu)值的一個下界為最優(yōu)值的一個下界為11.niiwLCa 表示不小于表示不小于 a 的最小整數(shù)的最小整數(shù).Theorem 3.2 設(shè)設(shè) a 是任意滿足是任意滿足 的整數(shù)的整數(shù),對對 BP 的任一實(shí)例的任一實(shí)例 I ,02Ca記記1,jIj wCa物品2,2jCIj Caw物品3,2jCIjwa物品則則32212()( )max 0,jjj Ij IwI CwL aIIC是最優(yōu)解的一個下界是最優(yōu)解的一個下界第八章第八章 裝箱問題

9、裝箱問題aCC/2C-aI1I2I3Proof : 僅考慮對僅考慮對 I1,I2,I3中物品的裝箱中物品的裝箱 .中物品的長度大于中物品的長度大于C/2 ,12II每個物品需單獨(dú)放入一個箱子，每個物品需單獨(dú)放入一個箱子，這就需要這就需要 個箱子個箱子 .12II又又 中每個物品長度至少為中每個物品長度至少為 a ,3I 但可能與但可能與 I2 中的中的物品共用箱子物品共用箱子，它不能與它不能與 I1 中的物品共用箱子中的物品共用箱子,與與 I2 中的物品如何？中的物品如何？ 由于放由于放 I2 中物品的中物品的 個箱子的剩余個箱子的剩余總長度為總長度為 2I22jj ICI Cw 在最好的情形

10、下，在最好的情形下， 被被 I3 中的物品全部充滿，故剩中的物品全部充滿，故剩下總長度下總長度 將另外至少將另外至少 個附加的箱子個附加的箱子 .C3jjIwwCwCNote: 可能小于零可能小于零w32212()( )max 0,jjj Ij IwI CwL aIIC是最優(yōu)解的一個下界是最優(yōu)解的一個下界 .2 2 裝箱問題的最優(yōu)解值下界裝箱問題的最優(yōu)解值下界問問 ？1( )L aL未必！未必！(,1)jwajn如如Corollary 3.1記記2max( ) 0,2CLL aaa為整數(shù)則則 L2 是裝箱問題的最優(yōu)解的一個下界，且是裝箱問題的最優(yōu)解的一個下界，且 .21LLProof :L2

11、為最優(yōu)解的下界是顯然的為最優(yōu)解的下界是顯然的 .若證明若證明 ，則可得，則可得1(0)LL21LL32212()( )max 0,jjj Ij IwI CwL aIIC當(dāng)當(dāng) a = 0 時(shí)，時(shí)， 是所有物品是所有物品 .123,III 212()(0)0max 0,njjwI CLIC212max 0,ILI21max,IL1L21(0)LLLGo back第八章第八章 裝箱問題裝箱問題一、一、NF ( Next Fit ) 算法算法 設(shè)物品設(shè)物品 J1，J2,，Jn 的長度分別為的長度分別為 w1，w2,，wn箱子箱子 B1，B2，的長均為的長均為 C ，按物品給定的順序裝箱，按物品給定的順

12、序裝箱 . 先將先將 J1 放入放入 B1, 如果如果 則將則將 J2 放入放入 B1 12wwC如果如果 而而12121jjjwwwCwwwwC則則 B1 已放入已放入 J1，J2,，Jj，將其，將其關(guān)閉關(guān)閉，將，將 Jj+1 放入放入 B2 .同法進(jìn)行，直到所有物品裝完為止同法進(jìn)行，直到所有物品裝完為止 .特點(diǎn)特點(diǎn)： 1、按物品給定的順序裝箱、按物品給定的順序裝箱；2、關(guān)閉原則關(guān)閉原則 . 對當(dāng)前要裝的物品對當(dāng)前要裝的物品 Ji 只關(guān)心具有最大下標(biāo)的已使只關(guān)心具有最大下標(biāo)的已使用過的箱子用過的箱子 Bj 能否裝得下？能否裝得下？能能. 則則 Ji 放入放入 Bj ；否；否 . 關(guān)閉關(guān)閉 B

13、j ，Ji 放入新箱子放入新箱子 Bj+1 .計(jì)算復(fù)雜性為計(jì)算復(fù)雜性為 O(n).3 3 裝箱問題的近似算法裝箱問題的近似算法Example 1物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution :首先，將首先，將 J1 放入放入 B1由于由于 J2 在在 B1 中放不下中放不下, 所所以關(guān)閉以關(guān)閉 B1 , 將將 J2 放入放入 B2 ,J3 在在 B2 中放不下中放不下(不考慮不考慮B1 是否能裝是否能裝), 所以關(guān)閉所以關(guān)閉 B2將將 J3 放入放入 B3，解為解為:1122333445

14、561xxxxxx其余為零，其余為零，( )5.NFzI 第八章第八章 裝箱問題裝箱問題Theorem 3.32NFRProof :先證先證再說明不可改進(jìn)再說明不可改進(jìn)2NFR設(shè)設(shè) I 為任一實(shí)例，為任一實(shí)例，( ).optzIk(要證要證 )( )2NFzIk顯然，由顯然，由 得得1( )niioptwkzIC1niiwCk反證反證如果如果 ,( )2NFzIk則則 對任意對任意 i = 1, 2, k由于起用第由于起用第 2i 個箱子是因?yàn)榈趥€箱子是因?yàn)榈?2i -1 個箱子放不下第個箱子放不下第2i個箱子中第一個物品個箱子中第一個物品,因此這兩個箱子中物品的總長度因此這兩個箱子中物品的總

15、長度大于大于 C ，所以前，所以前 2k 個箱子中物品的總長度大于個箱子中物品的總長度大于 Ck .這與這與 矛盾矛盾 .1niiwCk( )2,2.( )NFNFoptzIRzI從而考慮實(shí)例考慮實(shí)例 I : C = 1,124111111,2 22 22 2Nw wwNNN( )1( )2optNFzINzIN易證( )22 ()2( )1NFNFoptzINNRzIN 得3 3 裝箱問題的近似算法裝箱問題的近似算法二、二、FF ( First Fit ) 算法算法 設(shè)物品設(shè)物品 J1，J2,，Jn 的長度分別為的長度分別為 w1，w2,，wn箱子箱子 B1，B2，的長均為的長均為 C ，按

16、物品給定的順序裝箱，按物品給定的順序裝箱 .物品物品J1J2J3J4J5J6wj674283I : C = 10 用用 NF 算法裝算法裝箱箱, 當(dāng)放入當(dāng)放入 J3 時(shí)時(shí), 僅看僅看 B2是否能放入，因是否能放入，因 B1 已關(guān)閉已關(guān)閉,參見參見 EX .1但事實(shí)上，但事實(shí)上，B1 此時(shí)是能放得下此時(shí)是能放得下 J3 的的 .如何修正如何修正 NF 算算法法先將先將 J1 放入放入 B1，若，若 ,12wwC則則 J2 放入放入 B1 , 否否則，則，J2 放入放入 B2 ; 若若 J2 已放入已放入 B2，對于，對于 J3 則依次則依次檢查檢查B1、B2 , 若若 B1 能放得下能放得下,

17、則則 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ù)，直到所有物品裝完為止，如此繼續(xù)，直到所有物品裝完為止 . 計(jì)算復(fù)雜性為計(jì)算

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

19、章 裝箱問題裝箱問題Example 2物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution :首先，將首先，將 J1 放入放入 B1由于由于 J2 在在 B1 中放不下中放不下, 所所以將以將 J2 放入放入 B2 , 對于對于 J3 , 先檢查先檢查 B1 是否能是否能容納下容納下, 能能 . 所以將所以將 J3 放放入入 B1，解為解為:1122132435461xxxxxx其余為零，其余為零，( )4.FFzI 3 3 裝箱問題的近似算法裝箱問題的近似算法Example 3物品物品J1J2

20、J3J4J5J6wj678324I : C = 10J1J4J3J2Solution :用用 NF 算法算法B1B2B3B4B5J1J2J6J5J3J4B1B2B3B4B5J1J2J6J5J3J4J6J5( )4NFzI 用用 FF 算法算法( )4FFzI 參見參見 EX .3 用用 FF 算法裝箱算法裝箱, 當(dāng)放入當(dāng)放入 J4 時(shí)時(shí), B1 能容納能容納J4 就放入就放入 B1 ，而事實(shí)上，放入，而事實(shí)上，放入 B2 更好更好 .第八章第八章 裝箱問題裝箱問題三、三、BF ( Best Fit ) 算法算法 與與 FF 算法相似，按物品給定的順序裝箱，區(qū)別在算法相似，按物品給定的順序裝箱，

21、區(qū)別在于對于每個物品于對于每個物品 Jj 是放在一個使得是放在一個使得 Jj 放入之后，放入之后，Bi 所所剩余長度為最小者剩余長度為最小者 . 即在處理即在處理 Jj 時(shí)，若時(shí)，若 B1，B2,，Bi 非空，而非空，而 Bi+1 尚尚未啟用，設(shè)未啟用，設(shè) B1，B2,，Bi所余的長度為所余的長度為12,iwww若若1maxjkk iww 則將則將 Jj 放入放入 Bi+1 內(nèi)內(nèi);否則，從否則，從 的的 Bk 中，選取中，選取 一個一個 Bl jkww(1)li 使得使得為最小者為最小者min()kjljkjwwwwwwBF 算法的絕對性能比、計(jì)算復(fù)雜性與算法的絕對性能比、計(jì)算復(fù)雜性與 FF

22、算法相同算法相同 .Example 4物品物品J1J2J3J4J5J6wj678324I : C = 103 3 裝箱問題的近似算法裝箱問題的近似算法J1J4J3J2J6J5B1B2B3B4B5J1J2J6J5J3J4Solution :用用 BF 算法算法解為解為:1122332435161xxxxxx其余為零，其余為零，( )3.BFzI 611310jjwL1( ),BFzIL第八章第八章 裝箱問題裝箱問題四、四、FFD ( First Fit Decreasing ) 算法算法FFD 算法是先將物品按長度從大到小排序，然后用算法是先將物品按長度從大到小排序，然后用FF 算法對物品裝箱算

23、法對物品裝箱 . 該算法的計(jì)算復(fù)雜性為該算法的計(jì)算復(fù)雜性為 O(nlogn).Example 5物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2Solution :已知已知：( )4FFzI 物品物品J5J2J1J3J6J4wj876432B1B2B3B4B5J1J2J3J4J5J6( )3FFDzI 是最優(yōu)的是最優(yōu)的NFD 算法？算法？ BFD 算法？算法？3 3 裝箱問題的近似算法裝箱問題的近似算法Theorem 3.63( ).2FFDRI Proof :顯然對任意實(shí)例顯然對任意實(shí)例 I ，有，有( )( )FFDoptzIzI記記*( )(

24、)FFDoptzIlzIl首先證明兩個結(jié)論首先證明兩個結(jié)論：(1) FFD 算法所用的第算法所用的第 個箱子中每個的個箱子中每個的長度不超過長度不超過*1,2,.,lll;3C記記 wi 是放入第是放入第 個箱子中的第一個物品個箱子中的第一個物品,只需證只需證*1l 3iCw 用反證法，若不然，則有用反證法，若不然，則有 ，因此，因此 FFD11,.,3iCww算法中前算法中前 個箱子中個箱子中, 每個箱子至多有兩個物品每個箱子至多有兩個物品 .*lC3C23C第八章第八章 裝箱問題裝箱問題 可證明存在可證明存在 使前使前 k 個恰各含一個物品，后個恰各含一個物品，后 個箱子各含兩個物品個箱子

25、各含兩個物品0k *lk 因?yàn)槿舨蝗?，則存在兩個箱子因?yàn)槿舨蝗唬瑒t存在兩個箱子 使使 Bp有兩有兩個物品個物品 , Bq 有一個物品有一個物品 因物品已從大到因物品已從大到小排列，故小排列，故 , 因此因此 從從而可以將而可以將wi 放入放入 Bq 中，矛盾中，矛盾.,pqBBpq1221,()ttw wtt3tw132,tttiwwww123.tttiCwwww3 3 裝箱問題的近似算法裝箱問題的近似算法 因?yàn)橐驗(yàn)?FFD 未將未將 wk+1,，wi 放入前放入前 k 個箱子，說明個箱子，說明其中任一個箱子已放不下其中任一個箱子已放不下, 故在最優(yōu)解中也至少有故在最優(yōu)解中也至少有 k 個個箱

26、子不含箱子不含 wk+1,，wi中任一個物品中任一個物品 . 假設(shè)就是前假設(shè)就是前 k 個個箱子，因此在最優(yōu)解中，箱子，因此在最優(yōu)解中， wk+1,，wi-1也會兩兩放入第也會兩兩放入第個箱子中，且因?yàn)檫@些物品長度大于個箱子中，且因?yàn)檫@些物品長度大于 , 所所以以*1,.,kl3C每個箱子中只有兩個物品，且每個箱子中只有兩個物品，且 已放不下已放不下 . 但最但最優(yōu)解中優(yōu)解中 wi 必須放入前必須放入前 個箱子中，矛盾個箱子中，矛盾. 故故3iCw *l.3iCw (2) FFD 算法放入第算法放入第 個箱子中物品數(shù)不超過個箱子中物品數(shù)不超過*1,.,ll*1l *1,niiwl C而如果至少

27、有而如果至少有 個物品放入第個物品放入第*l*1,.,ll個箱子中，記前個箱子中，記前 個物品的長度為個物品的長度為 .*1,.,laa*l第八章第八章 裝箱問題裝箱問題記記 FFD 算法中前算法中前 個箱子中每個箱子物品總長為個箱子中每個箱子物品總長為 *l*,1jbjl顯然，對任意顯然，對任意*1,jjjlbaC否則長為否則長為 的物品可放入第的物品可放入第 j 個箱子中，因此個箱子中，因此ja*1111()nllljjjjjjjjjwbabal C矛盾矛盾 .所以所以 (2) 結(jié)論成立結(jié)論成立 . 由由(1)、(2) 知知FFD 算法比最優(yōu)算法多用的箱子是用算法比最優(yōu)算法多用的箱子是用來

28、放至多來放至多 個物品，而每個物品長不超過個物品，而每個物品長不超過 ，因此，因此*1l 3C3 3 裝箱問題的近似算法裝箱問題的近似算法( ) 1( )( ) 13( )411( )( )3( )33( )optoptoptFFDoptoptoptoptzIzIzIzIzIzIzIzI 因此因此因?yàn)橐驗(yàn)?如果如果 ，則，則 ，故不妨設(shè)，故不妨設(shè) ( )1optzI ( )1FFDzI ( )2optzI ( )413( )362FFDoptzIzI考慮實(shí)例考慮實(shí)例 I ：物品集長度為物品集長度為 , C 為箱長為箱長. ,233344C C C C C C( )2,( )3optFFDzIz

29、I說明說明 是不可改進(jìn)的是不可改進(jìn)的 .32第八章第八章 裝箱問題裝箱問題 比較比較 NF 算法、算法、FF ( BF ) 算法、算法、FFD 算法，它們算法，它們的近似程度一個比一個好，但這并不是說的近似程度一個比一個好，但這并不是說 NF、FF(BF)就失去了使用價(jià)值就失去了使用價(jià)值 .1、FF(BF)、FFD 算法都要將所有物品全部裝好后算法都要將所有物品全部裝好后 , 所所有箱子才能一起運(yùn)走，而有箱子才能一起運(yùn)走，而 NF 算法無此限制，很適合裝算法無此限制，很適合裝箱場地小的情形；箱場地小的情形；FFD 算法要求所有物品全部到達(dá)后才開始裝箱算法要求所有物品全部到達(dá)后才開始裝箱, 而而

30、 NF、FF(BF) 算法在給某一物品裝箱時(shí)，可以不知道算法在給某一物品裝箱時(shí)，可以不知道下一個物品的長度如何，適合在線裝箱下一個物品的長度如何，適合在線裝箱存儲罐注液問題存儲罐注液問題第八章第八章 裝箱問題裝箱問題 某化工廠有某化工廠有 9 個不同大小的存儲罐，有一些已經(jīng)裝個不同大小的存儲罐，有一些已經(jīng)裝某液體某液體 . 現(xiàn)新到一批液體化工原料需要存儲，這些液體現(xiàn)新到一批液體化工原料需要存儲，這些液體不能混合存儲，它們分別是不能混合存儲，它們分別是 1200 m3 苯，苯，700 m3 丁醇，丁醇，1000 m3 丙醇，丙醇，450 m3 苯乙醇和苯乙醇和1200 m3 四氫呋喃四氫呋喃 .

31、 下表列出每個存儲罐的屬性下表列出每個存儲罐的屬性(單位單位: m3), 問應(yīng)如何將新到問應(yīng)如何將新到的液體原料裝罐的液體原料裝罐, 才能使保留未用的存儲罐個數(shù)最多才能使保留未用的存儲罐個數(shù)最多?存儲罐編號存儲罐編號123456789容容 量量500400400600600900800800800當(dāng)前內(nèi)容當(dāng)前內(nèi)容-苯苯-四氫呋喃四氫呋喃-體體 積積100300第八章第八章 裝箱問題裝箱問題Solution :存儲罐編號存儲罐編號123456789容容 量量500400400600600900800800800當(dāng)前內(nèi)容當(dāng)前內(nèi)容-苯苯-四氫呋喃四氫呋喃-體體 積積100300 分別記苯、丁醇、丙醇

32、、苯乙醇、四氫呋喃分別記苯、丁醇、丙醇、苯乙醇、四氫呋喃為第為第1，2，3，4，5種液體種液體 . 顯然，新到液體應(yīng)盡可能顯然，新到液體應(yīng)盡可能裝入已存有此種液體的罐中裝入已存有此種液體的罐中 . 所以余下液體為：所以余下液體為：900 m3 苯，苯，700 m3 丁醇，丁醇，1000 m3 丙醇，丙醇，450 m3 乙醇和乙醇和700 m3 四氫呋喃四氫呋喃 . 剩余空罐剩余空罐為為1，3，4，5，6，8，9 . 由于不允許混合，每種液體由于不允許混合，每種液體至少需要至少需要1個空罐個空罐 .令令10ijx第第 i 種液體裝入第種液體裝入第 j 個存儲罐個存儲罐否則否則記第記第 j 個空罐的容量為