二维实用下料问题的数学模型及较优解

《二维实用下料问题的数学模型及较优解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第36卷第7期数学的实践与认识Vol.36No.72006年7月MATHEMATICSINPRACTICEANDTHEORYJuly,2006二维实用下料问题的数学模型及较优解王娟，温阳俊(东南大学数学系.南京210096)摘要:二维下料问题是20(”年首届全国部分高校研究生数学建模竞赛s题.建立了二维下料间题的数学模型，找到了用料451块，下料方式数为37的较优解，并证明了此问题总用料的下界是“9块.关健词:二维下料模型;下料方式;下界;减少损失的比率二维实用下料问题是全国研究生数学建模竞赛的赛

2、题，详细题目见〔1].由于竞赛时间限制，还有一些问题有待解决.1数学模型对于二维下料问题，要考虑零件长、宽两个方向上的限制，因而比一维下料问题复杂得多.此问题还要求集合刀中的零件必须在第一阶段(前四天)完成，企业每天的下料能力是20块，我们的目标是尽可能节省原材料，并采用尽量少的下料方式.尸，吞.几..了>0心1min艺勿，min习创动其中，k是全部可行下料方式数，叔勿)=0权‘矛j=1j二1=0艺a;jbj=n;，‘二‘,2，一m;j二1a;j:第i号零件在第1种方式下切得的个数;气:第j种下料

3、方式耗材块数习。(艺a;,)·bj二80,j.1D二{零件iIi=3,7,9,12,15,18,20,25,28,361，即前4天必须完成的零件集合令l;‘xii,《L一令l;，i=1,2，⋯，m;j=1，⋯，无;a=1，二’，内;L,W,m:原材料的长、宽及待加工的零件规格种类二Yo‘二一合。‘，‘二1,2，⋯，m;j二1，⋯，k;‘=1，⋯，ay;l;,w;,n;:第i号零件的长、宽、加工个数11，1，潇一2+功!·‘，，:一、、〕2“，+2c'2Yt,1t:一，i2jk2}二21w1‘i,‘

4、i2‘m;1,k,_

5、阶段(前四天)M20152，M,o二152，Mso=6第二阶段(四天后)MZo1062，M,o=335，Mss=125,M,=31，其中，M211:宽20的条材使用总数，其中个别零件调整放在更宽的条材上生产.然后，将上述四种宽度的条材进行搭配，按仅有的无损失的五种方式:1.50-50,2.50一30-20,3.30-30-20-20,4.35-35-30,5.20-20-20-20-20(其下料块数记为m=⋯，ms)进行优化组合，即以原板材消耗块数最少为目标，建立整数规划模型:mmlln+m2+m

6、,+m,+ms玩+m2)Mso叭s+.2M3+tm43.Mm叭+2m,+5ms)材20Zm)Mss利用matlab编程求解容易得到第一阶段最优解为:m,二3,m2=m4=ms=0，m,=76.用同样的方法得到第二阶段最优解为m,=0,m2=31，m,==63，ms=158，m,=120.这样得到所需原材料总量为451块，下料方式数为37种的下料方案，其中第一阶段使用11种下料方式，第二阶段使用26种下料方式.2二维下料问题最优解的下界按零件总面积(没有损失)计算，完成生产任务所需原材料总量为447

7、.592二448块，因总会有一定损失，可以证明二维下料问题所需原材料总量的下界为449块.定理完成生产任务所需原材料总量至少为449块.证明要证明下界为449块，只需证明总损失大于0.408块.生产分为第一阶段(前四天)和第二阶段(四天后)，如果第一阶段所有方案的损失都大于0.408块，则显然定理成立.首先，有以下几个结论:1)不同交货期零件在两个阶段各自单独生产不能减少第一阶段已产生的损失。2)第一阶段中宽30的零件生产量大，是产生损失的主要原因.总损失不会小于在第一阶段生产宽30的零件所产生的

8、损失.3)第一阶段中宽30的零件，按零件面积(没有损失情况下)至少需要宽30的条材148.66二149条.第一阶段生产能力为80块，减去生产3号零件(13=1046,w,=50,n3=12)所需3块，剩77块，按30-30-20-20切割方式(宽度方面无损失)，可生产宽30的条材154条.3号零件切割后剩余原料(3000-1046x2)x3/3000=0.908块，如用来切割宽30的条材(按30-30-30-10方式)，可产生2.4516条.这样，第一阶段宽30的条材可生产156.