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