劉芳宇，袁玥，唐淑娟

（南華大學(xué)計(jì)算機(jī)學(xué)院，衡陽421000）

0 引言

（1）問題背景

在當(dāng)今的工業(yè)領(lǐng)域中，木板切割是成品加工過程中最為重要的步驟，也是保證成品質(zhì)量的重要工序[1]。在資源和成本有限的情況下，合理的木板切割方案不僅可以保證產(chǎn)品的質(zhì)量，提高資源利用率，還能夠降低產(chǎn)品的制造成本。因此合理的木板切割方案成為木工廠亟待解決的問題。

（2）問題敘述

木工廠新進(jìn)一批木板如表1 所示，需要切割生產(chǎn)表2 所示規(guī)格的產(chǎn)品，請(qǐng)給出如下問題的木板最優(yōu)切割方案。

表1 待切木板的尺寸

表2 產(chǎn)品尺寸及生產(chǎn)任務(wù)

①在一塊木板上切割P1 產(chǎn)品，給出木板利用率最高的切割方案。

②在一塊木板上切割P1 和P3 產(chǎn)品，給出按照木板利用率由高到低排序的前3 種切割方案。

③需要完成表2 中P1 和P3 產(chǎn)品的生產(chǎn)任務(wù)，給出木板總利用率最高的切割方案。

④需要完成表2 中P1、P2、P3、P4 產(chǎn)品的生產(chǎn)任務(wù)，給出木板總利用率最高的切割方案。

1 問題假設(shè)

（1）木板厚度和割縫寬度忽略不計(jì)；

（2）假設(shè)最優(yōu)切割方案的邊緣空隙最小。

2 符號(hào)說明

表3

3 模型的建立與求解

3.1 問題一模型的建立與求解

3.1.1 模型的建立

為了得到在一塊木板上切割P1 產(chǎn)品使得木板利用率最高（即剩余木板面積最小）的切割方案，建立下列方程：

當(dāng)?shù)讓覲1 產(chǎn)品豎向切割時(shí)：

當(dāng)?shù)讓覲1 產(chǎn)品橫向切割時(shí)：

3.1.2 模型的求解

Step1：先針對(duì)木板橫看時(shí)最底層P1 產(chǎn)品切割的最優(yōu)化結(jié)果，建立式（1）的多元線性規(guī)劃模型，運(yùn)用Lingo軟件對(duì)其進(jìn)行求解；

Step2：在Step1 的結(jié)果上對(duì)木板豎看方向求解最優(yōu)化結(jié)果，建立式（2）和式（3）的多元線性規(guī)劃模型，運(yùn)用Lingo 對(duì)其進(jìn)行求解；

Step3：代入約束條件中驗(yàn)證所得到的結(jié)果是否滿足題意；

Step4：若滿足，則輸出此結(jié)果；若不滿足，則無解。

3.1.3 模型的結(jié)果

通過Lingo 軟件，分別對(duì)式（1-3）的多元線性規(guī)劃模型進(jìn)行求解，得到：

當(dāng)?shù)讓覲1 產(chǎn)品豎向切割時(shí)：

當(dāng)?shù)讓覲1 產(chǎn)品橫向切割時(shí)：

其中式（4）的結(jié)果表示橫看木板時(shí)最底層橫切P1產(chǎn)品1 塊，豎切P1 產(chǎn)品13 塊；式（5）的結(jié)果表示在式（4）的基礎(chǔ)上，豎看木塊時(shí)，豎切P1 產(chǎn)品4 塊；式（6）的結(jié)果表示在式（4）的基礎(chǔ)上，橫看木板時(shí)，橫切P1 產(chǎn)品7 塊。

根據(jù)得到的最優(yōu)解，我們可以確定木塊的最優(yōu)切割方式。通過CAD 作圖軟件對(duì)其進(jìn)行模擬切割，得到圖1。

圖1 問題一的最優(yōu)切割方案示意圖

根據(jù)所建立的數(shù)學(xué)模型，計(jì)算在一塊木板上切割P1 產(chǎn)品的數(shù)量和木板的利用率。

結(jié)果如表4 所示。

表4 問題1 的結(jié)果

3.2 問題二模型的建立與求解

3.2.1 模型的建立

為了得到在一塊木板上切割P1 和P3 產(chǎn)品使得木板利用率由高到低排序的前3 種切割方案，建立如下方程：

目標(biāo)函數(shù)：

約束條件

當(dāng)?shù)讓覲3產(chǎn)品垂直切割時(shí)：

目標(biāo)函數(shù)：

約束條件：

當(dāng)?shù)讓覲3 產(chǎn)品水平切割時(shí)：

目標(biāo)函數(shù)：

約束條件：

3.2.2 模型的求解

Step1：先針對(duì)木板橫看時(shí)最底層P1 和P3 產(chǎn)品切割的最優(yōu)化結(jié)果，建立式（7）的多元線性規(guī)劃模型，運(yùn)用Lingo 軟件對(duì)其進(jìn)行求解；

Step2：在Step1 的基礎(chǔ)上對(duì)木板豎看方向求解最優(yōu)化結(jié)果，建立式（8）和式（9）的多元線性規(guī)劃模型，運(yùn)用Lingo 軟件對(duì)其進(jìn)行求解；

Step3：對(duì)求解后的結(jié)果進(jìn)行分析，當(dāng)某一維度上不止一種擺放方式時(shí)，對(duì)剩余部分進(jìn)行再次Step1、Step2的操作，直至其只有一種擺放方式；

Step4：代入約束條件中驗(yàn)證所得到的結(jié)果是否滿足題意；

Step5：若滿足，則輸出此結(jié)果；若不滿足，則無解。

3.2.3 模型的結(jié)果

通過Lingo 軟件，分別對(duì)式（7-9）的多元線性規(guī)劃模型進(jìn)行求解，得到：

當(dāng)?shù)讓覲3 產(chǎn)品垂直切割時(shí)：

當(dāng)?shù)讓覲3 產(chǎn)品水平切割時(shí)：

其中式（10）的結(jié)果表示橫看木板時(shí)最底層橫切P3 產(chǎn)品4 塊，豎切P3 產(chǎn)品6 塊；式（11）的結(jié)果表示在式（10）的基礎(chǔ)上，豎看木板時(shí)，橫切P3 產(chǎn)品3 塊，豎切P3 產(chǎn)品2 塊；式（12）的結(jié)果表示在式（10）的基礎(chǔ)上，橫看木板時(shí)，橫切P3 產(chǎn)品3 塊，豎切P3 產(chǎn)品2 塊。

根據(jù)得到的最優(yōu)解，我們可以確定木塊的最優(yōu)切割方式。通過CAD 作圖軟件對(duì)其進(jìn)行模擬切割，得到圖2。

圖2 問題2的最優(yōu)切割方案示意圖

由于P3 的長(zhǎng)和寬都大于P1，因此我們可以用1個(gè)P1 替換P3，得到方案二，用2 個(gè)P1 替換兩個(gè)P3，得到方案3。

結(jié)果如表5 所示。

表5 問題2 的結(jié)果

3.3 問題三模型的建立與求解

3.3.1 模型的建立與求解

為了完成表2 中P1 和P3 產(chǎn)品的生產(chǎn)任務(wù)，給出木板總利用率最高的切割方案。根據(jù)問題1 和問題2的分析我們已經(jīng)得到了單獨(dú)切割P1 產(chǎn)品和同時(shí)切割P1 和P3 產(chǎn)品的最優(yōu)切割方案。因此，同問題1 的分析過程求解單獨(dú)切割P3 產(chǎn)品的最優(yōu)切割方案，建立如下方程：

目標(biāo)函數(shù)：

約束條件：

通過Lingo 軟件求解式（13），接著在該基礎(chǔ)上對(duì)木板豎向方向采用題1 的方案進(jìn)行同樣的分析求解，得到圖3。

從圖3 可知，單獨(dú)切割P3 時(shí)，一塊木板可以切割出47 塊P3 產(chǎn)品。綜合問題1、問題2 的以及單獨(dú)切割P3 的結(jié)果，得到表6。

圖3 單獨(dú)切割P3的最優(yōu)切割方案示意圖

表6

由于要完成表二中的產(chǎn)品生產(chǎn)要求，且又需要保證木板的利用率最高（即使用木板的總數(shù)量最少），因此將單獨(dú)切割P1 產(chǎn)品的最優(yōu)方案、單獨(dú)切割P3 產(chǎn)品的最優(yōu)方案和同時(shí)切割P1 和P3 產(chǎn)品的前3 種最優(yōu)方案進(jìn)行組合建立如下多元線性規(guī)劃模型：

目標(biāo)函數(shù)：

約束條件：

3.3.2 模型的結(jié)果

通過Lingo 軟件對(duì)式（14）求解得到圖4。

圖4 問題3的最優(yōu)解（Lingo求解）

由圖4 求解結(jié)果可知，8 塊木板采用方案1，40 塊木板采用方案3，其他方案都采用0 塊木板，由此得到表7。

表7 問題3 的結(jié)果

3.4 問題四模型的建立與求解

3.4.1 模型的建立與求解

為了完成表2 中P1、P2、P3 和P4 產(chǎn)品的生產(chǎn)任務(wù)，給出木板總利用率最高的切割方案。根據(jù)問題1、問題2、問題3 的分析得知，求解產(chǎn)品切割的最優(yōu)方案是使木板剩余空間盡可能減少。同問題3 的分析過程一致，首先，對(duì){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 軟件分別建立多元線性規(guī)劃模型求出每種方案的最優(yōu)切割方案。如表8 所示。

表8 15 種方案的最優(yōu)解

為了求得木板總利用率最高的切割方案，我們采用各最優(yōu)的切割方案進(jìn)行多元組合線性規(guī)劃計(jì)算，用最少的木板切割完成產(chǎn)品的生產(chǎn)，得到如下方程：

3.4.2 模型的結(jié)果

利用Lingo 軟件對(duì)多建立的多元線性規(guī)劃模型進(jìn)行求解，得到表9。

表9 問題4 的結(jié)果

4 模型的評(píng)價(jià)與推廣

4.1 模型的優(yōu)點(diǎn)

（1）該模型從最小間隙問題出發(fā)，使得切割間隙最小從而達(dá)到木板的最優(yōu)利用率，這樣可以將繁雜的產(chǎn)品切割問題轉(zhuǎn)變?yōu)殚g隙的最小化問題，優(yōu)化了模型結(jié)構(gòu)，減少了模型的計(jì)算難度，同時(shí)也提高了模型整體的準(zhǔn)確性。

（2）用表格的形式把所有方案的最優(yōu)切割方案展現(xiàn)出來，更加直觀，便于理解。

4.2 模型的缺點(diǎn)

（1）間隙的浪費(fèi)仍然存在部分問題需要我們?nèi)スタ?，我們只?duì)木板邊緣進(jìn)行了最小間隙化分析，內(nèi)部仍然存在一部分的間隙不能很好地被利用起來，導(dǎo)致總體的利用率在97%左右，不能完全利用。

（2）需要計(jì)算的方案組合太多，不利于產(chǎn)品過多時(shí)多元組合線性求解。

4.3 模型的推廣

本文主要研究木板的最優(yōu)切割問題，根據(jù)實(shí)際需求從而制定出不同的切割方案，可以把該模型和算法推廣用于玻璃的切割、平面的填裝等問題上，適用于各種固定結(jié)構(gòu)的切割、組裝問題等方面。

5 Lingo代碼樣板

max=（length1*x1+width1*y1+length2*x2+width2*y2+...+lengthN*xN+widthN*yN）/S1Length；

//S1 長(zhǎng)度填充最優(yōu)選擇，lengthN 為所切目標(biāo)木板的長(zhǎng)，widthN 為所切目標(biāo)木板的寬

//S1Length 為待切的S1 的長(zhǎng)，N 為目標(biāo)板塊類型的數(shù)目

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）；//整數(shù)限制

@gin（y1）；//整數(shù)限制

@gin（x2）；

@gin（y2）；

...

@gin（xN）；

@gin（yN）；

end

//通過這個(gè)通用模板，只需調(diào)節(jié)部分系數(shù)，就能給出某長(zhǎng)度上最低端的最優(yōu)切割方案

//即使得這種切割在這個(gè)維度的長(zhǎng)度上所剩余的無用縫隙最少

//再利用循環(huán)嵌套，換橫向繼續(xù)求取當(dāng)前方向長(zhǎng)度最優(yōu)切割方案

//直至整塊板子的最優(yōu)切割方案浮出水面

6 部分方案最優(yōu)切割示意圖

圖5 P2、P3產(chǎn)品組合的最優(yōu)切割方案示意圖

圖6 P2、P4產(chǎn)品組合的最優(yōu)切割方案示意圖

圖7 P3、P4產(chǎn)品組合的最優(yōu)切割方案示意圖

圖8 P1、P2、P3產(chǎn)品組合的最優(yōu)切割方案示意圖

圖9 P1、P2、P4產(chǎn)品組合的最優(yōu)切割方案示意圖

圖10 P1、P3、P4產(chǎn)品組合的最優(yōu)切割方案示意圖

圖11 P1、P2、P3、P4產(chǎn)品組合的最優(yōu)切割方案示意圖