玻璃划分的数学模型.pdf

1 9 9 9年 l 2月 De c 1 99 9 一 应用 数学与计算 数学学报 Co M M oN A PPL M ATH A ND Go M PU T 第 1 3卷第 2期 V0 I 1 3 No 2 玻 璃 划 分 的数 学 模 型 鲁 习文 华东 理工 大学 数学 系 上海 2 0 0 2 3 7 2 摘要 本 文讨论 了玻 璃 合理 划分 问题 建 立 了玻璃 划 分 的数 学模 型 该模 型 既使 得坯料 用 量最 优 也考虑 了余 料尽 可 能少 同时划 分 得到 的各 种规 格 的成 品玻 璃 尽 可能 刚好 满 足需 要 数值 计算 结 果表 明该模 型 是有 效 和合 理 的 关 键词 塑 塑 坌 查 1 问题 的提 出 目 标就划 某 玻璃制 品有 限公 司生产销售玻璃 当前拥有 玻璃 板的坯料 为 2 5 0 c mx 2 5 0 c m 现有客 户前 来订 购规 格分别为 4 0 c m 3 O c m 6 0 c mx 6 0 c m 8 0 c r a x 7 0 c m和 1 2 0 c mx 1 2 0 c m 四种规格 的玻璃 相应 的需 求量 分别为 1 5 0 0块 1 0 3 0块 8 0 0块和 2 0 0 块 该 公 司想 知道 在生 产过程 中如何合 理地划 分玻璃 理想 的划 分应该 满足 坯 料 的用量 要少 边角余料 尽可能 少 并最 好成块 操 作要方便 所得到 的成 品玻 璃要尽 可能 刚好满足客户 需要 即划 分下来成 品玻璃 余量 要尽 可能少 如果有 成品余量 那最好 是规 格相 对大一 些 的成 品 由于玻璃坯料 通常 有多种规格 不 同的客 户有不 同的需求 因此该 公 司需要 知道一 般 情 况下 最优或 合 理利用 坯料 的生产 操 作方 案 关 于 不 同的下料 问题 已 有不少研 究和 应用 例 如 1 2 本文针对 该 玻璃 制 品有 限公 司这一实 际 问题 的要 求 运用 优化 理论 和方 去 3 4 1 首先讨 论 了玻璃坯料 的合 理划 分方案 然后 建立 了该 问题 的数 学模 型 给 出了求 解方法 并对 模 型的结果进 行 了讨 论 较好地 解 决 了这 一实 际问题 2 建 模 分 析和 划 分 方 案 根 据玻璃 的特 点和实 际生产 中的要 求 玻璃划 分通常 是采用 一刀切断 并 且 在生产之前 先 对玻璃坯料 进行 排料 为了生产操 作方便起 见 在一块坯 料上 安 排 的成 品规格 有一 定的限制 安排 的数 量过 多要增加操 作难度 为 了寻 找到最 优 的或合 理 的生产操 方案 我 们根据 问题 的实 际背景 确定如 下几 条原 则 不考 虑刀 口宽度 和坯 料 的厚度 根据 玻璃 的特 点 玻璃划 分为截断划 分 即每 次划 分都将 玻璃 一分 为二 本文 1 9 9 9年 4月 1 5日收到 华 东理工 大学科 研基金 资助项 目 K9 0 1 2 0 3 维普资讯 应用 数学 与 计算 数学 学报 由于坯 料和 成 品都是长 方形 或正方 形 我们 也认为在每 次划 分过种中得到 的玻璃 都 是长方 形或者正 方 形 为了操作方 便 在 一般情 况下 一块 坯料上 最多 只划五种 规格 的成 品玻 璃 每次划 分 都是沿着平 行于 玻璃一 条边进行 划分 简称 为平 行划 分 根据 以上原 则 通 过对 问题 的深入 分析 我们认 为解决 玻璃划 分 问题应 先进 行排料 选定最优 的或 合理 的坯 料划 分方案 然后再确定坯料用 量和操作 方案 即 分 为选 定划 分方案 确定最佳坯 料用 量与 生产 操作方 案二个 阶段 为 了讨论 问题 方便 起见 我们 分别记 四种 类型 的成 品玻璃 4 0 c mx 3 O c m 6 0 c r n x 6 0 c r n 8 0 c rux 7 0 c m 和 1 2 0 c mx 1 2 0 m 为 I I I I I I 和 I v 下面 我们 首先考虑 坯料 的各种合理划 分方案 1 选定坯料 划分 方案 玻 璃制 品公司需要 根据现有 坯料和 客户 的需求 对坯 料进 行有 效的排料使 其 降低成 本和工 作难度 增加 效益 而在坯 料上进行 排料 的 方法 千差 万别 由此得 到 的结 果也 不尽相 同 如 处理 不当 会造成 较大 的浪 费 因此 如何对坯 料进行 高教划 分是 生产 中的关键 之一 也 是难 点之一 通过 对玻璃 划分过程 分析 并 根据截 断划分和 平行划 分的假设 下面 我们给 出一个确 定坯 料 划 分方案 的原 则 我们首先 将坯料划 分 为一 些长方 形 这些 长方 形的一边长 等于 某一成 品边长或其倍 数 例 如在上述 具体 的 问题 中 我们 首先 可以将坯料 划分 为 2 5 0 c mx 1 2 0 c m 2 5 0 c l n x 7 0 c ln和 2 5 0 c a l x 6 0 c m三 大块 然 后重 复这个 过程直到最 后 的 长 方形 的一条边小于 所有成 品玻璃 的最小 边为止 最 后剩 下 的这些长方形 即为余 料 将长 方形坯 料 划分为一些 长方 形的过程是一个 优化 过程 即求 成 品边长 的优 化组 合长度尽 可能接 近或等于 所要 划分坯料 的一边长 60t6 0 80 T0 1 2 0 1 2 0 6 0 6 0 8 0 t T 0 6 0t 6 0 6 0t 6 0 6 0 6 0 8 0 0 60 60 4 3 4 0 3 0 40 3 0 牵 夸料 图 1划分 方案 l 图 2划 分方案 2 通过上述 划 分方法 可 以得 到一 系列可行 的坯 料划 分方案 然后按 照预先 确 定 的选择标 准从 中选 出较 优 的或 合理 的划分方案 通常 的选择标 准是 坯料 利用 率 r要达 到或 超过预 先确 定 的要 求 即边 角余料要 低 于一个预 先设 定 的标准 n o r o与 有如 下关系 一 1 维普资讯 2期 鲁 习 文 玻 璃划 分 的数学 模 型 这 里 a b是坯 料 的面积 至少有 一种划 分方案 能产 生第 种 规格 的成 品玻璃 在上 述具体 问题 中 我们 选定 r o 9 6 根据 以上 划分原 则 我们 可以得到 2 3种满意 的划分方 案 上 图 l 和 图 2即 为划 分方 案 l和 2 我们 将这 2 3 种 划 分方 案 的有关信 息列 为表 l 表 1 坯 料划分 方案表 成 品数量 成 品 规 格 边 角余 料 坯料 面 积 划 分方 案 1 2 0 c m 1 2 0 c m 8 0 c mx 7 0 c m 6 0 c m 6 0 c m 4 0 c mx 3 0 c m C i i l 利用率 l l 2 5 l 5 9 0 0 9 8 5 6 2 1 3 6 7 l 3 0 0 9 7 9 2 3 1 4 6 2 1 7 o 0 9 7 2 螈 4 l 4 5 5 1 7 0 0 97 2 8 5 l 4 4 8 l 7 0 9 7 2 8 6 1 4 2 1 4 1 7 0 0 9 7 2 5 1 l 6 i 6 1 7 o 0 9 7 2 8 8 l l 2 2 8 l 7 o 0 9 7 2 8 9 2 3 4 0 2 50 0 9 600 1 0 2 3 0 1 2 2 5 0 0 9 6 0 0 l 1 2 0 4 i 4 2 5 0 0 9 6 O 0 i 2 2 0 0 2 6 25 o o 96 0 0 1 3 0 9 0 8 2 50 0 9 6 O0 1 4 0 6 4 1 0 2 5 0 0 9 6 O 0 1 5 0 6 0 2 2 2 5 O 0 9 6 0 0 i 6 0 3 1 2 0 2 5 0 0 9 6 O 0 1 7 0 3 8 1 2 2 5 0 0 9 6 O 0 1 8 0 3 4 2 4 2 5 0 0 9 6 O 0 1 9 0 3 0 3 6 25 o 0 9 6 0 0 2 0 0 O i 2 i 4 2 5 0 0 9 6 O0 2l 0 0 8 2 6 2 50 0 9 6 O 0 2 2 0 0 4 3 8 2 5 0 0 9 6 O 0 2 3 0 0 0 5 0 2 5 o 0 9 6 0 0 2 确 定最佳坯料 用量和 生产操 作方案 为了节省用料 增加效 益 公 司总是 根据坯料和 订单 规格 选 定一些最优 的或 合理 的坯料 划 分方案组 织生 产 公司根据订 单所要 求 的成 品规 格和数量 在 已确 定 的坯料划 分方 案中选择 所 需要 的方案 并决定 按每种划 分方案应划 分 的坯料 数 在具体加工 时就 按照 已经 选 定的划分 方案和 相应 的划分 数量进行 生产 这样 一来 简化 了操作 流程 便 于 大批 量 生 产 维普资讯 应 用 数学 与计算 数学 学 报 l 3卷 3 数 学模 型 在选定 最佳 或满意 的生产 方案过程 中 根 据公 司要求 目标 是既要 花费最少 的坯 料 数 也要 使边 角 余料 的面 积 尽 可 能 少 同时所 得 到 的成 品玻 璃要 尽 可 能 刚 好满足客 户 的需要等 为此 我们 先建立 一般情 形下 的数 学模型 假设坯 料 的规 格 为 x b 客 户 订购 m 种 规 格 的成 品玻璃 为 0 1 b l 口 2 6 2 一 a m b 不妨 设 a b l 2 b 2 a b 这 m 种玻 璃 的需求数量 分别 为 d 1 d 假如采 用 前述划 分原 则得 到 n种划 分方案 若该 坯料 的第 种划分得 到第 i 种成 品规格 的数 量 为 a i j 1 n 边 角余料 为 c j 则这 种划 分对应 于 向量 o z o 竹 我们 称该 向量 为第 J种划 分 的划分 向量 简记 为 即 0 l J 卸 啪 1 一 n 2 设 x j j 1 为按 第 J种划 分方案所用 的坯 料 的数量 z n 1 n m 为第 i 种 成 品玻璃 的剩 余量 则 生产 所用 的坯料总 数 z 和边 角余料总量 2 z 分别 为 n n z 2 c j x j 3 J 1 j l 由于在 生产过 程 中 坯 料用量最 优是最 高 目标 我们视 为第一级 目标 在此 基础上 再考 虑边 角余料尽可 能少 我们视 为第二级 目标 最 后才 是尽量满足 成 品 余量尽 可能少和 成 品余量尽 可能是 大规格 的要求 由于大规格 的玻璃在将 来 派上 用途 的可能性 大 因此我们对剩 余成 品余量 也依 次采用优先等 级 处理 根据上 述分析 和 目标规 划理 论 我们 能够建立 如下玻 璃划分 的数学模 型 m 2 只 z t 1 也 i 1 一 m x j o且 为整 数 1 n m 4 5 6 这里 瑞 该 模 型是一个 m 2 级 的多 目标整 数规划 模 型 因此 可 以运用 目标规划 和 整数 规划 的方法 3 l4 j 进行求 解 4 模 型 的应 用 根据 上面 已得 到 的划 分方案表 和需要 生产 的成 品玻 璃规格和数 量 我们 运用 上 述数学 模型 即可解决 公司 当前 的坯 料用量 问题 2 m 勺 R S 维普资讯 2期 鲁习 文 玻璃划 分 的数学模 型 5 l 设 z 1 2 3 为第 J种划 分方案所用 的坯 料 的数量 则 由划分 方案表 可 知 I I I I I I 和 I V这 四种玻璃 的生产 量分别 为 1 5xl一 7 x2十 2 3 5 x4 8 xs 1 4x6 1 6x7 2 8 xs 1 2xl O 1 4 x1 1 2 6 x 2 一 8x1 3 O x1 4十 2 2 x1 5 1 2 x1 7 24 x1 8十 36 x1 0 1 4x2 o 2 6x2 1 3 8x2 2 5 0z2 3 5xl一 6 x2 6 x3 5 x4 4x5 2 x6 6xr 2 xs 8 4 2 9 4Xl l 4x1 4 1 2 X1 6十 8 l 7 4 Xl s 1 2 x2 o 8 x2 1 4 2 2 2 xl 3 2 4 3 4 4上 4 5 4 6 7 x8 2 x9十 3 xl o 9 T1 3 f 91 6 X1 4 4 6 xl s 3 x1 6 3 xl 3 x1 8 3X 1 9 2 3 1 2 x 3 X 4 x 5一X 6 7十 X 8 2 x 9 2 xl o 9 X l l 2 x 1 2 1 O 生产所 用 的坯料 总数 为 1 1 边 角 余 料 总 量 为 2 9 0 0 x l 1 3 0 0 2 1 7 0 0 z 2 5 0 0 x i 1 2 J i 3 J 9 根 据 4 6 和 7 1 2 我 们 能够 得到如下 数学模型 m i n z RA 2 z P 3 3 扛 上P 4 P 5 5 P 6 6 P l P 2 9 o o 1 3 1 7 0 0 E 2 5 0 0 q X 2 4 C 2 5 B X2 6十 2 7 f 1 3 st1 5X l 7 x2 2x3 5 x4 8 x5 1 4x6 1 6x7 2 8 xs 1 2xl 0 1 4xl l 26 x1 2上 8 X1 3 1 0 X1 4 2 2x1 l 2 1 7 2 4 xl 8 3 6 xl 9 1 4x2 o 26 x2 1 38 x 2 2 5 0X2 3一 X2 4 1 5 0 0 f 1 4 1 5 Xl 6x2 6 x3 55 g 4 4 x5 2x6 6 x7 2 xa 4 x9 4xn 4 X 1 4 1 2 x 1 6 8 X 1 7 4 z 1 8 十 1 2 X o十8 2 l 4 x 2 2一X 2 5 1 0 0 0 1 5 2Xl 3x2 4 x31 4 x4 4 x5 4x6 x7十 x8 3 x9 3 xl 0 9 x1 3 6 x1 4 6 x 1 5 3 x 1 6 3 x 1 7 3 X1 8 3 l 9一 2 6 8 0 0 1 6 1 2 3 X4 X5十 6十 7 X8 2 x9 2xl o 2 x1 1 2 x1 2 2 x1 3一 X2 7 2 0 0 f 1 71 1 X 2 Z 2 7 0且 j 1 2 2 7 为 整数 f l 8 j 我们运用 目标规 划 的求解 方法 3 和 QS B软件包 可求得上述 问题 的两个解 第 个解 为 翼 x 1 5 0 z 1 5 2X 7 o 5 0 2 1 0 3 2 9 0 0 0 1 9 其 余 z z 2 z 维普资讯 应 用数 学 与计 算 数学学 报 l 3卷 第二个解 为 6 7 8 9 3 l 1 4 l 3 f 2 0 1 z 3 2 3 z u 1 0 其余 一0 l 2 1 0 丘 z 3 2 9 0 0 0 由 1 9 2 0 得到 两个 生产 方 案和有 关数值结 果如下 表 2 生产 方 案 A和有 关数值结 果 划 分 成 品数 量 成 品 规 格 边 角余料 方 案 坯料用 量 1 2 0 c m 1 2 0 c m 8 0 c m 7 0 c m 6 0 c m 6 0 c m 4 0 c m 3 0 c m c n l l 10 10 2 0 50 l 5 0 900 0 2 1 50 1 5O 45O 900 1 050 195OO0 9 15 30 45 6 0 0 37 500 1 0 5 1 0 1 5 0 60 1 2500 1 3 3 0 0 2 7 0 0 2 4 0 75 0 0 0 合 计 2 l 0 2 O 0 8 O 0 1 0 1 0 1 5 0 0 3 2 9 0 O O 表 3 生产方 案 B和有关 数值结 果 成 品数量 成 品 规 格 边 角余 料 坯 料用 量 1 2 0 c m 1 2 0 c m 8 0 c m 7 0 c m 6 0 c m 6 0 c m 4 0 c m 3 0 c m C I I I 1 6 7 67 1 34 335 1 0o5 6030 0 2 8 8 24 48 5 6 1 0400 3 93 93 3 72 558 l 86 1 58l 00 4 l l 4 5 1 70 0 5 l 1 4 4 8 l 700 6 4 4 16 8 56 6800 9 1 3 26 39 52 0 3 2500 1 3 23 0 如 7 0 1 84 5 75O0 台 计 2 l 0 2 0 0 8 0 0 1 0 1 0 l 5 0 0 3 2 9 0 0 0 5 结 果 与 讨 论 从模 型 的计 算结果可知 由第一个解 得到 的生产方 案 A只需采用五个坯 料 划 分方 案 并且 生产 集 中 而 由第二个 解得 到 的生产 方 案 B要 采用八 个划 分方 案 其 中有三个 方案划 分 的坯料 数 只有 1 到 4 块 显 然对实 际操作而 言 方 案 A 比方 案 B简便 因此 我们 建议采用 生产方 案 A进行 生 产 我们 很容 易知道坯料 用量 的一个下界 是 j 坐 j s 2 1 维普资讯 2期 鲁 习 文 玻璃 划 分 的数学 模型 而 坯料 的最优 用量 为 2 1 0块 由此可 见最 优坯料 用量 是相 当接近这 个 下 界 的 这说 明模型是 十分 有效和理 想 的 此 外边 角余料 总和 为 2 z 3 2 9 0 0 0 f 2 2 1 这样 坯 料利用 率 为 一 一 9 7 4 9 从坯 料 的利用 率达到 9 7 4 9 可以看 出原材料得 到较 为充分的利用 这 也说明模型 的效 果是十分理 想 的 如果不考虑坯料 的综合利 用 在坯料上 只排一种料 这对 生产是很方便 的 但 会造 成原材料 的浪费 此 时在每块坯 料 上 只排 I I I I l l 和 I V种规格 中一种 的数 量分别 为 5 0 1 6 9 和 4 在这 种情 况下 坯 料 的用 量为 l l l z c2 4 这 要超 出最优 用量 2 2块 超 出 1 0 4 8 坯 料 的利用 率也 只有 8 8 显然 是不经 济 的 在建立模 型过程 中 我们 根据实 际问题 的要求 采用 了多个 目标建立 模型 简 称 多 目标模型 这是十 分 必要 的 因为在通 常情况 下余料 是 比较细 小 的料 难 以 派上用场 如果只采用第一个 目标 z 建立模型 简称为单目标模型 将 J 1 会 在 同样 满足坯料用量 最少 的情况下 余料 总量会 明显增 大 我们 通过计算 可得 单 目标模 型 的最优 解是 i lI z 3 8 z 1 3 z i a 其余z 2 5 l 矿 2 1 0 2 z 3 6 5 0 0 0 从数值 结果可知坯 料用量也 是 2 1 0 块 模 型 的 3 2 9 0 0 0 c m 超 出 比例 为 1 0 9 4 算 结 果和 分析对 比列表 如下 但边角余料 是 3 6 5 0 0 0 c m 明显 大于多 目标 下 面我 们将 多 目标模 型和 单 目标模 型 的计 表 4 多 目标模 型和单 目标 模 型的计算 结果和 分析对 比表 坯料 得到 的成 品玻 璃数量 增加 所得 成 品数量 边角余料 模 型 用 量 I I I I I I I V I I I I l l I V c m0 多 目标 模 型 2 1 0 1 5 o 0 l 0 1 0 8 0 0 2 0 0 0 1 0 0 0 3 2 9 0 O 0 单 目标模 型 2 1 0 1 5 0 0 1 o 0 0 8 o 0 2 o 0 0 0 0 O 3 6 5 O M 从上表 的数 值结 果和 分析对 比中可 以看 出 两个模 型 的坯 料用量 相 同 但 多 目标模 型 比单 目标模 型 多获得 规格 较大 的 6 0 c m 6 0 c m 的成品玻璃 1 0块 由此 可 维普资讯 应 朋 数学 与计 算 数学 学报 见 多 目标 模型 比单 目标模 型 的效果更 为理想 它 既可使得 坯料 的用量最 少 也 可使得 余料 少 而且尽 量成 块 在建立 模型过 程 中 如 果我 们认 为边 角余料 为完全 损失 而 暂不 用 的块 料 由于存贮 损耗等原因也有部分损失 则我们可以将这两部分统一为一个等级 目 标 w c z w x n i 期 中权重 和 w 可根据 实际情 况确定 1 1 z 1 我 们上面建立 的模 型 4 6 J 能够 很好 地适应坯料 规格 和订 货规格 的变 化 模 型可 以很容 易推 广到公 司具 有 K种规格 坯料 的情 形 参考文 献 1 J 李 春华 线 性规 划 在下 料 中 的应用 运筹 与管理 N o 1 1 9 9 3 P 2 6 2 9 2 陶 谦坎 运 筹 学应用 案例 机械 工 业 出版 社 北京 1 9 9 3 P 1 8 2 6 3 赵 可培 目标规 划 及其 应 用 同济 大学 出版 社 上 海 1 9 8 7 P 1 4 8 7 4 Ha md y A T M l a 吴立 煦 和 朱 劫 文译 运 筹 学 第二 版 上 海 人 民 出版 社 上 海 1 9 8