基于多元线性规划模型的木板最优切割
2019-09-06刘芳宇袁玥唐淑娟
刘芳宇，袁玥，唐淑娟
（南华大学计算机学院，衡阳421000）
0 引言
（1）问题背景
在当今的工业领域中，木板切割是成品加工过程中最为重要的步骤，也是保证成品质量的重要工序[1]。在资源和成本有限的情况下，合理的木板切割方案不仅可以保证产品的质量，提高资源利用率，还能够降低产品的制造成本。因此合理的木板切割方案成为木工厂亟待解决的问题。
（2）问题叙述
木工厂新进一批木板如表1 所示，需要切割生产表2 所示规格的产品，请给出如下问题的木板最优切割方案。
表1 待切木板的尺寸
表2 产品尺寸及生产任务
①在一块木板上切割P1 产品，给出木板利用率最高的切割方案。
②在一块木板上切割P1 和P3 产品，给出按照木板利用率由高到低排序的前3 种切割方案。
③需要完成表2 中P1 和P3 产品的生产任务，给出木板总利用率最高的切割方案。
④需要完成表2 中P1、P2、P3、P4 产品的生产任务，给出木板总利用率最高的切割方案。
1 问题假设
（1）木板厚度和割缝宽度忽略不计；
（2）假设最优切割方案的边缘空隙最小。
2 符号说明
表3
3 模型的建立与求解
3.1 问题一模型的建立与求解
3.1.1 模型的建立
为了得到在一块木板上切割P1 产品使得木板利用率最高（即剩余木板面积最小）的切割方案，建立下列方程：
当底层P1 产品竖向切割时：
当底层P1 产品横向切割时：
3.1.2 模型的求解
Step1：先针对木板横看时最底层P1 产品切割的最优化结果，建立式（1）的多元线性规划模型，运用Lingo软件对其进行求解；
Step2：在Step1 的结果上对木板竖看方向求解最优化结果，建立式（2）和式（3）的多元线性规划模型，运用Lingo 对其进行求解；
Step3：代入约束条件中验证所得到的结果是否满足题意；
Step4：若满足，则输出此结果；若不满足，则无解。
3.1.3 模型的结果
通过Lingo 软件，分别对式（1-3）的多元线性规划模型进行求解，得到：
当底层P1 产品竖向切割时：
当底层P1 产品横向切割时：
其中式（4）的结果表示横看木板时最底层横切P1产品1 块，竖切P1 产品13 块；式（5）的结果表示在式（4）的基础上，竖看木块时，竖切P1 产品4 块；式（6）的结果表示在式（4）的基础上，横看木板时，横切P1 产品7 块。
根据得到的最优解，我们可以确定木块的最优切割方式。通过CAD 作图软件对其进行模拟切割，得到图1。
图1 问题一的最优切割方案示意图
根据所建立的数学模型，计算在一块木板上切割P1 产品的数量和木板的利用率。
结果如表4 所示。
表4 问题1 的结果
3.2 问题二模型的建立与求解
3.2.1 模型的建立
为了得到在一块木板上切割P1 和P3 产品使得木板利用率由高到低排序的前3 种切割方案，建立如下方程：
目标函数：
约束条件
当底层P3产品垂直切割时：
目标函数：
约束条件：
当底层P3 产品水平切割时：
目标函数：
约束条件：
3.2.2 模型的求解
Step1：先针对木板横看时最底层P1 和P3 产品切割的最优化结果，建立式（7）的多元线性规划模型，运用Lingo 软件对其进行求解；
Step2：在Step1 的基础上对木板竖看方向求解最优化结果，建立式（8）和式（9）的多元线性规划模型，运用Lingo 软件对其进行求解；
Step3：对求解后的结果进行分析，当某一维度上不止一种摆放方式时，对剩余部分进行再次Step1、Step2的操作，直至其只有一种摆放方式；
Step4：代入约束条件中验证所得到的结果是否满足题意；
Step5：若满足，则输出此结果；若不满足，则无解。
3.2.3 模型的结果
通过Lingo 软件，分别对式（7-9）的多元线性规划模型进行求解，得到：
当底层P3 产品垂直切割时：
当底层P3 产品水平切割时：
其中式（10）的结果表示横看木板时最底层横切P3 产品4 块，竖切P3 产品6 块；式（11）的结果表示在式（10）的基础上，竖看木板时，横切P3 产品3 块，竖切P3 产品2 块；式（12）的结果表示在式（10）的基础上，横看木板时，横切P3 产品3 块，竖切P3 产品2 块。
根据得到的最优解，我们可以确定木块的最优切割方式。通过CAD 作图软件对其进行模拟切割，得到图2。
图2 问题2的最优切割方案示意图
由于P3 的长和宽都大于P1，因此我们可以用1个P1 替换P3，得到方案二，用2 个P1 替换两个P3，得到方案3。
结果如表5 所示。
表5 问题2 的结果
3.3 问题三模型的建立与求解
3.3.1 模型的建立与求解
为了完成表2 中P1 和P3 产品的生产任务，给出木板总利用率最高的切割方案。根据问题1 和问题2的分析我们已经得到了单独切割P1 产品和同时切割P1 和P3 产品的最优切割方案。因此，同问题1 的分析过程求解单独切割P3 产品的最优切割方案，建立如下方程：
目标函数：
约束条件：
通过Lingo 软件求解式（13），接着在该基础上对木板竖向方向采用题1 的方案进行同样的分析求解，得到图3。
从图3 可知，单独切割P3 时，一块木板可以切割出47 块P3 产品。综合问题1、问题2 的以及单独切割P3 的结果，得到表6。
图3 单独切割P3的最优切割方案示意图
表6
由于要完成表二中的产品生产要求，且又需要保证木板的利用率最高（即使用木板的总数量最少），因此将单独切割P1 产品的最优方案、单独切割P3 产品的最优方案和同时切割P1 和P3 产品的前3 种最优方案进行组合建立如下多元线性规划模型：
目标函数：
约束条件：
3.3.2 模型的结果
通过Lingo 软件对式（14）求解得到图4。
图4 问题3的最优解（Lingo求解）
由图4 求解结果可知，8 块木板采用方案1，40 块木板采用方案3，其他方案都采用0 块木板，由此得到表7。
表7 问题3 的结果
3.4 问题四模型的建立与求解
3.4.1 模型的建立与求解
为了完成表2 中P1、P2、P3 和P4 产品的生产任务，给出木板总利用率最高的切割方案。根据问题1、问题2、问题3 的分析得知，求解产品切割的最优方案是使木板剩余空间尽可能减少。同问题3 的分析过程一致，首先，对{P1、P2、P3、P4}集合求其除空集外的子集，即得到{P1}、{P2}、{P3}、{P4}、{P1、P2}、{P1、P3}、{P1、P4}、{P2、P3}、{P2、P4}、{P3、P4}、{P1、P2、P3}、{P1、P2、P4}、{P1、P3、P4}、{P2、P3、P4}、{P1、P2、P3、P4}共15 种方案，通过Lingo 软件分别建立多元线性规划模型求出每种方案的最优切割方案。如表8 所示。
表8 15 种方案的最优解
为了求得木板总利用率最高的切割方案，我们采用各最优的切割方案进行多元组合线性规划计算，用最少的木板切割完成产品的生产，得到如下方程：
3.4.2 模型的结果
利用Lingo 软件对多建立的多元线性规划模型进行求解，得到表9。
表9 问题4 的结果
4 模型的评价与推广
4.1 模型的优点
（1）该模型从最小间隙问题出发，使得切割间隙最小从而达到木板的最优利用率，这样可以将繁杂的产品切割问题转变为间隙的最小化问题，优化了模型结构，减少了模型的计算难度，同时也提高了模型整体的准确性。
（2）用表格的形式把所有方案的最优切割方案展现出来，更加直观，便于理解。
4.2 模型的缺点
（1）间隙的浪费仍然存在部分问题需要我们去攻克，我们只对木板边缘进行了最小间隙化分析，内部仍然存在一部分的间隙不能很好地被利用起来，导致总体的利用率在97%左右，不能完全利用。
（2）需要计算的方案组合太多，不利于产品过多时多元组合线性求解。
4.3 模型的推广
本文主要研究木板的最优切割问题，根据实际需求从而制定出不同的切割方案，可以把该模型和算法推广用于玻璃的切割、平面的填装等问题上，适用于各种固定结构的切割、组装问题等方面。
5 Lingo代码样板
max=（length1*x1+width1*y1+length2*x2+width2*y2+...+lengthN*xN+widthN*yN）/S1Length；
//S1 长度填充最优选择，lengthN 为所切目标木板的长，widthN 为所切目标木板的宽
//S1Length 为待切的S1 的长，N 为目标板块类型的数目
length1*x1 + width1*y1 + length2*x2 + width2*y2 + ... +lengthN*xN+widthN*yN＜=S1Length；
//限制条件
x1＞=0；//限制条件
y1＞=0；//限制条件
x2＞=0；
y2＞=0；
...
xN＞=0；
yN＞=0；
@gin（x1）；//整数限制
@gin（y1）；//整数限制
@gin（x2）；
@gin（y2）；
...
@gin（xN）；
@gin（yN）；
end
//通过这个通用模板，只需调节部分系数，就能给出某长度上最低端的最优切割方案
//即使得这种切割在这个维度的长度上所剩余的无用缝隙最少
//再利用循环嵌套，换横向继续求取当前方向长度最优切割方案
//直至整块板子的最优切割方案浮出水面
6 部分方案最优切割示意图
图5 P2、P3产品组合的最优切割方案示意图
图6 P2、P4产品组合的最优切割方案示意图
图7 P3、P4产品组合的最优切割方案示意图
图8 P1、P2、P3产品组合的最优切割方案示意图
图9 P1、P2、P4产品组合的最优切割方案示意图
图10 P1、P3、P4产品组合的最优切割方案示意图
图11 P1、P2、P3、P4产品组合的最优切割方案示意图
