二维实用下料问题的数学模型及较优解 (1).pdf

1994 2010 China Academic Journal Electronic Publishing House All rights reserved 第36卷第7期 2006年7月 数学的实践与认识 MATHEMATICS IN PRACTICE AND THEORY Vol136 No17 July 2006 二维实用下料问题的数学模型及较优解 王 娟 温阳俊 东南大学数学系 南京 210096 摘要 二维下料问题是2004年首届全国部分高校研究生数学建模竞赛B题 建立了二维下料问题的数学 模型 找到了用料451块 下料方式数为37的较优解 并证明了此问题总用料的下界是449块 关键词 二维下料模型 下料方式 下界 减少损失的比率 二维实用下料问题是全国研究生数学建模竞赛的赛题 详细题目见 1 由于竞赛时间 限制 还有一些问题有待解决 1 数学模型 对于二维下料问题 要考虑零件长 宽两个方向上的限制 因而比一维下料问题复杂得 多 此问题还要求集合D中的零件必须在第一阶段 前四天 完成 企业每天的下料能力是 20块 我们的目标是尽可能节省原材料 并采用尽量少的下料方式 min k j 1 bj min k j 1 bj 其中 k是全部可行下料方式数 bj 1 bj 0 0 bj 0 s t k j 1 aijbj ni i 1 2 m aij 第i号零件在第j种方式下切得的个数 bj 第j种下料方式耗材块数 k j 1 i D aij bj 80 D 零件i i 3 7 9 12 15 18 20 25 28 36 即前4天必须完成的零件集合 1 2 li xijt L 1 2 li i 1 2 m j 1 k t 1 aij L W m 原材料的长 宽及待加工的零件规格种类 1 2 wi yijt W 1 2 wi i 1 2 m j 1 k t 1 aij li wi ni 第i号零件的长 宽 加工个数 xi1jk1 xi2jk2 1 2 li1 1 2 li2或yi1jk1 yi2jk2 1 2 wi1 1 2 wi2 1 i1 i2 m 1 k1 ai1j 1 k2 ai2j i1 i2 k1 k2 0 xijk yijk 第i号零件在第j种下料方式下切得第k块零件中心的横坐标 纵坐标 根据本题的特点 待加工的零件的宽只集中在50mm 30mm 35mm 20mm四种规格上 可 将二维问题转化为一维问题 对四种宽度且长3000的条材 分别用一维下料问题的方法寻 1994 2010 China Academic Journal Electronic Publishing House All rights reserved 求四种宽度条材在一维情况下的最优方案 根据一维下料问题求解的方法 解多目标整数规划 可以得到两个阶段所使用的条材 具体方案见第3节 分别为 第一阶段 前四天 M20 152 M30 152 M50 6 第二阶段 四天后 M20 1062 M30 335 M35 125 M50 31 其中 M20 宽20的条材使用总数 其中个别零件调整放在更宽的条材上生产 然后 将上述四种宽度的条材进行搭配 按仅有的无损失的五种方式 1 50250 2 50230220 3 30230220220 4 35235230 5 202202202202 20 其下料块数记为m1 m5 进 行优化组合 即以原板材消耗块数最少为目标 建立整数规划模型 min m1 m2 m3 m4 m5 s t 2m1 m2 M50 m2 2m3 m4 M30 m2 2m3 5m5 M20 2m4 M35 利用matlab编程求解容易得到第一阶段最优解为 m1 3 m2 m4 m5 0 m3 76 用同样的方法得到第二阶段最优解为m1 0 m2 31 m4 63 m5 158 m3 120 这样得到所需原材料总量为451块 下料方式数为37种的下料方案 其中第一阶段使用 11种下料方式 第二阶段使用26种下料方式 2 二维下料问题最优解的下界 按零件总面积 没有损失 计算 完成生产任务所需原材料总量为4471592 448块 因 总会有一定损失 可以证明二维下料问题所需原材料总量的下界为449块 定理 完成生产任务所需原材料总量至少为449块 证明 要证明下界为449块 只需证明总损失大于01408块 生产分为第一阶段 前四 天 和第二阶段 四天后 如果第一阶段所有方案的损失都大于01408块 则显然定理成立 首先 有以下几个结论 1 不同交货期零件在两个阶段各自单独生产不能减少第一阶段已产生的损失 2 第一阶段中宽30的零件生产量大 是产生损失的主要原因 总损失不会小于在第一 阶段生产宽30的零件所产生的损失 3 第一阶段中宽30的零件 按零件面积 没有损失情况下 至少需要宽30的条材 148166 149条 第一阶段生产能力为80块 减去生产3号零件 l3 1046 w3 50 n3 12 所需3块 剩77块 按30230220220切割方式 宽度方面无损失 可生产宽30的条材154 条 3号零件切割后剩余原料 300021046 2 3 3000 01908块 如用来切割宽30的条材 按30230230210方式 可产生214516条 这样 第一阶段宽30的条材可生产15614516条 减 去148166条 这样生产完第一阶段任务后剩下宽30的条材最多为717916条 其长度为 717916 3000 2337418mm 为减少损失应用第一阶段中宽30的余料来生产第二阶段中宽 30的零件 若只使用448块板 则第一阶段中宽30的条材允许损失的长度的上界为01408 3000 100 30 4080mm 如果77块中有一块按30 30 30 10方式切割 已产生011块 602数 学 的 实 践 与 认 识36卷 1994 2010 China Academic Journal Electronic Publishing House All rights reserved 的损失 因此 若在第一阶段生产宽30的零件中损失大于4080 011 3000 100 30 3080mm 则定理成立 这种情况下 宽30的余料为76 2 3 214516 148166 817916条 其长度为2637418mm 以此类推 我们得到如下表格 表1 序号宽30可用剩余条材 条 宽30可用剩余料长度 mm 其他损失的上界 mm 71791623374184080 81791626374183080 91791629374182080 101791632374181080 1117916353741880 其次 第一阶段中25号零件 l25 582 w25 30 n25 496 生产量大 是第一阶段方案的关 键 若仅考虑先交货零件之间的搭配 则各有关下料方式的最小损失为 表2 序号 含25号零件 个数 每条条材 最小损失 mm 每条条材搭配方式总搭配 损失合计 mm 1含1个58234582 847 2 69010个582 20个847 10个690340 2含2个58250582 2 893 212个582 12个893300 3含3个58233582 3 893 32836个582 12个893 12个328396 4含4个58239582 4 633360个582 90个6333510 5含5个58290582 575个5821350 通过验证 此搭配为第一阶段生产25号零件最好的下料方式 还剩3个582 68个732 2个 690零件必须生产 其中732必按732 4方式生产 此时损失为 3000 732 4 68 4 1224mm 这时总损失为340 300 396 3510 1350 1224 7120mm 还剩3个582 2个 690未生产 故要完成第一阶段的任务 总损失必大于7120mm 因为第一阶段剩余生产能力 用来生产第二阶段的零件可以减少损失 所以 如果对于表 1 重新安排下料方案后减 少的损失不大于7120 4080 3040mm 或者对于表 1 重新安排下料方案后减少的损失 不大于7120 3080 4040mm 则定理成立 其他情况以此类推 下面 我们仅考虑表 1 的情况 表2中 只含有第一阶段的任务 在第4列中 如果用第二阶段的任务替换除25号零件 的其他零件 如果减少损失的比率 减少损失的长度 增加的第二阶段任务的长度 都小 于01125 3040 2337418 那么结论得证 例如 序号3中 只替换893 替换范围893 926 找到一组 633 290 其中633为第一阶段任务 290为第二阶段任务 减少损失的比率为 633 290 893 290 011034 01125 但进一步考虑 序号2中 被替换掉的893 2必须在 7027期王 娟 等 二维实用下料问题的数学模型及较优解 1994 2010 China Academic Journal Electronic Publishing House All rights reserved 第一阶段生产 通过穷举每个宽30长3000的条材 只能生产1个 2个或3个893零件 其造 成的新损失如表3 表3 序号含893个数每条板条最小损失 mm 再生产一个893产生的新损失 mm a含3个8933110133 b含2个8934824 c含1个8931010 那么这2个893只有按其他方式进行生产 如表3序号c 新损失为10 2 20mm 因 此减少损失的比率实际为 847 732 255 893 2 20 255 0111 01125 如果893与 第二阶段零件搭配 则减少损失比率中的分母变大了 同样可证小于01125 对于表1中其他情况 由于第4列中其他损失的上界变小了 同样可证定理成立 3 目前已知最好方案 目前 网上有一个451块的下料方案和一些大于451块的下料方案 可惜 经验证 这个 451块的方案没有生产出全部零件 我们已经证明了下界是449块 下面给出的451块方案 很接近449块 因此 它有可能就是二维下料问题的最优解 第一阶段 前4天 的下料方案 其中 30 i 表示宽30的板条的第i种下料方式 588 2 是指长度为588mm的零件裁两 块 宽为20的条材 共152根 编号下料方式废料条材数编号下料方式废料条材数 20 1 882 588 2 184 5 22 1420 5 882 795 588 2 1472 20 2 882 795 2 488401920 6 882 588 3 1841701 20 3 882 2 588 2 6082 20 4 588 5 6033 20 7 588 2 488 10552811 宽为30的条材 共152根 编号下料方式废料条材数编号下料方式废 料条材数 30 1 847 1105 103216130 6 893 2 582 2 5012 30 2 847 732 2 328 2 33 630 7 732 4 729 30 3 847 2 690 58234330 8 582 5 9021 30 4 633 582 4 399030 9 847 732 2 5821074 30 5 847 732 690 2 41 330 10 732 3 6901143 宽为50的条材 共6根 50 1 1046 2 540 313556 802数 学 的 实 践 与 认 识36卷 1994 2010 China Academic Journal Electronic Publishing House All rights reserved 具 体 方 案 搭配序号搭配方式搭配次数搭配序号搭配方式搭配次数 130 4 230 4 220 3 220 3 41730 3 230 10 220 4 220 4 3 230 8 230 8 220 4 220 4 10830 1 230 5 220 2 220 4 1 330 6 230 7 220 2 220 2 9930 5 230 5 220 4 220 4 1 430 2 230 4 220 1 220 1 61030 6 230 8 220 6 220 7 1 530 4 230 6 220 4 220 4 21150 1 250 1 3 630 9 230 9 220 1 220 5 2 第二阶段 四天后 的下料方案 宽为20的条材 共1061根 编号下料方式废料条材数编号下料方式废料条材数 20 1 1030 2 665 2750420 19 1030 578 275 5 171 20 2 405 4 275 184 6 1 320 20 882 2 665 275 2 21210 20 3 590 2 588 2 275 184 2 14220 21 1030 2 275 2 184 2 221 20 4 665 590 588 578 2 1 120 22 578 3 414 3 241 20 5 665 3 590 4141120 23 1055 1030 882331 20 6 455 2 420 3 414 2 2 6 20 7 414 2 405 4 275 2 2 3 20 24 590 2 588 455 275 2 184 4342 20 8 590 588 455 4 2120 25 1030 665 2 590501 20 9 882 665 590 455 40534220 26 882 2 590 2 56126 20 10 665 588 2 578 2 3 520 27 588 5 602 20 11 588 2 455 4 4120 28 1030 665 2 184 3 881 20 12 588 4 275 184 2 5 4320 29 1030 2 414 2 1121 20 13 578 3 420 3 6220 30 1030 2 275 184 3 1133 20 14 588 3 405 275 3 6 46220 31 1030 665 588 2 1291 20 15 882 2 590 455 18474220 32 588 578 420 4 1541 20 16 455 2 420 2 414 3 8520 33 455 2 420 2 405 2 2751651 20 17 1055 2 8828220 34 578 455 4 4051971 20 18 414 405 5 275 2 11 120 35 1030 588 3 2061 宽为30的条材 共334根 编号下料方式废料条材数编号下料方式废 料条材数 30 1 845 415 2 265 5 0 1230 10 1032 434 255 6 418 30 2 830 3 255 2 02430 11 845 434 3 290 2 265812 30 3 845 2 290 255 4 0 4230 12 290 3 265 8 1042 30 4 830 290 2 265 6 0 1830 13 745 290 5 265 3 106 30 5 630 2 290 6 03030 14 1105 1032 290 265 255532 9027期王 娟 等 二维实用下料问题的数学模型及较优解 1994 2010 China Academic Journal Electronic Publishing House All rights reserved 30 6 290 5 265 2 255 4 0 4830 15 1032 2 434 2 681 30 7 434 411 5 255 2 1 3630 16 1105 745 719 2901416 30 8 719 630 2 255 4 1 1230 17 1105 2 6301606 30 9 719 2 265 3 255 3 2 1830 18 1105 2 275 20宽 5151 宽为35的条材 共126根 编号下料方式废料条材数编号下料方式废 料条材数 35 1 600 5 0121 35 2 766 3 6001024 35 3 600 3 588 2宽为 20 241 宽为50的条材 共31根 编号下料方式废料条材数编号下料方式废 料条材数 50 1 975 540 2 313 3 6 450 4 540 2 313 5 155 2 4522 50 2 714 3 540 155 2 8 3 50 3 975 2 714 155 2 26 1 50 5 540 1105 宽 30 1032 宽 30 3231 具体方案 搭配 序号 搭 配 方 式 搭 配 次 数 搭配 序号 搭 配 方 式 搭 配 次 数 150 1 220 1 230 1 41430 5 230 7 220 20 220 20 30 250 2 220 2 230 1 31530 16 230 17 220 6 220 26 6 350 3 220 4 230 1 11630 7 230 13 220 14 220 14 6 450 4 220 3 230 2 221730 4 230 4 220 10 220 16 4 550 5 220 5 230 15 11820 3 220 12 220 12 220 24 220 24 20 635 3 235 1 230 18 11920 14 220 14 220 14 220 14 220 14 90 735 2 235 1 230 1 42020 20 220 20 220 20 220 20 220 20 18 835 1 235 1 230 6 482120 26 220 26 220 26 220 26 220 26 24 935 1 235 1 230 4 102220 7 220 12 220 24 220 27 220 30 2 1030 2 230 14 220 13 220 17 22320 7 220 8 220 10 220 11 220 12 1 1130 3 230 12 220 9 220 15 422420 16 220 18 220 19 220 21 220 22 1 1230 9 230 10 220 20 220 20 182520 23 220 25 220 28 220 29 220 30 1 1330 8 230 11 220 20 220 20 122620 31 220 32 220 33 220 34 220 35 1 参考文献 1 朱道元 首届全国部分高校研究生数学建模竞赛 J 数学的实践与认识 2005 35 7 1 16 2 倪勤 实用下料问题的评注 J 数学的实践与认识 2005 35 7 71 7