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

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

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

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

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

4、可能具有各種不同的尺寸,如何根據(jù)用,戶提出的要求，用最少的線材截出所需的定貨；,2,、,二維,BP,玻璃廠生產(chǎn)出長(zhǎng)寬一定的大的平板玻璃,但用戶所需玻璃的長(zhǎng)寬可能有許多差異，如何根據(jù)用,戶提出的要求，用最少的平板玻璃截出所需的定貨,;,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ù)完成,.,4,、,生產(chǎn)流水線的平衡問(wèn)題,給定流水節(jié)拍,C,如何設(shè)置,最少的工作站，（按一定的緊前約束）沿著流水線將任,務(wù)分配到各工作站上,.,稱為帶附

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

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

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

8、按物品給定的順序裝箱,；,2,、,關(guān)閉原則,.,對(duì)當(dāng)前要裝的物品,J,i,只關(guān)心具有最大下標(biāo)的已使,用過(guò)的箱子,B,j,能否裝得下？,能,.,則,J,i,放入,B,j,；否,.,關(guān)閉,B,j,，,J,i,放入新箱子,B,j,+1,.,計(jì)算復(fù)雜性為,O,(,n,).,3,裝箱問(wèn)題的近似算法,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,，,解為,:,其余為零，,第八章 裝箱問(wèn)題,Theorem,3.3,Proof,:,先證,再說(shuō)明不可改進(jìn),設(shè),I,為任一實(shí)例，,(,要證,),顯然，由 得,反證,如果,則 對(duì)任意,i,=1,2,k,由于起用第,2,i,個(gè)箱子是因?yàn)榈?2,i,-1,個(gè)箱子放不下第,2,i,個(gè)箱子中第一個(gè)物品,因此這兩個(gè)箱子中物品的總長(zhǎng)度,大于,C,，所以前,2,k,個(gè)箱子中物品的總長(zhǎng)度大于,Ck,.,這與 矛盾,.

10、,考慮實(shí)例,I:,C,=1,3,裝箱問(wèn)題的近似算法,二、,FF,(,First Fit,),算法,設(shè)物品,J,1,，,J,2,，,J,n,的長(zhǎng)度分別為,w,1,，,w,2,，,w,n,箱子,B,1,，,B,2,，,的長(zhǎng)均為,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,時(shí),僅看,B,2,是否能放入，因,B,1,已關(guān)閉,參見(jiàn),EX,.1,但事實(shí)上，,B,1,此時(shí)是能放得下,J,3,的,.,如何修正,NF,算法,先將,J,1,放入,B,1,，若,則,J,2,放入,B,1

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

12、為,O,(,nlogn,).,特點(diǎn),：,1,、按物品給定的順序裝箱,；,2,、,對(duì)于每個(gè)物品,J,j,總是放在能容納它的具,有最小標(biāo)號(hào)的箱子,.,但精度比,NF,算法更高,3,裝箱問(wèn)題的近似算法,Theorem,3.4,Theorem,3.5,對(duì)任意實(shí)例,I,，,而且存在 任意大的實(shí)例,I,，使,因而,第八章 裝箱問(wèn)題,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,對(duì)于,J,3,先檢查,B,1,是否能,容納下,能,.,所以將,J,3,放,入,B,1,，,解為,:,其余為零，,3,裝箱問(wèn)題的近似算法,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,算法,參見(jiàn),EX,.3,用,FF,算法裝箱,當(dāng)放入,J,4,時(shí),B,1,能容納,J,4,就放入,B,1,，而事實(shí)上，放入,B,2,更好,.,第八章 裝箱問(wèn)題,三、,BF,(,Best Fit,),算法,與,FF,算法相似，按物品給定的順序裝箱，區(qū)別在,于對(duì)于每個(gè)物品,J,j,是放在一個(gè)使得,J,j,放入之后，,B,i,所,剩余長(zhǎng)度為最小者,.,即在處理,J,j,時(shí)，若,B,1,，,B,2,，,B,i,非空，而,B,i+,1,尚,未啟用，設(shè),B,1,，,B,2,，,B,i,所余的長(zhǎng)度為,若,則將,J,j,放入,B,i,+1,內(nèi),;,否則，從 的,B,k

15、,中，選取 一個(gè),B,l,使得,為最小者,.,BF,算法的絕對(duì)性能比、計(jì)算復(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,裝箱問(wèn)題的近似算法,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)解,.,第八章 裝箱問(wèn)題,四、,FFD,(,First Fit Decreasing,),算法,FFD,算法是先將物品按長(zhǎng)度從大到小排序，

16、然后用,FF,算法對(duì)物品裝箱,.,該算法的計(jì)算復(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,裝箱問(wèn)題的近似算法,Theorem,3.6,Proof,:,顯然對(duì)任意實(shí)例,I,，有,記,首先證明兩個(gè)結(jié)論,：,(1),FFD,算法所用的第 個(gè)箱子中每個(gè)的,長(zhǎng)度不超過(guò),記,w,i,是放入第 個(gè)箱子中的第一個(gè)物品,只需證,用反證法，若不然，則有 ，因此,FFD,算法中前 個(gè)箱子中,每個(gè)箱子至多有兩個(gè)物品,.,第八章 裝箱問(wèn)題,可證明存在 使前,k,個(gè)恰各含一個(gè)物品，后,個(gè)箱子各含兩個(gè)物品,.,因?yàn)槿舨蝗?，則存在兩個(gè)箱子 使,B,p,有兩,個(gè)物品,B,q,有一個(gè)物品 因物品已從大到,小