到满足需求的最小木板数，该值为 法的多目标二维切割和问题， 使得木板的利用率达最大。 （2）模型建立
35。假设全部木板都用一种切割方式，并结合贪心启发式算
建立了模型。后进行优化改进，让不同的木板有不同的切割方案，
min LW s.t. Bx1
l1w1 x1 l3 w3 x3 d1
min z s.t. Bx1
B
d1
Bx3 d3 LW l1w1x1 B 35
Bx3 d3
LW l1w1 x1 l 3w3x3 K B
35
B, x1, x3为非负整数
l 3w3 x3
B, x1, x3为非负整数
（3）模型求解
木板 S1 的数量
34 2
11
合计数量： ___47_____
P1 的数量 45 19
6
P3 的数量
4 36
52 1623
木板 利用率 0.9964 0.9923 0.9903 木板 总利用率 : ___0.99479___
备注
每块木板切割方案相同
774
木板总利用率 =
问题四
（1）算法分析
问题四采用了 guillotine 二维切割方法，通过贪心等启发式算法获取最优解的近似解。同时
由于该问题属于 NP 问题，无法采用多项式方法求解，故只能采用 （2）切割方案
guillotine 方法得到部分解。
P1
25.0000 18.0000 25.0000 34.0000 9.0000
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
利用率
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
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
14.0000 19.0000 24.0000 29.0000 34.0000 30.0000 28.0000 26.0000 24.0000
20.0000 18.0000 16.0000 4.0000 12.0000 8.0000 4.0000 12.0000 12.0000 12.0000 12.0000 12.0000 12.0000 12.0000 12.0000 16.0000 16.0000 16.0000 16.0000 16.0000 16.0000 16.0000 16.0000 16.0000 16.0000 16.0000
0 0 0 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
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
16.0000
（3）模型建立
k
k 4
min LWB
i 1 k
j 1
halwi ij j j
min B
k i 1
hi
s.t. B
k
i 1
hi
s.t.
i 1
hi aij d j , j 1,2,3,4
h a
i
ij
i 1
d j , j 1,..,4
aij ,h i 为非负整数
LW aij l j w j ,i 1,.., k
aij , hi为非负整数
（4）模型求解 木板 S1 的数量
359
P1 的数量
4
P2
的数量
6
P3 的数量
16
P4 的数量
27
木板 利用率 0.9964
备注
每块木板切割方案相同
合计数量： ___359____
774
2153
1623
1614
木板 总利用率 : __0.9964__
木板总利用率 =
问题五
（ 1）算法分析
根据第四题所得分割方案，建立数学模型进行求解。 （ 2）模型建立
k 4
max s.t.
ca
j
ij
i 1 k
j 1
ha
i
ij
4
i 1
d j
LW
aij l j w j , i 1,..., k
j 1
aij , hi 为非负整数
（3）模型求解
木板 S1 的数量 100
木板 S1
合计数量 100
P1 的数量
59
P2 的数量
0
P3 的数量
0
P4
的数量
0
利润（元）
木板 利用率 0.982979
木板
备注
1174.1
每块木板切割方案相同
木板总利用率
总利润 :
1174100
总利用率 :
_0.982979_
进一步讨论 结果表示，分析与检验 劳永逸的算法方案。 结语（模型评价，特点
误差分析
上述问题求得的只是近似解，可能还有优化的空间，目前还没有发现此类解决
NP 问题一
优缺点 改进方法 推广）
该数学模型只能得到解的下限，不能直接得出解的结果，一方面是因为该模型选择用面积
近似求解而没有考虑到所装载物体的形状，另一方面是因为无法很好的将木板的长宽与变量联
系在一起（约束条件的缺少），因此只能求出可行解的上限或者下限，不能求出精确解。除此
之外，上述贪心策略求解切割方案的移植性较差，只能用于解决一些问题，但对于某些问题能
得到更好的结果，例如问题一，采用
guillotine 只能求出装载 p1 数为 56，而采用贪心策略则能
求出装载 p1 数为 59，更大得接近此问题的上限装载量 60。对于已存在的切割方案的优化求解，
可以采用一些智能算法对问题的解空间进行检索，进一步获取较多的切割方案。这种方法也是寻求最优的全局最优解的另一种方式。
参考文献
[1] 向文欣,荀珂, 冉翠翠. 基于两段排样方式的剪冲下料优化算法[J]. 锻压技术,2019,44(06):35-40. [2] 郑明月 , 刘林 , 阚方 , 方昶 . 结合批量问题的多目标矩形件优化排样 用 ,2014,50(22):260-264.
[3] 潘卫平 . 矩形件二维剪切下料排样算法研究
[D]. 广西大学 ,2015.
[J]. 计算机工程与应
[4] 张军 , 金明 爱 , 王锡禄 , 冯 恩民 . 一刀切下 料的数学模型 版 ),2001(01):11-14.
[J]. 延边大学学报 ( 自然科学 [J]. 电子质
[5] 林春婷 , 杨连池 , 王志煌 , 张国忠 , 叶德火 . 激光切纸机网络共享的设计实现 量 ,2018(11):32-34 量
木材最优切割
