线材下料问题-线性规划

一 一 问题陈述问题陈述 下料问题 某工厂要做 150 套钢架 每套钢架分别需要长度为 2 5 米 2 6 米和 1 9 米的圆钢各一套 已知原料每根长 10 米 问应如何下料 可使所用原料最省 二 二 问题分析问题分析 该问题是运筹学在实际运用中比较经典的 线材下料问题 从第一部分问题陈述 中可以看出 该问题的一般提法是 要做 N 套产品 需要用规格不同的 M 种线材 各 种规格的长度分别为l1 l2 l3 lm 每一套产品需要不同规格的原料分别为 m1 m2 m3 mm根 已知原材料的长度为一定的长度 问应该如何下料 从而 使原材料的耗用最省 因此 在解决此类问题时应分两步考虑 1 确定可行的切割模式 即按照客户需 要在原材料钢材上安排切割的一种组合 2 确定合理的切割模式 合理的切割模式的 预料不应该大于或等于客户需要的钢材的最小尺寸 对于如上第一分部提出的线材下料问题 可以用运筹学中线性规划的方法求解 通过建立线性规划模型来具体分析 三 三 模型建立模型建立 建立线性规划模型时 对于约束条件这里为切割要满足客户对钢材数量的最低要 求 本题将对标准钢材的切割 2 5 米 2 6 米 1 9 米 从而组合成一套钢架 要 求为 150 套等因素建立约束条件 但是 对于目标函数而言 会有这样两种情况 1 求的钢材原材料总根数最少 2 求的钢材原材料余料最少 在本文的分析中 我们选 择前者 即 求解使用的钢材原材料总根数最少 为了建立模型方便 我们把下料后余下的小于最短用料的钢材称为废弃钢材 把 下料得到的长为 2 5m 2 6m 1 9m 的钢材称为规格钢材 把 10 米长的原材料钢材称 为原钢 因此 所用的原钢可以分解成三部分 1 成套利用的规格钢材 2 剩余的 规格钢材 3 废弃钢材 通过分析计算 可以得到原钢的 11 种下料方式如下 表 1 一条原料钢材的 11 种切法 X X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7X X8 8X X9 9X X10 10 X X11 11 2 5m2 5m43221110000 2 6m2 6m00102013210 1 9m1 9m01121321235 SumSum109 49 58 89 68 28 99 798 39 5 RemainRemain00 60 51 20 41 81 10 311 70 5 我们设决策变量 采取第 i 种下料方式的有xi根原钢 i 1 2 3 11 另外设 置辅助变量 剩余 2 5 米的规格钢材为y1根 剩余的 2 6 米规格钢材为y2根 剩余 的 1 9 米规格钢材为y3根 因此得到模型一 模型一 剩余的规格钢材当作废弃钢材的情况模型一 剩余的规格钢材当作废弃钢材的情况 MinMin Z 0 x1 0 6 x2 0 5 x3 1 2 x4 0 4 x5 1 8 x6 1 1 x7 0 3 x8Z 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 2 5 y1 2 6 y2 1 9 y3 1 x9 1 7 x10 0 5 x11 2 5 y1 2 6 y2 1 9 y3 1 1 4 x1 3 x2 2 x3 2 x4 x5 x6 x7 y1 1504 x1 3 x2 2 x3 2 x4 x5 x6 x7 y1 150 s t s t x3 2 x5 x7 3 x8 2 x9 x10 y2 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 x2 x3 2 x4 x5 3 x6 2 x7 x8 2 x9 3 x10 5 x11 y3 150 x xi i 0 0 y yj j 0 0 且为整数且为整数 i 1 2 3 11 j 1 2 3i 1 2 3 11 j 1 2 3 2 2 3 3 11 1i i xMinZ 由 1 2 组成的是求废弃钢材最少的整数线性规划模型 同时 很容易联想 到另一个模型 是由 2 3 组成的求所用原料钢材最少的整数线性规划模型 模型二 剩余的规格钢材 可同原钢一样可以再利用 模型二 剩余的规格钢材 可同原钢一样可以再利用 不当作废弃钢材的情况 不当作废弃钢材的情况 MinMin Z 0 x1 0 6 x2 0 5 x3 1 2 x4 0 4 x5 1 8 x6 1 1 x7 0 3 x8Z 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 1 x9 1 7 x10 0 5 x11 4 4 4 x1 3 x2 2 x3 2 x4 x5 x6 x7 1504 x1 3 x2 2 x3 2 x4 x5 x6 x7 150 s t s t x3 2 x5 x7 3 x8 2 x9 x10 150 x3 2 x5 x7 3 x8 2 x9 x10 150 5 5 x2 x3 2 x4 x5 3 x6 2 x7 x8 2 x9 3 x10 5 x11 150 x2 x3 2 x4 x5 3 x6 2 x7 x8 2 x9 3 x10 5 x11 150 x xi i 0 0 i 1 2 3 11i 1 2 3 11 由 4 5 组成的是求废弃钢材最少的整数线性规划模型具有一定的实际意义 特别是当最短的规格钢材长度较长时 剩余的规格钢材就可以再次被利用 在此 我 们应该注意到 由 3 5 组成的整数线性规划模型就是模型一 由于在建立模型一和模型二的时候 考虑了剩余规格钢材的不同处理情况 使这 个问题变得清晰了 所得到的模型也比较全面 基本没有漏洞和缺陷 并且比较容易 在这些基础上修改或添加一些其它的约束条件 比如 各种规格钢材下料成套时的不 同比例等等 所以 我们建立的线材下料问题的模型是可行的 基于以上的分析 我们选择 3 5 组合而成的模型和 4 5 组合而成的 模型进行具体求解 从而求出组合出 150 套圆钢所需要的最少原料钢材 求解模型 求解模型 3 3 11 1i i xMinZ 4 x1 3 x2 2 x3 2 x4 x5 x6 x7 1504 x1 3 x2 2 x3 2 x4 x5 x6 x7 150 s t s t x3 2 x5 x7 3 x8 2 x9 x10 150 x3 2 x5 x7 3 x8 2 x9 x10 150 5 5 x2 x3 2 x4 x5 3 x6 2 x7 x8 2 x9 3 x10 5 x11 150 x2 x3 2 x4 x5 3 x6 2 x7 x8 2 x9 3 x10 5 x11 150 x xi i 0 0 i 1 2 3 11i 1 2 3 11 此模型是设定最小使用原料钢材的条数为目标值进行求解 MinMin Z 0 x1 0 6 x2 0 5 x3 1 2 x4 0 4 x5 1 8 x6 1 1 x7 0 3 x8Z 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 1 x9 1 7 x10 0 5 x11 4 4 4 x1 3 x2 2 x3 2 x4 x5 x6 x7 1504 x1 3 x2 2 x3 2 x4 x5 x6 x7 150 s t s t x3 2 x5 x7 3 x8 2 x9 x10 150 x3 2 x5 x7 3 x8 2 x9 x10 150 5 5 x2 x3 2 x4 x5 3 x6 2 x7 x8 2 x9 3 x10 5 x11 150 x2 x3 2 x4 x5 3 x6 2 x7 x8 2 x9 3 x10 5 x11 150 x xi i 0 0 i 1 2 3 11i 1 2 3 11 此模型时设定最小废弃钢材为目标值进行求解 四 四 方法选择方法选择 指导思路 线性规划求解思路 选择方法 Excel 规划求解 使用工具 Excel 工具 五 五 求解过程求解过程 1 框架建立 2 模式调整 3 计算原料钢材使用及剩余钢材 4 设置目标函数及变量 以模型 3 5 组合而成的求解模型设定的目标值 说明 目标函数单元格 D9 即为我们所求的最少使用原料钢材条数 其具体在 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 L12 5 设置约束条件 说明 约束条件单元格 C15 C16 C17 分别为规格钢材 2 6m 2 5m 1 9m 所求的 最少使用条数 其中 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 组合而成的求解模型求解结果 从上表可以直接得出 最小原料钢材使用条数为 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 米规格钢材 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 条 但是 对不同目标值设定就一定是会得出相同的结果吗 在这里 我们引出另一 种情况来进行对比分析 如题 某工厂要做 100 套钢架 每套钢架需要长度分别为 2 9 米 2 1 米和 1 5 米的圆钢各一根 已知原料每根长 7 4 米 问应该如何下料 可以使所用原料最省 在这我们利用之前的分析 分别设定最小使用原料条数和最小剩余材料为目标值 进行模型建立 如下 X1X1X2X2X3X3X4X4X5X5 2 92 9 米米 12010 2 12 1 米米 00221 1 51 5 米米 31203 余余 料料 00 10 20 30 8 设定最小使用原料条数为目标值模型 Min Z x1 x2 x3 x4 x5 x1 2 x2 x4 100 2 x3 2 x4 x5 100 3 x1 x2 2 x3 3 x5 100 xi 0 i 1 2 5 设定最小余料为目标值模型 Min Z 0 x1 0 1 x2 0 2 x3 0 3 x4 0 8 x5 x1 2 x2 x4 100 2 x3 2 x4 x5 100 3 x1 x2 2 x3 3 x5 100 xi 0 i 1 2 5 对这两个模型进行求解 有 最小余料为目标值模型解 最小原料使用条数为目标值模型解 由以上两种模型解答可知 在以最小余料为目标值进行求解的时候 得出的原料 使用条数为 150 条 而以最小原料使用条数为目标值进行求解的时候 得出的原料使 用的条数为 90 条 综合两道题目的比较 可知 两种类型的模型设定是会得到不同的解答 因此 在不保证未