資源描述：
《一維下料優(yōu)化的一種新算法》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、第44卷第3期大連理工大學學報Vol.44,No.32004年5月JournalofDalianUniversityofTechnologyMay2004文章編號:100028608(2004)0320407205一維下料優(yōu)化的一種新算法3王小東,李剛,歐宗瑛(大連理工大學CAD&CG研究所,遼寧大連116024)摘要:針對一維下料優(yōu)化問題,提出了一種基于啟發(fā)式多級序列線性優(yōu)化思想的新算法,即將下料優(yōu)化問題轉化為多級序列線性優(yōu)化問題求解.每級求解時,在當前可行的下料方式中選擇最優(yōu)的一種進行下料,不斷重復此操作,直到所有剩余的
2、坯料數(shù)目均減小至零為止.原問題的最優(yōu)解就是各個序列優(yōu)化問題所求得的最優(yōu)下料方式的總合.計算表明,與目前常用的整數(shù)線性規(guī)劃或遺傳算法相比較,該算法有結構簡明、計算速度快、節(jié)材效果好的優(yōu)點.關鍵詞:一維下料;整數(shù)規(guī)劃;遺傳算法;線性優(yōu)化中圖分類號:TH12311文獻標識碼:A0引言1.2數(shù)學模型給定m種長度的坯料l1,l2,?,lm,所需的數(shù)最大限度地節(jié)約材料,提高材料的利用率,是量分別為b1,b2,?,bm,已知原材料長度為L.實際生產中的一個指導原則.一維下料優(yōu)化問題設有n種可能下料方式,每種方式的重復次是討論從一種規(guī)格的材
3、料中,分切出各種不同長數(shù)為xj(j=1,2,3,?,n).在方式j中,第i件坯度的坯料,以使材料的利用率最高.這類優(yōu)化問料的重復次數(shù)為aij(i=1,2,3,?,m),從而可建題在型材、棒材、管材、金屬結構材料、建筑材料,立如下數(shù)學模型.甚至布料下料中廣泛存在.目前,國內外關于這目標函數(shù):minS=x1+x2+?+xn方面的研究十分活躍,并涌現(xiàn)出了不少近似算法,約束條件:如Gilmore與Gomory用線性規(guī)劃建立的一刀切a11x1+a12x2+?+a1nxn≥b1[1、2]問題的數(shù)學模型;Dyckhoff提出的線性規(guī)劃a2
4、1x1+a22x2+?+a2nxn≥b2[3、4][5]方法以及Sarker提出的動態(tài)規(guī)劃方法等.??由于下料問題屬于布局(layout)問題,不同于一am1x1+am2x2+?+amnxn≥bm般的數(shù)值性優(yōu)化,近年又出現(xiàn)應用遺傳算法來求[6]x1,x2,?,xn≥0解下料優(yōu)化問題.本文在討論對比目前常用的優(yōu)化參數(shù)變量:x1,x2,?,xn均為非負整數(shù)兩種求解方法(常規(guī)整數(shù)線性規(guī)劃方法和遺傳算1.3所有可能下料方式的計算確定法)的同時,提出一種基于啟發(fā)式多級序列線性在上述模型中,如果所取的下料方式是選擇優(yōu)化思想的新方法,并分
5、別進行算例對比.所有可能的下料方式,則所求得的最優(yōu)解就是嚴1常規(guī)整數(shù)線性規(guī)劃求解方法格全局最優(yōu)解.所有可能下料方式的確定是決策下料方案的前提,因此,人們提出了很多方法,比1.1基本思想[7]較流行的是搜索樹(searchtree)法.其原理為窮舉出所有可能的下料方式(cutting設在同一種原材料L上切割m種零件毛坯l(1)pattern),以所需原材料最少為優(yōu)化目標,以每種～l(m)的個數(shù)分別為A(1)～A(m),則l(I)與下料方式的重復次數(shù)為優(yōu)化變量,按整數(shù)線性規(guī)A(J)應該滿足下列關系式:劃原理求解.收稿日期:200
6、3207201;修回日期:2004205203.作者簡介:王小東(19792),女,碩士生;歐宗瑛3(19362),男,教授,博士生導師.408大連理工大學學報第44卷m件毛坯的長度,據(jù)此確定下料方式.程序流程框(L-min{l(1),l(2),?,l(m)})<∑l(I)A(I)I=1圖如圖1所示.零件毛坯按長度從大到小排列成≤Ll(1)～l(m).即用料小于原材料的長度,余料小于最短零圖1確定所有可能下料方式的程序流程圖Fig11Flowchartofdeterminingallpossiblecuttingpatter
7、ns例如:原材料長度L=4m,需要切割4種零將成裂變式增加,n的增大可能遇到“組合爆炸”件毛坯(m=4),長度分別為38.6、32.2、19.4和問題.6.6cm.經計算,所有可能下料方式共有611種,1.4求解方法即n=611.由一維下料優(yōu)化問題的數(shù)學模型,可以看出又如:原材料長度L=2.6m,需要切割8種下料方法是一個整數(shù)規(guī)劃(integerprogramming,零件毛坯(m=8),長度分別為40.4、36.5、32.4、IP)問題.傳統(tǒng)的求解方法是簡單地將整數(shù)變量25.3、20.8、19.4、15.6和6.6cm.經
8、計算,所有松弛,作為連續(xù)量處理,簡化為常規(guī)的線性規(guī)劃,可能下料方式共有17166種,即n=17166.采用單純形方法(simplexmethod)求解,然后對可見,隨著所切割零件毛坯的種類m的增結果進行調整.但這樣做并不能保證得到最優(yōu)大,當原材料的長度L和所切割零件的長度l(I)解,而且調
