资源描述：
《二维实用下料问题的数学模型及较优解 (1)new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第36卷第7期数学的实践与认识Vol136No172006年7月MATHEMATICSINPRACTICEANDTHEORYJuly,2006二维实用下料问题的数学模型及较优解王娟,温阳俊(东南大学数学系,南京210096)摘要:二维下料问题是2004年首届全国部分高校研究生数学建模竞赛B题.建立了二维下料问题的数学模型,找到了用料451块,下料方式数为37的较优解,并证明了此问题总用料的下界是449块.关键词:二维下料模型;下料方式;下界;减少损失的比率二维实用下料问题是全国研究生数学建模竞赛的赛题,详细题目见[1].由于竞赛时间限制,还有一些问题有待解决.1数
2、学模型对于二维下料问题,要考虑零件长、宽两个方向上的限制,因而比一维下料问题复杂得多.此问题还要求集合D中的零件必须在第一阶段(前四天)完成,企业每天的下料能力是20块,我们的目标是尽可能节省原材料,并采用尽量少的下料方式.kk1,bj>0min∑bj,min∑δ(bj)其中,k是全部可行下料方式数,δ(bj)=j=1j=10,bj=0s.t.k∑aijbj=ni,i=1,2,⋯,m;j=1aij:第i号零件在第j种方式下切得的个数;bj:第j种下料方式耗材块数k∑δ∑aij·bj≤80,j=1i∈DD={零件i
3、i=3,7,9,12,15,18,20,25,28
4、,36},即前4天必须完成的零件集合11li≤xijt≤L-li,i=1,2,⋯,m;j=1,⋯,k;t=1,⋯,aij;22L,W,m:原材料的长、宽及待加工的零件规格种类11wi≤yijt≤W-wi,i=1,2,⋯,m;j=1,⋯,k;t=1,⋯,aij;22li,wi,ni:第i号零件的长、宽、加工个数1111xijk-xijk≥li+li或yijk-yijk≥wi+wi,11222122112221221≤i1≤i2≤m;1≤k1≤aij;1≤k2≤aij;i1-i2+k1-k2≠012xijk,yijk:第i号零件在第j种下料方式下切得第k块零件中心的横
5、坐标、纵坐标根据本题的特点,待加工的零件的宽只集中在50mm,30mm,35mm,20mm四种规格上,可将二维问题转化为一维问题,对四种宽度且长3000的条材,分别用一维下料问题的方法寻©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net206数学的实践与认识36卷求四种宽度条材在一维情况下的最优方案.根据一维下料问题求解的方法,解多目标整数规划,可以得到两个阶段所使用的条材(具体方案见第3节)分别为:第一阶段(前四天):M20=1
6、52,M30=152,M50=6第二阶段(四天后):M20=1062,M30=335,M35=125,M50=31,其中,M20:宽20的条材使用总数,其中个别零件调整放在更宽的条材上生产.然后,将上述四种宽度的条材进行搭配,按仅有的无损失的五种方式:1.50250,2.50230220,3.30230220220,4.35235230,5.20220220220220(其下料块数记为m1,⋯,m5)进行优化组合,即以原板材消耗块数最少为目标,建立整数规划模型:minm1+m2+m3+m4+m52m1+m2≥M50m2+2m3+m4≥M30s.t.m2+2m3+5
7、m5≥M202m4≥M35利用matlab编程求解容易得到第一阶段最优解为:m1=3,m2=m4=m5=0,m3=76.用同样的方法得到第二阶段最优解为m1=0,m2=31,m4=63,m5=158,m3=120.这样得到所需原材料总量为451块,下料方式数为37种的下料方案,其中第一阶段使用11种下料方式,第二阶段使用26种下料方式.2二维下料问题最优解的下界按零件总面积(没有损失)计算,完成生产任务所需原材料总量为4471592≈448块,因总会有一定损失,可以证明二维下料问题所需原材料总量的下界为449块.定理完成生产任务所需原材料总量至少为449块.证明要
8、证明下界为449块,只需证明总损失大于01408块.生产分为第一阶段(前四天)和第二阶段(四天后),如果第一阶段所有方案的损失都大于01408块,则显然定理成立.首先,有以下几个结论:1)不同交货期零件在两个阶段各自单独生产不能减少第一阶段已产生的损失.2)第一阶段中宽30的零件生产量大,是产生损失的主要原因.总损失不会小于在第一阶段生产宽30的零件所产生的损失.3)第一阶段中宽30的零件,按零件面积(没有损失情况下)至少需要宽30的条材148166≈149条.第一阶段生产能力为80块,减去生产3号零件(l3=1046,w3=50,n3=12)所需3块,剩77块,
9、按3023
