《第七轮含代码程序》由会员分享，可在线阅读，更多相关《第七轮含代码程序（36页珍藏版）》请在金锄头文库上搜索。
1、实用下料问题优化模型摘要关键字：整数规划模型 多目标决策优化 NP 问题 下料方案 分支定界法1.问题的重述“下料问题 (cutting stock problem) 是把相”同形状的一些原材料分割加工成若干 个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛 的应用 . 这里的 “实用下料问题 ”则是在某企业的实际条件限制下的单一材料的下料 问题。现考虑单一原材料下料问题设这种原材料呈长方形，长度为L,宽度为W，现 在需要将一批这种长方形原料分割成 m种规格的零件，所有零件的厚度均与原材料 一致，但长度和宽度分别为(li,wj, ,(lm,Wm)，其中wiVli L,
2、Wi W, i 1, ,m . m种零件的需求量分别为ni, ,nm.下料时，零件的边必须分别和原材料的边平行。 这类问题在工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相 等，即Wi W,i 1, ,m,则问题称为一维下料问题。一个好的下料方案首先应该使原材料的利用率最大， 从而减少损失， 降低成本， 提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料 方式来完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降 低效率。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的 限制。因此实用下料问题的目标是在生产能力容许的条件下， 以
3、最少数量的原材料， 尽可能按时完成需求任务 , 同时下料方式数也尽量地小 .就某企业考虑下面两个问 题：1 建立一维单一原材料实用下料问题的数学模型 , 并用此模型求解下列问题， 制定 出在生产能力容许的条件下满足需求的下料方案 , 同时求出等额完成任务所需的原 材料数，所采用的下料方式数和废料总长度 . 单一原材料的长度为 3000mm, 需要 完成一项有 53种不同长度零件的下料任务 . 具体数据见表一，其中 li 为需求零件的 长度， ni 为需求零件的数量 . 此外，在每个切割点处由于锯缝所产生的损耗为 5mm. 据估计，该企业每天最大下料能力是100块，要求在4天内完成的零件标号(i
4、)为： 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 需求材料的数据单位： mmi12345678910li17431680153214771
5、31312851232121711801177山42161043846048610i11121314151617181920li110510551046103210309758938828478458248828301638i21222324252627282930li830795766745730719714695645630308443418449030i31323334353637383940li6106005905885825785404883553433021210848219683245242i41424344454647484950li3205154144114053283132
6、90275265山88860136468286602286i515253li25518415519257242.建立二维单一原材料实用下料问题的数学模型，并用此模型求解下列问题.制定 出在企业生产能力容许的条件下满足需求的下料方案，同时求出等额完成任务所需 的原材料块数和所需下料方式数.这个问题的单一原材料的长度为3000mm,宽度为100mm,需要完成一项有43种不同长度和宽度零件的下料任务.具体数据见表二， 其中li,Wi,ni分别为需求零件的长度、宽度和数量.切割时的锯缝可以是直的也可 以是弯的，切割所引起的锯缝损耗忽略不计.据估计，该企业每天最大下料能力是20 块 要求在4天内完成的零
7、件标号（i）为：3,7,9,12,15,18, 20, 25, 28, 36.表2需求材料的数据单位：mmi12345678910li11051055104610321030995893882847845wi30205030206030203030ni2461224245724100120108i11121314151617181920li830795766745732722714690665633wi30203530304550302030904012126874101227090i21222324252627282930li630600590588582578540488455434wi3
8、0352020302050202030山90612508208249624622016292i31323334353637383940li420415414411405328313290275265wi20302030203050302030402440180536121286862002686i414243li255184155wi302050n692357522问题的分析本文要解决的是一个典型的多目标决策优化问题。一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料
9、方式需要费用和时间，既提高成本，又降低效率，故企业都希望尽可能地减少下料方式的数目。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下，在规定的时间需求内，以最少数量的原材料，尽可能按时完成需求任务，同时下料方式数也尽量地小。为顺利解决这一问题，我们先从最基本的单目标决策问题人手，以材料损耗最少为目标，由于个别零件的生产有时间的要求，因此，在下料时就应该优先生产那些有时间限制要求的零件，并且通过不同的数学原理建立多个单目标决策的最优化模型，得出最初的结果，并加以比较分析，然后逐步增加其约束条件，并根据这些约束条件进一步完善我们的
10、最优化模型，求出在需求的时间段内下料方式和损耗都最少的最优结果，紧接着再求出剩余板材下料方式和损耗的最优结果， 从而最终得出既满足时间条件限制又满足损耗少、下料方式数小的最优结果。具体 流程图如下：建立单目标模型 E目标时间需求条件增加约束条件输出结果满足损耗少、下料方式少增加约束条件原材料损耗最少图1总体流程图3模型的假设1 .假设每次切割都准确无误。2 .每天下料的数量受到企业生产能力的限制，在未完成需求任务前，每天下料的数量等于最大下料能力。3 .模型一中每切得一个规格的零件需要li 5 mm的原材料。4 .除最后一天外，其余每天均达到最大下料能力。.除了要求在规定时间内完成所需零件外，
11、不要求其余零件加工排列顺序。6.模型二中，切割所引起的锯缝损耗忽略不计。4. 符号说明符号符号解释说明口需求零件的数量li需求零件的长度Wi,需求零件的宽度aji第i种下料方式可生产第j种零件的数量Xi不同的下料方式所使用的原材料的数目c每种下料方式应用于每个原材料上所剩的余料m使用下料方式的种类n第j种零件所需要生产的数量L原材料长度，为3000M,4天内需要完成的零件编号建立集合m26天内需要完成的零件编号建立集合Ni理论所采用的原材料数目N2实际采用原材料的数目完成任务后的材料利用率M3问题二中4天内需要完成的零件编号建立集合5. 维下料问题对于一维优化下料问题，属于整数规划问题，从计算
12、复杂性理论分析，该问题 属于NP难题,即无法在多项式时间（在计算复杂度理论中，指的是一个问题的计算时 间m（n）不大于问题大小n的多项式倍数）内求解。虽然整数规划问题是 NP难题，但 是线性问题却是有有效算法的。所以要想求出下料方案的最优解，可以考虑不先求 解整数规划问题而先来求解其相应的线性问题，然后用计算机程序进行求解。首先 考虑在满足时间需求的情况下，材料总损失最少的情况，然后尽量使得总的下料方 式数目最少，故这里要寻找到所有下料方式中利用率最高的方式，同时在满足生产 力要求的情况下进行适当调整，采用尽可能少的下料方式，这样便可以得到一维下 料问题的优化结果。5.1模型一的建立根据题意，
13、现有数量充足的长度为 3000mm的原材料，需要完成一项有53种不同长度零件的下料任务。要求在生产能力许可的条件下，既省材料又容易操作（即下料方式尽可能少），由于本文问题的特殊性，还需要考虑个别标号的零件在4天内及 6 天内完成。故先对数据进行预处理，将 4 天和 6 天内完成的任务筛选出来，优先处理后再进行其他标号零件的加工。按照前面的分析，我们现假设有 m 种不同的下料方式，再根据每种零件的需求 量，可求得每种零件应用的次数，这样采用第一种下料方式生产的第一种零件的个 数为an个，同理可知，a,表示第i种下料方式可生产第j种零件的数量，则采用第 m种下料方式所能得到的第j种零件的数量表示为ajm，为更好地表示这个对应关系, 建立如下对应关系矩阵：a11a12a1ma21a22a2mAM
