實(shí)用下料問(wèn)題 - 同濟(jì)大學(xué)數(shù)學(xué)系

1、 實(shí)用下料問(wèn)題一問(wèn)題的重述“下料問(wèn)題(cutting stock problem)”是把相同形狀的一些原材料分割加工成若干個(gè)不同規(guī)格大小的零件的問(wèn)題，此類問(wèn)題在工程技術(shù)和工業(yè)生產(chǎn)中有著重要和廣泛的應(yīng)用. 這里的“實(shí)用下料問(wèn)題”則是在某企業(yè)的實(shí)際條件限制下的單一材料的下料問(wèn)題?，F(xiàn)考慮單一原材料下料問(wèn)題. 設(shè)這種原材料呈長(zhǎng)方形，長(zhǎng)度為,寬度為，現(xiàn)在需要將一批這種長(zhǎng)方形原料分割成種規(guī)格的零件, 所有零件的厚度均與原材料一致，但長(zhǎng)度和寬度分別為，其中wi. 種零件的需求量分別為.下料時(shí)，零件的邊必須分別和原材料的邊平行。這類問(wèn)題在工程上通常簡(jiǎn)稱為二維下料問(wèn)題。特別當(dāng)所有零件的寬度均與原材料相等，即，則

2、問(wèn)題稱為一維下料問(wèn)題。一個(gè)好的下料方案首先應(yīng)該使原材料的利用率最大，從而減少損失，降低成本，提高經(jīng)濟(jì)效益。其次要求所采用的不同的下料方式盡可能少，即希望用最少的下料方式來(lái)完成任務(wù)。因?yàn)樵谏a(chǎn)中轉(zhuǎn)換下料方式需要費(fèi)用和時(shí)間，既提高成本，又降低效率。此外，每種零件有各自的交貨時(shí)間，每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制。因此實(shí)用下料問(wèn)題的目標(biāo)是在生產(chǎn)能力容許的條件下，以最少數(shù)量的原材料，盡可能按時(shí)完成需求任務(wù), 同時(shí)下料方式數(shù)也盡量地小?，F(xiàn)在我們要為某企業(yè)考慮下面兩個(gè)問(wèn)題。1建立一維單一原材料實(shí)用下料問(wèn)題的數(shù)學(xué)模型, 并用此模型求解下列問(wèn)題，制定出在生產(chǎn)能力容許的條件下滿足需求的下料方案, 同時(shí)求出等

3、額完成任務(wù)所需的原材料數(shù)，所采用的下料方式數(shù)和廢料總長(zhǎng)度. 單一原材料的長(zhǎng)度為 3000mm, 需要完成一項(xiàng)有53種不同長(zhǎng)度零件的下料任務(wù). 具體數(shù)據(jù)見(jiàn)表一(略)，其中 為需求零件的長(zhǎng)度，為需求零件的數(shù)量. 此外，在每個(gè)切割點(diǎn)處由于鋸縫所產(chǎn)生的損耗為5mm. 據(jù)估計(jì)，該企業(yè)每天最大下料能力是100塊 ，要求在4天內(nèi)完成的零件標(biāo)號(hào)()為: 5,7,9,12,15,18,20,25, 28,36,48；要求不遲于6天完成的零件標(biāo)號(hào)()為:4,11,24,29,32,38,40,46,50。2立二維單一原材料實(shí)用下料問(wèn)題的數(shù)學(xué)模型, 并用此模型求解下列問(wèn)題.制定出在企業(yè)生產(chǎn)能力容許的條件下滿足需求的

4、下料方案, 同時(shí)求出等額完成任務(wù)所需的原材料塊數(shù)和所需下料方式數(shù).這個(gè)問(wèn)題的單一原材料的長(zhǎng)度為 3000mm,寬度為100mm, 需要完成一項(xiàng)有43種不同長(zhǎng)度和寬度零件的下料任務(wù). 具體數(shù)據(jù)見(jiàn)表二(略)，其中 分別為需求零件的長(zhǎng)度、寬度和數(shù)量. 切割時(shí)的鋸縫可以是直的也可以是彎的，切割所引起的鋸縫損耗忽略不計(jì).據(jù)估計(jì)，該企業(yè)每天最大下料能力是20塊 要求在4天內(nèi)完成的零件標(biāo)號(hào)()為: 3,7,9,12,15, 18, 20, 25, 28, 36. 二問(wèn)題的分析在生產(chǎn)實(shí)踐中，經(jīng)常會(huì)遇到如鋼材、木材等條型材的下料問(wèn)題，即如何根據(jù)原材料的長(zhǎng)度、零件的尺寸以及需求量確定出使原材料消耗最少的最優(yōu)下料方

5、案。本題要求：在生產(chǎn)能力容許的條件下，以最少數(shù)量的原材料，盡可能按時(shí)完成需求任務(wù), 同時(shí)下料方式數(shù)也盡量地小。對(duì)于一維下料問(wèn)題，首先我們必須找出全部可行的下料方式；然后才能確定下料方式作為決策變量和形式約束條件的結(jié)構(gòu)系數(shù)，這樣才能建立優(yōu)化決策模型，通過(guò)計(jì)算機(jī)編程計(jì)算得到我們所需要的最優(yōu)下料方案?？紤]到這里是單一原材料下料問(wèn)題，這大大減少了下料方式；但由于零件的種類有53種之多，因此下料方式仍然很多，計(jì)算量很大，所以在建立優(yōu)化模型的基礎(chǔ)上，我們需要找到比較合適的算法來(lái)解決這類實(shí)際問(wèn)題。近年來(lái)，國(guó)內(nèi)外關(guān)于這方面的研究比較活躍，并涌現(xiàn)出了不少近似算法，如Gilmore與Gomory用線性規(guī)劃建立的一

6、刀切問(wèn)題的數(shù)學(xué)模型；Dyckhoff提出的線性規(guī)劃方法以及Sarker提出的動(dòng)態(tài)規(guī)劃方法等。由于下料問(wèn)題屬于布局問(wèn)題，不同于一般的數(shù)值性優(yōu)化,近年又出現(xiàn)應(yīng)用遺傳算法來(lái)求解下料優(yōu)化問(wèn)題。我們力圖建立一種實(shí)用的模型多目標(biāo)整數(shù)規(guī)劃模型1 27，并提出一種新的優(yōu)化思想方法啟發(fā)式多層次逐層優(yōu)化方法，解決此問(wèn)題；同時(shí)與其他的求解方法進(jìn)行比較。對(duì)于二維下料問(wèn)題，我們采用分類層次分析法；由于原材料的長(zhǎng)度為3000mm，寬度為100mm，而43種零件的長(zhǎng)度最小的為155mm，這樣就不會(huì)出現(xiàn)零件的長(zhǎng)邊在原材料的寬邊上切割的情況，也就是說(shuō)零件的長(zhǎng)邊都是順著原材料的長(zhǎng)邊切割的?？紤]到零件的寬有20，30，35，50（

7、mm）這4種規(guī)格，為了盡量節(jié)省材料，我們應(yīng)該使原材料在寬邊上盡量利用完全，這樣只有幾種寬邊完全利用的組合方式（5種），分別為：50-50，50-30-20， 30-30-20-20，35-35-30，20-20-20-20-20。我們把零件按寬邊的規(guī)格分為4類（20，30，35，50），對(duì)每一類都可按問(wèn)題一的處理一維下料問(wèn)題的方式找最優(yōu)的方案，然后再把他們按上述的幾種方式進(jìn)行組合，以求得最優(yōu)解。三問(wèn)題的假設(shè)1對(duì)于第一問(wèn)的假設(shè)：1） 在每個(gè)切割點(diǎn)處由于鋸縫所產(chǎn)生的損耗為5mm；2） 企業(yè)每天的最大下料能力為100塊；3） 考慮下料方式的數(shù)量對(duì)總損耗的影響，下料方式越少則原材料總損耗越??；4） 對(duì)

8、于剩余長(zhǎng)度為mm的材料，可以通過(guò)細(xì)微調(diào)整鋸縫的位置鋸得長(zhǎng)度為mm的零件；2對(duì)于第二問(wèn)的假設(shè)：1） 切割所引起的鋸縫損耗忽略不計(jì)；2） 切割時(shí)鋸縫可以是直的也可以是彎的，但要求轉(zhuǎn)彎為直角；3） 企業(yè)每天最大的下料能力是20塊；4） 原材料和零件都是長(zhǎng)方形。四符號(hào)說(shuō)明原材料的長(zhǎng)度（=3000mm）原材料的寬度（=100mm）所用的原材料總數(shù)量所采用的下料方式總數(shù)量第i號(hào)零件的長(zhǎng)度（單位：mm，）第i號(hào)零件的寬度第i號(hào)零件的需求量第j種下料方式中切割第i號(hào)零件的數(shù)量按第j種下料方式切割的原材料的數(shù)量按第j種下料方式切割的廢料長(zhǎng)度（mm）第一問(wèn)中要求在4天內(nèi)完成的零件號(hào)的集合 第一問(wèn)中要求在不遲于6天

9、完成的零件號(hào)的集合 第二問(wèn)中要求在4天內(nèi)完成的零件號(hào)的集合 五模型的建立與求解1對(duì)問(wèn)題一的解決：此問(wèn)要求：在4天內(nèi)完成的零件標(biāo)號(hào)()為: 5,7,9,12,15,18,20,25, 28,36,48；不遲于6天完成的零件標(biāo)號(hào)()為:4,11,24,29,32,38,40,46,50。而該企業(yè)每天最大下料能力是100塊，我們要制定出在生產(chǎn)能力容許的條件下滿足需求的下料方案，同時(shí)要求等額完成任務(wù)，我們的目標(biāo)是要盡可能節(jié)省材料，盡可能用少的下料方式。為此我們建立多目標(biāo)整數(shù)規(guī)劃模型：（首先我們約定：）, （1） 注：1.我們有：若采用了第j種下料方式，則為大于0的整數(shù)，因此；若沒(méi)有采用第j種下料方式，

10、則為0，如上定義可得：，這樣即表示了所用的下料方式數(shù)量；2約束中第一條是：考慮了鋸縫時(shí)，原材料長(zhǎng)度L對(duì)下料方式的限制，即對(duì)于任意一種下料方式，所得到的零件總長(zhǎng)度與鋸縫總長(zhǎng)度之和要小于等于L；3約束中第二條是：考慮了鋸縫時(shí)，對(duì)于每一種下料方式的廢料長(zhǎng)度要小于零件的最小長(zhǎng)度；4約束中第三條是：為了滿足題中要求的等額完成任務(wù)的限制條件；5約束中第四條是：為了滿足在企業(yè)每天生產(chǎn)能力是100塊時(shí)，要求在4天內(nèi)完成零件集合的條件，其中表示第j種下料方式中所切割的第i種零件數(shù)占這種下料方式中所切割的零件集合中零件數(shù)的權(quán)數(shù)，因此表示了完成零件集合所用的原材料數(shù)，又由于在4天內(nèi)要完成零件集合，故上述所算出的所用

11、的原材料數(shù)要小于等于，注意若，即表示第j種下料方式中沒(méi)有切割到零件集合中的零件，因此：，這樣按照注釋1中的約定，可知正好表示：這種下料方式不產(chǎn)生集合中的零件，故而這條約束很完善；6約束中第五條和第四條的解釋類似；約束中第六條和第七條表示和要取整數(shù)。對(duì)于廢料的度量：由于存在鋸縫為5mm，對(duì)任何一種可行的下料方式，則其滿足條件，所以如果單純的用來(lái)度量此種下料方式的廢料是不對(duì)的，這可能取到負(fù)值；實(shí)際上，又由于對(duì)問(wèn)題一有假設(shè)4，我們可以知道：對(duì)所有滿足的下料方式來(lái)說(shuō)，廢料都為0；故而我們可以得到廢料的度量方式：經(jīng)過(guò)數(shù)學(xué)處理，得到：因此廢料總量為：廢棄率定義為：利用率定義為：對(duì)于此模型（即（1）式）的求

12、解比較困難，我們需要首先分解此模型，然后創(chuàng)建適應(yīng)的優(yōu)化算法解決此問(wèn)題：表第j種下料方式1） 當(dāng)前最優(yōu)的下料方式的模型：多層整數(shù)線性規(guī)劃模型a)當(dāng)時(shí)，求最優(yōu)的一種下料方式的數(shù)學(xué)模型為： （2） 其中表一種下料方式，為努力程度，定義為某種下料方式中含有集合中零件的個(gè)數(shù)，從中我們可以看出越大零件集合完成得越快；b) 當(dāng)且時(shí)，求最優(yōu)的一種下料方式的數(shù)學(xué)模型為： （3） 為努力程度，類似的定義和理解；c) 當(dāng)且時(shí)，求最優(yōu)的一種下料方式的數(shù)學(xué)模型為： （4）這三個(gè)模型都是整數(shù)線性規(guī)劃問(wèn)題，可以用分支定界法求解，亦可用lingo直接編程（見(jiàn)附錄程2序九），可以很快計(jì)算得結(jié)果；也可以用matlab7.03編程

13、算得。2） 針對(duì)模型，我們創(chuàng)建適應(yīng)性的算法啟發(fā)式多層次逐層優(yōu)化方法，此方法的基本思想是：在每層求解時(shí)，對(duì)于上層剩余的未完成的各零件數(shù)目，利用上面三個(gè)子模型可以在當(dāng)前可行的下料方式中選擇最優(yōu)的一種下料方式進(jìn)行下料，并盡可能的重復(fù)使用此種下料方式（這是為了使得下料方式盡可能少）；然后對(duì)剩余的未完成的各零件重新優(yōu)化選取新的最優(yōu)的一種下料方式，不斷反復(fù)上面的操作，直到所有剩余的未完成的各零件數(shù)目都減少到0為止。這樣原問(wèn)題的最優(yōu)解就是各個(gè)層次優(yōu)化問(wèn)題所求得的最優(yōu)下料方式的總和。3）啟發(fā)式多層次逐層優(yōu)化方法的計(jì)算方法將上述當(dāng)前最優(yōu)下料方式的三種模型的計(jì)算求解作為啟發(fā)式多層次逐層優(yōu)化方法計(jì)算的子程序,在每級(jí)

14、求解中，對(duì)于相應(yīng)的條件重復(fù)調(diào)用相應(yīng)的子程序。完整的求解過(guò)程如下：Step1：初始給定了未完成的各零件的數(shù)目，4天要完成的零件集合，6天要完成的零件集合；在上一層（j層）得到的未完成的各零件的數(shù)目基礎(chǔ)上，判斷和是否成立，然后依判定條件調(diào)用1）中相應(yīng)的當(dāng)前最優(yōu)下料計(jì)算子程序,求解得到最優(yōu)下料方式，并以此作為這一級(jí)的下料方式；Step2：計(jì)算此種下料方式的重復(fù)次數(shù),即用此種下料方式切割的原材料L的根數(shù)；Step3：計(jì)算去掉根按這種下料方式切割后,余下的未完成的各種零件的數(shù)量：；Step4：將上一步得到的作為新一層優(yōu)化計(jì)算的給定值,并記,令，如果則優(yōu)化計(jì)算結(jié)束；否則轉(zhuǎn)Step1重新判斷并調(diào)用當(dāng)前最優(yōu)下

15、料方式計(jì)算子程序,求得新一層的下料方式和重復(fù)次數(shù)；Step5：各層最優(yōu)下料方式及其重復(fù)次數(shù)的集合即為啟發(fā)式多層次逐層優(yōu)化方法的最終結(jié)果，即和的值；算法流程如圖1所示： （圖1：算法流程）用matlab編程可對(duì)問(wèn)題一進(jìn)行計(jì)算求解（見(jiàn)附錄2程序四），求解的結(jié)果為：所用的原材料的數(shù)量為：根，所用的下料方式為：，廢料總長(zhǎng)度為：，廢棄率為：，利用率為：；同時(shí)從數(shù)據(jù)中可以看出：采用這種方案，只需要4天半就可以完成問(wèn)題一中要求的6天內(nèi)必須完成的零件的要求；該方案對(duì)原材料的利用率非常高，效果很好。具體下料方式數(shù)據(jù)見(jiàn)附錄1表12對(duì)于問(wèn)題二的解決：這是一個(gè)二維下料問(wèn)題611，這里采用分類層次分析法；首先我們分析該

16、問(wèn)題的特點(diǎn)：由于原材料的長(zhǎng)度為3000mm，寬度為100mm，而43種零件的長(zhǎng)度最小的為155mm，這樣就不會(huì)出現(xiàn)零件的長(zhǎng)邊在原材料的寬邊上切割的情況，也就是說(shuō)零件的長(zhǎng)邊都是順著原材料的長(zhǎng)邊切割的?？紤]到零件的寬有20，30，35，50（mm）這4種規(guī)格，為了盡量節(jié)省材料，我們應(yīng)該使原材料在寬邊上盡量利用完全，這樣只有幾種寬邊完全利用的組合方式（5種），分別為：50-50，50-30-20， 30-30-20-20，35-35-30，20-20-20-20-20。我們把零件按寬邊的規(guī)格分為4類（20，30，35，50），對(duì)每一類都可按問(wèn)題一的處理一維下料問(wèn)題的方式找最優(yōu)的方案，然后再把他們按上

17、述的幾種方式進(jìn)行優(yōu)化組合，最后再對(duì)優(yōu)化組合剩余的部分進(jìn)行考慮。為此我們建立分類逐層分析模型：1） 第一層次：首先優(yōu)先考慮寬度的特征，我們把零件按寬邊的規(guī)格分為4類（20，30，35，50），對(duì)每一類都可按問(wèn)題一的用于處理一維下料問(wèn)題的多目標(biāo)整數(shù)規(guī)劃模型和啟發(fā)式多層次逐層優(yōu)化方法方式找最優(yōu)的方案，用mablab編程（見(jiàn)附錄2程序七、八）得到結(jié)果：具體下料方式數(shù)據(jù)見(jiàn)附錄1表2，從中我們可以得到各類寬度零件所需要的長(zhǎng)條數(shù)為（長(zhǎng)為3000mm，寬與零件相對(duì)應(yīng)的長(zhǎng)條）14天為：，。4天后為：，。2） 第二層次：由于寬邊若沒(méi)有填滿，對(duì)整個(gè)板材的利用影響非常大，所以我們要求在寬邊上要盡量填滿（即：盡量沒(méi)有費(fèi)

18、余的）。因此我們?cè)谏弦粚哟蔚玫浇Y(jié)果的基礎(chǔ)上，我們運(yùn)用上面給出的幾種最優(yōu)的組合方式進(jìn)行優(yōu)化組合：50-50，50-30-20， 30-30-20-20，35-35-30，20-20-20-20-20；設(shè)采用第i種組合的次數(shù)為；則可建立整數(shù)線性規(guī)劃模型，以求得所應(yīng)采用的各種組合的次數(shù)。模型如下： （5）利用lingo編程（見(jiàn)附錄2程序十）可以很快求解出此整數(shù)線性規(guī)劃的最優(yōu)解為：14天為：，4天后為：，可知：14天可以實(shí)現(xiàn)恰好的組合；而4天后的部分則余下一個(gè)寬為30的長(zhǎng)條，14天所用的原材料總數(shù)為：,4天后所用的原材料總數(shù)為：,其中1表示余下的一個(gè)寬為30的長(zhǎng)條要占用一塊原材料。則所用的原材料的總數(shù)

19、為：N=79+373=4523） 第三層次：對(duì)上述優(yōu)化組合后，剩余的部分進(jìn)行分析：即對(duì)第二層中優(yōu)化模型求出最優(yōu)解后，所剩余的部分進(jìn)行研究。對(duì)于上一層次中14天的情形，沒(méi)有余下的長(zhǎng)條，故可不考慮這一層；對(duì)于上一層次中4天后的情形，余下的一塊寬為30（單位：mm，下同）的長(zhǎng)條，我們選廢料長(zhǎng)度最長(zhǎng)的那一塊進(jìn)行討論，將這一長(zhǎng)條再分解為零件，然后尋找其他的寬度的廢料塊，看能否用這些廢料來(lái)切割得到那個(gè)寬為30的長(zhǎng)條上的零件：若可以做到這一點(diǎn)，則這塊余下的長(zhǎng)條就被消化掉了；若不可以，則這塊長(zhǎng)條就要占用一塊原材料。利用這種思想方法，結(jié)合附錄表2的下料數(shù)據(jù)，我們很容易找到浪費(fèi)最多的那塊寬為30的長(zhǎng)條：11051

20、032切割組合；同時(shí)可以找到寬為35的有長(zhǎng)為1200的廢料，寬為50的有長(zhǎng)為2460的廢料，這樣我們可以1105x30和1032x30的零件用2460x50這塊廢料來(lái)切割得到。這樣我們就消化掉了余下的這個(gè)長(zhǎng)條。因此，利用這種處理方法可以節(jié)省一塊原材料，故所用的原材料總數(shù)為:N=452-1=451。通過(guò)如上我調(diào)整后，得到數(shù)據(jù)見(jiàn)附錄1表3計(jì)算廢料面積為：廢棄率為：利用率為：4）第四層次：在此基礎(chǔ)上（即上面模型所求得的各組合最優(yōu)數(shù)量），再考慮怎樣使下料方式盡量少。從第二層次得到：14天的：3塊50-50，76塊30-30-20-20；4天后的：31塊50-30-20，120塊30-30-20-20，

21、63塊35-35-30，158塊20-20-20-20-20；同時(shí)要用到第三層次中調(diào)整后的數(shù)據(jù)表3。為了使下料方式最少，我們制定下述的下料方式搭配規(guī)則（算法）：對(duì)于14天的：a)首先考慮組合50-50：可知這里只有一種下料方式：14天寬50（1）-14天寬50（1），數(shù)量為3（注：14天寬50（i）：表示14天中寬為50的下料方式中的第i種下料方式）；b)再考慮組合30-30-20-20： 令表示14天寬為20的第i種下料的數(shù)量（i=1,7），表示14天寬為30的第k種下料的數(shù)量(k=1,10)，再令表示在此組合下第j種下料方式是：14天寬20（1）-14天寬20（7）-14天寬30（1）-1

22、4天寬30（10）；表示第j種下料方式采用的次數(shù)。則我們可建立整數(shù)規(guī)劃模型：（注意：同上文約定） （6） 求解此整數(shù)規(guī)劃模型可以得到最優(yōu)的下料方式，使得下料方式數(shù)最小。計(jì)算結(jié)果為：需要原材料的塊數(shù)為,下料方式為11種（見(jiàn)附錄1表4）對(duì)于4天后的： 用同樣的方法可計(jì)算得到結(jié)果為：需要原材料的塊數(shù)為,下料方式為26種（見(jiàn)附錄1表5）故而總的下料方式數(shù)為K=37,下料方式為：表4加上表5；綜上第一到第四層，我們就解決了問(wèn)題二：需要原材料的塊數(shù)為：，需要的下料方式數(shù)為： ，廢料總面積為：，廢棄率為：，原材料的利用率為：。六模型和算法的分析與評(píng)價(jià)1模型的評(píng)價(jià)對(duì)于問(wèn)題一所建立的多目標(biāo)整數(shù)規(guī)劃模型，很準(zhǔn)確的

23、概括了該問(wèn)題的所有約束和目標(biāo)，從理論上講是一個(gè)很嚴(yán)謹(jǐn)?shù)哪Ｐ?。但是?duì)于這一模型的求解卻是非常困難的，必須尋找比較好的算法支持它，而文中我們提出的啟發(fā)式多層次逐層優(yōu)化方法45就很好的支持了這個(gè)模型，并且有很好的求解效果，材料的利用率很高（廢料很少），計(jì)算速度快，結(jié)果很好。此模型和算法適應(yīng)能力強(qiáng)，求解結(jié)果好，有很強(qiáng)的普遍性和實(shí)用性。對(duì)于問(wèn)題二所建立的分類逐層分析模型較好的解決了問(wèn)題二，此方法根據(jù)具體問(wèn)題的具體特點(diǎn)進(jìn)行分析，找出針對(duì)性的解決方案，這樣我們同樣得到較好的結(jié)果，材料利用率高，計(jì)算速度快；但此模型有一定的缺陷，沒(méi)有很強(qiáng)的普遍性，為適應(yīng)某一特殊問(wèn)題都需要具體的分析計(jì)算，尋求針對(duì)性的方案。2算法

24、的評(píng)價(jià)、分析和比較一維下料問(wèn)題8910是組合優(yōu)化中的一個(gè)經(jīng)典問(wèn)題，從計(jì)算的復(fù)雜性理論上看，優(yōu)化下料問(wèn)題屬于NP難問(wèn)題，即至今還不存在多項(xiàng)式算法。NP難問(wèn)題的求解通常采用基于線性規(guī)劃的方法、分支定界法、啟發(fā)式算法、模擬退火算法、演化算法、遺傳算法等。這些方法都能在一定程度上得到最優(yōu)解或者次優(yōu)解。我們的啟發(fā)式多層次逐層優(yōu)化方法在獲得高的材料利用率的同時(shí)，在計(jì)算時(shí)間和存儲(chǔ)空間上都具有優(yōu)勢(shì)。七結(jié)果分析1對(duì)于第一問(wèn)的結(jié)果：在不考慮天數(shù)限制的情況下，我們運(yùn)用問(wèn)題一中建立的多目標(biāo)整數(shù)規(guī)劃模型及本文新建的啟發(fā)式多層次逐層優(yōu)化算法，用matlab編程（見(jiàn)附錄2程序二）可以得到結(jié)果為：根，所用的下料方式為：，廢料

25、總長(zhǎng)度為：，廢棄率為：，利用率為：，具體數(shù)據(jù)見(jiàn)附錄1表6而在考慮問(wèn)題一中天數(shù)限制的情況下，我們得到結(jié)果為：所用的原材料的數(shù)量為：根，所用的下料方式為：，廢料總長(zhǎng)度為：，廢棄率為：，利用率為：；比較兩個(gè)結(jié)果，很容易看出此模型和算法解決此問(wèn)題的高效性，在增加限制條件之后仍然可以找到與沒(méi)有限制情況近似的解答，并且原材料的利用率非常之高，可以基本保持在99%以上，因此從這個(gè)意義上說(shuō)，我們得到的解是非常優(yōu)的。2對(duì)于第二問(wèn)的結(jié)果：在不考慮天數(shù)限制的情況下，我們運(yùn)用問(wèn)題二的處理方法，可以得到結(jié)果為：，具體數(shù)據(jù)見(jiàn)附錄1表7，35塊50-30-20，193塊30-30-20-20，63塊35-35-30，158

26、塊20-20-20-20-20；余下三塊：寬度為20，30，50的各一塊。這樣我們需要原材料數(shù)為：449+1=450，下料方式數(shù)為：K=36，廢料總面積為：C=740880mm，原材料的利用率為：p=99.45%而在考慮問(wèn)題二中天數(shù)限制的情況下，我們得到結(jié)果為：需要原材料的塊數(shù)為N=451，需要的下料方式數(shù)為：K= 37，廢料總面積為：，廢棄率為：，原材料的利用率為：。比較兩個(gè)結(jié)果，同樣可以看出此模型和算法解決此問(wèn)題的高效性，在增加限制條件之后仍然可以找到與沒(méi)有限制情況近似的解答，并且原材料的利用率非常之高，可以基本保持在99%以上，因此從這個(gè)意義上說(shuō)，我們得到的解是非常優(yōu)的。八模型和算法的改進(jìn)與推廣從本文的兩個(gè)問(wèn)題的解決可看出，針對(duì)本問(wèn)題將多目標(biāo)整數(shù)規(guī)劃模型分解為多層整數(shù)線性規(guī)劃模型和啟發(fā)式多層次逐層優(yōu)化方法是十分有效的。它在大大降低計(jì)算復(fù)雜度的同時(shí)保持了很高的材料利用率和尚可接受的下料方式數(shù)。但是簡(jiǎn)化后的模型與算法在計(jì)算結(jié)果穩(wěn)定性方面未來(lái)得及分析證明，也就是說(shuō)此模型用于其它類似問(wèn)題是否還可以得到和本題兩個(gè)問(wèn)題同樣高的利用率沒(méi)有理論基礎(chǔ)。改進(jìn)的模型可以在證明或增加模型穩(wěn)定性方面作研究。前人的研究以及上述算法的評(píng)價(jià)說(shuō)明，現(xiàn)有的單一的模型與算法都有自身的缺陷，如常規(guī)的整數(shù)線性規(guī)劃求解法計(jì)算結(jié)果最優(yōu)，但是N