WORD文档
到满足需求的最小木板数，该值为 法的多目标二维切割和问题， 使得木板的利用率达最大。 （2）模型建立 min LW l w x
1 1 1
35。假设全部木板都用一种切割方式，并结合贪心启发式算
建立了模型。后进行优化改进，让不同的木板有不同的切割方案，
l w x
3 3
3
min z B
. Bx d s.t 1 1 Bx d
3
3
s.t . Bx
1 Bx
3
d
1
d
3
LW l w x l w x
1 1 1 3 3 3 B 35
B, x , x 为非负整数 3 1
LW l w x l w x
1 1 1 3 3 3
K
B 35
B, x , x 1
为非负整数
3
（3）模型求解
木板 S1 的数量 34 2 11
合计数量： ___47_____
P1 的数量 45 19 6 774
P3 的数量 4 36 52 1623
木板 利用率 0.9964 0.9923 0.9903 木板
总利用率 : ___0.99479___
备注
每块木板切割方案相同
木板总利用率 =
问题四 （1）算法分析
问题四采用了 guillotine 二维切割方法，通过贪心等启发式算法获取最优解的近似解。同时 由于该问题属于 NP 问题，无法采用多项式方法求解，故只能采用 （2）切割方案
guillotine 方法得到部分解。
P1
25.0 18.0 25.0 34.0 9.0 14.0 19.0 24.0 29.0 34.0 30.0 28.0 26.0 24.0
P2 11.0000 13.0000 6.0000 0 3.0000 6.0000 3.0000 0 3.0000 0 0 0 0 0
P3 3.0000 6.0000 9.0000 12.0000 29.0000 20.0000 21.0000 22.0000 13.0000 12.0000 2.0000 4.0000 6.0000 8.0000
P4 9.0000 9.0000 9.0000 9.0000 9.0000 9.0000 9.0000 9.0000 9.0000 9.0000 27.0000 27.0000 27.0000 27.0000
利用率 0.9473 0.9524 0.9218 0.9543 0.9787 0.9658 0.9801 0.9943 0.9814 0.9543 0.9610 0.9690 0.9770 0.9850
专业资料
WORD文档
98.2981 18.1 25.1 34.1 9.1 14.1 19.1 24.1 29.1 34.1 30.1 28.1 26.1 24.1 12.0 16.0 16.0 16.0 16.0 16.0 16.0 16.0 16.0 16.0 16.0 16.0 16.0
（3）模型建立
0 0
0 10.0000 12.0000 14.0000 16.0000 18.0000 20.0000 24.0000 3.0000 6.0000 12.0000 15.0000 18.0000 21.0000 27.0000 30.0000 28.0000 0 18.0000 2.0000 4.0000 6.0000 8.0000 10.0000 12.0000 14.0000 16.0000 18.0000
27.0000 27.0000 27.0000 27.0000 27.0000 27.0000 27.0000 37.0000 24.0000 18.0000 21.0000 12.0000 11.0000 5.0000 0 7.0000 14.0000 21.0000 27.0000 28.0000 28.0000 33.0000 24.0000 25.0000 23.0000 24.0000 21.0000
0.9597 0.9677 0.9757 0.9964 0.9917 0.9664 0.9824 0.9867 0.9661 0.9669 0.9859 0.9677 0.9842 0.9850 0.9692 0.9539 0.9028 0.9650 0.9669 0.9640 0.9754 0.9450 0.9659 0.9630 0.9733 0.9703 0.9650
6.0000 0 0 0 5.0000 9.0000 8.0000 5.0000 7.0000 6.0000 5.0000 5.0000 0 14.0000
0 8.0000 6.0000 5.0000 0 4.0000 2.0000 2.0000 0 0
k
4
h a l j w i ij j
min LWB
k
k
i 1 j 1
min B
i 1 k
h i ha i ij
d , j 1,2,3,4
j
s.t. B
i 1 k
h i
ha
i ij
s.t .
i 1
d , j 1,..,4
j
i 1
a ,h i 为非负整数 ij
（4）模型求解 木板 S1 的数量
专业资料
LW a l w ,i 1,.., k
ij j j
a , h为非负整ij
数
i
P1 的数量
P2 的数量
P3 的数量
P4
木板
的数量
利用率
备注
WORD文档
359 4 6 16 27 0.9964 每块木板切割方案相同
专业资料
WORD文档
合计数量：
774
___359____
2153
1623
1614
木板 总利用率 : __0.9964__
木板总利用率 =
问题五 （1）算法分析
根据第四题所得分割方案，建立数学模型进行求解。 （2）模型建立
k
4
max
i 1 j 1 k
c j a h a i ij
i 1
4
ij
s.t .
d j
LW
a l w ,i 1,..., k ij j j
j 1
h为非负整a , ij
数
i
（3）模型求解
木板 S1
的数量
100 木板 S1 合计数量 100
P1 的数量 59
P2 的数量
0
P3 的数量 0
P4 的数量
0
利润（元） 1174.1
木板 利用率 0.982979
备注
每块木板切割方案相同
木板总利用率
木板
总利润 :
总利用率 :
1174100
_0.982979_
误差分析
进一步讨论 结果表示，分析与检验 劳永逸的算法方案。 结语（模型评价，特点
上述问题求得的只是近似解，可能还有优化的空间，目前还没有发现此类解决
优缺点 改进方法 推广）
NP 问题一
该数学模型只能得到解的下限，不能直接得出解的结果，一方面是因为该模型选择用面积 近似求解而没有考虑到所装载物体的形状，另一方面是因为无法很好的将木板的长宽与变量联 系在一起（约束条件的缺少），因此只能求出可行解的上限或者下限，不能求出精确解。除此 之外，上述贪心策略求解切割方案的移植性较差，只能用于解决一些问题，但对于某些问题能 得到更好的结果，例如问题一，采用
guillotine 只能求出装载 p1 数为 56，而采用贪心策略则能
60。对于已存在的切割方案的优化求解，
求出装载 p1 数为 59，更大得接近此问题的上限装载量 寻求最优的全局最优解的另一种方式。 参考文献
[1] 向 文 欣 , 荀 珂 , 冉 翠 翠 . 基 于 两 段 排 样 方 式 的 剪 冲 下 料 优 化 算 法 [J]. 锻 压 技 术,2019,44(06):35-40.
[2] 郑明月 , 刘林 , 阚方 , 方昶 . 结合批量问题的多目标矩形件优化排样 用,2014,50(22):260-264.
[3]潘卫平 . 矩形件二维剪切下料排样算法研究
专业资料
可以采用一些智能算法对问题的解空间进行检索，进一步获取较多的切割方案。这种方法也是
[J]. 计算机工程与应
[D]. 广西大学 ,2015.
WORD文档
[4] 张军 , 金明 爱 , 王锡禄 , 冯恩民 . 一刀切下 料的数学模型 版),2001(01):11-14.
[J]. 延边大学学报 ( 自然科学 [J]. 电子质
[5] 林春婷 , 杨连池 , 王志煌 , 张国忠 , 叶德火 . 激光切纸机网络共享的设计实现 量,2018(11):32-34
专业资料
木材最优切割 - 图文
