下料问题资料

实用下料问题一．问题的重述“下料问题(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块，我们要制定出在生产能力容许的条件下满足新一层的下料方式和重复次数；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的废料，这样我们可以1105x30和1032x30的零件用2460x50这块废料来切割得到。这样我们就消化掉了余下的这个长条。因此，利用这种处理方法可以节省一块原材料，故所用的原材料总数为: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%以上，因此从这个意义上说，我们得到的解是非常优的。八．模型和算法的改进与推广从本文的两个问题的解决可看出，针对本问题将多目标整数规划模型分解为多层整数线性规划模型和启发式多层次逐层优化方法是十分有效的。它在大大降低计算复杂度的同时保持了很高的材料利用率和尚可接受的下料方式数。但是简化后的模型与算法在计算结果稳定性方面未来得及分析证明，也就是说此模型用于其它类似问题是否还可以得到和本题两个问题同样高的利用率没有理论基础。改进的模型可以在证明或增加模型稳定性方面作研究。前人的研究以及上述算法的评价说明，现有的单一的模型与算法都有自身的缺陷，如常规的整数线性规划求解法计算结果最优，但是NPC问题，随着问题规模的增加，计算量和存储空间的会产生组合爆炸；神经网络法、模拟退火法以及蒙特卡罗法初始收敛速度快，特别适用于优化目标和约束条件复杂的问题，但是为求出精确解付出的机时却特别大。因此接下来可以考虑将蒙特卡罗模拟与我们的方法结合，以期得到一定的稳定性与精确度。本模型在前人研究的基础上给出了含时间约束的多层整数线性规