第八章裝箱問題組合優(yōu)化理論

CombinatorialOptimizationTheory數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題§1裝箱問題的描述§2裝箱問題的最優(yōu)解值下界§3裝箱問題的近似算法數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題

裝箱問題（BinPacking）是一個(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<Cj=1，2，…，n的物品J1，J2，…，Jn

需要裝入箱內(nèi).裝箱問題：

是指尋找一種方法，使得能以最小數(shù)量的箱子數(shù)將J1，J2，…，Jn

全部裝入箱內(nèi).數(shù)學(xué)建模-第八章裝箱問題§1裝箱問題的描述

由于wi<C，所以BP

的最優(yōu)解的箱子數(shù)不超過n.設(shè)箱子Bi

被使用否則物品Jj

放入箱子Bi

中否則則裝箱問題的整數(shù)線性規(guī)劃模型為：約束條件（1）表示：一旦箱子Bi被使用，放入Bi

的物品總負(fù)荷不超過C；約束條件（2）表示：每個(gè)物品恰好放入一個(gè)箱子中.數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題

上述裝箱問題是這類問題最早被研究的，也是提法上最簡(jiǎn)單的問題，稱為一維裝箱問題

.但裝箱問題的其他一些提法：1、在裝箱時(shí)，不僅考慮長(zhǎng)度，同時(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.

數(shù)學(xué)建模-第八章裝箱問題§1裝箱問題的描述BP

的應(yīng)用舉例：1、下料問題軋鋼廠生產(chǎn)的線材一般為同一長(zhǎng)度,而用戶所需的線材則可能具有各種不同的尺寸,如何根據(jù)用戶提出的要求，用最少的線材截出所需的定貨；2、二維BP

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

是容量限制的工廠選址問題的特例之一.Goback數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題§2裝箱問題的最優(yōu)解值下界

由于BP

是NP-C問題，所以求解考慮一是盡可能改進(jìn)簡(jiǎn)單的窮舉搜索法，減少搜索工作量.如:分支定界法；二是啟發(fā)式（近似）算法

.

顯然是它的一個(gè)最優(yōu)解.數(shù)學(xué)建模-第八章裝箱問題§2裝箱問題的最優(yōu)解值下界Theorem

3.1BP

最優(yōu)值的一個(gè)下界為表示不小于a

的最小整數(shù).Theorem

3.2

設(shè)a

是任意滿足的整數(shù),對(duì)BP

的任一實(shí)例I,

記則是最優(yōu)解的一個(gè)下界

.數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題aCC/2C-aI1I2I3Proof:僅考慮對(duì)I1,I2,I3中物品的裝箱.中物品的長(zhǎng)度大于C/2,每個(gè)物品需單獨(dú)放入一個(gè)箱子，這就需要個(gè)箱子.又中每個(gè)物品長(zhǎng)度至少為a,

但可能與I2

中的物品共用箱子，它不能與I1

中的物品共用箱子,與I2

中的物品如何？

由于放I2

中物品的個(gè)箱子的剩余總長(zhǎng)度為

在最好的情形下，被I3

中的物品全部充滿，故剩下總長(zhǎng)度將另外至少個(gè)附加的箱子.Note:可能小于零是最優(yōu)解的一個(gè)下界.數(shù)學(xué)建模-第八章裝箱問題§2裝箱問題的最優(yōu)解值下界問？

未必！如Corollary3.1記則L2

是裝箱問題的最優(yōu)解的一個(gè)下界，且.Proof:L2

為最優(yōu)解的下界是顯然的.(若證明，則可得

)當(dāng)a=0時(shí)，是所有物品.Goback數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題§3裝箱問題的近似算法一、NF(NextFit)算法

設(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

放入

Bj

；否.關(guān)閉Bj

，Ji

放入新箱子Bj+1.計(jì)算復(fù)雜性為O(n).數(shù)學(xué)建模-第八章裝箱問題§3裝箱問題的近似算法Example1物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution:首先，將J1

放入B1;由于J2

在B1

中放不下,所以關(guān)閉B1,將J2

放入B2,J3在B2中放不下(不考慮B1是否能裝),所以關(guān)閉B2將J3

放入B3，…解為:其余為零，數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題Theorem

3.3Proof:先證再說明不可改進(jìn)設(shè)I為任一實(shí)例，(要證)顯然，由得反證如果,則對(duì)任意i=1,2,…,k由于起用第2i

個(gè)箱子是因?yàn)榈?i-1個(gè)箱子放不下第2i個(gè)箱子中第一個(gè)物品,因此這兩個(gè)箱子中物品的總長(zhǎng)度大于C

，所以前2k個(gè)箱子中物品的總長(zhǎng)度大于Ck.這與矛盾.考慮實(shí)例I:C=1,數(shù)學(xué)建模-第八章裝箱問題§3裝箱問題的近似算法二、FF(FirstFit)算法

設(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)閉,參見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.數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題

一般地，J1,…，Jj

已放入B1,…，Bi

箱子，對(duì)于Jj+1,則依次檢查B1，B2,…，Bi，將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

算法更高數(shù)學(xué)建模-第八章裝箱問題§3裝箱問題的近似算法Theorem

3.4Theorem

3.5對(duì)任意實(shí)例I，而且存在任意大的實(shí)例I，使因而數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題Example2物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution:首先，將J1

放入B1;由于J2

在B1

中放不下,所以將J2

放入B2,對(duì)于

J3,先檢查B1是否能容納下,能.所以將J3

放入B1，…解為:其余為零，數(shù)學(xué)建模-第八章裝箱問題§3裝箱問題的近似算法Example3物品J1J2J3J4J5J6wj678324I:C=10J1J4J3J2Solution:用NF

算法B1B2B3B4B5J1J2J6J5J3J4B1B2B3B4B5J1J2J6J5J3J4J6J5用FF

算法

參見EX.3用FF算法裝箱,當(dāng)放入

J4

時(shí),B1能容納J4

就放入B1

，而事實(shí)上，放入B2

更好.數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題三、BF(BestFit)算法

與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

算法相同.數(shù)學(xué)建模-第八章裝箱問題Example4物品J1J2J3J4J5J6wj678324I:C=10§3裝箱問題的近似算法J1J4J3J2J6J5B1B2B3B4B5J1J2J6J5J3J4Solution:用BF

算法解為:其余為零，而此為最優(yōu)解.數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題四、FFD(FirstFitDecreasing)算法

FFD

算法是先將物品按長(zhǎng)度從大到小排序，然后用FF

算法對(duì)物品裝箱.該算法的計(jì)算復(fù)雜性為O(nlogn).Example5物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2Solution:已知：物品J5J2J1J3J6J4wj876432B1B2B3B4B5J1J2J3J4J5J6是最優(yōu)的

.NFD

算法？BFD

算法？數(shù)學(xué)建模-第八章裝箱問題§3裝箱問題的近似算法Theorem

3.6Proof:顯然對(duì)任意實(shí)例I，有記首先證明兩個(gè)結(jié)論：(1)FFD算法所用的第個(gè)箱子中每個(gè)的長(zhǎng)度不超過記wi

是放入第個(gè)箱子中的第一個(gè)物品,只需證用反證法，若不然，則有，因此FFD算法中前個(gè)箱子中,每個(gè)箱子至多有兩個(gè)物品.數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題

可證明存在使前k個(gè)恰各含一個(gè)物品，后個(gè)箱子各含兩個(gè)物品.

因?yàn)槿舨蝗?，則存在兩個(gè)箱子使Bp有兩個(gè)物品

,Bq

有一個(gè)物品因物品已從大到小排列，故,因此從而可以將wi

放入Bq中，矛盾.數(shù)學(xué)建模-第八章裝箱問題§3裝箱問題的近似算法

因?yàn)镕FD

未將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ù)不超過而如果至少有個(gè)物品放入第個(gè)箱子中，記前個(gè)物品的長(zhǎng)度為.數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題記FFD

算法中前個(gè)箱子中每個(gè)箱子物品總長(zhǎng)為顯然，對(duì)任意否則長(zhǎng)為的物品可放入第j個(gè)箱子中，因此矛盾.所以(2)結(jié)論成立.

由(1)、(2)知FFD算法比最優(yōu)算法多用的箱子是用來放至多個(gè)物品，而每個(gè)物品長(zhǎng)不超過，因此數(shù)學(xué)建模-第八章裝箱問題§3裝箱問題的近似算法因此因?yàn)槿绻?，則，故不妨設(shè)考慮實(shí)例I：物品集長(zhǎng)度為,C為箱長(zhǎng).說明是不可改進(jìn)的.數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題

比較NF

算法、FF(BF)算法、FFD

算法，它們的近似程度一個(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)度如何，適合在線裝箱

.數(shù)學(xué)建模-第八章裝箱問題存儲(chǔ)罐注液?jiǎn)栴}第八章裝箱問題

某化工廠有9個(gè)不同大小的存儲(chǔ)罐，有一些已經(jīng)裝某液體.現(xiàn)新到一批液體化工原料需要存儲(chǔ)，這些液體不能混合存儲(chǔ)，它們分別是1200m3

苯，700m3

丁醇，1000m3

丙醇，450m3

苯乙醇和1200m3

四氫呋喃.下表列出每個(gè)存儲(chǔ)罐的屬性(單位:m3),問應(yīng)如何將新到的液體原料裝罐,才能使保留未用的存儲(chǔ)罐個(gè)數(shù)最多?存儲(chǔ)罐編號(hào)123456789容量500400400600600900800800800當(dāng)前內(nèi)容-苯----四氫呋喃--體積100300數(shù)學(xué)建模-第八章裝箱問題第八章裝箱問題Solution:存儲(chǔ)罐編號(hào)123456789容量500400400600600900800800800當(dāng)前內(nèi)容-苯----四氫呋喃--體積100300

分別記苯、丁醇、丙醇、苯乙醇、四氫呋喃為第1，2，3，4，5種液體.顯然，新到液體應(yīng)盡可能裝入已存有此種液體的罐中.

所以余下液體為：900m3

苯，700m3

丁醇，1000m3

丙醇，450m3

乙醇和700m3

四氫呋喃.剩余空罐為1，3，4，5，6，8，9.由于不允許混合，每種液體至少需要1個(gè)空罐.令第i種液體裝入第j

個(gè)存儲(chǔ)罐否則記第j個(gè)空罐的容量為cj

，j=1,3,4,5,6,8,9,第