实用下料问题

-.z.实用下料问题一．问题的重述"下料问题(cuttingstockproblem)〞是把一样形状的一些原材料分割加工成假设干个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的应用.这里的"实用下料问题〞则是在*企业的实际条件限制下的单一材料的下料问题。现考虑单一原材料下料问题.设这种原材料呈长方形，长度为,宽度为，现在需要将一批这种长方形原料分割成种规格的零件,所有零件的厚度均与原材料一致，但长度和宽度分别为，其中wi＜.种零件的需求量分别为.下料时，零件的边必须分别和原材料的边平行。这类问题在工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相等，即，则问题称为一维下料问题。一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低本钱，提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，既提高本钱，又降低效率。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务,同时下料方式数也尽量地小。现在我们要为*企业考虑下面两个问题。1．建立一维单一原材料实用下料问题的数学模型,并用此模型求解以下问题，制定出在生产能力容许的条件下满足需求的下料方案,同时求出等额完成任务所需的原材料数，所采用的下料方式数和废料总长度.单一原材料的长度为3000mm,需要完成一项有53种不同长度零件的下料任务.具体数据见表一(略)，其中为需求零件的长度，为需求零件的数量.此外，在每个切割点处由于锯缝所产生的损耗为5mm.据估计，该企业每天最大下料能力是100块，要求在4天内完成的零件标号()为:5,7,9,12,15,18,20,25,28,36,48；要求不迟于6天完成的零件标号()为:4,11,24,29,32,38,40,46,50。2．立二维单一原材料实用下料问题的数学模型,并用此模型求解以下问题.制定出在企业生产能力容许的条件下满足需求的下料方案,同时求出等额完成任务所需的原材料块数和所需下料方式数.这个问题的单一原材料的长度为3000mm,宽度为100mm,需要完成一项有43种不同长度和宽度零件的下料任务.具体数据见表二(略)，其中分别为需求零件的长度、宽度和数量.切割时的锯缝可以是直的也可以是弯的，切割所引起的锯缝损耗忽略不计.据估计，该企业每天最大下料能力是20块要求在4天内完成的零件标号()为: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．对于第一问的假设：在每个切割点处由于锯缝所产生的损耗为5mm；企业每天的最大下料能力为100块；考虑下料方式的数量对总损耗的影响，下料方式越少则原材料总损耗越小；对于剩余长度为mm的材料，可以通过细微调整锯缝的位置锯得长度为mm的零件；2．对于第二问的假设：切割所引起的锯缝损耗忽略不计；切割时锯缝可以是直的也可以是弯的，但要求转弯为直角；企业每天最大的下料能力是20块；原材料和零件都是长方形。四．符号说明——原材料的长度〔=3000mm〕——原材料的宽度〔=100mm〕——所用的原材料总数量——所采用的下料方式总数量——第i号零件的长度〔单位：mm，〕——第i号零件的宽度——第i号零件的需求量——第j种下料方式中切割第i号零件的数量——按第j种下料方式切割的原材料的数量——按第j种下料方式切割的废料长度〔mm〕——第一问中要求在4天内完成的零件号的集合——第一问中要求在不迟于6天完成的零件号的集合——第二问中要求在4天内完成的零件号的集合五．模型的建立与求解1．对问题一的解决：此问要求：在4天内完成的零件标号()为:5,7,9,12,15,18,20,25,28,36,48；不迟于6天完成的零件标号()为:4,11,24,29,32,38,40,46,50。而该企业每天最大下料能力是100块，我们要制定出在生产能力容许的条件下满足需求的下料方案，同时要求等额完成任务，我们的目标是要尽可能节省材料，尽可能用少的下料方式。为此我们建立多目标整数规划模型：〔首先我们约定：〕,〔1〕注：1.我们有：假设采用了第j种下料方式，则为大于0的整数，因此；假设没有采用第j种下料方式，则为0，如上定义可得：，这样即表示了所用的下料方式数量；2．约束中第一条是：考虑了锯缝时，原材料长度L对下料方式的限制，即对于任意一种下料方式，所得到的零件总长度与锯缝总长度之和要小于等于L；3．约束中第二条是：考虑了锯缝时，对于每一种下料方式的废料长度要小于零件的最小长度；4．约束中第三条是：为了满足题中要求的等额完成任务的限制条件；5．约束中第四条是：为了满足在企业每天生产能力是100块时，要求在4天内完成零件集合的条件，其中表示第j种下料方式中所切割的第i种零件数占这种下料方式中所切割的零件集合中零件数的权数，因此表示了完成零件集合所用的原材料数，又由于在4天内要完成零件集合，故上述所算出的所用的原材料数要小于等于，注意假设，即表示第j种下料方式中没有切割到零件集合中的零件，因此：，这样按照注释1中的约定，可知正好表示：这种下料方式不产生集合中的零件，故而这条约束很完善；6．约束中第五条和第四条的解释类似；约束中第六条和第七条表示和要取整数。对于废料的度量：由于存在锯缝为5mm，对任何一种可行的下料方式，则其满足条件，所以如果单纯的用来度量此种下料方式的废料是不对的，这可能取到负值；实际上，又由于对问题一有假设4，我们可以知道：对所有满足的下料方式来说，废料都为0；故而我们可以得到废料的度量方式：经过数学处理，得到：因此废料总量为：废弃率定义为：利用率定义为：对于此模型〔即〔1〕式〕的求解比拟困难，我们需要首先分解此模型，然后创立适应的优化算法解决此问题：表第j种下料方式当前最优的下料方式的模型：多层整数线性规划模型a)当时，求最优的一种下料方式的数学模型为：〔2〕其中表一种下料方式，为努力程度，定义为*种下料方式中含有集合中零件的个数，从中我们可以看出越大零件集合完成得越快；b)当且时，求最优的一种下料方式的数学模型为：〔3〕为努力程度，类似的定义和理解；c)当且时，求最优的一种下料方式的数学模型为：〔4〕这三个模型都是整数线性规划问题，可以用分支定界法求解，亦可用lingo直接编程〔见附录程2序九〕，可以很快计算得结果；也可以用matlab7.0[3]编程算得。针对模型，我们创立适应性的算法——启发式多层次逐层优化方法，此方法的根本思想是：在每层求解时，对于上层剩余的未完成的各零件数目，利用上面三个子模型可以在当前可行的下料方式中选择最优的一种下料方式进展下料，并尽可能的重复使用此种下料方式〔这是为了使得下料方式尽可能少〕；然后对剩余的未完成的各零件重新优化选取新的最优的一种下料方式，不断反复上面的操作，直到所有剩余的未完成的各零件数目都减少到0为止。这样原问题的最优解就是各个层次优化问题所求得的最优下料方式的总和。3〕启发式多层次逐层优化方法的计算方法将上述当前最优下料方式的三种模型的计算求解作为启发式多层次逐层优化方法计算的子程序,在每级求解中，对于相应的条件重复调用相应的子程序。完整的求解过程如下：Step1：初始给定了未完成的各零件的数目，4天要完成的零件集合，6天要完成的零件集合；在上一层〔j层〕得到的未完成的各零件的数目根底上，判断和是否成立，然后依判定条件调用1〕中相应的当前最优下料计算子程序,求解得到最优下料方式，并以此作为这一级的下料方式；Step2：计算此种下料方式的重复次数,即用此种下料方式切割的原材料L的根数；Step3：计算去掉根按这种下料方式切割后,余下的未完成的各种零件的数量：；Step4：将上一步得到的作为新一层优化计算的给定值,并记,令，如果则优化计算完毕；否则转Step1重新判断并调用当前最优下料方式计算子程序,求得新一层的下料方式和重复次数；Step5：各层最优下料方式及其重复次数的集合即为启发式多层次逐层优化方法的最终结果，即和的值；算法流程如图1所示：〔图1：算法流程〕用matlab编程可对问题一进展计算求解〔见附录2程序四〕，求解的结果为：所用的原材料的数量为：根，所用的下料方式为：，废料总长度为：，废弃率为：，利用率为：；同时从数据中可以看出：采用这种方案，只需要4天半就可以完成问题一中要求的6天内必须完成的零件的要求；该方案对原材料的利用率非常高，效果很好。具体下料方式数据见附录1表12．对于问题二的解决：这是一个二维下料问题[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〕，对每一类都可按问题一的处理一维下料问题的方式找最优的方案，然后再把他们按上述的几种方式进展优化组合，最后再对优化组合剩余的局部进展考虑。为此我们建立分类逐层分析模型：第一层次：首先优先考虑宽度的特征，我们把零件按宽边的规格分为4类〔20，30，35，50〕，对每一类都可按问题一的用于处理一维下料问题的多目标整数规划模型和启发式多层次逐层优化方法方式找最优的方案，用mablab编程〔见附录2程序七、八〕得到结果：具体下料方式数据见附录1表2，从中我们可以得到各类宽度零件所需要的长条数为〔长为3000mm，宽与零件相对应的长条〕1~4天为：，，。4天后为：，，，。第二层次：由于宽边假设没有填满，对整个板材的利用影响非常大，所以我们要求在宽边上要尽量填满〔即：尽量没有费余的〕。因此我们在上一层次得到结果的根底上，我们运用上面给出的几种最优的组合方式进展优化组合：50-50，50-30-20，30-30-20-20，35-35-30，20-20-20-20-20；设采用第i种组合的次数为；则可建立整数线性规划模型，以求得所应采用的各种组合的次数。模型如下：〔5〕利用lingo编程〔见附录2程序十〕可以很快求解出此整数线性规划的最优解为：1~4天为：，，，，，4天后为：，，，，，，可知：1~4天可以实现恰好的组合；而4天后的局部则余下一个宽为30的长条，1~4天所用的原材料总数为：,4天后所用的原材料总数为：,其中1表示余下的一个宽为30的长条要占用一块原材料。则所用的原材料的总数为：N=79+373=452第三层次：对上述优化组合后，剩余的局部进展分析：即对第二层中优化模型求出最优解后，所剩余的局部进展研究。对于上一层次中1~4天的情形，没有余下的长条，故可不考虑这一层；对于上一层次中4天后的情形，余下的一块宽为30〔单位：mm，下同〕的长条，我们选废料长度最长的那一块进展讨论，将这一长条再分解为零件，然后寻找其他的宽度的废料块，看能否用这些废料来切割得到那个宽为30的长条上的零件：假设可以做到这一点，则这块余下的长条就被消化掉了；假设不可以，则这块长条就要占用一块原材料。利用这种思想方法，结合附录表2的下料数据，我们很容易找到浪费最多的那块宽为30的长条：1105—1032切割组合；同时可以找到宽为35的有长为1200的废料，宽为50的有长为2460的废料，这样我们可以1105*30和1032*30的零件用2460*50这块废料来切割得到。这样我们就消化掉了余下的这个长条。因此，利用这种处理方法可以节省一块原材料，故所用的原材料总数为:N=452-1=451。通过如上我调整后，得到数据见附录1表3计算废料面积为：废弃率为：利用率为：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。为了使下料方式最少，我们制定下述的下料方式搭配规则〔算法〕：对于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=1,…7〕，表示1~4天宽为30的第k种下料的数量(k=1,…10)，再令表示在此组合下第j种下料方式是：1~4天宽20〔1〕--…--1~4天宽20〔7〕--1~4天宽30〔1〕--…--1~4天宽30〔10〕；表示第j种下料方式采用的次数。则我们可建立整数规划模型：〔注意：同上文约定〕〔6〕求解此整数规划模型可以得到最优的下料方式，使得下料方式数最小。计算结果为：需要原材料的块数为,下料方式为11种〔见附录1表4〕对于4天后的：用同样的方法可计算得到结果为：需要原材料的块数为,下料方式为26种〔见附录1表5〕故而总的下料方式数为K=37,下料方式为：表4加上表5；综上第一到第四层，我们就解决了问题二：需要原材料的块数为：，需要的下料方式数为：，废料总面积为：，废弃率为：，原材料的利用率为：。六．模型和算法的分析与评价1．模型的评价对于问题一所建立的多目标整数规划模型，很准确的概括了该问题的所有约束和目标，从理论上讲是一个很严谨的模型。但是对于这一模型的求解却是非常困难的，必须寻找比拟好的算法支持它，而文中我们提出的启发式多层次逐层优化方法[4][5]就很好的支持了这个模型，并且有很好的求解效果，材料的利用率很高〔废料很少〕，计算速度快，结果很好。此模型和算法适应能力强，求解结果好，有很强的普遍性和实用性。对于问题二所建立的分类逐层分析模型较好的解决了问题二，此方法根据具体问题的具体特点进展分析，找出针对性的解决方案，这样我们同样得到较好的结果，材料利用率高，计算速度快；但此模型有一定的缺陷，没有很强的普遍性，为适应*一特殊问题都需要具体的分析计算，寻求针对性的方案。2．算法的评价、分析和比拟一维下料问题[8][9][10]是组合优化中的一个经典问题，从计算的复杂性理论上看，优化下料问题属于NP难问题，即至今还不存在多项式算法。NP难问题的求解通常采用基于线性规划的方法、分支定界法、启发式算法、模拟退火算法、演化算法、遗传算法等。这些方法都能在一定程度上得到最优解或者次优解。我们的启发式多层次逐层优化方法在获得高的材料利用率的同时，在计算时间和存储空间上都具有优势。七．结果分析1．对于第一问的结果：在不考虑天数限制的情况下，我们运用问题一中建立的多目标整数规划模型及本文新建的启发式多层次逐层优化算法，用matlab编程〔见附录2程序二〕可以得到结果为：根，所用的下料方式为：，废料总长度为：，废弃率为：，利用率为：，具体数据见附录1表6而在考虑问题一中天数限制的情况下，我们得到结果为：所用的原材料的数量为：根，所用的下料方式为：，废料总长度为：，废弃率为：，利用率为：；比拟两个结果，很容易看出此模型和算法解决此问题的高效性，在增加限制条件之后仍然可以找到与没有限制情况近似的解答，并且原材料的利用率非常之高，可以根本保持在99%以上，因此从这个意义上说，我们得到的解是非常优的。2．对于第二问的结果：在不考虑天数限制的情况下，我们运用问题二的处理方法，可以得到结果为：，，，，具体数据见附录1表7，35块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，废料总面积为：，废弃率为：，原材料的利用率为：。比拟两个结果，同样可以看出此模型和算法解决此问题的高效性，在增加限制条件之后仍然可以找到与没有限制情况近似的解答，并且原材料的利用率非常之高，可以根本保持在99%以上，因此从这个意义上说，我们得到的解是非常优的。八．模型和算法的改良与推广从本文的两个问题的解决可看出，针对本问题将多目标整数规划模型分解为多层整数线性规划模型和启发式多层次逐层优化方法是十分有效的。它在大大降低计算复杂度的同时保持了很高的材料利用率和尚可承受的下料方式数。但是简化后的模型与算法在计算结果稳定性方面未来得及分析证明，也就是说此模型用于其它类似问题是否还可以得到和此题两个问题同样高的利用率没有理论根底。改良的模型可以在证明或增加模型稳定性方面作研究。前人的研究以及上述算法的评价说明，现有的单一的模型与算法都有自身的缺