示第j种下料方式采用的次数。

则我们可建立整数规划模型：（注意：同上文约定 MinK??j0??0） 0xjxj （6）

?7??a20,i,j?2，?j?i?1?10??a20,k,j?2，?j?k?1??S.T. ??a20,i,j?mi，?i

j????a20,k,j?mk，?k?k?a20,i,j?0，a30,i,j?0，且为整数,其中i?i1,i2,i3,i4???xj?0，且为整数求解此整数规划模型可以得到最优的下料方式，使得下料方式数最小。计算结果为：需要原材料的块数为N?79,下料方式为11种（见附录1表4）

对于4天后的： 用同样的方法可计算得到结果为：需要原材料的块数为N?372,下料方式为26种（见附录1表5）

故而总的下料方式数为K=37,下料方式为：表4加上表5；

综上第一到第四层，我们就解决了问题二：需要原材料的块数为：N?451，需要的下料方式数为：K?37 ，废料总面积为：C?1040880mm，废弃率为：q?0.77%，原材料的利用率为：p?1?q?99.23%。

六．模型和算法的分析与评价

1．模型的评价

对于问题一所建立的多目标整数规划模型，很准确的概括了该问题的所有约束和目标，从理论上讲是一个很严谨的模型。但是对于这一模型的求解却是非常困难的，必须寻找比较好的算法支持它，而文中我们提出的启发式多层次逐层优化方法[4][5]就很好的支持了这个模型，并且有很好的求解效果，材料的利用率很高（废料很少），计算速度快，结果很好。此模型和算法适应能力强，求解结果好，有很强的普遍性和实用性。

对于问题二所建立的分类逐层分析模型较好的解决了问题二，此方法根据具体问题的具体特点进行分析，找出针对性的解决方案，这样我们同样得到较好的结果，材料利用率高，计算速度快；但此模型有一定的缺陷，没有很强的普遍性，为适应某一特殊问题都需要具体的分析计算，寻求针对性的方案。

2．算法的评价、分析和比较

一维下料问题[8][9][10]是组合优化中的一个经典问题，从计算的复杂性理论上

11

看，优化下料问题属于NP难问题，即至今还不存在多项式算法。NP难问题的求解通常采用基于线性规划的方法、分支定界法、启发式算法、模拟退火算法、演化算法、遗传算法等。这些方法都能在一定程度上得到最优解或者次优解。我们的启发式多层次逐层优化方法在获得高的材料利用率的同时，在计算时间和存储空间上都具有优势。

七．结果分析

1．对于第一问的结果：在不考虑天数限制的情况下，我们运用问题一中建立的多目标整数规划模型及本文新建的启发式多层次逐层优化算法，用matlab

N?802根，K?73，编程（见附录2程序二）可以得到结果为：所用的下料方式为：废料总长度为：C?12856mm，废弃率为：q?0.53%，利用率为：

p?1?q?99.47%，具体数据见附录1表6

而在考虑问题一中天数限制的情况下，我们得到结果为：所用的原材料的数

量为：N?803根，所用的下料方式为：K?80，废料总长度为：C?16167mm，废弃率为：q?0.67%，利用率为：p?1?q?99.33%；

比较两个结果，很容易看出此模型和算法解决此问题的高效性，在增加限制条件之后仍然可以找到与没有限制情况近似的解答，并且原材料的利用率非常之高，可以基本保持在99%以上，因此从这个意义上说，我们得到的解是非常优的。

2．对于第二问的结果：在不考虑天数限制的情况下，我们运用问题二的处理方法，可以得到结果为：N20?1213，N30?484，N35?126，N50?36，具体数据见附录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，废料总面积为：C?1040880mm，废弃率为：q?0.77%，原材料的利用率为：p?1?q?99.23%。

比较两个结果，同样可以看出此模型和算法解决此问题的高效性，在增加限制条件之后仍然可以找到与没有限制情况近似的解答，并且原材料的利用率非常之高，可以基本保持在99%以上，因此从这个意义上说，我们得到的解是非常优的。

八．模型和算法的改进与推广

从本文的两个问题的解决可看出，针对本问题将多目标整数规划模型分解为多层整数线性规划模型和启发式多层次逐层优化方法是十分有效的。它在大大

12

降低计算复杂度的同时保持了很高的材料利用率和尚可接受的下料方式数。但是简化后的模型与算法在计算结果稳定性方面未来得及分析证明，也就是说此模型用于其它类似问题是否还可以得到和本题两个问题同样高的利用率没有理论基础。改进的模型可以在证明或增加模型稳定性方面作研究。

前人的研究以及上述算法的评价说明，现有的单一的模型与算法都有自身的缺陷，如常规的整数线性规划求解法计算结果最优，但是NPC问题，随着问题规模的增加，计算量和存储空间的会产生组合爆炸；神经网络法、模拟退火法以及蒙特卡罗法初始收敛速度快，特别适用于优化目标和约束条件复杂的问题，但是为求出精确解付出的机时却特别大。因此接下来可以考虑将蒙特卡罗模拟与我们的方法结合，以期得到一定的稳定性与精确度。

本模型在前人研究的基础上给出了含时间约束的多层整数线性规划模型和启发式多层次逐层优化方法，不仅给出了有效的多层整数线性规划模型简化算法而且解决了含时间约束的下料问题等一类问题。鉴于本算法的时间复杂度小，我们认为本算法完全可以由本题的单一原材料推广到多种原材料的情况。

参考文献：

[1] 彭祖赠，数学模型与建模方法，大连海事大学出版社，大连，1997

[2] 叶其孝，大学生数学建模竞赛辅导教材，湖南教育出版社，长沙，1993 [3] 张志涌，精通MATLAB6.5版，北京航空航天大学出版社，北京，2003 [4] 王小东等，一维下料优化的一种新算法，大连理工大学学报，第44卷，

第3期，2004年5月

[5] 张春玲、崔耀东，一维优化下料问题，桂林工学院学报，第24卷第1期，

2004年1月

[6] 黄崇斌，二维板材优化下料快速搜索法，计算机辅助工程，第1期，

2000年3月 [7] 林晓颖、王远，多目标优化下料问题的研究，哈尔滨师范大学自然科学学报，

第19卷第5期，2003年

[8] http://www.astrokettle.com

[9] G.Belov and G.Scheithauer, The Number of Setups(Different Patterns)

in One-Dimensional Stock Cutting, www.math.tu-dresden.de/capad, September23,2003

[10] G.Belov and G.Scheithauer, Setups and Open Stacks Minimazation

in One-Dimensional Stock Cutting, www.math.tu-dresden.de/capad, June24,2004

[11] 宋翔、聂义勇，无限制二维下料问题的改进动态规划算法，信息与控制， 第32卷第1期，2003年2月

13