下料問(wèn)題資料

實(shí)用下料問(wèn)題一．問(wèn)題的重述“下料問(wèn)題(cuttingstockproblem)”是把相同形狀的一些原材料分割加工成若干個(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)所有零件的寬度均與原材料相等，即，則問(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í)求出等額完成任務(wù)所需的原材料數(shù)，所采用的下料方式數(shù)和廢料總長(zhǎng)度.單一原材料的長(zhǎng)度為3000mm,需要完成一項(xiàng)有53種不同長(zhǎng)度零件的下料任務(wù).具體數(shù)據(jù)見表一(略)，其中為需求零件的長(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)能力容許的條件下滿足需求的下料方案,同時(shí)求出等額完成任務(wù)所需的原材料塊數(shù)和所需下料方式數(shù).這個(gè)問(wèn)題的單一原材料的長(zhǎng)度為3000mm,寬度為100mm,需要完成一項(xiàng)有43種不同長(zhǎng)度和寬度零件的下料任務(wù).具體數(shù)據(jù)見表二(略)，其中分別為需求零件的長(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)下料方案。本題要求：在生產(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ī)劃建立的一刀切問(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][2][7]，并提出一種新的優(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（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è)：在每個(gè)切割點(diǎn)處由于鋸縫所產(chǎn)生的損耗為5mm；企業(yè)每天的最大下料能力為100塊；考慮下料方式的數(shù)量對(duì)總損耗的影響，下料方式越少則原材料總損耗越??；對(duì)于剩余長(zhǎng)度為mm的材料，可以通過(guò)細(xì)微調(diào)整鋸縫的位置鋸得長(zhǎng)度為mm的零件；2．對(duì)于第二問(wèn)的假設(shè)：切割所引起的鋸縫損耗忽略不計(jì)；切割時(shí)鋸縫可以是直的也可以是彎的，但要求轉(zhuǎn)彎為直角；企業(yè)每天最大的下料能力是20塊；原材料和零件都是長(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天完成的零件號(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)能力容許的條件下滿足新一層的下料方式和重復(fù)次數(shù)；Step5：各層最優(yōu)下料方式及其重復(fù)次數(shù)的集合即為啟發(fā)式多層次逐層優(yōu)化方法的最終結(jié)果，即和的值；算法流程如圖1所示：（圖1：算法流程）用matlab編程可對(duì)問(wèn)題一進(jìn)行計(jì)算求解（見附錄2程序四），求解的結(jié)果為：所用的原材料的數(shù)量為：根，所用的下料方式為：，廢料總長(zhǎng)度為：，廢棄率為：，利用率為：；同時(shí)從數(shù)據(jù)中可以看出：采用這種方案，只需要4天半就可以完成問(wèn)題一中要求的6天內(nèi)必須完成的零件的要求；該方案對(duì)原材料的利用率非常高，效果很好。具體下料方式數(shù)據(jù)見附錄1表12．對(duì)于問(wèn)題二的解決：這是一個(gè)二維下料問(wèn)題[6][11]，這里采用分類層次分析法；首先我們分析該問(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)的方案，然后再把他們按上述的幾種方式進(jìn)行優(yōu)化組合，最后再對(duì)優(yōu)化組合剩余的部分進(jìn)行考慮。為此我們建立分類逐層分析模型：第一層次：首先優(yōu)先考慮寬度的特征，我們把零件按寬邊的規(guī)格分為4類（20，30，35，50），對(duì)每一類都可按問(wèn)題一的用于處理一維下料問(wèn)題的多目標(biāo)整數(shù)規(guī)劃模型和啟發(fā)式多層次逐層優(yōu)化方法方式找最優(yōu)的方案，用mablab編程（見附錄2程序七、八）得到結(jié)果：具體下料方式數(shù)據(jù)見附錄1表2，從中我們可以得到各類寬度零件所需要的長(zhǎng)條數(shù)為（長(zhǎng)為3000mm，寬與零件相對(duì)應(yīng)的長(zhǎng)條）1~4天為：，，。

4天后為：，，，。第二層次：由于寬邊若沒(méi)有填滿，對(duì)整個(gè)板材的利用影響非常大，所以我們要求在寬邊上要盡量填滿（即：盡量沒(méi)有費(fèi)余的）。因此我們?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編程（見附錄2程序十）可以很快求解出此整數(shù)線性規(guī)劃的最優(yōu)解為：1~4天為：，，，，，4天后為：，，，，，，可知：1~4天可以實(shí)現(xiàn)恰好的組合；而4天后的部分則余下一個(gè)寬為30的長(zhǎng)條，1~4天所用的原材料總數(shù)為：,4天后所用的原材料總數(shù)為：,其中1表示余下的一個(gè)寬為30的長(zhǎng)條要占用一塊原材料。則所用的原材料的總數(shù)為：N=79+373=452第三層次：對(duì)上述優(yōu)化組合后，剩余的部分進(jìn)行分析：即對(duì)第二層中優(yōu)化模型求出最優(yōu)解后，所剩余的部分進(jìn)行研究。對(duì)于上一層次中1~4天的情形，沒(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)條：1105—1032切割組合；同時(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ù)見附錄1表3計(jì)算廢料面積為：廢棄率為：利用率為：4）第四層次：在此基礎(chǔ)上（即上面模型所求得的各組合最優(yōu)數(shù)量），再考慮怎樣使下料方式盡量少。從第二層次得到：1~4天的：3塊50-50，76塊30-30-20-20；4天后的：31塊50-30-20，120塊30-30-20-20，63塊35-35-30，158塊20-20-20-20-20；同時(shí)要用到第三層次中調(diào)整后的數(shù)據(jù)表3。為了使下料方式最少，我們制定下述的下料方式搭配規(guī)則（算法）：對(duì)于1~4天的：a)首先考慮組合50-50：可知這里只有一種下料方式：1~4天寬50（1）--1~4天寬50（1），數(shù)量為3（注：1~4天寬50（i）：表示1~4天中寬為50的下料方式中的第i種下料方式）；b)再考慮組合30-30-20-20：令表示1~4天寬為20的第i種下料的數(shù)量（i=1,…7），表示1~4天寬為30的第k種下料的數(shù)量(k=1,…10)，再令表示在此組合下第j種下料方式是：1~4天寬20（1）--…--1~4天寬20（7）--1~4天寬30（1）--…--1~4天寬30（10）；表示第j種下料方式采用的次數(shù)。則我們可建立整數(shù)規(guī)劃模型：（注意：同上文約定）（6） 求解此整數(shù)規(guī)劃模型可以得到最優(yōu)的下料方式，使得下料方式數(shù)最小。計(jì)算結(jié)果為：需要原材料的塊數(shù)為,下料方式為11種（見附錄1表4）對(duì)于4天后的：用同樣的方法可計(jì)算得到結(jié)果為：需要原材料的塊數(shù)為,下料方式為26種（見附錄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)確的概括了該問(wèn)題的所有約束和目標(biāo)，從理論上講是一個(gè)很嚴(yán)謹(jǐn)?shù)哪Ｐ?。但是?duì)于這一模型的求解卻是非常困難的，必須尋找比較好的算法支持它，而文中我們提出的啟發(fā)式多層次逐層優(yōu)化方法[4][5]就很好的支持了這個(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．算法的評(píng)價(jià)、分析和比較一維下料問(wèn)題[8][9][10]是組合優(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編程（見附錄2程序二）可以得到結(jié)果為：根，所用的下料方式為：，廢料總長(zhǎng)度為：，廢棄率為：，利用率為：，具體數(shù)據(jù)見附錄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ù)見附錄1表7，35塊50-30-20，193塊30-30-20-20，63塊35-35-30，158塊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)，但是NPC問(wèn)題，隨著問(wèn)題規(guī)模的增加，計(jì)算量和存儲(chǔ)空間的會(huì)產(chǎn)生組合爆炸；神經(jīng)網(wǎng)絡(luò)法、模擬退火法以及蒙特卡羅法初始收斂速度快，特別適用于優(yōu)化目標(biāo)和約束條件復(fù)雜的問(wèn)題，但是為求出精確解付出的機(jī)時(shí)卻特別大。因此接下來(lái)可以考慮將蒙特卡羅模擬與我們的方法結(jié)合，以期得到一定的穩(wěn)定性與精確度。本模型在前人研究的基礎(chǔ)上給出了含時(shí)間約束的多層整數(shù)線性規(guī)