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种。
从条件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=0—>x9=0—>x6=0—>x4=0—>x1=0—>x2=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.41901.70879.38780.32630.61140.41380.33065.28680.3156ans =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.20003.80001.80002.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 -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)Optimization terminated.x =0.00000.000015.00000.00000.00000.00000.00007.00000.0000 ans =22.0000。