线材下料问题线性规划.docx

问题陈说
(下料问题)某工厂要做150套钢架，、。已知原料每根长10米，问应怎样下料，可使所用原料最省？
问题分析
该问题是运筹学在实际利用中比较经典“线材下料问题”，从第一部分问题陈说中能够看出，该问题通常提法是，要做N套产品，需要用规格不一样M种线材，多种规格长度分别为l1，l2，l3，...，lm，每一套产品需要不一样规格原料分别为m1，m2，m3，...，mm根，已知原材料长度为一定长度，问应该怎样下料，从而使原材料耗用最省。
所以，在处理这类问题时应分两步考虑：1、确定可行切割模式：即根据用户需要在原材料钢材上安排切割一个组合；2、确定合理切割模式：合理切割模式预料不应该大于或等于用户需要钢材最小尺寸。
对于如上第一分部提出线材下料问题，能够用运筹学中线性计划方法求解，经过建立线性计划模型来具体分析。
模型建立
建立线性计划模型时，对于约束条件这里为切割要满足用户对钢材数量最低要求，本题将对标准钢材切割（、、），从而组合成一套钢架，要求为150套等原因建立约束条件。不过，对于目标函数而言，会有这么两种情况：1、求钢材原材料总根数最少；2、求钢材原材料余料最少。在本文分析中，我们选择前者，即：求解使用钢材原材料总根数最少。
为了建立模型方便，我们把下料后余下小于最短用料钢材称为废弃钢材，，，，把10米长原材料钢材称为原钢。所以，所用原钢能够分解成三部分：1、成套利用规格钢材；2、剩下规格钢材；3、废弃钢材。经过分析计算，能够得到原钢11种下料方法以下：
表1：一条原料钢材11种切法
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
X11

4
3
2
2
1
1
1
0
0
0
0

0
0
1
0
2
0
1
3
2
1
0

0
1
1
2
1
3
2
1
2
3
5
Sum
10







9


Remain
0







1


我们设决议变量：采取第i种下料方法有xi根原钢，i=1,2,3,...,：，，。所以得到模型一：
模型一：剩下规格钢材看成废弃钢材情况
Min Z=0*x1+*x2+*x3+*x4+*x5+*x6+*x7+*x8
+1*x9+*x10+*x11+*y1+*y2+*y3 (1)
4*x1+3*x2+2*x3+2*x4+x5+x6+x7-y1=150
. x3+2*x5+x7+3*x8+2*x9+x10-y2=150
x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11-y3=150
xi>=0, yj>=0,且为整数
i=1,2,3...11,j=1,2,3 (2)
(3)
由（1）、（2）组成是求废弃钢材最少整数线性计划模型。同时，很轻易联想到另一个模型，是由（2）、（3）组成求所用原料钢材最少整数线性计划模型。
模型二：剩下规格钢材（可同原钢一样能够再利用），不妥作废弃钢材情况
Min Z=0*x1+*x2+*x3+*x4+*x5+*x6+*x7+*x8
+1*x9+*x10+*x11 (4)
4*x1+3*x2+2*x3+2*x4+x5+x6+x7>=150
. x3+2*x5+x7+3*x8+2*x9+x10>=150 (5)
x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11>=150
xi>=0, i=1,2,3...11
由（4）、（5）组成是求废弃钢材最少整数线性计划模型含有一定实际意义，尤其是当最短规格钢材长度较长时，剩下规格钢材就