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

《數(shù)學(xué)建模---第八章-裝箱問題概述》由會員分享，可在線閱讀，更多相關(guān)《數(shù)學(xué)建模---第八章-裝箱問題概述（33頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,第八章 裝箱問題,組合優(yōu)化理論,Combinatorial,Optimization Theory,第八章 裝箱問題,1,裝箱問題的描述,2,裝箱問題的最優(yōu)解值下界,3,裝箱問題的近似算法,第八章 裝箱問題,裝箱問題（,Bin Packing,）是一個經(jīng)典的組合優(yōu)化,問題，有著廣泛的應(yīng)用，在日常生活中也屢見不鮮,.,1,裝箱問題的描述,設(shè)有許多具有同樣結(jié)構(gòu)和負荷的箱子,B,1,，,B,2,，,其數(shù)量足夠供所達到目的之用,.,每個箱子的負荷（可為,長度、重量,etc,.,）,為,C,今有,n,個負荷為,w,j

2、,，,0,w,j,C,j,=1,，,2,，,，,n,的物品,J,1,，,J,2,，,，,J,n,需要裝入箱內(nèi),.,裝箱問題：,是指尋找一種方法，使得能以最小數(shù)量的箱子數(shù)將,J,1,，,J,2,，,，,J,n,全部裝入箱內(nèi),.,1,裝箱問題的描述,由于,w,i,C,，所以,BP,的最優(yōu)解的箱子數(shù)不超過,n,.,設(shè),箱子,B,i,被使用,否則,物品,J,j,放入箱子,B,i,中,否則,則裝箱問題的整數(shù)線性規(guī)劃模型為,：,約束條件（,1,）表示：一旦箱子,B,i,被使用，放入,B,i,的物品總負荷不超過,C,；,約束條件（,2,）表示：每個物品恰好放入一個箱子中,.,第八章 裝箱問題,上述裝箱問題是

3、這類問題最早被研究的，也是提,法上最簡單的問題，稱為一維裝箱問題,.,但,裝箱問題的其他一些提法,：,1,、,在裝箱時，不僅考慮長度，同時考慮重量或面積、,體積,etc,.,即二維、三維、,裝箱問題,；,2,、對每個箱子的負荷限制不是常數(shù),C,;,而是,最優(yōu)目標可如何提？,3,、物品,J,1,，,J,2,，,，,J,n,的負荷事先并不知道，來貨是,隨到隨裝；即 在線（,On-Line,）裝箱問題；,4,、由于場地的限制，在同一時間只能允許一定數(shù)量的,箱子停留現(xiàn)場可供使用,etc,.,1,裝箱問題的描述,BP,的應(yīng)用舉例,：,1,、,下料問題,軋鋼廠生產(chǎn)的線材一般為同一長度,而用,戶所需的線材則

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

5、加優(yōu)先約束的,BP,.,BP,是容量限制的工廠選址問題的特例之一,.,Go back,第八章 裝箱問題,2,裝箱問題的最優(yōu)解值下界,由于,BP,是,NP-C,問題，所以求解考慮 一是盡可能,改進簡單的窮舉搜索法，減少搜索工作量,.,如,:,分支,定界法；二是啟發(fā)式（近似）算法,.,顯然,是它的一個最優(yōu)解,.,2,裝箱問題的最優(yōu)解值下界,Theorem,3.1,BP,最優(yōu)值的一個下界為,表示不小于,a,的最小整數(shù),.,Theorem,3.2,設(shè),a,是任意滿足 的整數(shù),對,BP,的任一實例,I,記,則,是最優(yōu)解的一個下界,.,第八章 裝箱問題,a,C,C,/2,C-a,I,1,I,2,I,3,P

6、roof,:,僅考慮對,I,1,I,2,I,3,中物品的裝箱,.,中物品的長度大于,C,/2,每個物品需單獨放入一個箱子，,這就需要 個箱子,.,又 中每個物品長度至少為,a,但可能與,I,2,中的,物品共用箱子,，,它不能與,I,1,中的物品共用箱子,與,I,2,中的物品如何？,由于放,I,2,中物品的 個箱子的剩余,總長度為,在最好的情形下，被,I,3,中的物品全部充滿，故剩,下總長度 將另外至少 個附加的箱子,.,Note:,可能小于零,是最優(yōu)解的一個下界,.,2,裝箱問題的最優(yōu)解值下界,問？,未必！,如,Corollary,3.1,記,則,L,2,是裝箱問題的最優(yōu)解的一個下界，且,.,

7、Proof,:,L,2,為最優(yōu)解的下界是顯然的,.,(,若證明 ，則可得,),當(dāng),a,=0,時，是所有物品,.,Go back,第八章 裝箱問題,3,裝箱問題的近似算法,一、,NF,(,Next Fit,),算法,設(shè)物品,J,1,，,J,2,，,J,n,的長度分別為,w,1,，,w,2,，,w,n,箱子,B,1,，,B,2,，,的長均為,C,，按物品給定的順序裝箱,.,先將,J,1,放入,B,1,如果 則將,J,2,放入,B,1,如果 而,則,B,1,已放入,J,1,，,J,2,，,J,j,，將其,關(guān)閉,，將,J,j,+1,放入,B,2,.,同法進行，直到所有物品裝完為止,.,特點,：,1,、

8、按物品給定的順序裝箱,；,2,、,關(guān)閉原則,.,對當(dāng)前要裝的物品,J,i,只關(guān)心具有最大下標的已使,用過的箱子,B,j,能否裝得下？,能,.,則,J,i,放入,B,j,；否,.,關(guān)閉,B,j,，,J,i,放入新箱子,B,j,+1,.,計算復(fù)雜性為,O,(,n,).,3,裝箱問題的近似算法,Example,1,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,4,2,8,3,I,:,C,=10,J,1,J,5,J,6,J,4,J,3,J,2,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,3,J,4,J,5,J,6,Solution,:,首先，將,J,1,放入,B

9、,1,;,由于,J,2,在,B,1,中放不下,所,以關(guān)閉,B,1,將,J,2,放入,B,2,J,3,在,B,2,中放不下,(,不考慮,B,1,是否能裝,),所以關(guān)閉,B,2,將,J,3,放入,B,3,，,解為,:,其余為零，,第八章 裝箱問題,Theorem,3.3,Proof,:,先證,再說明不可改進,設(shè),I,為任一實例，,(,要證,),顯然，由 得,反證,如果,則 對任意,i,=1,2,k,由于起用第,2,i,個箱子是因為第,2,i,-1,個箱子放不下第,2,i,個箱子中第一個物品,因此這兩個箱子中物品的總長度,大于,C,，所以前,2,k,個箱子中物品的總長度大于,Ck,.,這與 矛盾,.

10、,考慮實例,I:,C,=1,3,裝箱問題的近似算法,二、,FF,(,First Fit,),算法,設(shè)物品,J,1,，,J,2,，,J,n,的長度分別為,w,1,，,w,2,，,w,n,箱子,B,1,，,B,2,，,的長均為,C,，按物品給定的順序裝箱,.,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,4,2,8,3,I,:,C,=10,用,NF,算法裝,箱,當(dāng)放入,J,3,時,僅看,B,2,是否能放入，因,B,1,已關(guān)閉,參見,EX,.1,但事實上，,B,1,此時是能放得下,J,3,的,.,如何修正,NF,算法,先將,J,1,放入,B,1,，若,則,J,2,放入,B,1

11、,否,則，,J,2,放入,B,2,;,若,J,2,已放入,B,2,，對于,J,3,則依次,檢查,B,1,、,B,2,若,B,1,能放得下,則,J,3,放入,B,1,否則查看,B,2,若,B,2,能放得下，則,J,3,放入,B,2,否則啟用,B,3,J,3,放入,B,3,.,第八章 裝箱問題,一般地，,J,1,，,J,j,已放入,B,1,，,B,i,箱子，對于,J,j,+1,則依次檢查,B,1,，,B,2,，,B,i,，將,J,j,+1,放入首先找到的能,放得下的箱子，如果都放不下，則啟用箱子,B,i,+1,，將,J,j,+1,放入,B,i,+1,，如此繼續(xù)，直到所有物品裝完為止,.,計算復(fù)雜性

12、為,O,(,nlogn,).,特點,：,1,、按物品給定的順序裝箱,；,2,、,對于每個物品,J,j,總是放在能容納它的具,有最小標號的箱子,.,但精度比,NF,算法更高,3,裝箱問題的近似算法,Theorem,3.4,Theorem,3.5,對任意實例,I,，,而且存在 任意大的實例,I,，使,因而,第八章 裝箱問題,Example,2,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,4,2,8,3,I,:,C,=10,J,1,J,5,J,6,J,4,J,3,J,2,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,3,J,4,J,5,J,6,Solution

13、,:,首先，將,J,1,放入,B,1,;,由于,J,2,在,B,1,中放不下,所,以將,J,2,放入,B,2,對于,J,3,先檢查,B,1,是否能,容納下,能,.,所以將,J,3,放,入,B,1,，,解為,:,其余為零，,3,裝箱問題的近似算法,Example,3,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,8,3,2,4,I,:,C,=10,J,1,J,4,J,3,J,2,Solution,:,用,NF,算法,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,6,J,5,J,3,J,4,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,6,J,5

14、,J,3,J,4,J,6,J,5,用,FF,算法,參見,EX,.3,用,FF,算法裝箱,當(dāng)放入,J,4,時,B,1,能容納,J,4,就放入,B,1,，而事實上，放入,B,2,更好,.,第八章 裝箱問題,三、,BF,(,Best Fit,),算法,與,FF,算法相似，按物品給定的順序裝箱，區(qū)別在,于對于每個物品,J,j,是放在一個使得,J,j,放入之后，,B,i,所,剩余長度為最小者,.,即在處理,J,j,時，若,B,1,，,B,2,，,B,i,非空，而,B,i+,1,尚,未啟用，設(shè),B,1,，,B,2,，,B,i,所余的長度為,若,則將,J,j,放入,B,i,+1,內(nèi),;,否則，從 的,B,k

15、,中，選取 一個,B,l,使得,為最小者,.,BF,算法的絕對性能比、計算復(fù)雜性與,FF,算法相同,.,Example,4,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,8,3,2,4,I,:,C,=10,3,裝箱問題的近似算法,J,1,J,4,J,3,J,2,J,6,J,5,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,6,J,5,J,3,J,4,Solution,:,用,BF,算法,解為,:,其余為零，,而 此為最優(yōu)解,.,第八章 裝箱問題,四、,FFD,(,First Fit Decreasing,),算法,FFD,算法是先將物品按長度從大到小排序，

16、然后用,FF,算法對物品裝箱,.,該算法的計算復(fù)雜性為,O,(,nlogn,).,Example,5,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,4,2,8,3,I,:,C,=10,J,1,J,5,J,6,J,4,J,3,J,2,Solution,:,已知,：,物品,J,5,J,2,J,1,J,3,J,6,J,4,w,j,8,7,6,4,3,2,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,3,J,4,J,5,J,6,是最優(yōu)的,.,NFD,算法？,BFD,算法？,3,裝箱問題的近似算法,Theorem,3.6,Proof,:,顯然對任意實例,I,，有,記,首先證明兩個結(jié)論,：,(1),FFD,算法所用的第 個箱子中每個的,長度不超過,記,w,i,是放入第 個箱子中的第一個物品,只需證,用反證法，若不然，則有 ，因此,FFD,算法中前 個箱子中,每個箱子至多有兩個物品,.,第八章 裝箱問題,可證明存在 使前,k,個恰各含一個物品，后,個箱子各含兩個物品,.,因為若不然，則存在兩個箱子 使,B,p,有兩,個物品,B,q,有一個物品 因物品已從大到,小