下料問題資料

實用下料問題一．問題的重述“下料問題(cuttingstockproblem)”是把相同形狀的一些原材料分割加工成若干個不同規(guī)格大小的零件的問題，此類問題在工程技術(shù)和工業(yè)生產(chǎn)中有著重要和廣泛的應(yīng)用.這里的“實用下料問題”則是在某企業(yè)的實際條件限制下的單一材料的下料問題。現(xiàn)考慮單一原材料下料問題.設(shè)這種原材料呈長方形，長度為,寬度為，現(xiàn)在需要將一批這種長方形原料分割成種規(guī)格的零件,所有零件的厚度均與原材料一致，但長度和寬度分別為，其中wi＜.種零件的需求量分別為.下料時，零件的邊必須分別和原材料的邊平行。這類問題在工程上通常簡稱為二維下料問題。特別當(dāng)所有零件的寬度均與原材料相等，即，則問題稱為一維下料問題。一個好的下料方案首先應(yīng)該使原材料的利用率最大，從而減少損失，降低成本，提高經(jīng)濟效益。其次要求所采用的不同的下料方式盡可能少，即希望用最少的下料方式來完成任務(wù)。因為在生產(chǎn)中轉(zhuǎn)換下料方式需要費用和時間，既提高成本，又降低效率。此外，每種零件有各自的交貨時間，每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制。因此實用下料問題的目標(biāo)是在生產(chǎn)能力容許的條件下，以最少數(shù)量的原材料，盡可能按時完成需求任務(wù),同時下料方式數(shù)也盡量地小?，F(xiàn)在我們要為某企業(yè)考慮下面兩個問題。1．建立一維單一原材料實用下料問題的數(shù)學(xué)模型,并用此模型求解下列問題，制定出在生產(chǎn)能力容許的條件下滿足需求的下料方案,同時求出等額完成任務(wù)所需的原材料數(shù)，所采用的下料方式數(shù)和廢料總長度.單一原材料的長度為3000mm,需要完成一項有53種不同長度零件的下料任務(wù).具體數(shù)據(jù)見表一(略)，其中為需求零件的長度，為需求零件的數(shù)量.此外，在每個切割點處由于鋸縫所產(chǎn)生的損耗為5mm.據(jù)估計，該企業(yè)每天最大下料能力是100塊，要求在4天內(nèi)完成的零件標(biāo)號()為:5,7,9,12,15,18,20,25,28,36,48；要求不遲于6天完成的零件標(biāo)號()為:4,11,24,29,32,38,40,46,50。2．立二維單一原材料實用下料問題的數(shù)學(xué)模型,并用此模型求解下列問題.制定出在企業(yè)生產(chǎn)能力容許的條件下滿足需求的下料方案,同時求出等額完成任務(wù)所需的原材料塊數(shù)和所需下料方式數(shù).這個問題的單一原材料的長度為3000mm,寬度為100mm,需要完成一項有43種不同長度和寬度零件的下料任務(wù).具體數(shù)據(jù)見表二(略)，其中分別為需求零件的長度、寬度和數(shù)量.切割時的鋸縫可以是直的也可以是彎的，切割所引起的鋸縫損耗忽略不計.據(jù)估計，該企業(yè)每天最大下料能力是20塊要求在4天內(nèi)完成的零件標(biāo)號()為:3,7,9,12,15,18,20,25,28,36.二．問題的分析在生產(chǎn)實踐中，經(jīng)常會遇到如鋼材、木材等條型材的下料問題，即如何根據(jù)原材料的長度、零件的尺寸以及需求量確定出使原材料消耗最少的最優(yōu)下料方案。本題要求：在生產(chǎn)能力容許的條件下，以最少數(shù)量的原材料，盡可能按時完成需求任務(wù),同時下料方式數(shù)也盡量地小。對于一維下料問題，首先我們必須找出全部可行的下料方式；然后才能確定下料方式作為決策變量和形式約束條件的結(jié)構(gòu)系數(shù)，這樣才能建立優(yōu)化決策模型，通過計算機編程計算得到我們所需要的最優(yōu)下料方案?？紤]到這里是單一原材料下料問題，這大大減少了下料方式；但由于零件的種類有53種之多，因此下料方式仍然很多，計算量很大，所以在建立優(yōu)化模型的基礎(chǔ)上，我們需要找到比較合適的算法來解決這類實際問題。近年來，國內(nèi)外關(guān)于這方面的研究比較活躍，并涌現(xiàn)出了不少近似算法，如Gilmore與Gomory用線性規(guī)劃建立的一刀切問題的數(shù)學(xué)模型；Dyckhoff提出的線性規(guī)劃方法以及Sarker提出的動態(tài)規(guī)劃方法等。由于下料問題屬于布局問題，不同于一般的數(shù)值性優(yōu)化,近年又出現(xiàn)應(yīng)用遺傳算法來求解下料優(yōu)化問題。我們力圖建立一種實用的模型——多目標(biāo)整數(shù)規(guī)劃模型[1][2][7]，并提出一種新的優(yōu)化思想方法——啟發(fā)式多層次逐層優(yōu)化方法，解決此問題；同時與其他的求解方法進行比較。對于二維下料問題，我們采用分類層次分析法；由于原材料的長度為3000mm，寬度為100mm，而43種零件的長度最小的為155mm，這樣就不會出現(xiàn)零件的長邊在原材料的寬邊上切割的情況，也就是說零件的長邊都是順著原材料的長邊切割的?？紤]到零件的寬有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），對每一類都可按問題一的處理一維下料問題的方式找最優(yōu)的方案，然后再把他們按上述的幾種方式進行組合，以求得最優(yōu)解。三．問題的假設(shè)1．對于第一問的假設(shè)：在每個切割點處由于鋸縫所產(chǎn)生的損耗為5mm；企業(yè)每天的最大下料能力為100塊；考慮下料方式的數(shù)量對總損耗的影響，下料方式越少則原材料總損耗越小；對于剩余長度為mm的材料，可以通過細微調(diào)整鋸縫的位置鋸得長度為mm的零件；2．對于第二問的假設(shè)：切割所引起的鋸縫損耗忽略不計；切割時鋸縫可以是直的也可以是彎的，但要求轉(zhuǎn)彎為直角；企業(yè)每天最大的下料能力是20塊；原材料和零件都是長方形。四．符號說明——原材料的長度（=3000mm）——原材料的寬度（=100mm）——所用的原材料總數(shù)量——所采用的下料方式總數(shù)量——第i號零件的長度（單位：mm，）——第i號零件的寬度——第i號零件的需求量——第j種下料方式中切割第i號零件的數(shù)量——按第j種下料方式切割的原材料的數(shù)量——按第j種下料方式切割的廢料長度（mm）——第一問中要求在4天內(nèi)完成的零件號的集合——第一問中要求在不遲于6天完成的零件號的集合——第二問中要求在4天內(nèi)完成的零件號的集合五．模型的建立與求解1．對問題一的解決：此問要求：在4天內(nèi)完成的零件標(biāo)號()為:5,7,9,12,15,18,20,25,28,36,48；不遲于6天完成的零件標(biā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編程可對問題一進行計算求解（見附錄2程序四），求解的結(jié)果為：所用的原材料的數(shù)量為：根，所用的下料方式為：，廢料總長度為：，廢棄率為：，利用率為：；同時從數(shù)據(jù)中可以看出：采用這種方案，只需要4天半就可以完成問題一中要求的6天內(nèi)必須完成的零件的要求；該方案對原材料的利用率非常高，效果很好。具體下料方式數(shù)據(jù)見附錄1表12．對于問題二的解決：這是一個二維下料問題[6][11]，這里采用分類層次分析法；首先我們分析該問題的特點：由于原材料的長度為3000mm，寬度為100mm，而43種零件的長度最小的為155mm，這樣就不會出現(xiàn)零件的長邊在原材料的寬邊上切割的情況，也就是說零件的長邊都是順著原材料的長邊切割的?？紤]到零件的寬有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），對每一類都可按問題一的處理一維下料問題的方式找最優(yōu)的方案，然后再把他們按上述的幾種方式進行優(yōu)化組合，最后再對優(yōu)化組合剩余的部分進行考慮。為此我們建立分類逐層分析模型：第一層次：首先優(yōu)先考慮寬度的特征，我們把零件按寬邊的規(guī)格分為4類（20，30，35，50），對每一類都可按問題一的用于處理一維下料問題的多目標(biāo)整數(shù)規(guī)劃模型和啟發(fā)式多層次逐層優(yōu)化方法方式找最優(yōu)的方案，用mablab編程（見附錄2程序七、八）得到結(jié)果：具體下料方式數(shù)據(jù)見附錄1表2，從中我們可以得到各類寬度零件所需要的長條數(shù)為（長為3000mm，寬與零件相對應(yīng)的長條）1~4天為：，，。

4天后為：，，，。第二層次：由于寬邊若沒有填滿，對整個板材的利用影響非常大，所以我們要求在寬邊上要盡量填滿（即：盡量沒有費余的）。因此我們在上一層次得到結(jié)果的基礎(chǔ)上，我們運用上面給出的幾種最優(yōu)的組合方式進行優(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天可以實現(xiàn)恰好的組合；而4天后的部分則余下一個寬為30的長條，1~4天所用的原材料總數(shù)為：,4天后所用的原材料總數(shù)為：,其中1表示余下的一個寬為30的長條要占用一塊原材料。則所用的原材料的總數(shù)為：N=79+373=452第三層次：對上述優(yōu)化組合后，剩余的部分進行分析：即對第二層中優(yōu)化模型求出最優(yōu)解后，所剩余的部分進行研究。對于上一層次中1~4天的情形，沒有余下的長條，故可不考慮這一層；對于上一層次中4天后的情形，余下的一塊寬為30（單位：mm，下同）的長條，我們選廢料長度最長的那一塊進行討論，將這一長條再分解為零件，然后尋找其他的寬度的廢料塊，看能否用這些廢料來切割得到那個寬為30的長條上的零件：若可以做到這一點，則這塊余下的長條就被消化掉了；若不可以，則這塊長條就要占用一塊原材料。利用這種思想方法，結(jié)合附錄表2的下料數(shù)據(jù)，我們很容易找到浪費最多的那塊寬為30的長條：1105—1032切割組合；同時可以找到寬為35的有長為1200的廢料，寬為50的有長為2460的廢料，這樣我們可以1105x30和1032x30的零件用2460x50這塊廢料來切割得到。這樣我們就消化掉了余下的這個長條。因此，利用這種處理方法可以節(jié)省一塊原材料，故所用的原材料總數(shù)為:N=452-1=451。通過如上我調(diào)整后，得到數(shù)據(jù)見附錄1表3計算廢料面積為：廢棄率為：利用率為：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；同時要用到第三層次中調(diào)整后的數(shù)據(jù)表3。為了使下料方式最少，我們制定下述的下料方式搭配規(guī)則（算法）：對于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ù)最小。計算結(jié)果為：需要原材料的塊數(shù)為,下料方式為11種（見附錄1表4）對于4天后的：用同樣的方法可計算得到結(jié)果為：需要原材料的塊數(shù)為,下料方式為26種（見附錄1表5）故而總的下料方式數(shù)為K=37,下料方式為：表4加上表5；綜上第一到第四層，我們就解決了問題二：需要原材料的塊數(shù)為：，需要的下料方式數(shù)為：，廢料總面積為：，廢棄率為：，原材料的利用率為：。六．模型和算法的分析與評價1．模型的評價對于問題一所建立的多目標(biāo)整數(shù)規(guī)劃模型，很準(zhǔn)確的概括了該問題的所有約束和目標(biāo)，從理論上講是一個很嚴謹?shù)哪Ｐ?。但是對于這一模型的求解卻是非常困難的，必須尋找比較好的算法支持它，而文中我們提出的啟發(fā)式多層次逐層優(yōu)化方法[4][5]就很好的支持了這個模型，并且有很好的求解效果，材料的利用率很高（廢料很少），計算速度快，結(jié)果很好。此模型和算法適應(yīng)能力強，求解結(jié)果好，有很強的普遍性和實用性。對于問題二所建立的分類逐層分析模型較好的解決了問題二，此方法根據(jù)具體問題的具體特點進行分析，找出針對性的解決方案，這樣我們同樣得到較好的結(jié)果，材料利用率高，計算速度快；但此模型有一定的缺陷，沒有很強的普遍性，為適應(yīng)某一特殊問題都需要具體的分析計算，尋求針對性的方案。2．算法的評價、分析和比較一維下料問題[8][9][10]是組合優(yōu)化中的一個經(jīng)典問題，從計算的復(fù)雜性理論上看，優(yōu)化下料問題屬于NP難問題，即至今還不存在多項式算法。NP難問題的求解通常采用基于線性規(guī)劃的方法、分支定界法、啟發(fā)式算法、模擬退火算法、演化算法、遺傳算法等。這些方法都能在一定程度上得到最優(yōu)解或者次優(yōu)解。我們的啟發(fā)式多層次逐層優(yōu)化方法在獲得高的材料利用率的同時，在計算時間和存儲空間上都具有優(yōu)勢。七．結(jié)果分析1．對于第一問的結(jié)果：在不考慮天數(shù)限制的情況下，我們運用問題一中建立的多目標(biāo)整數(shù)規(guī)劃模型及本文新建的啟發(fā)式多層次逐層優(yōu)化算法，用matlab編程（見附錄2程序二）可以得到結(jié)果為：根，所用的下料方式為：，廢料總長度為：，廢棄率為：，利用率為：，具體數(shù)據(jù)見附錄1表6而在考慮問題一中天數(shù)限制的情況下，我們得到結(jié)果為：所用的原材料的數(shù)量為：根，所用的下料方式為：，廢料總長度為：，廢棄率為：，利用率為：；比較兩個結(jié)果，很容易看出此模型和算法解決此問題的高效性，在增加限制條件之后仍然可以找到與沒有限制情況近似的解答，并且原材料的利用率非常之高，可以基本保持在99%以上，因此從這個意義上說，我們得到的解是非常優(yōu)的。2．對于第二問的結(jié)果：在不考慮天數(shù)限制的情況下，我們運用問題二的處理方法，可以得到結(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%而在考慮問題二中天數(shù)限制的情況下，我們得到結(jié)果為：需要原材料的塊數(shù)為N=451，需要的下料方式數(shù)為：K=37，廢料總面積為：，廢棄率為：，原材料的利用率為：。比較兩個結(jié)果，同樣可以看出此模型和算法解決此問題的高效性，在增加限制條件之后仍然可以找到與沒有限制情況近似的解答，并且原材料的利用率非常之高，可以基本保持在99%以上，因此從這個意義上說，我們得到的解是非常優(yōu)的。八．模型和算法的改進與推廣從本文的兩個問題的解決可看出，針對本問題將多目標(biāo)整數(shù)規(guī)劃模型分解為多層整數(shù)線性規(guī)劃模型和啟發(fā)式多層次逐層優(yōu)化方法是十分有效的。它在大大降低計算復(fù)雜度的同時保持了很高的材料利用率和尚可接受的下料方式數(shù)。但是簡化后的模型與算法在計算結(jié)果穩(wěn)定性方面未來得及分析證明，也就是說此模型用于其它類似問題是否還可以得到和本題兩個問題同樣高的利用率沒有理論基礎(chǔ)。改進的模型可以在證明或增加模型穩(wěn)定性方面作研究。前人的研究以及上述算法的評價說明，現(xiàn)有的單一的模型與算法都有自身的缺陷，如常規(guī)的整數(shù)線性規(guī)劃求解法計算結(jié)果最優(yōu)，但是NPC問題，隨著問題規(guī)模的增加，計算量和存儲空間的會產(chǎn)生組合爆炸；神經(jīng)網(wǎng)絡(luò)法、模擬退火法以及蒙特卡羅法初始收斂速度快，特別適用于優(yōu)化目標(biāo)和約束條件復(fù)雜的問題，但是為求出精確解付出的機時卻特別大。因此接下來可以考慮將蒙特卡羅模擬與我們的方法結(jié)合，以期得到一定的穩(wěn)定性與精確度。本模型在前人研究的基礎(chǔ)上給出了含時間約束的多層整數(shù)線性規(guī)