资源描述：
《一维下料优化的一种新算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第44卷第3期大连理工大学学报Vol.44,No.32004年5月JournalofDalianUniversityofTechnologyMay2004文章编号:100028608(2004)0320407205一维下料优化的一种新算法3王小东,李刚,欧宗瑛(大连理工大学CAD&CG研究所,辽宁大连116024)摘要:针对一维下料优化问题,提出了一种基于启发式多级序列线性优化思想的新算法,即将下料优化问题转化为多级序列线性优化问题求解.每级求解时,在当前可行的下料方式中选择最优的一种进行下料,不断重复此操作,直到所有剩余的
2、坯料数目均减小至零为止.原问题的最优解就是各个序列优化问题所求得的最优下料方式的总合.计算表明,与目前常用的整数线性规划或遗传算法相比较,该算法有结构简明、计算速度快、节材效果好的优点.关键词:一维下料;整数规划;遗传算法;线性优化中图分类号:TH12311文献标识码:A0引言1.2数学模型给定m种长度的坯料l1,l2,⋯,lm,所需的数最大限度地节约材料,提高材料的利用率,是量分别为b1,b2,⋯,bm,已知原材料长度为L.实际生产中的一个指导原则.一维下料优化问题设有n种可能下料方式,每种方式的重复次是讨论从一种规格的材
3、料中,分切出各种不同长数为xj(j=1,2,3,⋯,n).在方式j中,第i件坯度的坯料,以使材料的利用率最高.这类优化问料的重复次数为aij(i=1,2,3,⋯,m),从而可建题在型材、棒材、管材、金属结构材料、建筑材料,立如下数学模型.甚至布料下料中广泛存在.目前,国内外关于这目标函数:minS=x1+x2+⋯+xn方面的研究十分活跃,并涌现出了不少近似算法,约束条件:如Gilmore与Gomory用线性规划建立的一刀切a11x1+a12x2+⋯+a1nxn≥b1[1、2]问题的数学模型;Dyckhoff提出的线性规划a2
4、1x1+a22x2+⋯+a2nxn≥b2[3、4][5]方法以及Sarker提出的动态规划方法等.⋯⋯由于下料问题属于布局(layout)问题,不同于一am1x1+am2x2+⋯+amnxn≥bm般的数值性优化,近年又出现应用遗传算法来求[6]x1,x2,⋯,xn≥0解下料优化问题.本文在讨论对比目前常用的优化参数变量:x1,x2,⋯,xn均为非负整数两种求解方法(常规整数线性规划方法和遗传算1.3所有可能下料方式的计算确定法)的同时,提出一种基于启发式多级序列线性在上述模型中,如果所取的下料方式是选择优化思想的新方法,并分
5、别进行算例对比.所有可能的下料方式,则所求得的最优解就是严1常规整数线性规划求解方法格全局最优解.所有可能下料方式的确定是决策下料方案的前提,因此,人们提出了很多方法,比1.1基本思想[7]较流行的是搜索树(searchtree)法.其原理为穷举出所有可能的下料方式(cutting设在同一种原材料L上切割m种零件毛坯l(1)pattern),以所需原材料最少为优化目标,以每种～l(m)的个数分别为A(1)～A(m),则l(I)与下料方式的重复次数为优化变量,按整数线性规A(J)应该满足下列关系式:划原理求解.收稿日期:200
6、3207201;修回日期:2004205203.作者简介:王小东(19792),女,硕士生;欧宗瑛3(19362),男,教授,博士生导师.408大连理工大学学报第44卷m件毛坯的长度,据此确定下料方式.程序流程框(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.由一维下料优化问题的数学模型,可以看出又如:原材料长度L=2.6m,需要切割8种下料方法是一个整数规划(integerprogramming,零件毛坯(m=8),长度分别为40.4、36.5、32.4、IP)问题.传统的求解方法是简单地将整数变量25.3、20.8、19.4、15.6和6.6cm.经
8、计算,所有松弛,作为连续量处理,简化为常规的线性规划,可能下料方式共有17166种,即n=17166.采用单纯形方法(simplexmethod)求解,然后对可见,随着所切割零件毛坯的种类m的增结果进行调整.但这样做并不能保证得到最优大,当原材料的长度L和所切割零件的长度l(I)解,而且调
