五一数学建模竞赛
承 诺 书
我们仔细阅读了五一数学建模竞赛的竞赛规则。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人 （包括指导教师） 研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的 , 如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。
我们授权五一数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示
（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
参赛题号（从 A/B/C 中选择一项填写）：
B
参赛队号：
参赛组别（研究生、本科、专科、高中）：
所属学校（学校全称）：
参赛队员： 队员 1 姓名： XXX
队员 2 姓名： XXX
队员 3 姓名： XXX
联系方式： Email ： 联系电话：
日期： 年 月 日
（除本页外不允许出现学校及个人信息）
五一数学建模竞赛
题 目：
木料切割最优化问题
关键词：
矩形件下料
切割问题 guillotine
摘 要：
随着社会的发展、人们对环境资源的重视，提高材料的利用率、获得最大利润就成了不可
避免的问题，而解决这个问题的关键就是对产品的生产进行紧凑型的布局。本文旨在解决家具 厂木料的切割问题，由一维问题（或者说是
割方法（采用 guillotine ，贪心启发式算法的多目标二维切割），使得我们从目标木板上切割出 的所需产品的面积和最大或者利润最大，后对方案进行优化处理，最终得出最优方案。问题一 用 guillotine 方法切割可得一块木板上 代的方法，分析得出前三甲利用率分别为
P1 最多能切割 59 个。问题二在问题一的基础上，
1.5 维问题）递推到二维问题，通过寻找合适的切
通过迭
99.64% ， 99.23%和 99.03% 的最佳方案。问题三又在
lingo
359 块。问题五
问题二的基础上，引入了生产任务作为限制因素，并结合贪心启发式算法的多目标二维切割和 问题使问题得到解决。问题四在问题三的基础上，又增添了两个长宽不同的矩形件，用 找寻它的最下限后，用循环得出最大利用率为 是在一块木板上切割 98.2979%。
99.64%，这时候使用的木板数为
改变了问题四的目标函数，消除了生产任务对木块切割的限制。在这种情形下，得到最优方案
59 块矩形件
P1，从而得出最大利润为
1174100 元，木板的利用率为
五一数学建模竞赛
题 目：
木料切割最优化问题
关键词：
矩形件下料
切割问题 guillotine
摘 要：
随着社会的发展、人们对环境资源的重视，提高材料的利用率、获得最大利润就成了不可
避免的问题，而解决这个问题的关键就是对产品的生产进行紧凑型的布局。本文旨在解决家具 厂木料的切割问题，由一维问题（或者说是
割方法（采用 guillotine ，贪心启发式算法的多目标二维切割），使得我们从目标木板上切割出 的所需产品的面积和最大或者利润最大，后对方案进行优化处理，最终得出最优方案。问题一 用 guillotine 方法切割可得一块木板上 代的方法，分析得出前三甲利用率分别为
P1 最多能切割 59 个。问题二在问题一的基础上，
1.5 维问题）递推到二维问题，通过寻找合适的切
通过迭
99.64% ， 99.23%和 99.03% 的最佳方案。问题三又在
lingo
359 块。问题五
问题二的基础上，引入了生产任务作为限制因素，并结合贪心启发式算法的多目标二维切割和 问题使问题得到解决。问题四在问题三的基础上，又增添了两个长宽不同的矩形件，用 找寻它的最下限后，用循环得出最大利用率为 是在一块木板上切割 98.2979%。
99.64%，这时候使用的木板数为
改变了问题四的目标函数，消除了生产任务对木块切割的限制。在这种情形下，得到最优方案
59 块矩形件
P1，从而得出最大利润为
1174100 元，木板的利用率为
hi
表示第 i 种方案所用原料木板的数量
模型建立与优化
1、问题一
（1）算法分析
分析第一题，其采用单一材料形式进行分割，我们通过 用“一刀切”的形式对问题进行求解，得出在一块木板上
guillotine 切割方案进行初步求解，其采
P1 切割的最大数为
56，但是（相对
误差比较大）利用率比较低。后通过贪心算法再次对问题进行优化求解，得出切割的最大数为 60，接近于木板切割（装载）的上限，针对于该问题，贪心策略能得到较好的解，但它不适用 于其他问题。
图例 1：贪心算法
图例 2： guillotine 切割
（2）模型建立
建立一个 1.5 维的切割问题模型来求近似解
n
min LW
i 1
l1w1xi
'
s.t. l1 xi L , i 1,...,n
n
'
W w1
'
或者
s.t. l1 xi W , i 1,...,n
n
L w1
（3）模型求解
P1 的数量
木板利用率
59
2、问题二 （1）算法分析
98.29793%
在第一题的基础上， 继续贪心找到了每种产品的上限， 通过 guillotine 切割进行迭代分析求出不同方案的木板利用率，经过对比分析，选取了三种利用率最高的方案。（2）模型建立
min LW s.t. LW
l1w1 x1 l3 w3 x3 l 1w1x1 l 3w3x3
x1 , x3都为非负整数
（3）切割 P1 和 P3 的全部方案
方案编号
1 2 3 4 5 6 7 8 9 10 11 12 13
P1 的数量
4 8 12 16 20 24 28 32 36 40 44 48 52 56
P3 的数量
45 40 38 33 31 26 25 21 19 14 12 7 6 0
木板利用率
0.9964 0.9597 0.9850 0.9484 0.9737 0.9370 0.9830 0.9670 0.9923 0.9557 0.9810 0.9443 0.9903 0.9330
14
（ 4）模型求解
根据上面的方案，进行利用率的排序，易得三种最佳方案
方案编号
1 9
P1 的数量
4 36 52
P3 的数量
45 19 6
木板利用率
0.9964 0.9923 0.9903
13
3、问题三
（1）算法分析
可结合问题一，得出在一块木板上分别切割 P1 和 P3 所能得到的最大数，再结合生产任务能得
木材最优切割
