ABSTRACT

In this paper, based on integer linear programming and multi-objective programming, a multi-stage analysis model with the goal of maximizing the utilization rate of wood board is established 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 results show that the model can effectively solve the problem of wood cutting, and the model is stable and has good optimization ability.

Keywords:Integral Linear Programming, Multistage Analysis, Multi-Objective Programming

木板最优切割问题

张帆¹，陈泽中¹，何光亮¹，王明春^1,2

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

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

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

摘 要

本文以整数线性规划和多目标规划为理论基础，针对二维矩形切割优化问题，建立了以木板利用率最大为目标的多阶段分析模型。考虑了产品类型由单一到多元，产品生产任务以及木板原料的限定，由浅到深，一步步编写程序结合LINGO求解得到系统的最优切割方案。与商业切割软件对比结果表明，该模型可以有效地解决木板切割问题，模型稳定且寻优能力较好。

关键词 :整数线性规划，多阶段分析，多目标规划

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/

1. 引言

工厂中经常会碰到一些材料切割的优化问题，为了节省材料，减少废料对环境的污染，必须选择最优的切割方案。某家具行业中有一批木板用于加工，在加工过程中，木板被切割成不同面积大小，分别加工成不同的产品。在木板的面积和数量有限的情况下，安排木板切割使得在完成生产任务的基础上，最大化利用率和家具厂的利润成为亟需解决的问题。简化切割操作，对提高工厂的经济效益和增大产品竞争力具有重要意义。

在工业生产流程中，一般是家具厂根据订单要求的产品类型来加工。原木板作为毛坯按照产品生产任务被切割成不同面积大小。优化切割方案并得出利润最大的方案是最终决策的来源。如图1所示。

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

本文依据这个流程基于二维矩形切割建立了规划模型，分析了怎样实现木板的最优切割，使木板利用率与利润达到最高，产品类型由单一到多元，并考虑了产品的生产任务以及木板原料的限定，最终系统给出了符合要求的切割方案。

2. 数据来源和模型假设

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

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

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

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

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

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

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

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

3. 符号说明

相关符号说明见表3。

表3. 符号说明

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

矩形切割问题是二维下料的一个重要研究方向，对于一块木板，在水平方向和垂直方向切割可以得到两种毛坯，将这两种毛坯沿同一方向堆砌，组成两种同类条带 [1]，如图2所示。

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

5. 单一产品的木板切割

在木板上切割单一产品，求木板利用率最大的切割方案。即看成产品在木板上的排列组合，与木板利用率直接关联的排列面积为目标函数。决策变量假设是产品在某一方向的排列个数，那么约束条件包括产品排列长宽不能大于木板本身。

假设第i个产品在水平方向上的个数和在垂直方向上的个数分别为 $L{l}_i$，$L{w}_i$，以他们为决策变量，切割面积最大为目标建立如下的整数线性规划模型

目标函数

$\max W{w}_i\times L{l}_i+W{l}_i\times L{w}_i$ (1)

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

$\{\begin{array}{l}{l}_i\times L{l}_i+W{l}_i\times L{w}_i\le L\\ L{l}_i,L{w}_i\ge 0,为整数\end{array}$ (2)

其中， $L{l}_i=\lfloor L/l_i\rfloor$，$L{w}_i=\lfloor L/w_i\rfloor$，$\lfloor \rfloor$ 为向下取整符号。

木板利用率是评价一个切割方案的有效指标，利用率高的切割方案不仅节省了原料，而且提高了工厂利润，利用率用在木板上切割下来的毛坯面积与木板面积的比例表示，即一块木板的利用率 [2] 为

$\frac{{\displaystyle {\sum }_i{l}_i{w}_i\left(W{w}_i\times L{l}_i+W{l}_i\times L{w}_i\right)}}{LW}$ (3)

对于产品P1，其中 $i=7$，$L{l}_1=\lfloor L/l_1\rfloor =7$，$L{w}_i=\lfloor L/w_i\rfloor =4$，那么

$\max 7L{l}_1+4L{w}_1$

$\{\begin{array}{l}373L{l}_1+201L{w}_1\le 3000\\ L{l}_1,L{w}_1\ge 0,为整数\end{array}$

利用LINGO [3] 得到最优解为： $L{l}_1=1$，$L{w}_1=13$，最优值为：59。因此一块木板的利用率为98.3%。

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

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

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

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

6. 多元产品的木板切割

6.1. 双产品的木板切割

在木板上切割两类产品，以集合 $\left\{L{l}_i,L{w}_i\right\}$ 为决策变量，切割度最大为目标建立如下的整数线性规划模型。

目标函数

$\max {\displaystyle {\sum }_i\left(l_i\times L{l}_i\right)}+{\displaystyle {\sum }_i{w}_i\times L}\left(w_i\right)$ (4)

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

$\{\begin{array}{l}{\displaystyle {\sum }_i\left(l_i\times L{l}_i\right)}+{\displaystyle {\sum }_i\left(w_i\times L{w}_i\right)}\le W\\ L{l}_i,L{w}_i\ge 0,为整数\end{array}$ (5)

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

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

$k_j=\frac{{\displaystyle {\sum }_{j=1}^m{l}_i{w}_i{a}_{ji}}}{LW}\times 100\%$ (6)

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

$\max 373L{l}_1+201L{w}_1+406L{l}_3+229l{w}_3$

$\{\begin{array}{l}373L{l}_1+201L{w}_1+406L{l}_3+229L{w}_3\le 3000\\ L{l}_1,L{w}_1,L{l}_3,L{w}_3为整数\end{array}$

利用LINGO得到最优解为： ${\left(L{l}_1,L{w}_1,L{l}_3,L{w}_3\right)}^{\text{T}}={\left(1,7,3,0\right)}^{\text{T}}$。

由于 $L{w}_1$ 的个数最多，占切割木板的面积最大，因此先排列此毛坯，由最优解得出一部分排列a，如图4所示。

步骤2：模型迭代

$\max 373L{l}_1+406L{l}_3$

$\{\begin{array}{l}373L{l}_1+406L{l}_3\le 1593\\ L{l}_1,L{w}_1,L{l}_3,L{w}_3为整数\end{array}$

利用LINGO得到最优解为： $L{l}_1=1$，$L{l}_3=3$，由此得到排列b，如图4所示。

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

图4. 迭代排列过程图

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

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

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

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

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

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

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

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

构造方案矩阵 $A_{n\times m}=\left(a_{ji}\right)$，其中 $i=1,2;j=1,\cdots ,5$。方案矩阵用于存储每一个方案下的产品数量。

$A_{5\times 2}=\left(\begin{array}{ccc}32& \cdots & 22\\ ⋮& \ddots & ⋮\\ 0& \cdots & 47\end{array}\right)$

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

目标函数

$\max \frac{{\displaystyle {\sum }_i{l}_i{w}_i{P}_i}}{LW{\displaystyle {\sum }_{j=1}^n{c}_j}}$ (7)

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

$\{\begin{array}{l}{\displaystyle {\sum }_{j=1}^n{a}_{ji}{c}_j}\ge P_i,i=1,\cdots ,m\\ c_j\ge 0,为整数,j=1,\cdots ,n\end{array}$ (8)

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

$K=\frac{{\displaystyle {\sum }_i{l}_i{w}_i{P}_i}}{LW{\displaystyle {\sum }_{j=1}^n{c}_j}}\times 100\%$ (9)

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

$\max \frac{373\times 202\times 774+406\times 229\times 1623}{{\displaystyle {\sum }_{j=1}^5{c}_j}\times 3000\times 1500}$

$\{\begin{array}{l}32c_1+33c_2+44c_3+59c_4+0\times c_5\ge 774\\ 22c_1+21c_2+12c_3+0\times c_4+47c_5\ge 1623\\ c_j\ge 0,为整数,j=1,\cdots ,5\end{array}$

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

${\left(c_1,c_2,c_3,c_4,c_5\right)}^{\text{T}}={\left(21,1,2,0,24\right)}^{\text{T}}$

最优值为： $K=96.7\%$，$K^{\prime }=97.9\%$。其中K是实际的木板总利用率，P1和P3的产品数量为774件和1623件不变。 $K^{\prime }$ 是按超过生产任务的产品数量计算的木板利用率。切割下来的产品数量和总利用率如表7所示。

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

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

由基于生产任务的两类产品木板切割可得到多类产品的切割处理方法。假设四类产品P1，P2，P3和P4都需要完成生产任务，由排列组合的原理四类产品有 $2^4-1$ 种切割方案。

设方案矩阵 $B_{15\times 4}=\left(b_{ji}\right)$，其中 $b_{ji}$ 表示在第j个方案下产品i的数量。文章前面已知矩阵B里每一个元素的数值。以 $c_j$ 为决策变量，总木板利用率最高为目标建立整数规划模型

目标函数

$\max \frac{{\displaystyle {\sum }_{i=1}^4{l}_i{w}_i{P}_i}}{LW{\displaystyle {\sum }_{j=1}^{15}{c}_j}}$

约束条件

$\{\begin{array}{l}{\displaystyle \underset{j=1}{\overset{15}{\sum }}{B}_{ji}{c}_j}\ge P_i,i=1,\cdots ,5\\ c_j\ge 0,为整数,j=1,\cdots ,15\end{array}$

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

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

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

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

通过该表可以看出15个方案中，模型结果与软件模拟结果基本相同，甚至较多方案的利用率超过了软件结果，说明模型得出的切割方案是合理的，且模型的寻优能力好。模型结果的最大利用率大于软件的最大利用率，最小利用率数值相同，说明该模型比较稳定。

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

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

据来选取产品组合，由公式 $h_i=\frac{p_i}{l_i{w}_i}$ 计算出 $h_1,h_2,h_3,h_4$，且 $\max \left\{h_i\right\}=h_1$，如表10所示。

表10. 产品的具体参数值

假设给定100张木板S1，每张木板的切割方案相同，对于P1，P2，P3和P4四类产品，以 $c_j\left(j=1,\cdots ,15\right)$ 为决策变量，总木板利用率最高为目标函数1，总利润最大为目标函数2，建立多目标规划模型。

目标函数1

$\max \frac{{\displaystyle {\sum }_{i=1}^4{l}_i{w}_i{P}_i}}{LW{\displaystyle {\sum }_{j=1}^{15}{c}_j}}$

目标函数2

$\max {\displaystyle \underset{i}{\sum }{a}_{ji}{P}_i}$

约束条件

$\{\begin{array}{l}{\displaystyle \underset{j=1}{\overset{15}{\sum }}{b}_{ji}{c}_j}\ge P_i,i=1,2,3,4\\ c_j\ge 0,为整数,j=1,\cdots ,15\end{array}$

利用LINGO得到 $K=98.3\%$，$w_1=1174.1$，$W=1174.1\times 100=11740$。切割下来的产品数量和总利用率如表11所示。

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

7. 模型评价与改进

7.1. 模型评价

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

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

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

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

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

7.2. 模型改进

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

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

文章引用

张 帆,陈泽中,何光亮,王明春. 木板最优切割问题
Optimal Cutting of Wood[J]. 应用数学进展, 2020, 09(07): 1072-1083. https://doi.org/10.12677/AAM.2020.97127

参考文献