数学建模论文——下料问题.doc

3.下料问题班级：计科0901班 姓名：徐松林 学号：2009115010130摘要：本文建立模型，以最少数量的原材料以及最少的余料浪费来满足客户的需求。主要考虑到两方面的问题。钢管零售商是短时间内出售钢管，则应该以最少原材料根数为目标函数来建模模型；钢管零售商是长时间内出售钢管，则应该以最少余料浪费为目标函数。有效地使用背包问题及线性规划、非线性规划等算法，算出最优解。特别是钢管零售商是短时间内出售钢管，需要分析切割模式的种类1到4种的各个情况的整数最优解，再依次比较每个情况的最优解得出总的最优解。关键词：余料、原材料、加工费、总费用。一、 问题背景工厂在实际生产中需要对标准尺寸的原材料进行切割，以满足进一步加工的需要，成为下料问题。相关数据表明，原材料成本占总生产成本的百分比可以高达45%60%，而下料方案的优劣直接影响原材料的利用率，进而影响原材料成本。因此需要建立优化的下料方案，以最少数量的原材料以及最少的余料浪费，尽可能按时完成需求任务。二问题描述及提出某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出.从钢管厂进货时得到的原料钢管长度都是1850mm.现有一客户需要15根290mm、28根315mm、21根350mm和30根455mm的钢管.为了简化生产过程，规定所使用的切割模式的种类不能超过4种，使用频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一根原料钢管价值的2/10增加费用，依此类推，且每种切割模式下的切割次数不能太多（一根原料钢管最多生产5根产品）。此外，为了减少余料浪费，每种切割模式下的余料浪费不能超过100mm.为了使总费用最小，应如何下料？在该目标下要求考虑下面两个问题：1. 若钢管零售商是短时间内出售钢管（即每次将钢管按照顾客的要求切割后售出，多余的零件不准备下次售出），则每次应该以最少原材料根数为目标函数。2. 若钢管零售商是长时间内出售钢管（即每次将钢管按照顾客的要求切割后售出，多余的零件也留着准备下次售出），则每次应该以最少余料浪费为目标函数。三符号说明L：1850mm长的原料钢管。a:长为290mm的零件。b:长为315mm的零件。c:长为350mm的零件。d:长为455mm的零件。e:余料。p：一根原料钢管的价值。x1:按照方案1需切割的原料钢管的个数。x2:按照方案2需切割的原料钢管的个数。x3:按照方案3需切割的原料钢管的个数。x4:按照方案4需切割的原料钢管的个数。x5:按照方案5需切割的原料钢管的个数。x6:按照方案6需切割的原料钢管的个数。x7:按照方案7需切割的原料钢管的个数。x8:按照方案8需切割的原料钢管的个数。x9:按照方案9需切割的原料钢管的个数。x10:按照方案10需切割的原料钢管的个数。s:原料费。q：加工费。Q:总费用x:频率最高的一种切割方案。y:频率次之的切割方案。由x,y依此类推定义n,m。四问题分析由上问题描述可知，每根钢管L对应有很多种分割零件方案。分别如下：满足条件：1：规定所使用的切割模式的种类不能超过4种。2：每种切割模式下的切割次数不能太多（一根原料钢管最多生产5根产品）。3：为了减少余料浪费，每种切割模式下的余料浪费不能超过100mm.为了使总费用最小。满足条件2和条件3的方案有10种。 零件（mm）方案a(290mm)b(315mm)c(350mm)d(455mm)e(余料)1300270221024531202204112190510315560311100702216580131309005010010000430从条件1知，现在从10个切割方案中选出不超过4种的方案使得总费用最小。则从x1到x10中至少有6个约束变量为0。.6模型的建立与求解首要满足原料费最小值。次要满足加工费最小值。1.基于问题一：目标函数：原料费s=(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10)*p加工费q=(x/10+y*2/10+n*3/10+m*4/10)*p约束函数:3*x1+2*x2+1*x1+1*x1+1*x1=15;1*x2+2*x3+1*x4+3*x6+2*x7+1*x8=28;2*x4+3*x5+1*x6+2*x7+3*x8+5*x9=21;2*x1+2*x2+2*x3+1*x4+1*x5+1*x6+1*x7+1*x8+4*x10=30xj=0,j=1,2,3,4,5,6,7,8,9,10且xj为整数;(i)先不考虑整数的限制，即解相应的线性规划，的最优解为：x1=0.4190,x2=1.7087,x3=9.3878,x4=0.3278,x5=0.6114,x6=0.4138,x7=0.3306,x8=5.2868,x9=0.3156,x10=0.0000。(ii)因为xj当前均非整数，故不满足整数要求，则需进行分支定界法。（即每次对一个最趋近于0的点取0，在回带，使之最少有6个变量为0，依次顺序为x10=0x9=0x6=0x4=0x1=0x2=0具体操作见matlab程序）当回带到第6个值为0的变量时得当前最优解：x1=0,x2=0,x3=11.2,x4=0,x5=3.8,x6=0,x7=1.8,x8=2,x9=0,x10=0。（1）当切割模式的种类为4种此时可得最优解：x1=0,x2=0,x3=11,x4=0,x5=4,x6=0,x7=2,x8=2,x9=0,x10=0。原料费s=19p加工费q=3.3p总费用Q=22.3p（2）当切割模式的种类为3种此时可得最优解：x1=0,x2=0,x3=12,x4=0,x5=3,x6=0,x7=0,x8=4,x9=0,x10=0。原料费s=19p加工费q=3p总费用Q=22p（3）当切割模式的种类为2种此时可得最优解：x1=0,x2=0,x3=15,x4=0,x5=0,x6=0,x7=0,x8=7,x9=0,x10=0。原料费s=22p加工费q=2.9p总费用Q=24.9p（4） 当切割模式的种类为1种此时可得最优解：x1=0,x2=0,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0,x9=0,x10=0。原料费s=30p加工费q=3p总费用Q=33p综上所述：最优解：切割方案的种类为3种：按照方案3切割的原料钢管的个数为12根；按照方案5切割的原料钢管的个数为3根；按照方案8切割的原料钢管的个数为4根是，所的费用最少，为22p。2.基于问题二:目标函数：余料：e=x1*70+x2*45+x3*20+x4*90+x5*55+x6*100+x7*65+x8*30+x9*100+x10*30加工费q=(x/10+y*2/10+n*3/10+m*4/10)*p约束函数:3*x1+2*x2+1*x1+1*x1+1*x1=15;1*x2+2*x3+1*x4+3*x6+2*x7+1*x8=28;2*x4+3*x5+1*x6+2*x7+3*x8+5*x9=21;2*x1+2*x2+2*x3+1*x4+1*x5+1*x6+1*x7+1*x8+4*x10=30xj=0,j=1,2,3,4,5,6,7,8,9,10且xj为整数;此时可得最优解：x1=0,x2=0,x3=15,x4=0,x5=0,x6=0,x7=0,x8=7,x9=0,x10=0。余料e=510mm。恰各个解都满足条件。最优解：切割方案的种类为2种：按照方案3切割的原料钢管的个数为15根；按照方案8切割的原料钢管的个数为3根；按照方案8切割的原料钢管的个数为7根是，所的余料最少，为510mm。七模型评价求解结果表明，若钢管零售商是短时间内出售钢管（即每次将钢管按照顾客的要求切割后售出，多余的零件不准备下次售出），则每次应该以最少原材料根数为目标函数。若钢管零售商是长时间内出售钢管（即每次将钢管按照顾客的要求切割后售出，多余的零件也留着准备下次售出），则每次应该以最少余料浪费为目标函数。本模型在对问题深入分析地基础上，有效地使用背包问题及线性规划、非线性规划等算法，对于实用下料问题提出简明的方案优化算法，结果接近最优解。模型在算法的稳定性等方面缺乏理论分析，有效度的定义需要更加严密的证明。附录：matlab代码：问题一中：（i）f=1 1 1 1 1 1 1 1 1 1;a=-3 -2 -1 -1 -1 0 0 0 0 0;0 -1 -2 -1 0 -3 -2 -1 0 0;0 0 0 -2 -3 -1 -2 -3 -5 0;-2 -2 -2 -1 -1 -1 -1 -1 0 -4;b=-15;-28;-21;-30;ib=0 0 0 0 0 0 0 0 0 0;ub=;x=linprog(f,a,b,ib,ub) sum(x)x = 0.4190 1.7087 9.3878 0.3263 0.6114 0.4138 0.3306 5.2868 0.3156 0.0000ans = 18.8000(ii)f=1 1 1 1;a=-1 -1 0 0;-2 0 -2 -1;0 -3 -2 -3;-2 -1 -1 -1;b=-15;-28;-21;-30;ib=0 0 0 0;ub=;x=linprog(f,a,b,ib,ub) sum(x) Optimization terminated.x = 11.2000 3.8000 1.8000 2.0000ans = 18.8000问题二中：f=70 45 20 90 55 100 65 30 100 30;a=-3 -2 -1 -1 -1 0 0 0 0 0;0 -1 -2 -1 0 -3 -2 -1 0 0;0 0 0 -2 -3 -1 -2 -3 -5 0;-2 -2