下料问题的逐级优化方法

摘要原材料的切割问题是工业生产中的重要问题，可以直接决定一个工厂的效益大小，是一个很有实际研究价值的问题。对于一维下料问题，我们主要以整数规划为模型，讨论了钢管数最少和余料最少两种方式，但由于数据较大，后面又通过对变量变化范围的缩减，找到了较优的在大数据时替代穷举法的非线性整数规划来确定较优的几种切割方式，以得到较节省的剪裁方法。后面的成本问题可以转化为一维下料问题的加权问题。解决二维的下料问题，采用逐级优化的方法，进行下料方案的筛选。首先选用单一下料两个方向排料优选的下料策略，成品料的长在原材料的长和宽两个方向上分别排列，求出最优解；其次采用单一下料中成品料的长和宽在原材料的长、宽两个方向套裁排料优选，算出所需原材料的块数和利用率；最后按照零件需求量，进行几种零件配套优选，用新易优化板材切割软件求出最优的板材切割方法，列以原材料消耗总张数最少为目标函数的数学模型，用LINGO软件编程，求出最佳下料方案。按照原材料的利用率，筛选出最佳的下料方案为按照零件需求量，进行几种零件的配套优选下料方案关键字：下料问题整数规划逐级优化1问题重述如何更大程度的获得合理利润在当今这个以经济发展为核心的社会已经成了工厂实际生产中急需解决的问题，其中原材料利用率低则是每个工厂所关心的重点问题。因此有必要对原材料的利用方式进行讨论，找到更合理的使用方法。本问题就以生产实践中遇到的材料剪裁问题为基础，以寻找消耗原材料最少的剪裁方式为目的，并通过一维、二维的多维度分析，以及使用频率对原材料价格的影响，通过多种合理的数学模型，找到更符合实际情况的最优剪裁方式。2问题分析直接分析问题为为找到最好的几种剪裁方案，使得钢管数最少，余料尽可能少或余料最少，钢管数尽可能少，但在完成的过程中，我发现只要分配好了几种剪裁方案，用整数规划可以较容易的找到最省的下料方案，而遇到的困难是如何选择几种较优的剪裁模式，这就变成了问题的核心；而后面的几问基本上都是该问题的变形或推广，原理相似，价格问题只是切割问题中钢管数最少的加权处理，第二问是改变了衡量的单位，有长度变成了面积，可以由一维的情况推广解决3问题假设原材料在生产过程中除去剪裁方式造成的损耗外其他损耗为0，且生产后的钢管均符合要求剩余的原材料无法利用原材料中没有不合格品客户中途无退单情况运输过程中没有其它损耗原材料的增加费用只与使用频率有关，模式使用频率相同时，其产生的增加费用相同。生产的总费用只与钢管数有关，本问题不考虑人工工资、厂房用地、管理

费等其他费用根据问题的需要，我们会在后面的具体解决过程中在提出一些必要的假设4模型符号解释符号表示意义L1规格为2100cmX1650cm的原材料的长W1规格为2100cmX1650cm的原材料的宽L2规格为2000cmX1500cm的原材料的长W2规格为2000cmX1500cm的原材料的宽Xi成品零件的长，i=1,2,……，26yi成品零件的宽，i=1,2,……，26ni所需成品料的块数，i=1,2,……，26n所需原材料的块数S11规格为2100cmX1650cm的原材料的面积S12规格为2000cmX1500cm的原材料的面积Lx.第i个成品料的七在L1方向上能被排下的个数Li第i个成品料的）,在L1方向上能被排下的个数.第i个成品料的七在w1方向上能被排下的个数Wy1i第i个成品料的）,在w1方向上能被排下的个数1只有一种原材料的利用率Si第i个成品料的面积ai,j组成切割矩阵的各个数值bi,j第j种切割方式下七在L方向套裁切割被排下的个数dk,j第j种切割方式下y,■在L方向套裁切割被排下的个数

符号表示意义5j第j种切割方式下长度方向的余料ASj第j种切割方式下余料面积Nj第j种切割方式使用的次数Xn第n种切割方法5模型的建立与求解5.1.1.剪裁方式有很多，经过思考讨论，以余料较少作为评判标准，较优的剪裁方法有如下几种：模式3米钢管数模式3米钢管数2.5米钢管数1202033124105106017021.3米钢管数1.8米钢管数余料010.2000.5000120.1210.6300.3200.4127127设模式1用钢管数x，模式2用钢管数x模式7用钢管数x，且x、X…x均为整数，后面不再强调1124567根据题意可得方程组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)运用整数规划，用LINGGO软件得到的结果为用于方案3的钢管数为80，用于方案4的钢管数为240，余料为24米，这显然不很符合实际情况，所以我们考虑

用所需钢管数最少来衡量。1271271124567若按原模式进行运算，则得到如下结果:方程组为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)用钢管数最少则得到结果为方案4用钢管20根，方案5用钢管60根，方案7用钢管50根，总共用钢管130根，余料为58。这组数据的余料过大，使得我们进行了新剪裁模式的探索我认为应该根据钢管的利用率重新规划模式，为了增大钢管的利用率，应该使得3米、2.5米、1.8米、1.3米的钢管数尽可能符合80：100：240：100，即4：5：12：5,但也要兼顾余料问题，经研究讨论用以下几种模式剪钢管：模式3米钢管数模式3米钢管数2.5米钢管数1202033124105016007001.3米钢管数1.8米钢管数余料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)再次运用整数规划，用Lingo软件得到的结果为，方案3用45跟钢管，方案4

用35根钢管，方案5用10根钢管，方案7用35根钢管；总共用125根钢管，

余料为11.5米；可以看出新模式比以前的模式无论从钢管数还是余料方面都有

很大进步，接下来的进一步优化，我们考虑将多余的钢管数也算入到余料中，即增加假设：剩余的钢管也无法得到有效利用，则得到的方程组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)得到的结果为方案三使用钢管61根，方案4使用钢管48根，方案5使用钢管2根，方案7使用钢管32根；总共使用钢管143根，总的浪费量为11.4米，但在新的余料衡量方式下，仍使得钢管数增加了不少。因此，我们下一步则研究如何选取方案使得这些数据尽可能达到最优。对于大规模的问题，用模型的约束条件界定合理模式。rx+rx+rx+rx>80TOC\o"1-5"\h\z111122133144rx+rx+rx+rx>100211222233244rx+rx+rx+rx>240311322333344rx+rx+rx+rx>100考虑到余料应该不超过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根据题目需求，钢管数的下界「*80+1.8*100+技240+2&100]=1238前面得到的130作为钢管数的上界，因为方式并未固定，所以不妨假设x>x>x>x将数据代入Lingo软件运算，可以得到最优的方案：模式3米2.5米1.3米1.8米余料112000200600.2310120.1400230方案一使用钢管数51，方案2使用钢管数31，方案3使用钢管数29，方案4使用钢管数14,总钢管数为125,余料9.1米，可以看到很大程度上提高了钢管的利用率，该模型应该较好的完成了这个问题5.1.2利用已经完成的第一问得模型，我们只需对钢管数根据价格加权即可解决该问题，得到方程组为rx+rx+rx+rx>80TOC\o"1-5"\h\z111122133144rx+rx+rx+rx>100211222233244rx+rx+rx+rx>240311322333344rx+rx+rx+rx>100411422433444考虑到余料应该不超过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的下界假设每种方式使用频率相同则不产生增加费用，W的下界为123,若按照已有的其中一种切割方法，不妨是第一问中第一种方法（表1），可得W的上界为146；在软件中运算后的结果为模式3米2.5米1.3米1.8米余料112000210210.6300230400600.2其中方案一用钢管数52根，方案2用钢管数28根，方案3用钢管数24根，方案5用钢管数21根，总费用W=135.85.25.2.1单一下料两个方向排料优选对于一张原材料上仅裁一种零件（即单一下料）的切割方式，每一种零件可以排出两种单一切割方式。第一种，成品料的长在原材料长的方向上排列的下料方式；第二种，成品料的长在原材料宽的方向上排列的下料方式。（1）、单一下料两个方向排料优选数学模型如下：

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单一下料在长、宽两个方向套裁排料优选成品料在原材料L和W方向上套裁下料，x和y可以套裁。但这时应注意，

11ii在切割玻璃时，每切一刀将玻璃板一分为二。数学模型与单一下料两个方向排料选优一样5.2.3按照零件需求量，进行几种成品料配套优选按照零件需求量，进行玻璃套裁下料方式的数学模型表示为: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且为整数；(9)上述9个方程组成了玻璃下料问题的数学模型。我们的目的是要求出满足上述9个方程的各种切割方式的张数七。通过“新易优化板材切割”软件，排出玻璃板材的最优切割方法，共有72种切割方案，每一种切割方案如附录中表1.0所示。建立线性规划方程组：minN=Uxj=i'顼寸ax>b(i=1,2,…,m)x.>0(1=1,2,..•,n)整数求得的利用率为：殆Sxnii门=J=1x100%=95.03%1Sxn按照零件需求量，进行几种成品料配套优选结果如下：通过用LINGO软件，对上述线性方程进行编程求解，求得在原材料只有6.模型的评价与推广评价：对数据少的问题可以很快准确解决，对于数据大的问题也可以在较高的精度内得到解决，而且一维二维均采用逐级优化的思想，每个模型的精确度一目了然，但仍然没有解决计算量大的问题改进：可以考虑用遗传算法以及模拟退火法进行更准确的运算，以及运用一些近似算法推广：可以在空间维度上进行推广，推广到N维空间的应用，也可以更广泛的推广应用到任何规则形状的二维剪裁问题，也可将不规则的图形通过微分方法近似看为多种规则图形后利用此方法得到求解附录：问题一余料模型用LINGO软件实现的程序：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问题一钢管数最少用LINGO软件实现的程序(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问题一钢管数最少用LINGO软件实现的程序(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问题一钢管数最少用LINGO软件实现的程序(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