下料问题含代码程序

实用下料问题优化模型实用下料问题优化模型 摘要摘要 关键字： 整数规划模型多目标决策优化 NP 问题 下料方案 分支定界法 1. 1.问题的重述问题的重述 “下料问题(cutting stock problem)”是把相同形状的一些原材料分割加工成若干 个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛 的应用. 这里的“实用下料问题”则是在某企业的实际条件限制下的单一材料的下料 问题。 现考虑单一原材料下料问题. 设这种原材料呈长方形，长度为L,宽度为W，现 在需要将一批这种长方形原料分割成m种规格的零件, 所有零件的厚度均与原材料 一致，但长度和宽度分别为(l 1,w1 ),,(l m ,w m )，其中wi＜l i  L, w i W,i 1,,m. m种零件的需求量分别为n 1 ,,n m .下料时，零件的边必须分别和原材料的边平行。 这类问题在工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相 等，即w i W,i 1,,m，则问题称为一维下料问题。 一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本， 提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料 方式来完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降 低效率。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的 限制。 因此实用下料问题的目标是在生产能力容许的条件下， 以最少数量的原材料， 尽可能按时完成需求任务, 同时下料方式数也尽量地小.就某企业考虑下面两个问 题： 1． 建立一维单一原材料实用下料问题的数学模型, 并用此模型求解下列问题， 制定 出在生产能力容许的条件下满足需求的下料方案, 同时求出等额完成任务所需的原 材料数，所采用的下料方式数和废料总长度.单一原材料的长度为 3000mm, 需要 完成一项有53种不同长度零件的下料任务. 具体数据见表一，其中l i 为需求零件的 长度，n i 为需求零件的数量. 此外，在每个切割点处由于锯缝所产生的损耗为5mm. 据估计，该企业每天最大下料能力是100块 ，要求在4天内完成的零件标号(i)为: 5,7,9,12,15,18,20,25, 28,36,48;要求不迟于6天完成的零件标号(i)为：4，11，24, 29,32,38,40,46,50. (提示：可分层建模。(1).先考虑用材料既少,下料方式又少的模型, 或先仅考虑所用材料最少的模型及增加一种下料方式大致相当于使原材料总损耗增 加0.08%情况下的最佳方案。(2).在解决具体问题时,先制定4天的下料方案,再制定6 天的下料方案,最后制定53种零件的下料方案. 这一提示对第2题也部分适用.) 表 1 需求材料的数据单位：mm i l i n i 1 1743 4 11 1105 8 21 830 30 31 610 30 41 320 8 51 255 192 2 1680 216 12 1055 2 22 795 8 32 600 212 42 515 8 52 184 57 3 1532 104 13 1046 4 23 766 4 33 590 108 43 414 8 53 155 24 4 1477 38 14 1032 8 24 745 4 34 588 482 44 411 60 5 1313 4 15 1030 8 25 730 34 35 582 196 45 405 136 6 1285 60 16 975 2 26 719 18 36 578 8 46 328 4 7 1232 4 17 893 8 27 714 4 37 540 32 47 313 68 8 1217 8 18 882 301 28 695 4 38 488 4 48 290 286 9 1180 6 19 847 6 29 645 90 39 355 52 49 275 602 10 1177 10 20 845 38 30 630 30 40 343 42 50 265 286 i l i n i i l i n i i l i n i i l i n i i l i n i 2． 建立二维单一原材料实用下料问题的数学模型, 并用此模型求解下列问题.制定 出在企业生产能力容许的条件下满足需求的下料方案, 同时求出等额完成任务所需 的原材料块数和所需下料方式数.这个问题的单一原材料的长度为 3000mm,宽度为 100mm, 需要完成一项有43种不同长度和宽度零件的下料任务. 具体数据见表二， 其中l i ,w i ,n i 分别为需求零件的长度、宽度和数量.切割时的锯缝可以是直的也可 以是弯的，切割所引起的锯缝损耗忽略不计.据估计，该企业每天最大下料能力是20 块 要求在4天内完成的零件标号(i)为: 3,7,9,12,15, 18, 20, 25, 28, 36. 表 2 需求材料的数据单位：mm i l i w i n i 1 1105 30 24 2 1055 20 6 3 1046 50 12 4 1032 30 24 5 1030 20 24 6 995 60 57 7 893 30 24 8 882 20 1001 9 847 30 20 10 845 30 108 i l i w i n i 11 830 30 90 21 630 30 90 31 420 20 40 41 255 30 692 12 795 20 40 22 600 35 612 32 415 30 24 42 184 20 357 13 766 35 12 23 590 20 508 33 414 20 40 43 155 50 52 14 745 30 12 24 588 20 2082 34 411 30 180 15 732 30 68 25 582 30 496 35 405 20 536 16 722 45 74 26 578 20 24 36 328 30 12 17 714 50 10 27 540 50 62 37 313 50 128 18 690 30 12 28 488 20 20 38 290 30 686 19 665 20 270 29 455 20 162 39 275 20 2002 20 633 30 90 30 434 30 92 40 265 30 686 i l i w i n i i l i w i n i i l i w i n i 2. 2.问题的分析问题的分析 本文要解决的是一个典型的多目标决策优化问题。一个好的下料方案首先应该 使原材料的利用率最大，从而减少损失，降低成本，提高经济效益。其次要求所采 用的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产 中转换下料方式需要费用和时间，既提高成本，又降低效率，故企业都希望尽可能 地减少下料方式的数目。此外，每种零件有各自的交货时间，每天下料的数量受到 企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下，在规 定的时间需求内，以最少数量的原材料，尽可能按时完成需求任务，同时下