实用下料问题 - 同济大学数学系

实用下料问题实用下料问题 一 问题的重述一 问题的重述 下料问题 cutting stock problem 是把相同形状的一些原材料分割加工成若干个 不同规格大小的零件的问题 此类问题在工程技术和工业生产中有着重要和广泛的应用 这 里的 实用下料问题 则是在某企业的实际条件限制下的单一材料的下料问题 现考虑单一原材料下料问题 设这种原材料呈长方形 长度为 宽度为 现在需要LW 将一批这种长方形原料分割成种规格的零件 所有零件的厚度均与原材料一致 但长度和m 宽度分别为 其中wi 种零件的需求量分别 11mm wlwl miWwLl ii 1 m 为 下料时 零件的边必须分别和原材料的边平行 这类问题在工程上通常简称为 m nn 1 二维下料问题 特别当所有零件的宽度均与原材料相等 即 则问题称为miWwi 1 一维下料问题 一个好的下料方案首先应该使原材料的利用率最大 从而减少损失 降低成本 提高经 济效益 其次要求所采用的不同的下料方式尽可能少 即希望用最少的下料方式来完成任务 因为在生产中转换下料方式需要费用和时间 既提高成本 又降低效率 此外 每种零件有 各自的交货时间 每天下料的数量受到企业生产能力的限制 因此实用下料问题的目标是在 生产能力容许的条件下 以最少数量的原材料 尽可能按时完成需求任务 同时下料方式数 也尽量地小 现在我们要为某企业考虑下面两个问题 1 建立一维单一原材料实用下料问题的数学模型 并用此模型求解下列问题 制定出 在生产能力容许的条件下满足需求的下料方案 同时求出等额完成任务所需的原材料数 所 采用的下料方式数和废料总长度 单一原材料的长度为 3000mm 需要完成一项有53种不同 长度零件的下料任务 具体数据见表一 略 其中 为需求零件的长度 为需求零件的 i l i n 数量 此外 在每个切割点处由于锯缝所产生的损耗为5mm 据估计 该企业每天最大下料 能力是100块 要求在4天内完成的零件标号 为 5 7 9 12 15 18 20 25 28 36 48 要i 求不迟于6天完成的零件标号 为 4 11 24 29 32 38 40 46 50 i 2 立二维单一原材料实用下料问题的数学模型 并用此模型求解下列问题 制定出在企 业生产能力容许的条件下满足需求的下料方案 同时求出等额完成任务所需的原材料块数和 所需下料方式数 这个问题的单一原材料的长度为 3000mm 宽度为100mm 需要完成一项有43 种不同长度和宽度零件的下料任务 具体数据见表二 略 其中 分别为需求零件的 iii nwl 长度 宽度和数量 切割时的锯缝可以是直的也可以是弯的 切割所引起的锯缝损耗忽略 不计 据估计 该企业每天最大下料能力是20块 要求在4天内完成的零件标号 为 i 3 7 9 12 15 18 20 25 28 36 二 问题的分析二 问题的分析 在生产实践中 经常会遇到如钢材 木材等条型材的下料问题 即如何根据原材料的长 度 零件的尺寸以及需求量确定出使原材料消耗最少的最优下料方案 本题要求 在生产能 力容许的条件下 以最少数量的原材料 尽可能按时完成需求任务 同时下料方式数也尽量 地小 对于一维下料问题 首先我们必须找出全部可行的下料方式 然后才能确定下料方式作 为决策变量和形式约束条件的结构系数 这样才能建立优化决策模型 通过计算机编程计算 得到我们所需要的最优下料方案 考虑到这里是单一原材料下料问题 这大大减少了下料方 式 但由于零件的种类有 53 种之多 因此下料方式仍然很多 计算量很大 所以在建立优 化模型的基础上 我们需要找到比较合适的算法来解决这类实际问题 近年来 国内外关于 这方面的研究比较活跃 并涌现出了不少近似算法 如 Gilmore 与 Gomory 用线性规划建立 的一刀切问题的数学模型 Dyckhoff 提出的线性规划方法以及 Sarker 提出的动态规划方法 等 由于下料问题属于布局问题 不同于一般的数值性优化 近年又出现应用遗传算法来求 解下料优化问题 我们力图建立一种实用的模型 多目标整数规划模型多目标整数规划模型 1 2 7 并提出 一种新的优化思想方法 启发式多层次逐层优化方法启发式多层次逐层优化方法 解决此问题 同时与其他的求解方 法进行比较 对于二维下料问题 我们采用分类层次分析法分类层次分析法 由于原材料的长度为 3000mm 宽度为 100mm 而 43 种零件的长度最小的为 155mm 这样就不会出现零件的长边在原材料的宽边上 切割的情况 也就是说零件的长边都是顺着原材料的长边切割的 考虑到零件的宽有 20 30 35 50 mm 这 4 种规格 为了尽量节省材料 我们应该使原材料在宽边上尽量利 用完全 这样只有几种宽边完全利用的组合方式 5 种 分别为 50 50 50 30 20 30 30 20 20 35 35 30 20 20 20 20 20 我们把零件按宽边的规格分为 4 类 20 30 35 50 对每一类都可按问题一的处理一维下料问题的方式找最优的方案 然 后再把他们按上述的几种方式进行组合 以求得最优解 三 问题的假设三 问题的假设 1 对于第一问的假设 1 在每个切割点处由于锯缝所产生的损耗为 5mm 2 企业每天的最大下料能力为 100 块 3 考虑下料方式的数量对总损耗的影响 下料方式越少则原材料总损耗越小 4 对于剩余长度为mm 的材料 可以通过细微调整锯缝的位置锯得长度为 50 yyx mm 的零件 x 2 对于第二问的假设 1 切割所引起的锯缝损耗忽略不计 2 切割时锯缝可以是直的也可以是弯的 但要求转弯为直角 3 企业每天最大的下料能力是 20 块 4 原材料和零件都是长方形 四 符号说明四 符号说明 原材料的长度 3000mm LL 原材料的宽度 100mm WW 所用的原材料总数量N 所采用的下料方式总数量K 第 i 号零件的长度 单位 mm i lLli 53 2 1 i 第 i 号零件的宽度 i wWwi 第 i 号零件的需求量 i n 第 j 种下料方式中切割第 i 号零件的数量 ij a 按第 j 种下料方式切割的原材料的数量 j x 按第 j 种下料方式切割的废料长度 mm j c 第一问中要求在 4 天内完成的零件号的集合 1 G 4836282520181512975 1 G 第一问中要求在不迟于 6 天完成的零件号的集合 2 G 50 46 40 38 32 29 24 11 4 2 G 第二问中要求在 4 天内完成的零件号的集合 3 G 36 28 25 20 18 15 12 9 7 3 3 G 五 模型的建立与求解五 模型的建立与求解 1 对问题一的解决 此问要求 在4天内完成的零件标号 为 5 7 9 12 15 18 20 25 28 36 48 不迟于i 6天完成的零件标号 为 4 11 24 29 32 38 40 46 50 而该企业每天最大下料能力是100i 块 我们要制定出在生产能力容许的条件下满足需求的下料方案 同时要求等额完成任务 我们的目标是要尽可能节省材料 尽可能用少的下料方式 为此我们建立多目标整数规划模型多目标整数规划模型 首先我们约定 0 0 0 1 j j xMinN j j j x x MinK TS 且为整数 且为整数 0 0 6100 4100 53 2 1 min 5 5 5 21 21 1 1 531 53 1 53 1 j ij GGij GGi ij jij Gij Gi ij jij j ijij i i i iij i iij x a a xa a xa inxa jllaL jLla 注 注 1 我们有 若采用了第 j 种下料方式 则为大于 0 的整数 因此 若没有采 j x1 j j x x 用第 j 种下料方式 则为 0 如上定义可得 这样即表示了所用 j x0 0 0 j j x x j j j x x K 的下料方式数量 2 约束中第一条是 考虑了锯缝时 原材料长度 L 对下料方式的限制 即对于任意一 种下料方式 所得到的零件总长度与锯缝总长度之和要小于等于 L 3 约束中第二条是 考虑了锯缝时 对于每一种下料方式的废料长度要小于零件的最 小长度 4 约束中第三条是 为了满足题中要求的等额完成任务的限制条件 5 约束中第四条是 为了满足在企业每天生产能力是 100 块时 要求在 4 天内完成零 件集合的条件 其中表示第 j 种下料方式中所切割的第 i 种零件数占这种下料方式 1 G 1 Gi ij jij a xa 中所切割的零件集合中零件数的权数 因此表示了完成零件集合所用的 1 G 1 1 Gij Gi ij jij a xa 1 G 原材料数 又由于在 4 天内要完成零件集合 故上述所算出的所用的原材料数要小于等 1 G 于 注意若 即表示第 j 种下料方式中没有切割到零件集合中的零件 4100 0 1 Gi ij a 1 G 因此 这样按照注释 1 中的约定 可知正好表示 这种下料方式不产 1 0Giaij 0 0 0 生集合中的零件 故而这条约束很完善 1 G 6 约束中第五条和第四条的解释类似 约束中第六条和第七条表示和要取整数 ij a j x 对于废料的度量 由于存在锯缝为 5mm 对任何一种可行的下料方式 jjj aaa 5321 则其满足条件 所以如果单纯的用来度量此种下料方式的Lla i iij 5 5 53 1 53 1 5 i iij laL 废料是不对的 这可能取到负值 实际上 又由于对问题一有假设 4 我们可以知道 对所 有满足的下料方式来说 废料都为 0 故而我们可以得到废料的度量方式 0 5 53 1 i iij laL 时 当 时 当 0 5 0 0 5 5 53 1 53 1 53 1 i iij i iij i iij j laL laLlaL c 经过数学处理 得到 2 5 5 53 1 53 1 i iij i iijj laLlaLc 因此废料总量为 j jjx cC 废弃率定义为 j j j jj j j xxcxCq3000 3000 利用率定义为 j j j jj j j xxcxCqp3000 13000 11 对于此模型 即 1 式 的求解比较困难 我们需要首先分解此模型 然后创建适应 的优化算法解决此问题 表第 j 种下料方式 jjj aaa 5321 1 当前最优的下料方式的模型 多层整数线性规划模型多层整数线性规划模型 a 当时 求最优的一种下料方式的数学模型为 0 1 Gi i n 2 53 1i iil aMaxS TS 1 53 1 1 0 5 5 ga na Lla Gi i ii i ii 且为整数 其中表一种下料方式 为努力程度 定义为某种下料方式中含有集合 5321 aaa 1 g 中零件的个数 从中我们可以看出越大零件集合完成得越快 1 G 1 g 1 G b 当且时 求最优的一种下料方式的数学模型为 0 1 Gi i n0 2 Gi i n 3 53 1i iil aMaxS TS 2 53 1 2 0 5 5 ga na Lla Gi i ii i ii 且为整数 为努力程度 类似的定义和理解 2 g 1 g c 当且时 求最优的一种下料方式的数学模型为 0 1 Gi i n0 2 Gi i n 4 53 1i iil aMaxS TS 且为整数 ii i ii na Lla 0 5 5 53 1 这三个模型都是整数线性线性规划问题 可以用分支定界法求解 亦可用 lingolingo 直接编程 见附录程 见附录程 2 2 序九 序九 可以很快计算得结果 也可以用 matlab7 0matlab7 0 3 编程算得 2 针对模型 我们创建适应性的算法 启发式多层次逐层优化方法启发式多层次逐层优化方法 此 方法的基本思想是 在每层求解时 对于上层剩余的未完成的各零件数目 利用上面三个子 模型可以在当前可行的下料方式中选择最优的一种下料方式进行下料 并尽可能的重复使用 此种下料方式 这是为了使得下料方式尽可能少 然后对剩余的未完成的各零件重新优化 选取新的最优的一种下料方式 不断反复上面的操作 直到所有剩余的未完成的各零件数目 都减少到 0 为止 这样原问题的最优解就是各个层次优化问题所求得的最优下料方式的总和 3 启发式多层次逐层优化方法启发式多层次逐层优化方法的计算方法 将上述当前最优下料方式的三种模型的计算求解作为启发式多层次逐层优化方法计算的 子程序 在每级求解中 对于相应的条件重复调用相应的子程序 完整的求解过程如下 Step1 初始给定了未完成的各零件的数目 4 天要完成 53215312111 nnnnnn 的零件集合 6 天要完成的零件集合 在上一层 j 层 得到的未完成的各 111 GG 221 GG 零件的数目基础上 判断和是否成立 然后依判定条件 jjj nnn 5321 0 1 j Gi ij n0 2 j Gi ij n 调用 1 中相应的当前最优下料计算子程序 求解得到最优下料方式 并以 jjj aaa 5321 此作为这一级的下料方式 Step2 计算此种下料方式的重复次数 即用此种下料方式切割的原材料 L 的根数 j j j j j j j a n a n a n x 53 53 2 2 1 1 min Step3 计算去掉根按这种下料方式切割后 余下的未完成的各种零件的数量 j x jjjjjjjjjj aaaxnnnnnn 532153211531211 Step4 将上一步得到的作为新一层优化计算的给定值 并记 1531211 jjj nnn 令 0 1 ijj niH jjj HGG 111jjj HGG 212 如果则优化计算结束 否则转 Step1 重新判断并调用当前最优 0 1531211 jjj nnn 下料方式计算子程序 求得新一层的下料方式和重复次数 Step5 各层最优下料方式及其重复次数的集合即为启发式多层次逐层优化方法的最终 结果 即和的值 jjj aaa 5321 j x 算法流程如图如图 1 1 所示 给定L li ni j 1 求出当前最优最优下料方式子程 a1j a2j amj xj min n1j n2j nmj n ni ij j 1 1 n ni ij j d d a ai ij j nij 1全为0 j j 1 保存下料方式重 复次数 停止 否 是 主程序子程序 动态整数规划求 下料方式 输入当前还需零件 数 n1 n2 nm 还有4天必须完成的零件数吗 整数线性规划求较优 下料方式 输出下料方式向量 还有6天必须完成的零件数吗 是 否 是 图图 1 1 算法流程 用 matlab 编程可对问题一进行计算求解 见附录见附录 2 2 程序四程序四 求解的结果为 所用的原 材料的数量为 根 所用的下料方式为 废料总长度为 803 N80 KmmC16167 废弃率为 利用率为 同时从数据中可以看出 采用这种 67 0 q 33 991 qp 方案 只需要 4 天半就可以完成问题一中要求的 6 天内必须完成的零件的要求 该方案对原 材料的利用率非常高 效果很好 具体下料方式数据见附录附录 1 1 表表 1 1 2 对于问题二的解决 这是一个二维下料问题 6 11 这里采用分类层次分析法分类层次分析法 首先我们分析该问题的特点 由于原材料的长度为 3000mm 宽度为 100mm 而 43 种零件的长度最小的为 155mm 这样就 不会出现零件的长边在原材料的宽边上切割的情况 也就是说零件的长边都是顺着原材料的 长边切割的 考虑到零件的宽有 20 30 35 50 mm 这 4 种规格 为了尽量节省材料 我们应该使原材料在宽边上尽量利用完全 这样只有几种宽边完全利用的组合方式 5 种 分别为 50 50 50 30 20 30 30 20 20 35 35 30 20 20 20 20 20 我们把零件按宽 边的规格分为 4 类 20 30 35 50 对每一类都可按问题一的处理一维下料问题的方式 找最优的方案 然后再把他们按上述的几种方式进行优化组合 最后再对优化组合剩余的部 分进行考虑 为此我们建立分类逐层分析模型分类逐层分析模型 1 第一层次 首先优先考虑宽度的特征 我们把零件按宽边的规格分为 4 类 20 30 35 50 对每一类都可按问题一的用于处理一维下料问题的多目标整数规划模型和启发式 多层次逐层优化方法方式找最优的方案 用 mablab 编程 见附录附录 2 2 程序七 八程序七 八 得到结果 具体下料方式数据见附录附录 1 1 表表 2 2 从中我们可以得到各类宽度零件所需要的长条数为 长为 3000mm 宽与零件相对应的长条 1 4 天为 152 20 N152 30 N6 50 N 4 天后为 1061 20 N335 30 N126 35 N31 50 N 2 第二层次 由于宽边若没有填满 对整个板材的利用影响非常大 所以我们要求在宽 边上要尽量填满 即 尽量没有费余的 因此我们在上一层次得到结果的基础上 我们运 用上面给出的几种最优的组合方式进行优化组合 50 50 50 30 20 30 30 20 20 35 35 30 20 20 20 20 20 设采用第 i 种组合的次数为 则可建立整数线性规划模型 以求得所应1 2 3 4 5i i m 采用的各种组合的次数 模型如下 2 2 2 52 21504354323053220 mmNmNmmmNmmmNMinY TS 5 5 4 3 2 10 2 2 2 52 5021 354 30432 20532 im Nmm Nm Nmmm Nmmm i 且为整数 利用 lingo 编程 见附录附录 2 2 程序十程序十 可以很快求解出此整数线性规划的最优解为 1 4 天为 3 1 m0 2 m76 3 m0 4 m0 5 m0 MinY 4 天后为 0 1 m31 2 m120 3 m63 4 m158 5 m1 MinY 可知 1 4 天可以实现恰好的组合 而 4 天后的部分则余下一个宽为 30 的长条 1 4 天 所用的原材料总数为 79 54321 mmmmmN 4 天后所用的原材料总数为 3731 54321 mmmmmN 其中 1 表示余下的一个宽为 30 的长条要占用一块原材料 则所用的原材料的总数为 N 79 373 452 3 第三层次 对上述优化组合后 剩余的部分进行分析 即对第二层中优化模型求出最优解后 所剩 余的部分进行研究 对于上一层次中 1 4 天的情形 没有余下的长条 故可不考虑这一层 对于上一层次中 4 天后的情形 余下的一块宽为 30 单位 mm 下同 的长条 我们 选废料长度最长的那一块进行讨论 将这一长条再分解为零件 然后寻找其他的宽度的废料 块 看能否用这些废料来切割得到那个宽为 30 的长条上的零件 若可以做到这一点 则这 块余下的长条就被消化掉了 若不可以 则这块长条就要占用一块原材料 利用这种思想方法 结合附录表 2 的下料数据 我们很容易找到浪费最多的那块宽为 30 的长条 1105 1032 切割组合 同时可以找到宽为 35 的有长为 1200 的废料 宽为 50 的 有长为 2460 的废料 这样我们可以 1105x30 和 1032x30 的零件用 2460 x50 这块废料来切割 得到 这样我们就消化掉了余下的这个长条 因此 利用这种处理方法可以节省一块原材料 故所用的原材料总数为 N 452 1 451 通过如上我调整后 得到数据见附录附录 1 1 表表 3 3 计算废料面积为 mmnwlNC i iii 1040880103425912 1 10353 1 1003000 88 43 1 废弃率为 77 0 1003000 NCq 利用率为 23 991 qp 4 第四层次 在此基础上 即上面模型所求得的各组合最优数量 再考虑怎样使下料方式尽量少 从第二层次得到 1 4 天的 3 块 50 50 76 块 30 30 20 20 4 天后的 31 块 50 30 20 120 块 30 30 20 20 63 块 35 35 30 158 块 20 20 20 20 20 同时要用到第三层次中 调整后的数据表数据表 3 3 为了使下料方式最少 我们制定下述的下料方式搭配规则 算法 对于 1 4 天的 a 首先考虑组合 50 50 可知这里只有一种下料方式 1 4 天宽 50 1 1 4 天宽 50 1 数量为 3 注注 1 4 天宽 50 i 表示 1 4 天中宽为 50 的下料方式中的第 i 种下 料方式 b 再考虑组合 30 30 20 20 令表示 1 4 天宽为 20 的第 i 种下料的数量 i m 20 i 1 7 表示 1 4 天宽为 30 的第 k 种下料的数量 k 1 10 再令 k m30 表示在此组合下第 j 种下料方式是 1 4 天宽 20 1 jjjj aaaa 10 30 1 30 7 20 1 20 1 4 天宽 20 7 1 4 天宽 30 1 1 4 天宽 30 10 表示第 j 种下料方式采用 j x 的次数 则我们可建立整数规划模型 注意 同上文约定 0 0 0 6 j j j x x MinK TS 且为整数 其中 且为整数 0 00 2 2 4321 30 20 20 20 10 1 20 7 1 20 j jiji k k jk i j ji k jk i ji x iiiiiaa kma ima ja ja 求解此整数规划模型可以得到最优的下料方式 使得下料方式数最小 计算结果为 需 要原材料的块数为 下料方式为 11 种 见附录附录 1 1 表表 4 4 79 N 对于 4 天后的 用同样的方法可计算得到结果为 需要原材料的块数为 下料372 N 方式为 26 种 见附录附录 1 1 表表 5 5 故而总的下料方式数为 K 37 下料方式为 表 4 加上表 5 综上第一到第四层 我们就解决了问题二 需要原材料的块数为 需要的下451 N 料方式数为 废料总面积为 废弃率为 原材料的37 KmmC1040880 77 0 q 利用率为 23 991 qp 六 模型和算法的分析与评价六 模型和算法的分析与评价 1 模型的评价 对于问题一所建立的多目标整数规划模型 很准确的概括了该问题的所有约束和目标 从理论上讲是一个很严谨的模型 但是对于这一模型的求解却是非常困难的 必须寻找比较 好的算法支持它 而文中我们提出的启发式多层次逐层优化方法 4 5 就很好的支持了这个模 型 并且有很好的求解效果 材料的利用率很高 废料很少 计算速度快 结果很好 此 模型和算法适应能力强 求解结果好 有很强的普遍性和实用性 对于问题二所建立的分类逐层分析模型较好的解决了问题二 此方法根据具体问题的具 体特点进行分析 找出针对性的解决方案 这样我们同样得到较好的结果 材料利用率高 计算速度快 但此模型有一定的缺陷 没有很强的普遍性 为适应某一特殊问题都需要具体 的分析计算 寻求针对性的方案 2 算法的评价 分析和比较 一维下料问题 8 9 10 是组合优化中的一个经典问题 从计算的复杂性理论上看 优化 下料问题属于 NP 难问题 即至今还不存在多项式算法 NP 难问题的求解通常采用基于线 性规划的方法 分支定界法 启发式算法 模拟退火算法 演化算法 遗传算法等 这些方 法都能在一定程度上得到最优解或者次优解 我们的启发式多层次逐层优化方法在获得高的 材料利用率的同时 在计算时间和存储空间上都具有优势 七 结果分析七 结果分析 1 对于第一问的结果 在不考虑天数限制的情况下 我们运用问题一中建立的多目标 整数规划模型及本文新建的启发式多层次逐层优化算法 用 matlab 编程 见附录附录 2 2 程序二程序二 可以得到结果为 根 所用的下料方式为 废料总长度为 802 N73 K 废弃率为 利用率为 具体数据见附录附录 1 1mmC12856 53 0 q 47 991 qp 表表 6 6 而在考虑问题一中天数限制的情况下 我们得到结果为 所用的原材料的数量为 根 所用的下料方式为 废料总长度为 废弃率为 803 N80 KmmC16167 利用率为 67 0 q 33 991 qp 比较两个结果 很容易看出此模型和算法解决此问题的高效性 在增加限制条件之后仍 然可以找到与没有限制情况近似的解答 并且原材料的利用率非常之高 可以基本保持在 99 以上 因此从这个意义上说 我们得到的解是非常优的 2 对于第二问的结果 在不考虑天数限制的情况下 我们运用问题二的处理方法 可 以得到结果为 具体数据见附录附录 1 1 表表 7 7 351213 20 N484 30 N126 35 N36 50 N 块 50 30 20 193 块 30 30 20 20 63 块 35 35 30 158 块 20 20 20 20 20 余下三块 宽度为 20 30 50 的各一块 这样我们需要原材料数为 449 1 450 下料方式数为 K 36 废料总面积为 C 740880mm 原材料的利用率为 p 99 45 而在考虑问题二中天数限制的情况下 我们得到结果为 需要原材料的块数为 N 451 需要的下料方式数为 K 37 废料总面积为 废弃率为 原mmC1040880 77 0 q 材料的利用率为 23 991 qp 比较两个结果 同样可以看出此模型和算法解决此问题的高效性 在增加限制条件之后 仍然可以找到与没有限制情况近似的解答 并且原材料的利用率非常之高 可以基本保持在 99 以上 因此从这个意义上说 我们得到的解是非常优的 八 八 模型和算法的改模型和算法的改进与推广进与推广 从本文的两个问题的解决可看出 针对本问题将多目标整数规划模型分解为多层整数多层整数 线性规划模型线性规划模型和启发式多层次逐层