线材下料问题-线性规划

1、实用标准文档一、问题陈述（下料问题 ）某工厂要做 150 套钢架， 每套钢架分别需要长度为 2.5 米、2.6 米和 1.9 米的圆钢各一套。已知原料每根长 10 米，问应如何下料，可使所用原料最省？二、问题分析该问题是运筹学在实际运用中比较经典的“线材下料问题” ，从第一部分问题陈述 中可以看出，该问题的一般提法是，要做 N 套产品，需要用规格不同的 M 种线材，各 种规格的长度分别为 l1，l2，l3，.，lm ，每一套产品需要不同规格的原料分别为m1，m 2，m 3， .，m m 根，已知原材料的长度为一定的长度，问应该如何下料，从而使 原材料的耗用最省。因此，在解决此类问题时应分两步考

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

3、最少。在本文的分析中，我们选择前者， 即：求解使用的钢材原材料总根数最少。为了建立模型方便， 我们把下料后余下的小于最短用料的钢材称为废弃钢材， 把下 料得到的长为 2.5m ， 2.6m ， 1.9m 的钢材称为规格钢材，把 10 米长的原材料钢材称文案大全实用标准文档为原钢。因此，所用的原钢可以分解成三部分：1 、成套利用的规格钢材； 2、剩余的规格钢材； 3 、废弃钢材。通过分析计算，可以得到原钢的 11 种下料方式如下：表 1 ：一条原料钢材的 11 种切法X1X2X3X4X5X6X7X8X9X10X112.5m432211100002.6m001020132101.9m0112132

4、1235Sum109.49.58.89.68.28.99.798.39.5Rema 0 0.6 0.5 1.2 0.4 1.8 1.1 0.3 1 1.7 0.5in我们设决策变量： 采取第 i种下料方式的有 xi根原钢， i=1,2,3,.,11. 另外设置辅助 变量：剩余 2.5 米的规格钢材为 y1 根，剩余的 2.6 米规格钢材为 y2 根 ，剩余的 1.9 米 规格钢材为 y3 根。因此得到模型一：模型一：剩余的规格钢材当作废弃钢材的情况Min Z=0*x1+0.6*x2+0.5*x3+1.2*x4+0.4*x5+1.8*x6+1.1*x7+0.3*x8+1*x9+1.7*x10+0

5、.5*x11+2.5*y1+2.6*y2+1.9*y3 (1) 4*x1+3*x2+2*x3+2*x4+x5+x6+x7-y1=150s.t. 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=150x i=0, y j =0, 且为整数i=1,2,3.11,j=1,2,3（2）11MinZxi（3）i1由（ 1 ）、（ 2 ）组成的是求废弃钢材最少的整数线性规划模型。同时，很容易联想 到另一个模型，是由（ 2）、（3 ）组成的求所用原料钢材最少的整数线性规划模型。模型

6、二：剩余的规格钢材（可同原钢一样可以再利用） ，不当作废弃钢材的情况Min Z=0*x1+0.6*x2+0.5*x3+1.2*x4+0.4*x5+1.8*x6+1.1*x7+0.3*x8+1*x9+1.7*x10+0.5*x11 （4）4*x1+3*x2+2*x3+2*x4+x5+x6+x7=150s.t. 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=150x i =0, i=1,2,3.11由（ 4 ）、（ 5）组成的是求废弃钢材最少的整数线性规划模型具有一定的实际意义， 特别是当最

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

8、大全实用标准文档求解模型：11MinZxii 1(3 )4*x1+3*x2+2*x3+2*x4+x5+x6+x7=150s.t. x3+2*x5+x7+3*x8+2*x9+x10=1505)x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11=150x i =0, i=1,2,3.11 此模型是设定最小使用原料钢材的条数为目标值进行求解。MinZ=0*x1+0.6*x2+0.5*x3+1.2*x4+0.4*x5+1.8*x6+1.1*x7+0.3*x8(4)+1*x9+1.7*x10+0.5*x114*x1+3*x2+2*x3+2*x4+x5+x6+x7=15

9、0s.t. 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=150x i =0, i=1,2,3.11此模型时设定最小废弃钢材为目标值进行求解。四、方法选择指导思路：线性规划求解思路选择方法： Excel 规划求解 使用工具： Excel 工具文案大全实用标准文档五、 求解过程1、框架建立2、模式调整3、计算原料钢材使用及剩余钢材文案大全实用标准文档4、设置目标函数及变量、以模型（ 3）、（5 ）组合而成的求解模型设定的目标值。说明：目标函数单元格 D9 即为我们所求的最少使用原料钢材条数。

10、其具体在 excel中的操作为 D9=C12+D12+E12+F12+G12+H12+I12+J12+K12+L12+M12.文案大全实用标准文档、以模型（ 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 分别为规格钢材 2.6m 、2.5m 、1.9m 所

11、求的最少使用条数。其中：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+G12+H12*3+I12*2+J12+K12*2+L12*3+M12*5;6、利用规划求解工具Excel :工具 - 规划求解 - 依次输入目标单元格、可变单元格、约束条件进行求解。其中，点击规划求解参数选项框右边的选项按钮，在弹出的选项框中选中采用线性模型和假定非负。求解结果如下图：、以模型（ 3）、（5 ）组合而成的求解模型求解结果。文案大全实用标准文档从上表可以直接得出：最小原

12、料钢材使用条数为 108 条。但实际的使用情况为107.5 条，多切割出来的 0.5 条（152-150 ） *2.5 ）米）。、以模型（ 4）、（5 ）组合而成的求解模型设定的目标值。25 米。但实际的剩余废弃钢材为 30从上表可以直接看得，最小剩余废弃钢材为文案大全实用标准文档米（152-150 ） *2.5+25 ）。六、 答案分析由上图可知，按照模式 1 切 38 条原料钢材，按照模式 8 切原料钢材 50 条，按照 模式 11 切原料钢材 20 条，从而可以得到： 2.6 米规格钢材 152（ 38*4 ）条， 2.5 米规 格钢材 150 （ 50*3 ）条， 1.9 米规格钢材

13、150 （50*1+20*20 ）条。同时，可以从得出 来的数据算出剩余的废弃钢材为 30 米，其中包含多切割出的 2 条 2.5 米规格钢材共 5 米，按照模式 8 切割的剩余废弃钢材 15 米（ 0.3*50 ）以及按照模式 11 切割的剩余废 弃钢材 10 米（ 0.5*20 ）。通过分别设置目标值为最小使用原料钢材的使用条数和最小剩余废弃钢材的计算， 我们得出相同的结果，即切割 2.5 米规格钢材 152 条， 2.6 米规格钢材 150 条以及 1.9 米规格钢材 150 条，同时剩余废弃钢材为 30 米，使用原料钢材 108 条。但是，对不同目标值设定就一定是会得出相同的结果吗？在

14、这里， 我们引出另一种 情况来进行对比分析。如题：某工厂要做 100 套钢架，每套钢架需要长度分别为 2.9 米， 2.1 米和 1.5 米 的圆钢各一根。已知原料每根长 7.4 米，问应该如何下料，可以使所用原料最省？在这我们利用之前的分析， 分别设定最小使用原料条数和最小剩余材料为目标值进行模型建立，如下：X1X2X3X4X52.9 米120102.1 米002211.5 米31203余料00.10.20.30.8文案大全实用标准文档设定最小使用原料条数为目标值模型：Min Z=x1+x2+x3+x4+x5x1+2*x2+x4=1002*x3+2*x4+x5=1003*x1+x2+2*x3

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