基于多元線性規劃模型的木板最優切割

劉芳宇，袁玥，唐淑娟

（南華大學計算機學院，衡陽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產品組合的最優切割方案示意圖