合计 废料头 7.4 0 7.3 0.1 7.2 0.2 7.1 0.3 6.6 0.8 6.5 0.9 6.3 1.1 6 1.4
但有许多书籍在介绍套裁方案时，为了简单通常会将其中的料头较大的方案去掉，如在本例 中去掉方案6、方案 7、方案 8，从而建立只有 5种方案的模型。事实上，这种仅仅根据料头的多少来确定套裁方案的解题方法存在较大的不足，首先是不能判定到底选几种方案作为建模时的方案，这本身没有一个标准，选5种方案可以，那4种方案又如何?实在难以确定；再就是通过料头大小来放弃一些方案，这种方式并不能与现实中完全吻合，假设我们放弃方案5，但在现实生活中，如果我们对于2.9m这种规格的材料需求特别大，而对于其它两种规格的材料需求量却较小，那么当 2.9m规格材料满足需求时，其它两种规格的材料就已经超过了需求，从而使多余的部分成为料头弃掉，而未能实现真正的用料最省。 我们做这道题时，设决策变量 ：采取第 i种下料方式的有xi根
i=1，2，?，8．
另外设辅助变量：剩余的2.9 m规格钢 为y1根，剩余的2.1m规格钢为 y2根，剩余的 1.5m规格钢为 y3 根．
模型 I：剩余的规格钢当作废料的情况
min z=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8+2.9y1+2.1y2+1.5y3 (1) ?1x1?2x2?0x3?1x4?0x5?1x6?0x7?0x8?y1?100??0x1?0x2?2x3?2x4?1x5?1x6?3x7?0x8?y2?100??3x1?1x2?2x3?0x4?3x5?1x6?0x7?4x8?y3?100?xi?0,yj?0,为整数,i?1,2,....,8,j?1,2,3?8 (2)
Min z=?xi (3)
i?1由(1)、(2)组成的是求废料最少的整数线性规划模型 ．容易想到与其等价的另一模型，是由(3)、(2)组成的求所用原钢最少的整数线性规划模型．
模型 Ⅱ：剩余的规格钢(可 同原钢一样可以再利用)不当作废料的情况
min z=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8?1x1?2x2?0x3?1x4?0x5?1x6?0x7?0x8?100??0x1?0x2?2x3?2x4?1x5?1x6?3x7?0x8?100??3x1?1x2?2x3?0x4?3x5?1x6?0x7?4x8?100?xi?0,为整数,i?1,2,....,8? (4)
（
(5)（
由(4)、(5)组成的是求废料最少的整数线性规划模型也具有一定的实际意义，特别是当
最短的规格钢长度较长时，剩余的规格钢应当可以再次利用 。应该注意到，由(3)、(5)组成的整数线性规划模型就是模型 I．由于在建立模型 I和模型 Ⅱ时，考虑了剩余规 格钢的不同处理情况，使问题变得清晰了，所得到的模型也比较全面，没有漏洞和缺陷，另外，套裁下料问题所研究的都是成根的管、线材，所以在严格意义上讲，此问题应该是一个整数规划问题。
依照模型 I，建立如下的整数线性规划模型 ：
min z=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8+2.9y1+2.1y2+1.5y3 (1) ?1x1?2x2?0x3?1x4?0x5?1x6?0x7?0x8?y1?100??0x1?0x2?2x3?2x4?1x5?1x6?3x7?0x8?y2?100??3x1?1x2?2x3?0x4?3x5?1x6?0x7?4x8?y3?100?xi?0,yj?0,为整数,i?1,2,....,8,j?1,2,3?8 (2)
Min z=?xi (3)
i?1由(1)、(2)组成的模型和 由(2)、(3)组成的模型，其结果是一样的。 问题的求解
根据（1）和（2）建立的模型来求解 调用上面的ILp.m函数求解
>>C：[0，0.1，0.2，0.3，0.8，0.9，1.1，1.4]；
>>A=[1，2，0，1，0，1，0，0；0，0，2，2，1，1，3， 0；3，1，2，0，3，1，0，4]； >>b=[100；100；100]；
>>[ =ILp(C，[]，[]，A，b，[0，0，0，0，0，
0，0，0]，[inf，inf，inf，inf，inf，inf，inf，inf])； =。
例二
按照客户需要在一根原料钢管上安排切割的一种组合。合理切割模式的余料应小于客户
需要钢管的最小尺寸 合理切割模式如下： 模式 1 2 3 4 5 6 7 4米钢管根数 4 3 2 1 1 0 0 6米钢管根数 0 1 0 2 1 3 0 8米钢管根数 0 0 1 0 1 0 2 余料（米） 3 1 3 3 1 3 3 为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？ 两种标准1原料钢管剩余总余量最少2．所用原料钢管总根数最少 决策变量
xi～按第i种模式切割的原料钢管根数（i=1，2?7）
目标1（总余量）minz1=3x1+x2+3x3+3x4+x5+x6+3x7 模式 1 2 3 4 5 6 4米根数 4 3 2 1 1 0 6米根数 0 1 0 2 1 3 8米根数 0 0 1 0 1 0 余料 3 1 3 3 1 3 7 需求 0 50 0 20 2 15 3 ?4x1?3x2?2x3?x4?x5?50??x2?2x4?x5?3x6?20满足需求的约束条件为?最优解：x2=12,x5=15,其余为
x3?x5?2x7?15??xi为整数?0；最优值：27 按模式2切割12根,按模式5切割15根，余料27米 当余料没有用处时，通常以总根数最少为目标
?4x1?3x2?2x3?x4?x5?50??x2?2x4?x5?3x6?20目标2（总根数）minz2=x1+x2+x3+x4+x5+x6+x7 s.t?
?x3?x5?2x7?15?xi为整数?最优解：x2=15, x5=5, x7=5, 其余为0；最优值：25。
按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米 与目标1的结果“共切割27根，余料27米” 相比: 虽余料增加8米，但减少了2根 当余料没有用处时，通常以总根数最少为目标 在模型窗口中输入如下代码： minz2=x1+x2+x3+x4+x5+x6+x7 4*x1+3*x2+2*x3+x4+x5>50 x2+2*x4+x5+x6+x7>20 x3+x5+2*x7>15
都是第二种下料方式 125根原钢，第四种下料方式 50根原钢，共用 175根原钢． 小结
下料问题的求解，答案比较活泛．尽管在所需原材料总块数上答案一致，但在施工方案上却可以大相径庭．通常，在求解小规模问题时利用手工演算，可以找到全部解，而利用Lindo、
Microsoft Office Excel等只可找到部分解，而通常实际问题只需找到一个解即可．
结束语
经过几个月的学习，我终于完成了《关于一维下料问题的研究》这一毕业设计。刚开始时，我对下料问题并不是太了解，后来经过不断的学习和总结，现在已经变得很清晰了。本文介绍了简单的一维下料问题，我通过不断地查阅资料和书籍，同时在吕老师的耐心
分支定界法、指导下，现在已经知道解决一维下料问题有很多种方法，比如线性规划、动态规划法、整数规划法、遗传算法、遗传模拟退火算法、非线性规划、顺序启发式算法、广义粒子群优化算法等等。通过对一维下料问题的研究，我明白了一维下料问题在建筑、电力、水利等很多领域的重要性，让我受益匪浅。
在这里，我要谢谢指导老师吕红杰老师，在她的不断帮助和指导下我才能够完成论文。以前从未单独完成过这么大的一个设计，现在我终于也有能力独立做成一件事情，再次谢谢老师。
参考文献
[1]李培勇．多规格一维型材优化下料[J]．机械科学与技术，2003，22(增刊)80—86 [2] 王小东，李刚，欧宗瑛．一维下料优化的一种新算法[J]．大连理工大学学报，2004，44(3)：407—411
[3]张春玲，崔耀东．一维优化下料问题[J]．桂林工学院学报，2004，24(1)：103—106 [4] 钱送迪主编一运筹学 清华大学出版牡1990年1月 p37~ 98 [5] 胡运权 运筹学习题集 清华大学出版牡．1983年9月．p11
[6]Barry Render r Ratph M Stair Quantit i e Analyfis fo Management Atlyn and Bacon press． 1991 p583 590
袁亚湘，孙文瑜．最优化理论与方法．北京：北京科学出版社，1997 吴祈宗．运筹学与最优化方法．北京：北京机械工业出版社，2003 汪祖柱，程家兴．求解组合优化问题的一种方法——分支定界 法．安徽大学学报(自然科学版)，2004；28(1)：
杜江，盂香惠．一种改进的分支定界算法．数学杂志，1998； 卢仁甫，冯刚．混合遗传算法求解一维优化下料问题．中国水 运(理论版)，2006；4(4)：
张艳诚．一维下料问题的优化模型．黄石理工学院学报，2oo6 (4)： 李琼．一维优化下料问题的模型与算法的综合比较．武汉交通 科技大学学报，1998；
李涛，贺永军，刘志俭．Matlab工具箱应用指南—— 应用数学 篇．北京：电子工业出版社，2000