线材下料问题-线性规划

1、一、问题陈述（下料问题）某工厂要做150套钢架，每套钢架分别需要长度为米、米和米的圆钢各一套。已知原料每根长 10米，问应如何下料，可使所用原料最省二、问题分析该问题是运筹学在实际运用中比较经典的“线材下料问题”，从第一部分问题陈述中可以看出，该问题的一般提法是，要做N套产品，需要用规格不同的 M种线材，各种规格的长度分别为丨1,丨2, |3，. ,1m每一套产品需要不同规格的原料分别为m,m，m，.，mm根，已知原材料的长度为一定的长度，问应该如何下料，从而使原材料的耗用最省。因此，在解决此类问题时应分两步考虑： 1、确定可行的切割模式：即按照客户需 要在原材料钢材上安排切割的一种组合； 2

2、、确定合理的切割模式：合理的切割模式的 预料不应该大于或等于客户需要的钢材的最小尺寸。对于如上第一分部提出的线材下料问题，可以用运筹学中线性规划的方法求解，通过建立线性规划模型来具体分析。三、模型建立建立线性规划模型时，对于约束条件这里为切割要满足客户对钢材数量的最低要求，本题将对标准钢材的切割（米、米、米），从而组合成一套钢架，要求为150套等因素建立约束条件。但是，对于目标函数而言，会有这样两种情况：1、求的钢材原材料总根数最少；2、求的钢材原材料余料最少。在本文的分析中，我们选择前者，即： 求解使用的钢材原材料总根数最少。为了建立模型方便，我们把下料后余下的小于最短用料的钢材称为废弃钢材

3、，把下料得到的长为，的钢材称为规格钢材，把 10米长的原材料钢材称为原钢。因此，所用 的原钢可以分解成三部分：1、成套利用的规格钢材；2、剩余的规格钢材；3、废弃钢材。通过分析计算，可以得到原钢的11种下料方式如下：表1 :一条原料钢材的11种切法X1XaX3X4X5X6X7X8X9X10X11432211100000010201321001121321235Sum109Remai n01我们设决策变量：采取第i种下料方式的有Xi根原钢，i=1,2,3,11.另外设置辅助变量：剩余米的规格钢材为y1根，剩余的米规格钢材为y2根，剩余的米规格钢材为y3根。因此得到模型一：模型一：剩余的规格钢材当

4、作废弃钢材的情况Min Z=0*x1+*x2+*x3+*x4+*x5+*x6+*x7+*x8+1*x9+*x10+*x11+*y1+*y2+*y34*x1+3*x2+2*x3+2*x4+x5+x6+x7-y1=150x3+2*x5+x7+3*x8+2*x9+x10-y2=150x2+x：3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11-y3=150Xi>=0, y j>=0,且为整数i=1,2,3.11,j=1,2,311MinZXii 1由（1 ）、（ 2）组成的是求废弃钢材最少的整数线性规划模型。同时，很容易联想到 另一个模型，是由（2）、（3）组

5、成的求所用原料钢材最少的整数线性规划模型。模型二：剩余的规格钢材（可同原钢一样可以再利用），不当作废弃钢材的情况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>=150Xi>=0, i=1,2,3.11由（4）、（ 5）组成的是求废弃钢材最少的整数线性规划模型具有一定的实际意义，特别是当最

6、短的规格钢材长度较长时，剩余的规格钢材就可以再次被利用。 在此，我们应该注意到，由（3）、（ 5）组成的整数线性规划模型就是模型一。由于在建立模型一和模型二的时候，考虑了剩余规格钢材的不同处理情况，使这个问题变得清晰了，所得到的模型也比较全面，基本没有漏洞和缺陷，并且比较容易在这些基础上修改或添加一些其它的约束条件（比如：各种规格钢材下料成套时的不同比例等等），所以，我们建立的线材下料问题的模型是可行的。基于以上的分析，我们选择（3 ）、（ 5）组合而成的模型和（4）、（ 5）组合而成的 模型进行具体求解，从而求出组合出150套圆钢所需要的最少原料钢材。求解模型：11Mi nZxii 1（ 3

7、）'4*x1+3*x2+2*x3+2*x4+x5+x6+x7>=150x3+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,311此模型是设定最小使用原料钢材的条数为目标值进行求解。Min Z=0*x1+*x2+*x3+*x4+*x5+*x6+*x7+*x8+1*x9+*x10+*x114*x1+3*x2+2*x3+2*x4+x5+x6+x7>=150.x3+2*x5+x；+3*x8+2*x9+x10>=150(5)

8、x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11>=150Xi >=0, i=1,2,3.11此模型时设定最小废弃钢材为目标值进行求解。四、方法选择指导思路：线性规划求解思路选择方法：Excel规划求解使用工具：Excel工具五、求解过程1、框架建立2、模式调整3、计算原料钢材使用及剩余钢材4、设置目标函数及变量I、以模型(3)、(5)组合而成的求解模型设定的目标值。说明：目标函数单元格D9即为我们所求的最少使用原料钢材条数。其具体在excel中的操作为 D9=C12+D12+E12+F12+G12+H12+I12+J12+K12+L12+M1

9、2.n、以模型（4）、（ 5）组合而成的求解模型设定的目标值。说明：目标函数单元格 D9即为我们所求最少剩余的废弃钢材。其具体在excel中的操作为：D9=C7*B12+D7*C12+E7*D12+F7*E12+G7*F12+H7*G12+I7*H12+J7*I12+K7*J12+L7*K12+M7*L125、设置约束条件说明：约束条件单元格 C15 C16 C17分别为规格钢材、所求的最少使用条数。其中:C15 =C12*4+D12*3+E12*2+F12*2+G12+H12+I12;C16 =E12+G12*2+I12+J12*3+K12*2+L12;C17 =D12+E12+F12*2+

10、G12+H12*3+I12*2+J12+K12*2+L12*3+M12*5;6、利用规划求解工具Excel :工具-规划求解-依次输入目标单元格、可变单元格、约束条件进行求解。其中，点击规划求解参数选项框右边的选项按钮,在弹出的选项框中选中采用线性模型和假定非负。求解结果如下图：I、以模型(3)、(5)组合而成的求解模型求解结果。从上表可以直接得出：最小原料钢材使用条数为108条。但实际的使用情况为条,多切割出来的条（152-150）*）米）。II、以模型（4）、（5）组合而成的求解模型设定的目标值。从上表可以直接看得，最小剩余废弃钢材为25米。但实际的剩余废弃钢材为30米(152-150 )

11、 *+25 )。六、答案分析由上图可知，按照模式1切38条原料钢材，按照模式8切原料钢材50条，按照模式11切原料钢材20条，从而可以得到：米规格钢材152（ 38*4 ）条，米规格钢材 150（50*3 ）条，米规格钢材150（ 50*1+20*20 ）条。同时，可以从得出来的数据算出剩余的废弃钢材为30米，其中包含多切割出的2条米规格钢材共5米，按照模式8切割的剩余废弃钢材15米（*50）以及按照模式11切割的剩余废弃钢材 10米（*20 ）。通过分别设置目标值为最小使用原料钢材的使用条数和最小剩余废弃钢材的计算,我们得出相同的结果，即切割米规格钢材152条，米规格钢材150条以及米规格钢

12、材150条，同时剩余废弃钢材为 30米，使用原料钢材108条。但是，对不同目标值设定就一定是会得出相同的结果吗在这里,我们引出另一种情况来进行对比分析。如题：某工厂要做100套钢架，每套钢架需要长度分别为米,米和米的圆钢各一根。已知原料每根长米，问应该如何下料，可以使所用原料最省在这我们利用之前的分析，分别设定最小使用原料条数和最小剩余材料为目标值进X1X2X3X4X5米12010米00221米31203余料0行模型建立，如下:设定最小使用原料条数为目标值模型:Min Z=x1+x2+x3+x4+x5<x1+2*x2+x4>=1002*x3+2*x4+x5>=100W3*x1

13、+x2+2*x3+3*x5>=100xi>=0(i=1,2,.5)设定最小余料为目标值模型:Min Z=0*x1+*x2+*x3+*x4+*x5fXl+2*x2+x4>=1002*x3+2*x4+x5>=100 3*x1+x2+2*x3+3*x5>=100xi>=0(i=1,2,.5)对这两个模型进行求解，有：最小余料为目标值模型解:最小原料使用条数为目标值模型解:由以上两种模型解答可知： 在以最小余料为目标值进行求解的时候， 得出的原料使 用条数为150条，而以最小原料使用条数为目标值进行求解的时候，得出的原料使用的条数为90条。综合两道题目的比较，可知，两种类型的模型设定是会得到不同的解答。因此，在不保证未来多余规格材料是否有用的时候，这就可能会造成原料更大的浪费，所以，对此类问题的求解，应多采用以最小原料使用条数为目标值的模型