下料問題的逐級優(yōu)化方法

摘要原材料的切割問題是工業(yè)生產(chǎn)中的重要問題，可以直接決定一個工廠的效益大小，是一個很有實際研究價值的問題。對于一維下料問題，我們主要以整數(shù)規(guī)劃為模型，討論了鋼管數(shù)最少和余料最少兩種方式，但由于數(shù)據(jù)較大，后面又通過對變量變化范圍的縮減，找到了較優(yōu)的在大數(shù)據(jù)時替代窮舉法的非線性整數(shù)規(guī)劃來確定較優(yōu)的幾種切割方式，以得到較節(jié)省的剪裁方法。后面的成本問題可以轉(zhuǎn)化為一維下料問題的加權(quán)問題。解決二維的下料問題，采用逐級優(yōu)化的方法，進行下料方案的篩選。首先選用單一下料兩個方向排料優(yōu)選的下料策略，成品料的長在原材料的長和寬兩個方向上分別排列，求出最優(yōu)解；其次采用單一下料中成品料的長和寬在原材料的長、寬兩個方向套裁排料優(yōu)選，算出所需原材料的塊數(shù)和利用率；最后按照零件需求量，進行幾種零件配套優(yōu)選，用新易優(yōu)化板材切割軟件求出最優(yōu)的板材切割方法，列以原材料消耗總張數(shù)最少為目標函數(shù)的數(shù)學(xué)模型，用LINGO軟件編程，求出最佳下料方案。按照原材料的利用率，篩選出最佳的下料方案為按照零件需求量，進行幾種零件的配套優(yōu)選下料方案關(guān)鍵字：下料問題整數(shù)規(guī)劃逐級優(yōu)化1問題重述如何更大程度的獲得合理利潤在當(dāng)今這個以經(jīng)濟發(fā)展為核心的社會已經(jīng)成了工廠實際生產(chǎn)中急需解決的問題，其中原材料利用率低則是每個工廠所關(guān)心的重點問題。因此有必要對原材料的利用方式進行討論，找到更合理的使用方法。本問題就以生產(chǎn)實踐中遇到的材料剪裁問題為基礎(chǔ)，以尋找消耗原材料最少的剪裁方式為目的，并通過一維、二維的多維度分析，以及使用頻率對原材料價格的影響，通過多種合理的數(shù)學(xué)模型，找到更符合實際情況的最優(yōu)剪裁方式。2問題分析直接分析問題為為找到最好的幾種剪裁方案，使得鋼管數(shù)最少，余料盡可能少或余料最少，鋼管數(shù)盡可能少，但在完成的過程中，我發(fā)現(xiàn)只要分配好了幾種剪裁方案，用整數(shù)規(guī)劃可以較容易的找到最省的下料方案，而遇到的困難是如何選擇幾種較優(yōu)的剪裁模式，這就變成了問題的核心；而后面的幾問基本上都是該問題的變形或推廣，原理相似，價格問題只是切割問題中鋼管數(shù)最少的加權(quán)處理，第二問是改變了衡量的單位，有長度變成了面積，可以由一維的情況推廣解決3問題假設(shè)原材料在生產(chǎn)過程中除去剪裁方式造成的損耗外其他損耗為0，且生產(chǎn)后的鋼管均符合要求剩余的原材料無法利用原材料中沒有不合格品客戶中途無退單情況運輸過程中沒有其它損耗原材料的增加費用只與使用頻率有關(guān)，模式使用頻率相同時，其產(chǎn)生的增加費用相同。生產(chǎn)的總費用只與鋼管數(shù)有關(guān)，本問題不考慮人工工資、廠房用地、管理

費等其他費用根據(jù)問題的需要，我們會在后面的具體解決過程中在提出一些必要的假設(shè)4模型符號解釋符號表示意義L1規(guī)格為2100cmX1650cm的原材料的長W1規(guī)格為2100cmX1650cm的原材料的寬L2規(guī)格為2000cmX1500cm的原材料的長W2規(guī)格為2000cmX1500cm的原材料的寬Xi成品零件的長，i=1,2,……，26yi成品零件的寬，i=1,2,……，26ni所需成品料的塊數(shù)，i=1,2,……，26n所需原材料的塊數(shù)S11規(guī)格為2100cmX1650cm的原材料的面積S12規(guī)格為2000cmX1500cm的原材料的面積Lx.第i個成品料的七在L1方向上能被排下的個數(shù)Li第i個成品料的）,在L1方向上能被排下的個數(shù).第i個成品料的七在w1方向上能被排下的個數(shù)Wy1i第i個成品料的）,在w1方向上能被排下的個數(shù)1只有一種原材料的利用率Si第i個成品料的面積ai,j組成切割矩陣的各個數(shù)值bi,j第j種切割方式下七在L方向套裁切割被排下的個數(shù)dk,j第j種切割方式下y,■在L方向套裁切割被排下的個數(shù)

符號表示意義5j第j種切割方式下長度方向的余料ASj第j種切割方式下余料面積Nj第j種切割方式使用的次數(shù)Xn第n種切割方法5模型的建立與求解5.1.1.剪裁方式有很多，經(jīng)過思考討論，以余料較少作為評判標準，較優(yōu)的剪裁方法有如下幾種：模式3米鋼管數(shù)模式3米鋼管數(shù)2.5米鋼管數(shù)1202033124105106017021.3米鋼管數(shù)1.8米鋼管數(shù)余料010.2000.5000120.1210.6300.3200.4127127設(shè)模式1用鋼管數(shù)x，模式2用鋼管數(shù)x模式7用鋼管數(shù)x，且x、X…x均為整數(shù)，后面不再強調(diào)1124567根據(jù)題意可得方程組minz=0.2x+0.5x+0.1x+0.6x+0.3x+0.4x2x+x+x+x>803x+2x+x+2x>100Stx+2x+3x+2x>240x+2x+x>100x>0(i=1,2...7)運用整數(shù)規(guī)劃，用LINGGO軟件得到的結(jié)果為用于方案3的鋼管數(shù)為80，用于方案4的鋼管數(shù)為240，余料為24米，這顯然不很符合實際情況，所以我們考慮

用所需鋼管數(shù)最少來衡量。1271271124567若按原模式進行運算，則得到如下結(jié)果:方程組為minz-x+x+x+x+x+x+x212345672x+x+x+x>803x+2x+x+2x>100Stx+2x+3x+2x>240x+2x+x>100x>0(i-1,2...7)用鋼管數(shù)最少則得到結(jié)果為方案4用鋼管20根，方案5用鋼管60根，方案7用鋼管50根，總共用鋼管130根，余料為58。這組數(shù)據(jù)的余料過大，使得我們進行了新剪裁模式的探索我認為應(yīng)該根據(jù)鋼管的利用率重新規(guī)劃模式，為了增大鋼管的利用率，應(yīng)該使得3米、2.5米、1.8米、1.3米的鋼管數(shù)盡可能符合80：100：240：100，即4：5：12：5,但也要兼顧余料問題，經(jīng)研究討論用以下幾種模式剪鋼管：模式3米鋼管數(shù)模式3米鋼管數(shù)2.5米鋼管數(shù)1202033124105016007001.3米鋼管數(shù)1.8米鋼管數(shù)余料010.2000.5000120.1030.1320.5600.2方程組為minz-x+x+x+x+x+x+x212345672x+x+x>803x+2x+x>100Stx+3x+6x>240467x+2x+3x+2x>1001456x>0(i-1,2...7)再次運用整數(shù)規(guī)劃，用Lingo軟件得到的結(jié)果為，方案3用45跟鋼管，方案4

用35根鋼管，方案5用10根鋼管，方案7用35根鋼管；總共用125根鋼管，

余料為11.5米；可以看出新模式比以前的模式無論從鋼管數(shù)還是余料方面都有

很大進步，接下來的進一步優(yōu)化，我們考慮將多余的鋼管數(shù)也算入到余料中，即增加假設(shè)：剩余的鋼管也無法得到有效利用，則得到的方程組minz=0.2x+0.5x+0.1x+0.6x+0.3x+0.4x+3(2x+x+x-80)+2.5(3x+2x+x-100)1124567134235+1.3(x+3x+6x-240)+1.8(x+2x+3x+2x-100)4571456x+x+x>80x+2x+x>100Stx+3x+6x>240x+2x+3x+2x>100x.>0(i=1,2...7)得到的結(jié)果為方案三使用鋼管61根，方案4使用鋼管48根，方案5使用鋼管2根，方案7使用鋼管32根；總共使用鋼管143根，總的浪費量為11.4米，但在新的余料衡量方式下，仍使得鋼管數(shù)增加了不少。因此，我們下一步則研究如何選取方案使得這些數(shù)據(jù)盡可能達到最優(yōu)。對于大規(guī)模的問題，用模型的約束條件界定合理模式。rx+rx+rx+rx>80TOC\o"1-5"\h\z111122133144rx+rx+rx+rx>100211222233244rx+rx+rx+rx>240311322333344rx+rx+rx+rx>100考慮到余料應(yīng)該不超過14米，嘉2433444\o"CurrentDocument"7<3r+2.5r+1.3r+1.8r<87<3r“+2.5z?1+1.3廣+1.8：<87<3r+2.5r+1.3r+1.8r<87<3r+2.5r+1.3r+1.8r<8根據(jù)題目需求，鋼管數(shù)的下界「*80+1.8*100+技240+2&100]=1238前面得到的130作為鋼管數(shù)的上界，因為方式并未固定，所以不妨假設(shè)x>x>x>x將數(shù)據(jù)代入Lingo軟件運算，可以得到最優(yōu)的方案：模式3米2.5米1.3米1.8米余料112000200600.2310120.1400230方案一使用鋼管數(shù)51，方案2使用鋼管數(shù)31，方案3使用鋼管數(shù)29，方案4使用鋼管數(shù)14,總鋼管數(shù)為125,余料9.1米，可以看到很大程度上提高了鋼管的利用率，該模型應(yīng)該較好的完成了這個問題5.1.2利用已經(jīng)完成的第一問得模型，我們只需對鋼管數(shù)根據(jù)價格加權(quán)即可解決該問題，得到方程組為rx+rx+rx+rx>80TOC\o"1-5"\h\z111122133144rx+rx+rx+rx>100211222233244rx+rx+rx+rx>240311322333344rx+rx+rx+rx>100411422433444考慮到余料應(yīng)該不超過1米，所以7<3r+2.5r+1.3r+1.8r<87<3盧+2.5r22+1.3r32+1.8r42<87<3盧+2.5定+1.3舟+1.8/<8rc11CL21TC31TC41c7<3r+2.5r+1.3r+1.8r<8價格W的下界假設(shè)每種方式使用頻率相同則不產(chǎn)生增加費用，W的下界為123,若按照已有的其中一種切割方法，不妨是第一問中第一種方法（表1），可得W的上界為146；在軟件中運算后的結(jié)果為模式3米2.5米1.3米1.8米余料112000210210.6300230400600.2其中方案一用鋼管數(shù)52根，方案2用鋼管數(shù)28根，方案3用鋼管數(shù)24根，方案5用鋼管數(shù)21根，總費用W=135.85.25.2.1單一下料兩個方向排料優(yōu)選對于一張原材料上僅裁一種零件（即單一下料）的切割方式，每一種零件可以排出兩種單一切割方式。第一種，成品料的長在原材料長的方向上排列的下料方式；第二種，成品料的長在原材料寬的方向上排列的下料方式。（1）、單一下料兩個方向排料優(yōu)選數(shù)學(xué)模型如下：

Lx=INT(L/x),i=1,2,……，26；iiiiLy=INT(L/y),i=1,2,……，26；iiii*.=INT(Wyx.),i=1,2,……，26；Wiy■=INT(Wyy,),i=1,2,……，26；S]]=L]XW]；"6Sxn門i=i=i''x100%；ii5.2.2單一下料在長、寬兩個方向套裁排料優(yōu)選成品料在原材料L和W方向上套裁下料，x和y可以套裁。但這時應(yīng)注意，

11ii在切割玻璃時，每切一刀將玻璃板一分為二。數(shù)學(xué)模型與單一下料兩個方向排料選優(yōu)一樣5.2.3按照零件需求量，進行幾種成品料配套優(yōu)選按照零件需求量，進行玻璃套裁下料方式的數(shù)學(xué)模型表示為:x點dyXi,jik,jk-m/5j2°；(2))；(1)5jv^-且\V七_i=1,2,,m；k=m+1,m+2,,2m；(3)k-m。i如果b〉0則b=0；如果b=0則b>0；(4)a=bxWy,a=d.xWx；⑸ASj=LxW-^axxx點dyXi,jik,jk-m/5j2°；(2)ASj11i,jiii=1minS=丈NAS；⑺j=ij=iN>0且為整數(shù)；(9)上述9個方程組成了玻璃下料問題的數(shù)學(xué)模型。我們的目的是要求出滿足上述9個方程的各種切割方式的張數(shù)七。通過“新易優(yōu)化板材切割”軟件，排出玻璃板材的最優(yōu)切割方法，共有72種切割方案，每一種切割方案如附錄中表1.0所示。建立線性規(guī)劃方程組：minN=Uxj=i'頊寸ax>b(i=1,2,…,m)x.>0(1=1,2,..?,n)整數(shù)求得的利用率為：殆Sxnii門=J=1x100%=95.03%1Sxn按照零件需求量，進行幾種成品料配套優(yōu)選結(jié)果如下：通過用LINGO軟件，對上述線性方程進行編程求解，求得在原材料只有6.模型的評價與推廣評價：對數(shù)據(jù)少的問題可以很快準確解決，對于數(shù)據(jù)大的問題也可以在較高的精度內(nèi)得到解決，而且一維二維均采用逐級優(yōu)化的思想，每個模型的精確度一目了然，但仍然沒有解決計算量大的問題改進：可以考慮用遺傳算法以及模擬退火法進行更準確的運算，以及運用一些近似算法推廣：可以在空間維度上進行推廣，推廣到N維空間的應(yīng)用，也可以更廣泛的推廣應(yīng)用到任何規(guī)則形狀的二維剪裁問題，也可將不規(guī)則的圖形通過微分方法近似看為多種規(guī)則圖形后利用此方法得到求解附錄：問題一余料模型用LINGO軟件實現(xiàn)的程序：model:sets:model/1..7/:x;endsetsmin=z1;z1=0.2*x(1)+0.5*x(2)+0*x(3)+0.1*x(4)+0.6*x(5)+0.3*x(6)+0.4*x(7);z2=x(1)+x(2)+x(3)+x(4)+x(5)+x(6)+x(7);2*x(1)+0*x(2)+x(3)+x(4)+x(5)>=80;3*x(2)+2*x(3)+x(6)+2*x(7)>=100;x(4)+2*x(5)+3*x(6)+2*x(7)>=240;x(1)+2*x(4)+x(5)>=100;@for(model(i):@gin(x(i)));End問題一鋼管數(shù)最少用LINGO軟件實現(xiàn)的程序(1)：model:sets:model/1..7/:x;endsetsmin=z2;z1=0.2*x(1)+0.5*x(2)+0*x(3)+0.1*x(4)+0.6*x(5)+0.3*x(6)+0.4*x(7);z2=x(1)+x(2)+x(3)+x(4)+x(5)+x(6)+x(7);2*x(1)+0*x(2)+x(3)+x(4)+x(5)>=80;3*x(2)+2*x(3)+x(6)+2*x(7)>=100;x(4)+2*x(5)+3*x(6)+2*x(7)>=240;x(1)+2*x(4)+x(5)>=100;@for(model(i):@gin(x(i)));End問題一鋼管數(shù)最少用LINGO軟件實現(xiàn)的程序(2)：model:sets:model/1..7/:x;endsetsmin=z2;z1=0.2*x(1)+0.5*x(2)+0*x(3)+0.1*x(4)+0.1*x(5)+0.5*x(6)+0.2*x(7);z2=x(1)+x(2)+x(3)+x(4)+x(5)+x(6)+x(7);2*x(1)+0*x(2)+x(3)+x(4)>=80;3*x(2)+2*x(3)+x(5)>=100;x(4)+3*x(6)+6*x(7)>=240;x(1)+2*x(4)+3*x(5)+2*x(6)>=100;@for(model(i):@gin(x(i)));End問題一鋼管數(shù)最少用LINGO軟件實現(xiàn)的程序(3)：model:sets:model/1..7/:x;endsetsmin=z3+z1;z1=0.2*x(1)+0.5*x(2)+0*x(3)+0.1*x(4)+0.1*x(5)+0.5*x(6)+0.2*x(7);z2=x(1)+x(2)+x(3)+x(4)+x(5)+x(6)+x(7);z3=3*(2*x(1)+x(3)+x(4)-80)+2.5*(3*x(2)+2*x(3)+x(5)-100)+1.3*(x(4)+3*x(5)+6*x(7)-240)+1.8*(x(1)+2*(4)+3*x(5)+2*x(6)-100);2*x(1)+x(3)+x(4)>=80;3*x(2)+2*x(3)+x(5)>=100;x(4)+3*x(6)+6*x(7)>=240;x(1)+2*x(4)+3*x(5)+2