数学建模-截断切割的优化设计

工业中截断切割的优化设计工业中截断切割的优化设计 一摘要一摘要 本文讨论了加工业中 截断切割的优化排序策略我们对于不同的切割 方式总数用穷举法得到 720 种所可行解及其费用并对于原问题建立了决策 并对所给出的算法进行了分析和检验 1 当 e 0 时我归纳出解决问题的最优法则 从而提出了将面间距统一成判断权重来作为 排序准则的算法 同时证明 了e 0 的情况下根据这种最优准则能够实现题目所要求的优化目标 2 对于e 0 时我们提出了实用准则 最后我结合实际问题 将本问题进行了拓展讨论了当最终产品 成品 在毛坯 待加工长方体 中位置不预定时应如何实施加工方案以达到节省费用 和节约资源的目的 使我们的方案适用于更为广阔的领域 二问题的重述 二问题的重述 在工业生产中 常需要采取将物理一分为二的截断切割方式从一块长方体材料中切出一个 小长方体 其加工费用取决于水平切割和垂直切割的截面面积 以及调整刀具时的额外费 用 对本题所给出的问题我们首先面临的对加工次序的排序策略然后我们考虑当毛坯和产 品位置不预定的时候如何采取策略以达到我们的优化目的 问题 1 需考虑的不同切割方式的总数 2 给出上述问题的数学模型和求解方法 3 试对某部门用的如下准则做出评价 每次选择一个加工费用最少的切割面进行切割 4 对于 e 0 的情况有无简明的优化准则 5 用以下实例验证你的方法 待加工长方体和成品长方体的长 宽 高分别为 10 14 5 19 和 3 2 4 两者左侧面 正面 底面之间的距离分别为 6 7 5 单位为厘米 垂直切割费用为每平方厘米 1 元 r 和 e 的 数据有 4 组 1 r 1 e 0 2 r 1 5 e 0 3 r 8 e 0 4 r 1 5 2 e 15 三三 模型的假设和符号说明模型的假设和符号说明 1 切割刀具为两个一个水平放置一个为垂直放置 2 目标长方体所在位置不与毛坯任一表面重合 3 水平方向只需平行移动水平刀具垂直方向只平行移动或调整后再平行 移动刀具因此调整费用e 是否付出仅取决于先后两次垂直切割是否平行而 不记是否穿插着水平切割 4 毛坯与工作台接触的底面是事先指定的 5 毛坏 成品均为长方体 且这两个长方体的对应面是平行的 如下图 a b c 毛坯的长宽高单位厘米 aa bb cc 最终产品的长宽高单位厘米 毛坯的左表面右表面前表面后表面上表面下 表面 最终产品的左表面右表面前表面后表面上表面 下表面 有时我们为了叙述问题的方便将其依次记为 5 6 3 4 1 2 d j 最终产品与毛坯的对应表面的距离 j 1 2 6 r 水平切割单位面积费用与垂直切割单位面积费用之比 e 调整一次垂直刀具的额外费用 p 垂直切割单位面积费用 ti 加工过程中的第 i 刀切割第 ti 个面 wi 第 i 次切割的切割费用单位元 vi 第 i 次切割被切割掉部分的体积单位立方厘米 si 第 i 次切割时切割面积 分别表示在切割第 侧面时的费率 依题意 其它变量如果出现 则在使用时另行说明 四四 模型的建立模型的建立 2 3 4 5 6 3 4 5 6 4 5 6 5 6 6 1 3 4 5 6 2 4 5 6 3 5 6 4 6 5 1 2 4 5 6 2 3 5 6 3 4 6 4 5 4 1 2 3 4 5 6 1 2 3 5 6 2 3 4 6 3 4 5 3 1 2 3 4 6 2 3 4 5 2 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1 e 0的情形 的情形 1 2 3 4 5 6 表示初态 即没有进行任何加工 对应一个完整的加工策略事实上为 1 2 3 4 5 6 的一个全排列 而 1 2 3 4 5 6 的任一子集 S应某个策略在对毛坯加工过程中某个中间状态 3 在对毛坯加工过程中某个中间状态 S 它仅与在它之前截掉了那些面的组合有关 而与过 程 即排列 无关 4 1 2 3 4 5 6 的 64 个子集构成方体切割的所有可能的状态 包括初始状态 终态 以的 64 个子集构造有向图 G 以 S 为起点 以为终点连边 且 使得 对有向图 G 边赋权 任取有向图 G 边 不设其以 S 起点 以为终点 w 或记为 w 表示在状态 S 截去 i 所需费用 这些集合按照其包含元素数目的多少可分为 7 组 从多到少排序 相邻两组间构成一个决 策阶段 1 因此得如下 6 阶段动态规划问题 Min S t 1 2 3 4 5 6 为 的一全排列 w 的表述 记分别表示方体的长 宽 高 这 1 面到 2 面 3 到 4 5 到 6 的距离 可得 A B C w 五 五 模型求解模型求解 定理定理 最优准则 设 e 0 若策略 满足 则策略 必为截断切割的最优策略 证明 某截断切割策略 若满足 且 即称构成策略 的一逆序对 逆序数 以下证明对任一策略 若策略 中存在逆序对 则总可以构造某截断切割策略 其逆 序数小于策略 的逆序数 但总的切割费用不比策略 的多 设某截断切割策略 的逆序数大于 0 则必存在相邻的 两刀 k k 1 成策略 的一逆序对 交换 的次序 此时 与 比较 前者的逆序数比后者的减少 1 而在下面 证明前者的切割费用不比后者的多 1 当面 相对时 仅仅交换相邻两刀 k k 1 次序对切割费用没有影响 2 当面 相邻时 不妨设 此时 与 切割费用之差等于 其符号与相同假设 即 的切割费用比 的少 可用 mathematics 编程求解 程序见附件 问题条件切割方式 最少费用 Ar 1 e 0 Br 1 5 e 0 437 5 Cr 8 e 0 540 5 d r 1 5 e 2 15 e 取值 最少费用 最优切割方案 e 2 445 5 e 2 1 445 9 e 2 2 446 3 e 2 3 446 7 e 2 4 447 1 e 2 5 447 5 6 e 3 448 5 e 3 5 449 5 e 4 450 5 e 4 5 451 5 e 5 452 5 e 5 5 453 5 e 6 454 5 e 6 5 455 5 e 7 456 5 e 7 5 457 5 e 8 458 5 e 8 5 459 5 e 9 460 5 e 9 5 461 5 e 10 462 5 e 10 5 463 5 e 11 464 5 e 11 5 465 5 e 12 466 5 e 12 5 467 5 e 13 468 5 e 13 5 469 5 e 14 470 5 e 14 5 471 5 e 15 472 5 其中 1 2 3 4 5 6 代表切割的面如下图 2 3 5 4 1 由此可见对于不同的 e 值 会有不同的最优切割方式 当 e 大于 2 5 却只有唯一的最优切 割方式 下图为 e 取不同值时最少切割费用的图像 画出 最可能是最优切割方式的三种切割方式切割费用随 e 的取值而变化的图像 2468101214 450 460 470 480 可知当 e 等于 2 5 时为突变拐点 综上对于 e 不同取值时对应的最优方案为 e 的取值 最优切割方式 2 e 2 5 e 2 5 2 5 e 15 对此我们可以提出一个很实用的准则 当 e 较小时 换刀的费用很小 对于切割方式可以 不考虑换刀的影响 选择单纯切割费用最少的方式即可 当 e 较大时 则必须主要考虑换 刀的次数 在单纯切割费用尽量小的前提下 尽量选择换刀次数少的切割方式 六六 结果分析及讨论结果分析及讨论 由以上的计算与分析可知 r 以及 e 是在毛坯与成品要求已固定情况下影响费用和切割方 式的重要因素 当 e 0 时 根据优化准则 可以找到最优的切割方式 当 e 不等于零时 可以根据实用