遞推矩陣的列生成算法下的一維下料方案研究

馬俊燕，韓志會，駱德鋮，肖海華

（廣西大學(xué)機械工程學(xué)院，廣西 南寧 530004）

1 引言

下料問題被應(yīng)用在很多領(lǐng)域中，一維下料亦是如此，如金屬、造紙、紡織品和木材等，增大材料利用率，降低成本，一直是企業(yè)追求的目標(biāo)，即快速的獲得下料方案[1-2]。對此國內(nèi)外許多學(xué)者都對一維下料問題進行了深入研究，發(fā)表了大量優(yōu)秀期刊著作，新算法、改進算法和混合算法不斷被提出。文獻(xiàn)[3]通過在采用一維下料CAD系統(tǒng)生成線材的下料方案，明顯提高材料利用率考慮基礎(chǔ)上，考慮優(yōu)化目標(biāo)與工藝約束作為參考；文獻(xiàn)[4]采用修正傳統(tǒng)的順序啟發(fā)式算法的改進的混合啟發(fā)式算法，提高了切割率；文獻(xiàn)[5]提出改進的蟻群算法降低了不定長原管一維下料廢料率，文獻(xiàn)[6]介紹了順序修正法和動態(tài)規(guī)劃算法提高了鋼釘下料的材料利用率；文獻(xiàn)[7]以滿足零件需求為導(dǎo)向的對一維下料問題借用混合啟發(fā)式算法進行求解，在綜合考慮材料利用率情況下，能快速求解，但是求解質(zhì)量不高；由于這些算法無法適用高精度布局優(yōu)化問題，在求解問題時往往會陷入局部尋優(yōu)。同時針對一維下料問題，也有很多通過建立常規(guī)線性規(guī)劃模型，在進行求解。文獻(xiàn)[8]提出一種線型規(guī)劃與啟發(fā)式算法結(jié)合的方法；文獻(xiàn)[9]不同于啟發(fā)式算法研究，提出分支定界法解決下料問題。文獻(xiàn)[10-11]是針對二維下料問題進行列生成算法，并驗證符合實際案例；文獻(xiàn)[12]通過大量實驗對枚舉法、列生成算法和混合算法進行了對比。若常規(guī)線性規(guī)劃問題中的決策變量要求為整數(shù)，則該問題就變?yōu)檎麛?shù)線性規(guī)劃問題，其求解算法主要有窮舉法、割平面法和分支界定法，但是以上方法具有適用于規(guī)模較小的一維切割問題、求解結(jié)果不精確、容易陷入局部尋優(yōu)等缺點。為求解一維下料問題數(shù)學(xué)模型的過程中，提出了采用一種基于遞推矩陣的列生成法并結(jié)合分支定界算法來求解一維下料整數(shù)線性規(guī)劃問題，此方法對比其他算法能夠快速得到較少的下料方案數(shù)量。

2 遞推矩陣的列生成算法

在2.1節(jié)中，首先借用常規(guī)列生成算法思路建立列生成優(yōu)化模型；2.2節(jié)中，為求解未知列向量Pj，這里引入遞推矩陣Sj和常數(shù)向量Dj，并對它們進行遞推求解；具體算法實現(xiàn)流程步驟見2.3節(jié)。

2.1 列生成優(yōu)化模型的建立

針對一定環(huán)境下對于一維下料問題進行描述，實際優(yōu)化目標(biāo)主要有兩個：一是原材料使用量最少；二是余料總和最少。這里是原材料的使用量最少，建立數(shù)學(xué)模型如下：

（1）以最小化原材料消耗量為優(yōu)化目標(biāo)：

xj≥0且為整數(shù)，j=1，2，…，n

式中：xj—決策變量；表示第j（j=1，2，…，n）種有效切割方式重復(fù)的次數(shù)；n—切割方式數(shù)

（2）滿足需求約束：

式中：m—零件種類數(shù)；d i—每種零件數(shù)量，并且m=n。

（3）滿足有效切割方式約束，指切割原材料的余料長度小于最短零件長度lmin的切割方式：

為降低水體中各類水質(zhì)要素的濃度水平，改善大伙房水庫的水環(huán)境質(zhì)量，對排放進入水庫的污染源進行控制并削減其排放總量。本次設(shè)計了3組數(shù)值試驗，如表1。

式中：li—每種零件長度；H—原材料的長度，并且數(shù)量不限；ɑij—第j種切割方式切割出來第i種零件的數(shù)量。

（4）常規(guī)列生成算法的研究步驟可知，需要把整數(shù)規(guī)劃模型轉(zhuǎn)化成基于列生成的優(yōu)化模型，上面中約束條件中的需求約束公式（2）的矩陣表達(dá)式，如式（4）所示。

式中：A—系數(shù)矩陣；Pj—m×1階的列向量，也是該線性規(guī)劃數(shù)學(xué)模型的未知向量。

（5）用變量Pj來表示的X：

式中：Dj—1×m階的不等式右邊的常數(shù)向量；kj—滿足一定條件的非負(fù)常數(shù)項；Sj—遞推矩陣，也是m×n階的矩陣。

（6）利用上述X的表達(dá)式，將下料模型中的未知變量X消去，得到關(guān)于未知列向量Pj的基于矩陣變化列生成的線性規(guī)劃模型，如下：

式中：j=1，2，…，n；C—1×n階已知常數(shù)向量，為目標(biāo)函數(shù)中價值數(shù)系，取值為C=(c1，c2，…，cn)=(1，1，…，1)；Pj≥0；Dj—1×m階的不等式右邊的常數(shù)向量，其數(shù)值由相關(guān)遞推關(guān)系式獲得；L—各種零件的長度集合，是一個1×m階的已知行向量，其數(shù)值為L=(l1，l2，…，ln)

2.2 遞推矩陣的生成

以數(shù)學(xué)模型（6）為例，闡述遞推矩陣的生成，觀察數(shù)學(xué)模型（7）可知，只有Sj和Dj為未知向量，要求解決策變量為Pj的模型（6），則必須先求出Sj和Dj。由于j=1，2，…，n，所以每次Pj的求取都必須先求解模型（6）中的未知向量Sj和Dj。通過觀察發(fā)現(xiàn)Sj和Sj-1是存在遞推關(guān)系式。在轉(zhuǎn)化模型求解添加列Pj的過程中可以歸納得到遞推矩陣Sj的遞推關(guān)系式。

式中：S1—單位矩陣。

（2）未知向量Dj和遞推矩陣Sj也存在關(guān)系，通過遞推矩陣Sj可得Dj，令Dj(i，：)=kj，帶入模型（6）中參與求解模型。

式中：D1—由問題可知的已知向量。

2.3 遞推矩陣的列生成法求解問題步驟

針對模型（6）的求解，采用單純形法和分支定界法相結(jié)合的方法進行求解，得出整數(shù)添加列Pj。為更清晰地闡述這里的算法在一維下料問題中的應(yīng)用，采用這里的算法求解常規(guī)線性規(guī)劃問題過程，如圖1所示。

圖1 這里的算法求解常規(guī)線性規(guī)劃問題過程Fig.1 The Algorithm Here Solvesthe Conventional Linear Programming Problem

將最后一次生成的添加列Pj帶入相關(guān)公式X=D-kSP和Z=C(D-SPk)中，可以求得的原問題模型的決策變量X和目標(biāo)函數(shù)最優(yōu)值Z。

3 案例分析

實例運行的計算機的配置如下：Inte（l R）Pentium（R）CPU G630＠2.70GHz，RAM為6.00GB，64位操作系統(tǒng)。軟件版本為MATLABR2016a（9.0.0.341360）64-bi（t win64）。

在本節(jié)中，為了驗證算法對一維下料方式的有效性，從降低下料方案數(shù)量方面針對一組數(shù)值數(shù)據(jù)采用多種算法優(yōu)化求解并將結(jié)果與這里采用算法所得的結(jié)果進行分析比較，驗證算法的優(yōu)勢。在工業(yè)切割下料中，滿足給定訂單所需的下料方案的數(shù)量對于切割下料設(shè)備可實現(xiàn)的產(chǎn)能可能是至關(guān)重要的，因為在不同下料方案之間進行切換下料通常需要耗費一定的時間。因此，在規(guī)劃切割下料時，不一定只要求最小成本的下料方案，而且還需要要求具有較少（或甚至最少）的下料方案數(shù)量。對于生產(chǎn)設(shè)備不足，產(chǎn)能有限的工廠，每種下料方案的切換都需要重新設(shè)置下料設(shè)備，此過程必須中斷切割下料過程，那么就會產(chǎn)生耗時的情況。所以為避免非生產(chǎn)性的設(shè)置時間，最小化下料方案數(shù)量對生產(chǎn)設(shè)備不足的工廠尤為重要。

現(xiàn)有另外一組有關(guān)一維下料方面的訂單，原材料長度為1000，供應(yīng)充足。現(xiàn)需要下料10種零件，10種零件的長度和需求，如表1所示。

表1 訂單數(shù)據(jù)Tab.1 Order Data

為評估這里的算法對一維下料方式的有效，這里與Cláudio Alves et a（l 2009）、Foerster和W?scher（2000）、Araujo（2014）、Yanasse（2006）等人為減少切割下料方案數(shù)量而提出的算法進行測試比較。這里他們采用的算法分別命名為Claudio、KOMBI、MOGA和Yanasse。對表1中訂單的數(shù)據(jù)進行測試，分別采用Claudio、KOMBI、MOGA、Yanasse和采用算法進行優(yōu)化求解，得出下料方案數(shù)量，如表2所示。

表2 多種算法求得的下料方案數(shù)量Tab.2 Number of Blanking Schemes Obtained by Various Algorithms

每種算法相對于Claudio產(chǎn)生的百分比變化，如表3所示。

表3 每種算法相對于Claudio產(chǎn)生的變化/%Tab.3 Variations of Each Algorithm Relative to Claudio/%

表中：負(fù)號“-”—在排樣方案數(shù)量方面每種算法相對于Claudio減少的變化，反之，若出現(xiàn)加號“+”，則表示增加的變化。

由表3分析可知，在降低下料方案數(shù)量方面，KOMBI、MOGA、Yanasse和這里的算法相對于Claudio分別降低了6.18%、4.25%、4.45%和9.09%。對比數(shù)據(jù)可知這里采用的算法相比較MOGA和Yanasse兩種算法得到了更大的百分比變化數(shù)值，大幅度地降低了下料方案的數(shù)量，相比較KOMBI算法在降低下料方案數(shù)量方面，這里采用的算法也表現(xiàn)良好，結(jié)果證明了此算法對于一維下料實例應(yīng)用的有效性。

4 結(jié)語

針對一維下料問題，建立數(shù)學(xué)優(yōu)化模型，采用一種基于遞推矩陣的列生成新的迭代方法，更新了傳統(tǒng)方法中求解逆矩陣的迭代過程。并通過對比其他算法，這里的算法從降低下料方案數(shù)量，針對案例分析得到了理想的結(jié)果，驗證了采用算法在一維下料領(lǐng)域的有效性和優(yōu)勢。