木板最优切割问题pdf模板 g193

木板最优切割问题

Advances in Applied Mathematics 应用数学进展, 2020, 9(7), 1072-1083

Published Online July 2020 in Hans. 

https://doi.org/10.12677/aam.2020.97127

Optimal Cutting of Wood

Fan Zhang1, Zezhong Chen1, Guangliang He1, Mingchun Wang1,2

1

College of Information and Intelligent Science and Technology, Hunan Agricultural University, Changsha Hunan

Hunan Agricultural University, Changsha Hunan

2

th

st

th

Received: Jul. 5 , 2020; accepted: Jul. 21 , 2020; published: Jul. 28 , 2020

Abstract

In this paper, based on integer linear programming and multi-objective programming, a mul-

ti-stage analysis model with the goal of maximizing the utilization rate of wood board is estab-

lished for the optimization of two-dimensional rectangular cutting. Considering the product type

from single to multiple, the product production task and the limit of wood material, from the

shallow to the deep, program is written step by step, and then combined with LINGO solution, the

system’s optimal cutting program is gotten. Compared with commercial cutting software, the re-

sults show that the model can effectively solve the problem of wood cutting, and the model is sta-

ble and has good optimization ability.

Keywords

Integral Linear Programming, Multistage Analysis, Multi-Objective Programming

木板最优切割问题

1

1

1

帆 ，陈泽中 ，何光亮 ，王明春

1,2

张

1湖南农业大学信息与智能科学技术学院，湖南 长沙

2湖南农业大学，湖南 长沙

收稿日期：2020年7月5日；录用日期：2020年7月21日；发布日期：2020年7月28日

摘 要

本文以整数线性规划和多目标规划为理论基础，针对二维矩形切割优化问题，建立了以木板利用率最大

为目标的多阶段分析模型。考虑了产品类型由单一到多元，产品生产任务以及木板原料的限定，由浅到

深，一步步编写程序结合LINGO求解得到系统的最优切割方案。与商业切割软件对比结果表明，该模型

可以有效地解决木板切割问题，模型稳定且寻优能力较好。

文章引用: 张帆, 陈泽中, 何光亮, 王明春. 木板最优切割问题[J]. 应用数学进展, 2020, 9(7): 1072-1083.

DOI: 10.12677/aam.2020.97127

张帆 等

关键词

整数线性规划，多阶段分析，多目标规划

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Open Access

1. 引言

工厂中经常会碰到一些材料切割的优化问题，为了节省材料，减少废料对环境的污染，必须选择最

优的切割方案。某家具行业中有一批木板用于加工，在加工过程中，木板被切割成不同面积大小，分别

加工成不同的产品。在木板的面积和数量有限的情况下，安排木板切割使得在完成生产任务的基础上，

最大化利用率和家具厂的利润成为亟需解决的问题。简化切割操作，对提高工厂的经济效益和增大产品

竞争力具有重要意义。

在工业生产流程中，一般是家具厂根据订单要求的产品类型来加工。原木板作为毛坯按照产品生产

任务被切割成不同面积大小。优化切割方案并得出利润最大的方案是最终决策的来源。如图 1 所示。

Figure 1. Curve: system result of standard experiment

图 1. 标准试验系统结果曲线

本文依据这个流程基于二维矩形切割建立了规划模型，分析了怎样实现木板的最优切割，使木板利

用率与利润达到最高，产品类型由单一到多元，并考虑了产品的生产任务以及木板原料的限定，最终系

统给出了符合要求的切割方案。

2. 数据来源和模型假设

本研究对象来源于第 16 届五一数学建模竞赛数据，对矩形木板进行切割，需要得到四种类型的产品，

木板的具体参数数据如表 1 所示，产品的具体参数数据如表 2 所示。

DOI: 10.12677/aam.2020.97127

1073

应用数学进展

张帆 等

Table 1. The specific parameter data of the plank

表 1. 木板的具体参数数据

木板

长度(cm)

宽度(cm)

S1

300

150

Table 2. Product specific parameter data

表 2. 产品的具体参数数据

产品类型

长度(cm)

37.3

宽度(cm)

生产任务(件)

774

利润(元/件)

P1

P2

P3

P4

20.1

28.2

22.9

22.5

19.9

23.0

21.0

16.0

47.7

2153

40.6

1623

31.1

1614

1) 不计木板的厚度和割缝宽度；

2) 每一刀仅可切割成直线；

3) 每一刀不考虑斜向切割；

4) 切割下来的木板在通过加工得到产品时，没有材料的损失；

5) 切割木板时无损耗，即不产生废料。

3. 符号说明

相关符号说明见表 3。

Table 3. Symbol description

表 3. 符号说明

符号

Z

含义

总利润

单位

元

%

K

L

木板总利用率

S1 木板长度

cm

cm

件

W

Pi

S1 木板宽度

第 i 个产品生产任务

第 i 个产品长度

li

cm

cm

元

wi

pi

第 i 个产品宽度

第 i 个产品的利润

hi

第 i 个产品的单位面积价格

第 j 个方案的木板数量

第 j 个方案的木板利用率

第 j 个方案的利润

元/件∙cm2

件

c

j

k

z

%

j

元

j

Lli

Wwi

Lwi

Wli

m

第 i 个产品的长度在水平方向上的个数

第 i 个产品的宽度在垂直方向上的个数

第 i 个产品的长度在垂直方向上的个数

第 i 个产品的宽度在水平方向上的个数

产品种类数

件

件

件

件

类

n

方案个数

个

DOI: 10.12677/aam.2020.97127

1074

应用数学进展

张帆 等

4. 二维下料中的矩形切割

矩形切割问题是二维下料的一个重要研究方向，对于一块木板，在水平方向和垂直方向切割可以得

到两种毛坯，将这两种毛坯沿同一方向堆砌，组成两种同类条带[1]，如图 2 所示。

Figure 2. Blank 1.1 (left), Blank 1.2 (right), Strip 1.1 (left), Strip 1.2 (right)

图 2. 毛坯 1.1 (左)，毛坯 1.2 (右)，同型条带 1.1 (左)，同型条带 1.2 (右)

5. 单一产品的木板切割

在木板上切割单一产品，求木板利用率最大的切割方案。即看成产品在木板上的排列组合，与木板

利用率直接关联的排列面积为目标函数。决策变量假设是产品在某一方向的排列个数，那么约束条件包

括产品排列长宽不能大于木板本身。

假设第 i 个产品在水平方向上的个数和在垂直方向上的个数分别为 Ll ， Lw ，以他们为决策变量，

i

i

切割面积最大为目标建立如下的整数线性规划模型

目标函数

maxWw ×Ll +Wl ×Lw

i

(1)

(2)

i

i

i

由于切割下来的条带集合的长度不能超过木板的长度，则约束条件

l × Ll +Wl × Lw ≤ L

i

i

i

i



Ll , Lw ≥ 0,为整数



i

i

其中， Ll = L l  ， Lw = L w  ，   为向下取整符号。

i

i

i

i

木板利用率是评价一个切割方案的有效指标，利用率高的切割方案不仅节省了原料，而且提高了工

厂利润，利用率用在木板上切割下来的毛坯面积与木板面积的比例表示，即一块木板的利用率[2]为

∑

(

)

l w Ww Lli Wli Lwi

×

+

×

i

i

i

i

(3)

LW

对于产品 P1，其中 i = 7 ， Ll = L l  = 7 ， Lw = L w  = 4 ，那么

1

1

i

i

max 7Ll1 + 4Lw

1

373Ll + 201Lw ≤ 3000

1

1



Ll , Lw ≥ 0,为整数

1

1

DOI: 10.12677/aam.2020.97127

1075

应用数学进展

张帆 等

利用 LINGO [3]得到最优解为：Ll1

=1，L w1 =13

，最优值为：59。因此一块木板的利用率为 98.3%。

切割方案示意图如图 3 所示，其中切割下来的产品 P1 数量如表 4 所示。

Figure 3. Schematic diagram of wood cutting scheme for product P1

图 3. 产品 P1 的木板切割方案示意图

Table 4. The specific parameter value of the cutting scheme

表 4. 切割方案的具体参数值

P1 数量(件)

利用率(%)

59

98.3

单一产品的木板切割排列简单，建立整数线性规划模型可以得到切割面积最大的方案，该方案下的

利用率较高。

6. 多元产品的木板切割

6.1. 双产品的木板切割

{

}

在木板上切割两类产品，以集合 Ll , Lw 为决策变量，切割度最大为目标建立如下的整数线性规划

i

i

模型。

目标函数

∑ ( × )+ ∑ × ( )

max

l

Lli

wi L w

(4)

(5)

i

i

i

i

由于切割下来的宽度不能超过木板的宽度，则约束条件



∑

( × )+

∑ (

i

) ≤



l

i

Lli

wi

×

Lwi

W



i

Ll , Lw ≥ 0,为整数

i

i

由该模型得到某一种毛坯的排列方式，将他作为初始排列，不断迭代模型，最终木板不能排列毛坯

时停止。

统计这两类产品的数量，根据下面公式计算木板利用率

∑

m

l w a

i

i

ji ×100%

(6)

k

=

j=1

j

LW

步骤 1：对于产品 P1 和产品 P3， i =1,3 。这两种类型组合的整数线性规划为

DOI: 10.12677/aam.2020.97127

1076

应用数学进展

张帆 等

max 373Ll + 201Lw + 406Ll + 229lw

3

1

1

3

373Ll + 201Lw + 406Ll + 229Lw ≤ 3000

1

1

3

3



Ll , Lw , Ll , Lw 为整数



1

1

3

3

(

)T = (1, 7,3, 0

利用 LINGO 得到最优解为： Ll , Lw , Ll , Lw

3

)

T

。

1

1

3

由于 Lw1 的个数最多，占切割木板的面积最大，因此先排列此毛坯，由最优解得出一部分排列 a，如

图 4 所示。

步骤 2：模型迭代

max 373Ll1 + 406Ll3

373Ll + 406Ll ≤1593

1

3



Ll , Lw , Ll , Lw 为整数



1

1

3

3

利用 LINGO 得到最优解为： Ll1

=1， Ll3 = 3，由此得到排列 b，如图 4 所示。

步骤 3：木板中间的剩下未排列区域，以余料最少为原则，得到排列 c，如图 4 所示。

Figure 4. Iteratively arrangement process diagram

图 4. 迭代排列过程图

该模型可以得到多种方案，图 5，图 6，图 7 分别为三种切割方案，其中切割下来的产品数量和利用

率如表 5 所示。

DOI: 10.12677/aam.2020.97127

1077

应用数学进展

张帆 等

Figure 5. Schematic diagram of wood cutting scheme 1 for product P1 and P3

图 5. 产品 P1 和 P3 的木板切割方案 1 示意图

Figure 6. Schematic diagram of wood cutting scheme 2 for product P1 and P3

图 6. 产品 P1 和 P3 的木板切割方案 2 示意图

Figure 7. Schematic diagram of wood cutting scheme 3 for product P1 and P3

图 7. 产品 P1 和 P3 的木板切割方案 3 示意图

DOI: 10.12677/aam.2020.97127

1078

应用数学进展

张帆 等

Table 5. The specific parameter value of the cutting scheme

表 5. 切割方案的具体参数值

方案编号

P1 数量(件)

P3 数量(件)

利用率(%)

98.8

1

2

3

32

33

43

22

21

13

98.6

98.5

6.2. 基于生产任务的双产品木板切割

在木板上全部切割产品 P1 作为方案 4，全部切割产品 P3 作为方案 5，得到表 6。

Table 6. The specific parameter value of the cutting scheme

表 6. 切割方案的具体参数值

方案编号

P1 数量(件)

P3 数量(件)

利用率(%)

98.8

1

2

3

4

5

32

33

43

59

0

22

21

13

0

98.6

98.5

98.3

47

97.1

构造方案矩阵 An×m = a ，其中 i 1, 2; j 1, ,5 。方案矩阵用于存储每一个方案下的产品数量。

= 

( )

=

ji







22

32





A

5×2

=













 0

47

以 cj 为决策变量，总木板利用率最高为目标建立整数规划模型。

目标函数

∑

l w P

i

i

i i

max

(7)

(8)

(9)

∑

n

LW j=1c

j

由于需要完成产品的生产任务，则约束条件为

∑

n





a c ≥ P, i =1, ,m

j i



j=1 ji



c ≥ 0,

为整数, j =1, ,n



j

统计这两类产品分别在每种方案下的数量，根据下面公式计算木板利用率

∑

l w P

K =

i

i

i

i

×100%

∑

n

LW j=1c

j

对于产品 P1 和 P3，整数规划为

373×202×774 + 406×229×1623

max

∑

5

j=1c 3000 1500

×

×

j

DOI: 10.12677/aam.2020.97127

1079

应用数学进展

张帆 等



+

+

+

+ ×

32c1 33c2 44c3 59c4 0 c5 774

≥



22c + 21c +12c + 0×c + 47c ≥1623

1

2

3

4

5



c ≥ 0,为整数, j =1,,5



j

编写程序，求出每个方案下木板 S1 的数量以及总利用率。结合 LINGO 得出最优解为：

(

c ,c ,c ,c ,c

)T = (21,1, 2, 0, 24)

5

T

1

2

3

4

最优值为： K = 96.7% ， K′ = 97.9% 。其中 K 是实际的木板总利用率，P1 和 P3 的产品数量为 774

′

件和 1623 件不变。 K 是按超过生产任务的产品数量计算的木板利用率。切割下来的产品数量和总利用

率如表 7 所示。

Table 7. The specific parameter value of the cutting scheme

表 7. 切割方案的具体参数值

方案编号

S1 数量(张)

P1 数量(件)

P3 数量(件)

利用率(%)

1

2

3

4

5

21

32

22

98.8

1

33

21

98.6

2

0

43

13

98.5

98.3

59

0

0

47

24

97.1

合计 48

合计 774

合计 1623

木板总利用率 96.7

6.3. 基于生产任务的多产品木板切割

由基于生产任务的两类产品木板切割可得到多类产品的切割处理方法。假设四类产品 P1，P2，P3

和 P4 都需要完成生产任务，由排列组合的原理四类产品有 24 −1种切割方案。

( )

= b ，其中 bji 表示在第 j 个方案下产品 i 的数量。文章前面已知矩阵 B 里每一个

ji

设方案矩阵 B

15×4

元素的数值。以 cj 为决策变量，总木板利用率最高为目标建立整数规划模型

目标函数

∑

4

l w P

1

i

i i

max

i=

∑

15

LW j=1c

j

约束条件

 15

∑



B c ≥ P, i =1, ,5



ji

j

i



j=1



c ≥ 0,为整数, j =1,,15



j

利用 LINGO 得到 K = 97.06% ， K′ = 97.70% 。切割下来的产品数量和总利用率如表 8 所示。

Table 8. The specific parameter value of the cutting scheme

表 8. 切割方案的具体参数值

方案编号

S1 数量(张)

P1 数量(件)

P2 数量(件)

P3 数量(件)

P4 数量(件)

利用率(%)

98.3

1

2

11

0

59

0

0

0

0

0

0

31

92.67

DOI: 10.12677/aam.2020.97127

1080

应用数学进展

张帆 等

Continued

3

4

0

0

0

47

0

97.1

93.5

0

0

0

0

48

5

0

20

21

0

0

96.09

98.3

6

0

17

0

0

45

7

39

0

16

24

0

97.41

98.76

96.98

97.63

98.1

8

5

32

0

22

0

9

0

0

21

0

22

10

11

12

13

14

15

0

0

0

31

9

0

10

0

25

9

0

7

19

0

18

96.45

97.41

97.81

98.21

0

20

9

18

0

85

0

0

23

18

5

7

21

19

1

合计 140

合计 774

合计 2153

合计 1623

合计 1614

木板总利用率 97.06

将模型得到的不同方案下木板利用率与商业软件 cuttLogic 得到的结果做对比，如表 9 所示。

Table 9. The specific parameter value of the cutting scheme

表 9. 切割方案的具体参数值

方案编号

组合

P1

模型结果(%)

98.3

cuttLogic 结果(%)

98.3

差值(%)

0

1

2

P2

92.67

97.1

92.67

97.1

0

3

P3

0

4

P4

93.5

93.5

0

5

P1, P2

96.09

98.3

97.9

-1.81

0

6

P1, P4

98.3

7

P2, P3

97.41

98.76

96.98

97.63

98.1

96.05

98.23

97.34

98.7

1.36

0.53

-0.36

-1.07

-0.46

-1.1

0.52

-0.39

0.16

8

P1, P3

9

P2, P4

10

11

12

13

14

15

P3, P4

P1, P3, P4

P1, P2, P4

P1, P2, P3

P2, P3, P4

P1, P2, P3, P4

98.56

97.55

96.89

98.2

96.45

97.41

97.81

98.21

98.05

模型结果：

最大值 98.76

最小值 92.67

软件结果：

最大值 98.7

最小值 92.67

通过该表可以看出 15 个方案中，模型结果与软件模拟结果基本相同，甚至较多方案的利用率超过了

软件结果，说明模型得出的切割方案是合理的，且模型的寻优能力好。模型结果的最大利用率大于软件

DOI: 10.12677/aam.2020.97127

1081

应用数学进展

张帆 等

的最大利用率，最小利用率数值相同，说明该模型比较稳定。

6.4. 限定原料的多产品木板切割

不考虑产品的生产任务，给定木板数量，首先考虑产品的组合形式。以产品的单位面积价格作为依

pi

li wi

据来选取产品组合，由公式 hi =

计算出 h ,h ,h ,h ，且 max{h } =

h1 ，如表 10 所示。

1

2

3

4

i

Table 10. Product specific parameter data

表 10. 产品的具体参数值

产品类型

单位面积价格(元/件∙cm2)

P1

P2

P3

P4

0.0265

0.0171

0.0226

0.0229

( = ,15)

1,

假设给定 100 张木板 S1，每张木板的切割方案相同，对于 P1，P2，P3 和 P4 四类产品，以 c

j

j

为决策变量，总木板利用率最高为目标函数 1，总利润最大为目标函数 2，建立多目标规划模型。

目标函数 1

∑

4

l w P

1

i

i i

max

i=

∑

15

LW j=1c

j

目标函数 2

∑

max a P

ji

i

i

约束条件

 15

∑

b c ≥ P, i =1, 2,3, 4



ji

j

i



j=1



c ≥ 0,为整数, j =1,,15



j

利用 LINGO 得到 K = 98.3% ， w

=1174.1，W

=

1174.1 100 11740 。切割下来的产品数量和总利

×

=

1

用率如表 11 所示。

Table 11. The specific parameter value of the cutting scheme

表 11. 切割方案的具体参数值

S1 数量(张)

P1 数量(件)

P2 数量(件)

P3 数量(件)

P4 数量(件)

利润(元/件)

1174.1

利用率(%)

98.3

1

59

0

0

0

100

774

2153

1623

1614

总利润 117410

木板总利用率 98.3

7. 模型评价与改进

7.1. 模型评价

1) 计算简单，结果正确，符合实际，模型具有合理性和可行性，是解决木板切割问题的有效方法；

2) 模型可由少量的编程结合 LINGO 得到最优切割方案，简洁有效，易于求解；

DOI: 10.12677/aam.2020.97127

1082

应用数学进展

张帆 等

3) 模型约束条件不多，一些复杂的因素没有纳入考虑范围。比如只考虑的同型条带没有考虑普通条

带等；

4) 迭代求解会使误差成倍增长；

5) 本文求解属于半自动方法，不够智能，在处理巨大数据上不够快速。

7.2. 模型改进

1) 结合模型缺点，对规划作更加严格的约束，建立更加精确，更加适用于实际工艺应用的模型；

2) 改进算法，使得原有模型更加快捷和智能。

参考文献

[1] 陈秋莲, 宋仁坤, 崔耀东. 考虑余料价值的三阶段二维剪切下料算法[J]. 图学学报, 2017, 38(1): 10-14.

[2] 杨振东. 基于数控的玻璃最优化切割的研究[D]: [硕士学位论文]. 青岛: 山东科技大学, 2003.

[3] 谢金星, 薛毅. 优化建模与 LINDO/LINGO 软件[M]. 北京: 清华大学出版社, 2005.

DOI: 10.12677/aam.2020.97127

1083

应用数学进展

word模板链接: https://pan.baidu.com/s/1A3q3nYK_PdfzhVoYWLyfyA 提取码: h932

pdf模板链接: https://pan.baidu.com/s/1JdnuhFd0TL6w2adb24aGRA 提取码: jgsb