a)当?ni?0时，求最优的一种下料方式的数学模型为：

i?G1MaxS??aili （2）

i?153S.T.

?53??ai(li?5)?5?Li?1???0?ai?ni，且为整数 ?a?gi1?i??G1??其中?a1,a2,?,a53?表一种下料方式，g1为努力程度，定义为某种下料方式中含有集合G1中零件的个数，从中我们可以看出g1越大零件集合G1完成得越快；

b) 当?ni?0且?ni?0时，求最优的一种下料方式的数学模型为：

i?G1i?G2MaxS??aili （3）

i?153S.T.

?53??ai(li?5)?5?Li?1???0?ai?ni，且为整数 ?a?gi2?i??G2??g2为努力程度，类似g1的定义和理解；

c) 当?ni?0且?ni?0时，求最优的一种下料方式的数学模型为：

i?G1i?G2MaxS??aili （4）

i?153S.T.

?53??ai(li?5)?5?L ?i?1?0?a?n，且为整数ii?这三个模型都是整数线性规划问题，可以用分支定界法求解，亦可用lingo

直接编程（见附录程2序九），可以很快计算得结果；也可以用matlab7.0[3]编程算得。

6

2）针对模型，我们创建适应性的算法——启发式多层次逐层优化方法，此 方法的基本思想是：在每层求解时，对于上层剩余的未完成的各零件数目，利用上面三个子模型可以在当前可行的下料方式中选择最优的一种下料方式进行下料，并尽可能的重复使用此种下料方式（这是为了使得下料方式尽可能少）；然后对剩余的未完成的各零件重新优化选取新的最优的一种下料方式，不断反复上面的操作，直到所有剩余的未完成的各零件数目都减少到0为止。这样原问题的最优解就是各个层次优化问题所求得的最优下料方式的总和。

3）启发式多层次逐层优化方法的计算方法

将上述当前最优下料方式的三种模型的计算求解作为启发式多层次逐层优化方法计算的子程序,在每级求解中，对于相应的条件重复调用相应的子程序。

完整的求解过程如下：

Step1：初始给定了未完成的各零件的数目?n11,n21,?,n531???n1,n2,?,n53?，4天要完成的零件集合G11?G1，6天要完成的零件集合G21?G2；在上一层（j层）得到的未完成的各零件的数目?n1j,n2j,?,n53j?基础上，判断

i?G1j?nij?0和

i?G2j?nij?0是否成立，然后依判定条件调用1）中相应的当前最优下料计算子程序,

求解得到最优下料方式?a1j,a2j,?,a53j?，并以此作为这一级的下料方式；

Step2：计算此种下料方式的重复次数,即用此种下料方式切割的原材料L

?n1jn2jn53j,,?,的根数xj?min??aaa53j?1j2j??； ??Step3：计算去掉xj根按这种下料方式切割后,余下的未完成的各种零件的数量：?n1j?1,n2j?1,?,n53j?1???n1j,n2j,?,n53j??xj?a1j,a2j,?,a53j?；

Step4：将上一步得到的?n1j?1,n2j?1,?,n53j?1?作为新一层优化计算的给定值,并记Hj??i;nij?1?0?,令G1j?1?G1j?Hj，G2j?1?G2j?Hj

如果?n1j?1,n2j?1,?,n53j?1??0则优化计算结束；否则转Step1重新判断并调用当前最优下料方式计算子程序,求得新一层的下料方式和重复次数；

Step5：各层最优下料方式及其重复次数的集合即为启发式多层次逐层优化方法的最终结果，即?a1j,a2j,?,a53j?和xj的值；

算法流程如图1所示：

7

主程序给定L，li,ni子程序输入当前还需零件数,n1,n2,...,nmj=1是求出当前最优最优下料方式子程还有4天必须完成的零件数吗？否还有6天必须完成的零件数吗？是a1j,a2j,?,amjxj=min(n1j,n2j,?,nmj)nij+1=nij-d*aij整数线性规划求较优下料方式动态整数规划求下料方式nij+1全为0？否j=j+1是输出下料方式向量保存下料方式重复次数，停止 （图1：算法流程）

用matlab编程可对问题一进行计算求解（见附录2程序四），求解的结果为：所用的原材料的数量为：N?803根，所用的下料方式为：K?80，废料总长度为：C?16167mm，废弃率为：q?0.67%，利用率为：p?1?q?99.33%；同时从数据中可以看出：采用这种方案，只需要4天半就可以完成问题一中要求的6天内必须完成的零件的要求；该方案对原材料的利用率非常高，效果很好。具体下料方式数据见附录1表1

2．对于问题二的解决：

这是一个二维下料问题[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），对每一类都可按问题一的处理一维下料问题的方式找最优的方案，然后再把他们按上述的几种方式进行优化组合，最后再对优化组合剩余的部分进行考虑。

8

为此我们建立分类逐层分析模型： 1）第一层次：

首先优先考虑宽度的特征，我们把零件按宽边的规格分为4类（20，30， 35，50），对每一类都可按问题一的用于处理一维下料问题的多目标整数规划模型和启发式多层次逐层优化方法方式找最优的方案，用mablab编程（见附录2程序七、八）得到结果：具体下料方式数据见附录1表2，从中我们可以得到各类宽度零件所需要的长条数为（长为3000mm，宽与零件相对应的长条）

1~4天为：N20?152，N30?152，N50?6。（此处应该把下料方式数算出来了，是后面的7，10。）

4天后为：N20?1061，N30?335，N35?126，N50?31。

2）第二层次：

由于宽边若没有填满，对整个板材的利用影响非常大，所以我们要求在宽 边上要尽量填满（即：尽量没有费余的）。因此我们在上一层次得到结果的基础上，我们运用上面给出的几种最优的组合方式进行优化组合：50-50，50-30-20， 30-30-20-20，35-35-30，20-20-20-20-20；

设采用第i种组合的次数为mi，i?1,2,3,4,5；则可建立整数线性规划模型，以求得所应采用的各种组合的次数。 模型如下：

MinY?(N20?m2?2m3?5m5)?(N30?m2?2m3?m4)?(N35?2m4)?(N50?2m1?m2)?m2?2m3?5m5?N20??m2?2m3?m4?N30?S.T.?2m4?N35 （5）

?2m?m?N250?1??mi?0且为整数，i?1,2,3,4,5利用lingo编程（见附录2程序十）可以很快求解出此整数线性规划的最优解为：1~4天为：m1?3，m2?0，m3?76，m4?0，m5?0，MinY?0

4天后为：m1?0，m2?31，m3?120，m4?63，m5?158，MinY?1， 可知：1~4天可以实现恰好的组合；而4天后的部分则余下一个宽为30的长条，1~4天所用的原材料总数为：N?m1?m2?m3?m4?m5?79,

4天后所用的原材料总数为：N?m1?m2?m3?m4?m5?1?373, 其中1表示余下的一个宽为30的长条要占用一块原材料。 则所用的原材料的总数为：N=79+373=452

9

3）第三层次： 对上述优化组合后，剩余的部分进行分析：即对第二层中优化模型求出最优解后，所剩余的部分进行研究。

对于上一层次中1~4天的情形，没有余下的长条，故可不考虑这一层； 对于上一层次中4天后的情形，余下的一块宽为30（单位：mm，下同）的长条，我们选废料长度最长的那一块进行讨论，将这一长条再分解为零件，然后寻找其他的宽度的废料块，看能否用这些废料来切割得到那个宽为30的长条上的零件：若可以做到这一点，则这块余下的长条就被消化掉了；若不可以，则这块长条就要占用一块原材料。

利用这种思想方法，结合附录表2的下料数据，我们很容易找到浪费最多的那块宽为30的长条：1105—1032切割组合；同时可以找到宽为35的有长为1200的废料，宽为50的有长为2460的废料，这样我们可以1105x30和1032x30的零件用2460x50这块废料来切割得到。这样我们就消化掉了余下的这个长条。因此，利用这种处理方法可以节省一块原材料，故所用的原材料总数为:N=452-1=451。

通过如上我调整后，得到数据见附录1表3 计算废料面积为：

C?3000?100?N??liwini?1.353?108?1.3425912?108?1040880mm

i?143废弃率为：q?C/(3000?100?N)?0.77% 利用率为：p?1?q?99.23%

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： 令m20,i表示1~4天宽为20的第i种下料的数量（i=1,?7），m30k表示1~4天宽为30的第k种下料的数量(k=1,?10)，再令

?a20,1,j,?,a20,7,j,a30,1,j,?,a30,10,j?表示在此组合下第j种下料方式是：1~4天宽20

（1）--?--1~4天宽20（7）--1~4天宽30（1）--?--1~4天宽30（10）；xj表

10