實(shí)用下料問題

-.z.實(shí)用下料問題一．問題的重述"下料問題(cuttingstockproblem)〞是把一樣形狀的一些原材料分割加工成假設(shè)干個不同規(guī)格大小的零件的問題，此類問題在工程技術(shù)和工業(yè)生產(chǎn)中有著重要和廣泛的應(yīng)用.這里的"實(shí)用下料問題〞則是在*企業(yè)的實(shí)際條件限制下的單一材料的下料問題?，F(xiàn)考慮單一原材料下料問題.設(shè)這種原材料呈長方形，長度為,寬度為，現(xiàn)在需要將一批這種長方形原料分割成種規(guī)格的零件,所有零件的厚度均與原材料一致，但長度和寬度分別為，其中wi＜.種零件的需求量分別為.下料時，零件的邊必須分別和原材料的邊平行。這類問題在工程上通常簡稱為二維下料問題。特別當(dāng)所有零件的寬度均與原材料相等，即，則問題稱為一維下料問題。一個好的下料方案首先應(yīng)該使原材料的利用率最大，從而減少損失，降低本錢，提高經(jīng)濟(jì)效益。其次要求所采用的不同的下料方式盡可能少，即希望用最少的下料方式來完成任務(wù)。因?yàn)樵谏a(chǎn)中轉(zhuǎn)換下料方式需要費(fèi)用和時間，既提高本錢，又降低效率。此外，每種零件有各自的交貨時間，每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制。因此實(shí)用下料問題的目標(biāo)是在生產(chǎn)能力容許的條件下，以最少數(shù)量的原材料，盡可能按時完成需求任務(wù),同時下料方式數(shù)也盡量地小?，F(xiàn)在我們要為*企業(yè)考慮下面兩個問題。1．建立一維單一原材料實(shí)用下料問題的數(shù)學(xué)模型,并用此模型求解以下問題，制定出在生產(chǎn)能力容許的條件下滿足需求的下料方案,同時求出等額完成任務(wù)所需的原材料數(shù)，所采用的下料方式數(shù)和廢料總長度.單一原材料的長度為3000mm,需要完成一項(xiàng)有53種不同長度零件的下料任務(wù).具體數(shù)據(jù)見表一(略)，其中為需求零件的長度，為需求零件的數(shù)量.此外，在每個切割點(diǎn)處由于鋸縫所產(chǎn)生的損耗為5mm.據(jù)估計(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í)用下料問題的數(shù)學(xué)模型,并用此模型求解以下問題.制定出在企業(yè)生產(chǎn)能力容許的條件下滿足需求的下料方案,同時求出等額完成任務(wù)所需的原材料塊數(shù)和所需下料方式數(shù).這個問題的單一原材料的長度為3000mm,寬度為100mm,需要完成一項(xiàng)有43種不同長度和寬度零件的下料任務(wù).具體數(shù)據(jù)見表二(略)，其中分別為需求零件的長度、寬度和數(shù)量.切割時的鋸縫可以是直的也可以是彎的，切割所引起的鋸縫損耗忽略不計(jì).據(jù)估計(jì)，該企業(yè)每天最大下料能力是20塊要求在4天內(nèi)完成的零件標(biāo)號()為:3,7,9,12,15,18,20,25,28,36.二．問題的分析在生產(chǎn)實(shí)踐中，經(jīng)常會遇到如鋼材、木材等條型材的下料問題，即如何根據(jù)原材料的長度、零件的尺寸以及需求量確定出使原材料消耗最少的最優(yōu)下料方案。此題要求：在生產(chǎn)能力容許的條件下，以最少數(shù)量的原材料，盡可能按時完成需求任務(wù),同時下料方式數(shù)也盡量地小。對于一維下料問題，首先我們必須找出全部可行的下料方式；然后才能確定下料方式作為決策變量和形式約束條件的構(gòu)造系數(shù)，這樣才能建立優(yōu)化決策模型，通過計(jì)算機(jī)編程計(jì)算得到我們所需要的最優(yōu)下料方案?？紤]到這里是單一原材料下料問題，這大大減少了下料方式；但由于零件的種類有53種之多，因此下料方式仍然很多，計(jì)算量很大，所以在建立優(yōu)化模型的根底上，我們需要找到比擬適宜的算法來解決這類實(shí)際問題。近年來，國內(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)化問題。我們力圖建立一種實(shí)用的模型——多目標(biāo)整數(shù)規(guī)劃模型[1][2][7]，并提出一種新的優(yōu)化思想方法——啟發(fā)式多層次逐層優(yōu)化方法，解決此問題；同時與其他的求解方法進(jìn)展比擬。對于二維下料問題，我們采用分類層次分析法；由于原材料的長度為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)的方案，然后再把他們按上述的幾種方式進(jìn)展組合，以求得最優(yōu)解。三．問題的假設(shè)1．對于第一問的假設(shè)：在每個切割點(diǎn)處由于鋸縫所產(chǎn)生的損耗為5mm；企業(yè)每天的最大下料能力為100塊；考慮下料方式的數(shù)量對總損耗的影響，下料方式越少則原材料總損耗越??；對于剩余長度為mm的材料，可以通過細(xì)微調(diào)整鋸縫的位置鋸得長度為mm的零件；2．對于第二問的假設(shè)：切割所引起的鋸縫損耗忽略不計(jì)；切割時鋸縫可以是直的也可以是彎的，但要求轉(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)能力容許的條件下滿足需求的下料方案，同時要求等額完成任務(wù)，我們的目標(biāo)是要盡可能節(jié)省材料，盡可能用少的下料方式。為此我們建立多目標(biāo)整數(shù)規(guī)劃模型：〔首先我們約定：〕,〔1〕注：1.我們有：假設(shè)采用了第j種下料方式，則為大于0的整數(shù)，因此；假設(shè)沒有采用第j種下料方式，則為0，如上定義可得：，這樣即表示了所用的下料方式數(shù)量；2．約束中第一條是：考慮了鋸縫時，原材料長度L對下料方式的限制，即對于任意一種下料方式，所得到的零件總長度與鋸縫總長度之和要小于等于L；3．約束中第二條是：考慮了鋸縫時，對于每一種下料方式的廢料長度要小于零件的最小長度；4．約束中第三條是：為了滿足題中要求的等額完成任務(wù)的限制條件；5．約束中第四條是：為了滿足在企業(yè)每天生產(chǎn)能力是100塊時，要求在4天內(nèi)完成零件集合的條件，其中表示第j種下料方式中所切割的第i種零件數(shù)占這種下料方式中所切割的零件集合中零件數(shù)的權(quán)數(shù)，因此表示了完成零件集合所用的原材料數(shù)，又由于在4天內(nèi)要完成零件集合，故上述所算出的所用的原材料數(shù)要小于等于，注意假設(shè)，即表示第j種下料方式中沒有切割到零件集合中的零件，因此：，這樣按照注釋1中的約定，可知正好表示：這種下料方式不產(chǎn)生集合中的零件，故而這條約束很完善；6．約束中第五條和第四條的解釋類似；約束中第六條和第七條表示和要取整數(shù)。對于廢料的度量：由于存在鋸縫為5mm，對任何一種可行的下料方式，則其滿足條件，所以如果單純的用來度量此種下料方式的廢料是不對的，這可能取到負(fù)值；實(shí)際上，又由于對問題一有假設(shè)4，我們可以知道：對所有滿足的下料方式來說，廢料都為0；故而我們可以得到廢料的度量方式：經(jīng)過數(shù)學(xué)處理，得到：因此廢料總量為：廢棄率定義為：利用率定義為：對于此模型〔即〔1〕式〕的求解比擬困難，我們需要首先分解此模型，然后創(chuàng)立適應(yīng)的優(yōu)化算法解決此問題：表第j種下料方式當(dāng)前最優(yōu)的下料方式的模型：多層整數(shù)線性規(guī)劃模型a)當(dāng)時，求最優(yōu)的一種下料方式的數(shù)學(xué)模型為：〔2〕其中表一種下料方式，為努力程度，定義為*種下料方式中含有集合中零件的個數(shù)，從中我們可以看出越大零件集合完成得越快；b)當(dāng)且時，求最優(yōu)的一種下料方式的數(shù)學(xué)模型為：〔3〕為努力程度，類似的定義和理解；c)當(dāng)且時，求最優(yōu)的一種下料方式的數(shù)學(xué)模型為：〔4〕這三個模型都是整數(shù)線性規(guī)劃問題，可以用分支定界法求解，亦可用lingo直接編程〔見附錄程2序九〕，可以很快計(jì)算得結(jié)果；也可以用matlab7.0[3]編程算得。針對模型，我們創(chuàng)立適應(yīng)性的算法——啟發(fā)式多層次逐層優(yōu)化方法，此方法的根本思想是：在每層求解時，對于上層剩余的未完成的各零件數(shù)目，利用上面三個子模型可以在當(dāng)前可行的下料方式中選擇最優(yōu)的一種下料方式進(jìn)展下料，并盡可能的重復(fù)使用此種下料方式〔這是為了使得下料方式盡可能少〕；然后對剩余的未完成的各零件重新優(yōu)化選取新的最優(yōu)的一種下料方式，不斷反復(fù)上面的操作，直到所有剩余的未完成的各零件數(shù)目都減少到0為止。這樣原問題的最優(yōu)解就是各個層次優(yōu)化問題所求得的最優(yōu)下料方式的總和。3〕啟發(fā)式多層次逐層優(yōu)化方法的計(jì)算方法將上述當(dāng)前最優(yōu)下料方式的三種模型的計(jì)算求解作為啟發(fā)式多層次逐層優(yōu)化方法計(jì)算的子程序,在每級求解中，對于相應(yīng)的條件重復(fù)調(diào)用相應(yīng)的子程序。完整的求解過程如下：Step1：初始給定了未完成的各零件的數(shù)目，4天要完成的零件集合，6天要完成的零件集合；在上一層〔j層〕得到的未完成的各零件的數(shù)目根底上，判斷和是否成立，然后依判定條件調(diào)用1〕中相應(yīng)的當(dāng)前最優(yōu)下料計(jì)算子程序,求解得到最優(yōu)下料方式，并以此作為這一級的下料方式；Step2：計(jì)算此種下料方式的重復(fù)次數(shù),即用此種下料方式切割的原材料L的根數(shù)；Step3：計(jì)算去掉根按這種下料方式切割后,余下的未完成的各種零件的數(shù)量：；Step4：將上一步得到的作為新一層優(yōu)化計(jì)算的給定值,并記,令，如果則優(yōu)化計(jì)算完畢；否則轉(zhuǎn)Step1重新判斷并調(diào)用當(dāng)前最優(yōu)下料方式計(jì)算子程序,求得新一層的下料方式和重復(fù)次數(shù)；Step5：各層最優(yōu)下料方式及其重復(fù)次數(shù)的集合即為啟發(fā)式多層次逐層優(yōu)化方法的最終結(jié)果，即和的值；算法流程如圖1所示：〔圖1：算法流程〕用matlab編程可對問題一進(jìn)展計(jì)算求解〔見附錄2程序四〕，求解的結(jié)果為：所用的原材料的數(shù)量為：根，所用的下料方式為：，廢料總長度為：，廢棄率為：，利用率為：；同時從數(shù)據(jù)中可以看出：采用這種方案，只需要4天半就可以完成問題一中要求的6天內(nèi)必須完成的零件的要求；該方案對原材料的利用率非常高，效果很好。具體下料方式數(shù)據(jù)見附錄1表12．對于問題二的解決：這是一個二維下料問題[6][11]，這里采用分類層次分析法；首先我們分析該問題的特點(diǎn)：由于原材料的長度為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)的方案，然后再把他們按上述的幾種方式進(jìn)展優(yōu)化組合，最后再對優(yōu)化組合剩余的局部進(jìn)展考慮。為此我們建立分類逐層分析模型：第一層次：首先優(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天后為：，，，。第二層次：由于寬邊假設(shè)沒有填滿，對整個板材的利用影響非常大，所以我們要求在寬邊上要盡量填滿〔即：盡量沒有費(fèi)余的〕。因此我們在上一層次得到結(jié)果的根底上，我們運(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天后的局部則余下一個寬為30的長條，1~4天所用的原材料總數(shù)為：,4天后所用的原材料總數(shù)為：,其中1表示余下的一個寬為30的長條要占用一塊原材料。則所用的原材料的總數(shù)為：N=79+373=452第三層次：對上述優(yōu)化組合后，剩余的局部進(jìn)展分析：即對第二層中優(yōu)化模型求出最優(yōu)解后，所剩余的局部進(jìn)展研究。對于上一層次中1~4天的情形，沒有余下的長條，故可不考慮這一層；對于上一層次中4天后的情形，余下的一塊寬為30〔單位：mm，下同〕的長條，我們選廢料長度最長的那一塊進(jìn)展討論，將這一長條再分解為零件，然后尋找其他的寬度的廢料塊，看能否用這些廢料來切割得到那個寬為30的長條上的零件：假設(shè)可以做到這一點(diǎn)，則這塊余下的長條就被消化掉了；假設(shè)不可以，則這塊長條就要占用一塊原材料。利用這種思想方法，結(jié)合附錄表2的下料數(shù)據(jù)，我們很容易找到浪費(fèi)最多的那塊寬為30的長條：1105—1032切割組合；同時可以找到寬為35的有長為1200的廢料，寬為50的有長為2460的廢料，這樣我們可以1105*30和1032*30的零件用2460*50這塊廢料來切割得到。這樣我們就消化掉了余下的這個長條。因此，利用這種處理方法可以節(jié)省一塊原材料，故所用的原材料總數(shù)為:N=452-1=451。通過如上我調(diào)整后，得到數(shù)據(jù)見附錄1表3計(jì)算廢料面積為：廢棄率為：利用率為：4〕第四層次：在此根底上〔即上面模型所求得的各組合最優(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ù)最小。計(jì)算結(jié)果為：需要原材料的塊數(shù)為,下料方式為11種〔見附錄1表4〕對于4天后的：用同樣的方法可計(jì)算得到結(jié)果為：需要原材料的塊數(shù)為,下料方式為26種〔見附錄1表5〕故而總的下料方式數(shù)為K=37,下料方式為：表4加上表5；綜上第一到第四層，我們就解決了問題二：需要原材料的塊數(shù)為：，需要的下料方式數(shù)為：，廢料總面積為：，廢棄率為：，原材料的利用率為：。六．模型和算法的分析與評價(jià)1．模型的評價(jià)對于問題一所建立的多目標(biāo)整數(shù)規(guī)劃模型，很準(zhǔn)確的概括了該問題的所有約束和目標(biāo)，從理論上講是一個很嚴(yán)謹(jǐn)?shù)哪Ｐ?。但是對于這一模型的求解卻是非常困難的，必須尋找比擬好的算法支持它，而文中我們提出的啟發(fā)式多層次逐層優(yōu)化方法[4][5]就很好的支持了這個模型，并且有很好的求解效果，材料的利用率很高〔廢料很少〕，計(jì)算速度快，結(jié)果很好。此模型和算法適應(yīng)能力強(qiáng)，求解結(jié)果好，有很強(qiáng)的普遍性和實(shí)用性。對于問題二所建立的分類逐層分析模型較好的解決了問題二，此方法根據(jù)具體問題的具體特點(diǎn)進(jìn)展分析，找出針對性的解決方案，這樣我們同樣得到較好的結(jié)果，材料利用率高，計(jì)算速度快；但此模型有一定的缺陷，沒有很強(qiáng)的普遍性，為適應(yīng)*一特殊問題都需要具體的分析計(jì)算，尋求針對性的方案。2．算法的評價(jià)、分析和比擬一維下料問題[8][9][10]是組合優(yōu)化中的一個經(jīng)典問題，從計(jì)算的復(fù)雜性理論上看，優(yōu)化下料問題屬于NP難問題，即至今還不存在多項(xiàng)式算法。NP難問題的求解通常采用基于線性規(guī)劃的方法、分支定界法、啟發(fā)式算法、模擬退火算法、演化算法、遺傳算法等。這些方法都能在一定程度上得到最優(yōu)解或者次優(yōu)解。我們的啟發(fā)式多層次逐層優(yōu)化方法在獲得高的材料利用率的同時，在計(jì)算時間和存儲空間上都具有優(yōu)勢。七．結(jié)果分析1．對于第一問的結(jié)果：在不考慮天數(shù)限制的情況下，我們運(yùn)用問題一中建立的多目標(biāo)整數(shù)規(guī)劃模型及本文新建的啟發(fā)式多層次逐層優(yōu)化算法，用matlab編程〔見附錄2程序二〕可以得到結(jié)果為：根，所用的下料方式為：，廢料總長度為：，廢棄率為：，利用率為：，具體數(shù)據(jù)見附錄1表6而在考慮問題一中天數(shù)限制的情況下，我們得到結(jié)果為：所用的原材料的數(shù)量為：根，所用的下料方式為：，廢料總長度為：，廢棄率為：，利用率為：；比擬兩個結(jié)果，很容易看出此模型和算法解決此問題的高效性，在增加限制條件之后仍然可以找到與沒有限制情況近似的解答，并且原材料的利用率非常之高，可以根本保持在99%以上，因此從這個意義上說，我們得到的解是非常優(yōu)的。2．對于第二問的結(jié)果：在不考慮天數(shù)限制的情況下，我們運(yù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%而在考慮問題二中天數(shù)限制的情況下，我們得到結(jié)果為：需要原材料的塊數(shù)為N=451，需要的下料方式數(shù)為：K=37，廢料總面積為：，廢棄率為：，原材料的利用率為：。比擬兩個結(jié)果，同樣可以看出此模型和算法解決此問題的高效性，在增加限制條件之后仍然可以找到與沒有限制情況近似的解答，并且原材料的利用率非常之高，可以根本保持在99%以上，因此從這個意義上說，我們得到的解是非常優(yōu)的。八．模型和算法的改良與推廣從本文的兩個問題的解決可看出，針對本問題將多目標(biāo)整數(shù)規(guī)劃模型分解為多層整數(shù)線性規(guī)劃模型和啟發(fā)式多層次逐層優(yōu)化方法是十分有效的。它在大大降低計(jì)算復(fù)雜度的同時保持了很高的材料利用率和尚可承受的下料方式數(shù)。但是簡化后的模型與算法在計(jì)算結(jié)果穩(wěn)定性方面未來得及分析證明，也就是說此模型用于其它類似問題是否還可以得到和此題兩個問題同樣高的利用率沒有理論根底。改良的模型可以在證明或增加模型穩(wěn)定性方面作研究。前人的研究以及上述算法的評價(jià)說明，現(xiàn)有的單一的模型與算法都有自身的缺