矩形零件排样问题的数学建模.pdf

矩形零件排样矩形零件排样问题问题 摘要摘要 本文针对矩形板材的排样问题 建立了整数规划模型 利用了贪心算法和遗 传算法 给出了多种限制条件下的最优排样方案 针对问题一第一问 对于 9 种零件进行排样且限制只能沿一个方向排样 每一 行只能排放一种类型的零件的问题 将排样零件所用面积占板材的比率最大作为 目标函数 所有排样零件面积不超过板材面积 排样的每种零件个数不超出题目 所给的限制以及排样的所有行宽度之和不超过板材宽度作为约束条件 建立整数 规划模型 利用 LINGO 软件进行计算 最终得到最优排样方案如表一所示 排样 零件总面积 2 2482170Smm 板材利用率 0 99 2868 S S 针对问题一第二问 只能使用 一刀切 在整料或余料中 从一边的某点 到另外一边某点的连线一次切割 但可以在切割下来的板料中再次切割 的生产 工艺 再对 9 种给定零件进行排样 找出板材利用率最高的排样方案 将排样零 件总面积最大作为目标函数 每行的宽度应等于某种零件的长度或宽度 每行内 排样零件的宽度应不超过该行宽度 排样长度应不超过板材长度以及每种零件排 样个数应不超过题目所给限制作为约束条件 建立整数规划模型 借助贪心算法 进行计算 得到最优排样方案如表二所示 排样零件总面积 2 2489688Smm 板材利用率 0 99 5875 S S 针对问题二 对于固定宽度的卷材设计使用长度最短的方案以满足各个规格 的零件的排样问题 在板材上建立直角坐标系 用每一个零件的左下角坐标 bibi xy和右上角坐标 aiai xy来描述零件安放位置 用 0 1 变量 i 表示该零件横 排或纵排 将卷材使用长度最短转化为最末端零件右上角横坐标最大并以此作为 目标函数 以两零件之间的应满足不重叠的要求 每一种零件的数量应满足需求 量以及同一零件右上角坐标和左下角坐标之间的关系作为约束条件 建立整数规 划模型 利用遗传算法计算得到使用卷材长度最小的排样方案如图二所示 卷材 使用长度为 40dm 关键词 二维矩形排样 整数规划 贪心算法 遗传算法 1 问题重述 问题1 有九种矩阵零件 按1 9编号 它们的尺寸 毫米 分别是 按编号排列 零件长度l 15 85 85 155 93 176 150 185 185 零件宽度w 55 70 75 115 185 69 37 175 120 零件个数M 200 200 200 100 100 200 400 100 300 现有一个长2500宽1000的板材 欲充分利用该板材切割出零件 应采用什么 样的方案 有时由于工艺或其他实际情况限制 只能沿一个方向 纵向或横向 排样 而且每一行只能排放一种类型的零件 排放这一行时 要么都是竖着排 要么都 是横着排 如下图所示 如果有这种限制 应该怎样切 当工艺提高了 限制 少了 切割的方法会更灵活 请结合实际讨论几种限制更少的情况下的切割方法 问题2 欲从宽为15 分米 的卷材上切割出二十五个零件 编号1 25 尺寸 分米 分别是 按编号排列 零件长度 12 4 6 10 2 6 4 4 7 4 6 4 6 4 2 8 8 8 6 2 8 3 2 3 2 零件宽度 6 7 7 2 5 4 2 6 9 5 4 6 3 5 4 4 6 3 3 6 2 5 5 4 4 请给出使用卷材长度尽可能小的方案 2 问题分析 2 1 问题一的分析 问题一第一问要求在限制条件为只能沿一个方向排样 且每一行只能排放一 种类型的零件 每行零件排放方式相同的情况下 对 9 种零件进行排样使板材利 用率最高 排样零件占用板材面积可以由排样的每种零件所占的行数与每行相应 的个数表示出来 所以可以以排样零件占用板材面积最大作为目标函数 所有排 样零件面积需不超过板材面积 排样的每种零件个数不能超出题目所给的限制 排样的所有行宽度之和不能超过板材宽度 以此作为约束条件 可以建立整数规 划模型 问题一第二问要求在切割只能实行 一刀切 的工艺 在整料或余料中 从 一边的某点到另外一边某点的连线一次切割 但可以在切割下来的板料中再次切 割 的限制条件下对 9 种零件进行排样 使板材利用率最高 板材利用率可以用 排样零件的总面积与板材面积的比值表示 因此可以将排样零件总面积最大作为 目标函数 而排样零件总面积可以用每种零件面积乘以排样个数再求和来表示 若考虑先从下方开始沿平行于板材长边方向进行切割 将板材切割成若干长为L 的行 再分割成若干零件 则最多可切割为 66 行 每行的宽度应等于某种零件 的长度或宽度 每行内排样零件的宽度应不超过该行宽度 排样长度应不超过板 材长度 同时每种零件排样个数应不超过题目所给的限制 以此为约束条件 可 以建立整数规划模型 2 2 问题二的分析 问题二是针对固定宽度的卷材设计使用长度最短的方案以满足各个规格的 零件的排样问题 该问题中零件的排样和问题一第二问中方式相同 均为无只能 沿一个方向排样和一行只能排放同一种类零件两个约束的排样 因此可考虑建立 与上述去除约束条件后排样模型类似的整数规划模型 区别于上述模型 该问题 的目标为卷材使用长度最短 因此将模型的目标函数改为最后一个零件的右上角 坐标最小 结合上述模型的约束条件 即可建立起问题三的排样优化模型 图一 模型目标函数示意图 3 模型假设 1 假设不考虑刀具的厚度 2 假设不考虑在切割过程中的损耗 3 假设不考虑板材厚度的影响 4 假设不考虑切割工艺的不同 5 假设矩形零件只横排和纵排 不斜着排 15W max ai x 4 符号说明 5 模型建立与求解 5 1 模型一的建立与求解 问题一第一问以排样零件占用板材面积最大为目标函数 排样零件总面积不超 过板材面积 各种排样零件数量不超过题目给出的相应零件数量等为约束条件建 立了限制条件下矩形零件排样优化问题的线性规划模型 5 1 1 模型一的目标函数 以 i z表示第i种零件所排行数 可将每种零件的长宽交换变为另一种零件 表示 该零件竖放 故 9 种零件变为 18 种零件 i l表示第i种零件的长 i w表示第i种 板材的宽 1 L表示板材的长 1 W表示板材的宽度 每一行第i种零件的个数可表 示为 1 i L l 则排样零件所占板材面积最大的目标函数为 1 max iii i L Szl w l 5 1 2 模型一的约束条件 1 存在排样零件面积不超过板材面积 即 1 11 0 iii i L W Lzl w l 2 每种参与排样的零件个数不能超过题目所给出的对应零件的个数 i M 每种 参与排样的零件由横放和竖放两部分构成 横放或竖放的个数为横放或竖放的行 数与每行摆放的个数的乘积 横放的个数为 1 i i L z l 竖放的个数为 1 9 9 i i L z l 则该约束条件为 11 9 9 iii ii LL zzM ll 19 i 3 排样的所有行宽度之和能超过板材宽度 即 18 1 1 067 iiii i z wWzzZ 5 1 3 整数规划模型一 综上所述 该限制条件下矩形零件排样优化问题的整数规划模型为 18 1 1 18 1 11 1 11 9 9 18 1 1 max 0 19 067 ii i i ii i i iii ii iiii i L zs l L W Lzs l LL stzzMi ll z wWzzZ 5 1 4 模型一的求解 对于上述线性规划 利用 LINGO 软件进行求解 得到最优排样方案 如下表所 示 零件编号 排样行数 排放方式 每行排放个数 1 3 竖放 45 3 1 横放 29 6 5 竖放 36 表一 模型一求解结果 排样零件总面积 2 2482170Smm 板材利用率 0 99 2868 S S 5 2 模型二的建立与求解 问题一第二问以排样零件占用板材面积最大为目标函数 每行的宽度应等于 某种零件的长度或宽度 每行内排样零件的宽度应不超过该行宽度 排样长度应 不超过板材长度 每种零件排样个数应不超过题目所给的限制为约束条件建立了 整数规划模型 5 2 1 模型二的目标函数 为了方便表示 依然将同一种零件的横放和竖放看作两种零件 即认为共有 18 种零件 以 j p表示第j行的宽度 i s表示第i种零件的面积 ij t表示第j行中 第i种零件的个数 则排样零件所占板材面积最大这一目标函数可表示为 1866 11 max ij i ij St s 5 2 2 模型二的约束条件 1 每行的宽度应等于某种零件的宽度或等于零 表示该行不排件 可表示为 0 118 166 ji pl llliiZjjZ 或 2 每行内排件的零件宽度应不超过该行宽度 可表示为 0 118 166 ijij ti ji jwpiiZjjZ 且且 4 每行内排件的零件总长度应不超过板材长度 可表示为 18 1 1 ij i ij i t l L p w 5 每种零件排样个数不应超过题目所给限制 可表示为 66 9 1 ijiji j ttM 5 2 3 模型二整数规划模型 综上所述 用于求解问题一第二问的整数规划模型为 1866 11 max ij i ij St s 18 1 1 66 9 1 0 118 166 0 118 166 01 118 166 ji ijij ij i ij i ijiji j ijij pl llliiZjjZ ti ji jwpiiZjjZ t l L p w stttM ttZ iiZ jjZ 或 且且 5 2 4 模型二的求解 行号 该行宽 度 排样总长 度 排样方式 1 15 2475 零件 1 并排排放 45 个 竖放 2 15 2475 零件 1 并排排放 45 个 竖放 3 15 2475 零件 1 并排排放 45 个 竖放 4 75 2495 零件 3 并排排放 28 个 横放 零件 1 竖放 每 5 个并 为一列 排放 2 列 共 10 个 5 176 2490 零件 6 并排排放 35 个 竖放 零件 1 横放 每 3 个并 为 1 列 排放 5 列 共 15 个 6 176 2490 零件 6 并排排放 35 个 竖放 零件 1 横放 每 3 个并 为 1 列 排放 5 列 共 15 个 7 176 2490 零件 6 并排排放 35 个 竖放 零件 1 横放 每 3 个并 为 1 列 排放 5 列 共 15 个 8 176 2430 零件 6 并排排放 36 个 竖放 零件 1 横放 每 3 个并 为 1 列 排放 1 列 共 3 个 9 176 2430 零件 6 并排排放 36 个 竖放 零件 1 横放 每 3 个并 为 1 列 排放 1 列 共 3 个 表二 模型二求解结果 排样零件总面积 2 2489688Smm 板材利用率 0 99 5875 S S 5 3 模型三的建立与求解 本问题是对既定宽度的卷材求解最小长度的排样优化问题 与模型二的背景 类似 该模型同样是针对无只能沿一个方向排样和一行只能排放同一种类零件的 约束的排样 区别于模型二 本模型的优化目标是卷材的使用长度最小 为了刻画零件在卷材上的排样情况 在板材上建立直角坐标系 用每一个零 件的左下角坐标 bibi xy和右上角坐标 aiai xy来描述零件安放位置 用 0 1 变量 i 表示该零件横排或纵排 5 3 1 卷材排样优化模型的目标函数 要求卷材使用长度最小 可转化为最末端排放的零件的右上角坐标 max ai x 最小 即 minmax ai x 5 3 2 卷材排样优化模型的约束条件 1 每个零件的左下角坐标与右上角坐标满足以下关系 wlyy wlxx ba ba 1 1 2 对于25种不同规格的零件 每一种排放的零件都对应一个右上角横坐标 ai x 则可用 1 n ai i ai x x 来表示排样零件的总数 排样的零件总数应等于该零件的需求量可 表示为 1 25 n ai i ai x x 3 任意两个零件之间不能存在重叠部分 若要保证满足此条约束 应满足 0 0 0 0 biaj bjai biaj bjai xx xx yy yy 中至少有一条成立 用阶跃函数 f x来表示以上关系 1 biajbjaibiajbjai f xxf xxf yyf yyij 5 3 2 卷材排样优化模型 1 2 minmax 1 25 0 1 0 1 ai biajbjaiqbiajbjai I ai i ai biiiii x f xxf xxf yyf yyij x stx yWlw f x 为阶跃函数 5 3 3 模型三的求解 图二 卷材排样方案 此时卷材最小利用长度为 40dm 6