一維裝箱問題典型算法

一維裝箱問題典型算法當(dāng)前1頁，總共32頁。第三章裝箱問題§1裝箱問題的描述§2裝箱問題的最優(yōu)解值下界§3裝箱問題的近似算法當(dāng)前2頁，總共32頁。第三章裝箱問題

裝箱問題（BinPacking）是一個經(jīng)典的組合優(yōu)化問題，有著廣泛的應(yīng)用，在日常生活中也屢見不鮮.§1裝箱問題的描述

設(shè)有許多具有同樣結(jié)構(gòu)和負(fù)荷的箱子B1，B2，…其數(shù)量足夠供所達(dá)到目的之用.每個箱子的負(fù)荷（可為長度、重量etc.）為

C,今有

n

個負(fù)荷為wj，0<wj<Cj=1，2，…，n的物品

J1，J2，…，Jn

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

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

全部裝入箱內(nèi).當(dāng)前3頁，總共32頁。§1裝箱問題的描述

由于wi<C，所以BP

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

被使用否則物品Jj

放入箱子Bi

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

的物品總負(fù)荷不超過C；約束條件（2）表示：每個物品恰好放入一個箱子中.當(dāng)前4頁，總共32頁。第三章裝箱問題

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

.但裝箱問題的其他一些提法：1、在裝箱時，不僅考慮長度，同時考慮重量或面積、體積

etc.即二維、三維、…裝箱問題；2、對每個箱子的負(fù)荷限制不是常數(shù)C;而是最優(yōu)目標(biāo)可如何提？3、物品J1，J2，…，Jn

的負(fù)荷事先并不知道，來貨是隨到隨裝；即在線（On-Line）裝箱問題；4、由于場地的限制，在同一時間只能允許一定數(shù)量的箱子停留現(xiàn)場可供使用,etc.

當(dāng)前5頁，總共32頁?！?裝箱問題的描述BP

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

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

是容量限制的工廠選址問題的特例之一.Goback當(dāng)前6頁，總共32頁。第三章裝箱問題§2裝箱問題的最優(yōu)解值下界

由于BP

是NP-C問題，所以求解考慮一是盡可能改進(jìn)簡單的窮舉搜索法，減少搜索工作量

.如:分支定界法；二是啟發(fā)式（近似）算法

.

顯然是它的一個最優(yōu)解.當(dāng)前7頁，總共32頁?！?裝箱問題的最優(yōu)解值下界Theorem

3.1BP

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

的最小整數(shù).Theorem

3.2

設(shè)a

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

的任一實(shí)例I,

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

.當(dāng)前8頁，總共32頁。第三章裝箱問題aCC/2C-aI1I2I3Proof:僅考慮對I1,I2,I3中物品的裝箱

.中物品的長度大于C/2,每個物品需單獨(dú)放入一個箱子，這就需要個箱子.又中每個物品長度至少為a,

但可能與I2

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

中的物品共用箱子,與I2

中的物品如何？

由于放I2

中物品的個箱子的剩余總長度為

在最好的情形下，被I3

中的物品全部充滿，故剩下總長度將另外至少個附加的箱子.Note:可能小于零是最優(yōu)解的一個下界

.當(dāng)前9頁，總共32頁?！?裝箱問題的最優(yōu)解值下界問？

未必！如Corollary3.1記則L2

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

為最優(yōu)解的下界是顯然的

.(若證明，則可得

)當(dāng)a=0時，是所有物品.Goback當(dāng)前10頁，總共32頁。第三章裝箱問題§3裝箱問題的近似算法一、NF(NextFit)算法

設(shè)物品J1，J2,…，Jn

的長度分別為w1，w2,…，wn箱子B1，B2，…的長均為C

，按物品給定的順序裝箱.

先將J1

放入B1,如果則將J2

放入B1…如果而則B1

已放入J1，J2,…，Jj，將其關(guān)閉，將Jj+1

放入B2.同法進(jìn)行，直到所有物品裝完為止

.特點(diǎn)：1、按物品給定的順序裝箱；2、關(guān)閉原則.

對當(dāng)前要裝的物品Ji

只關(guān)心具有最大下標(biāo)的已使用過的箱子Bj

能否裝得下？能.則Ji

放入

Bj

；否.關(guān)閉Bj

，Ji

放入新箱子Bj+1.計(jì)算復(fù)雜性為

O(n).當(dāng)前11頁，總共32頁?！?裝箱問題的近似算法Example1物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution:首先，將J1

放入B1;由于J2

在B1

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

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

放入B3，…解為:其余為零，當(dāng)前12頁，總共32頁。第三章裝箱問題Theorem

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

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

，所以前2k個箱子中物品的總長度大于Ck.這與矛盾.考慮實(shí)例I:C=1,當(dāng)前13頁，總共32頁?！?裝箱問題的近似算法二、FF(FirstFit)算法

設(shè)物品J1，J2,…，Jn

的長度分別為w1，w2,…，wn箱子B1，B2，…的長均為C

，按物品給定的順序裝箱.物品J1J2J3J4J5J6wj674283I:C=10

用NF算法裝箱,當(dāng)放入

J3

時,僅看B2是否能放入，因B1

已關(guān)閉,參見EX.1但事實(shí)上，B1

此時是能放得下J3

的.如何修正NF

算法先將J1放入B1，若,

則J2

放入B1,否則，J2

放入B2;若J2

已放入B2，對于J3

則依次檢查

B1、B2,若B1

能放得下,則J3

放入B1,否則查看

B2,若B2

能放得下，則J3

放入B2,否則啟用B3,J3放入B3.當(dāng)前14頁，總共32頁。第三章裝箱問題

一般地，J1,…，Jj

已放入B1,…，Bi

箱子，對于Jj+1,則依次檢查B1，B2,…，Bi，將Jj+1

放入首先找到的能放得下的箱子，如果都放不下，則啟用箱子Bi+1

，將Jj+1

放入Bi+1

，如此繼續(xù)，直到所有物品裝完為止.計(jì)算復(fù)雜性為

O(nlogn).特點(diǎn)：1、按物品給定的順序裝箱；2、對于每個物品Jj

總是放在能容納它的具有最小標(biāo)號的箱子.但精度比NF

算法更高當(dāng)前15頁，總共32頁?！?裝箱問題的近似算法Theorem

3.4Theorem

3.5對任意實(shí)例I，而且存在任意大的實(shí)例I，使因而當(dāng)前16頁，總共32頁。第三章裝箱問題Example2物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution:首先，將J1

放入B1;由于J2

在B1

中放不下,所以將J2

放入B2,對于

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

放入B1，…解為:其余為零，當(dāng)前17頁，總共32頁?！?裝箱問題的近似算法Example3物品J1J2J3J4J5J6wj678324I:C=10J1J4J3J2Solution:用NF

算法B1B2B3B4B5J1J2J6J5J3J4B1B2B3B4B5J1J2J6J5J3J4J6J5用FF

算法

參見

EX.3

用FF算法裝箱,當(dāng)放入

J4

時,B1能容納J4

就放入B1

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

更好.當(dāng)前18頁，總共32頁。第三章裝箱問題三、BF(BestFit)算法

與FF

算法相似，按物品給定的順序裝箱，區(qū)別在于對于每個物品Jj

是放在一個使得Jj放入之后，Bi

所剩余長度為最小者.

即在處理Jj

時，若B1，B2,…，Bi

非空，而Bi+1

尚未啟用，設(shè)B1，B2,…，Bi

所余的長度為若則將Jj

放入Bi+1

內(nèi);否則，從的

Bk

中，選取一個

Bl

使得

為最小者

.BF

算法的絕對性能比、計(jì)算復(fù)雜性與

FF

算法相同

.當(dāng)前19頁，總共32頁。Example4物品J1J2J3J4J5J6wj678324I:C=10§3裝箱問題的近似算法J1J4J3J2J6J5B1B2B3B4B5J1J2J6J5J3J4Solution:用BF

算法解為:其余為零，而此為最優(yōu)解.當(dāng)前20頁，總共32頁。第三章裝箱問題四、FFD(FirstFitDecreasing)算法

FFD

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

算法對物品裝箱.該算法的計(jì)算復(fù)雜性為

O(nlogn).Example5物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2Solution:已知：物品J5J2J1J3J6J4wj876432B1B2B3B4B5J1J2J3J4J5J6是最優(yōu)的

.NFD

算法？BFD

算法？當(dāng)前21頁，總共32頁?！?裝箱問題的近似算法Theorem

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

是放入第個箱子中的第一個物品,只需證用反證法，若不然，則有，因此FFD算法中前個箱子中,每個箱子至多有兩個物品.當(dāng)前22頁，總共32頁。第三章裝箱問題

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

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

,Bq

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

放入Bq中，矛盾.當(dāng)前23頁，總共32頁。§3裝箱問題的近似算法

因?yàn)镕FD

未將wk+1,…，wi

放入前k個箱子，說明其中任一個箱子已放不下,故在最優(yōu)解中也至少有k個箱子不含wk+1,…，wi

中任一個物品

.假設(shè)就是前k個箱子，因此在最優(yōu)解中，wk+1,…，wi-1

也會兩兩放入第個箱子中，且因?yàn)檫@些物品長度大于,所以每個箱子中只有兩個物品，且已放不下.但最優(yōu)解中wi

必須放入前個箱子中，矛盾.故(2)FFD

算法放入第個箱子中物品數(shù)不超過而如果至少有個物品放入第個箱子中，記前個物品的長度為.當(dāng)前24頁，總共32頁。第三章裝箱問題記FFD

算法中前個箱子中每個箱子物品總長為顯然，對任意否則長為的物品可放入第j個箱子中，因此矛盾

.所以(2)結(jié)論成立

.

由(1)、(2)知FFD算法比最優(yōu)算法多用的箱子是用來放至多個物品，而每個物品長不超過，因此當(dāng)前25頁，總共32頁。§3裝箱問題的近似算法因此因?yàn)槿绻?，則，故不妨設(shè)考慮實(shí)例I：物品集長度為,C為箱長.說明是不可改進(jìn)的.當(dāng)前26頁，總共32頁。第三章裝箱問題

比較NF

算法、FF(BF)算法、FFD

算法，它們的近似程度一個比一個好，但這并不是說

NF、FF(BF)就失去了使用價值.1、FF(BF)、FFD

算法都要將所有物品全部裝好后,所有箱子才能一起運(yùn)走，而NF

算法無此限制，很適合裝箱場地小的情形；2、FFD

算法要求所有物品全部到達(dá)后才開始裝箱,而

NF、FF(BF)算法在給某一物品裝箱時，可以不知道下一個物品的長度如何，適合在線裝箱

.當(dāng)前27頁，總共32頁。存儲罐注液問題第三章裝箱問題

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

苯，700m3

丁醇，1000m3

丙醇，450m3

苯乙醇和1200m3

四氫呋喃.下表列出每個存儲罐的屬性(單位:m3),問應(yīng)如何將新到的液體原料裝罐,才能使保留未用的存儲罐個數(shù)最多?存儲罐編號123456789容量500400400600600900800800800當(dāng)前內(nèi)容-苯----四氫呋喃--體積100300當(dāng)前28頁，總共32頁。第三章裝箱問題Solution:存儲罐編號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個空罐.令第i種液體裝入第j

個存儲罐否則記第j