王 巍，柯育軍

(東北林業(yè)大學(xué)工程技術(shù)學(xué)院，哈爾濱150040)

木材是人們?nèi)粘Ｉ钪胁豢扇鄙俚奶烊徊牧?，我國天然森林資源比較貧乏，如何保護現(xiàn)有森林資源，充分挖掘資源潛力是緩解日趨緊張的木材供需矛盾的根本途徑［1-3］，其中，加強技術(shù)改造、提高原木和板材加工的利用率是一條主要途徑。我國制材工業(yè)落后，原木的綜合出材率一直很低，大部分原木都需要經(jīng)過鋸割加工后才能使用，如何提高原木出材率和原木利用率，對推進制材技術(shù)的現(xiàn)代化有著極為重要的影響［4-7］。對木材加工性能的深入研究，對充分認(rèn)識和開發(fā)實體木材的利用潛能，提高木材的利用水平和實現(xiàn)木材工業(yè)的可持續(xù)發(fā)展具有重要意義［8-11］。

1 原木下料問題模型構(gòu)建

1．1 問題描述

本文是以制材業(yè)中的木門制造企業(yè)為對象研究原木下料問題，木門制造企業(yè)統(tǒng)一購進只有一種規(guī)格的原木，其固定長度為7．4 m?，F(xiàn)在需要根據(jù)客戶的要求，對其進行切割，以便制成不同規(guī)格的木門，如果需要20根2．9 m長、40根2．1 m長和80根1．5 m長的該種特質(zhì)原木，則應(yīng)當(dāng)如何對原木進行切割才能用料最省。

1．2 整數(shù)規(guī)劃方法

整數(shù)規(guī)劃是指一類要求問題中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃。是近三十年來發(fā)展起來的、規(guī)劃論的一個分支［2］。整數(shù)規(guī)劃問題是要求決策變量取整數(shù)值的線性規(guī)劃或非線性規(guī)劃問題。

非線性的整數(shù)規(guī)劃一般可分成線性部分和整數(shù)部分，因此常常把整數(shù)規(guī)劃作為線性規(guī)劃的特殊部分。在線性規(guī)劃問題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對于某些具體問題，常要求解答必須是整數(shù)。例如:所求解是機器的臺數(shù)、工作的人數(shù)或裝貨的車數(shù)等。為了滿足整數(shù)的要求，初看起來似乎只要把己得的非整數(shù)解舍入化整就可以了。實際上化整后的數(shù)不見得是可行解和最優(yōu)解，所以應(yīng)該有特殊的方法來求解整數(shù)規(guī)劃。

整數(shù)規(guī)劃問題根據(jù)對設(shè)計變量的取值要求的不同可以分為如下幾類:

整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式如下:

1．3 問題分析并建模

合理下料問題的關(guān)鍵在于確定合適的切割方案，在這個過程中，需要找到所有可行的切割方案，需要收集盡可能多的切割方案以考慮更多的情況。在此需要指出，切割模式必須合理，盡可能最大限度使用原材料，即余料應(yīng)當(dāng)小于要求的最小規(guī)格尺寸，否則原料則可以繼續(xù)被切割滿足需要。根據(jù)下料要求，通過試算的方法進行分析比較，得出以下8種方案。

對于上述問題，可以得到所有合理可行的切割方案，見表1。

表1 原木切割模式Tab．1 Wood cutting mode

接下來是確定設(shè)計目標(biāo)，所謂的用料最省，可以有兩種理解:

(1)所用的原木數(shù)量最少，這種情況適用于余料廢棄。

(2)余料最少，這種情況余料可以再利用。

在這兩種前提下的目標(biāo)函數(shù)不同，解也可能不同。

根據(jù)上述兩種理解，下面分別對其進行分析:

第(1)種理解:

假設(shè)用第i種方案切割的原木根數(shù)為Xi(i=1，2，……，8)，則所需要的原木數(shù)量為切割的原木數(shù)總和，即:

根據(jù)表格中的數(shù)據(jù)和上述假設(shè)，可以知道經(jīng)過切割以后獲得符合要求的各種規(guī)格的原木數(shù)目如下，設(shè)用Pi表示i米長的原木的數(shù)量，即:

由于需要20根2．9 m長、40根2．1 m長、80根1．5 m長的原木，故最后得到的各種規(guī)格的原木數(shù)目應(yīng)當(dāng)不小于當(dāng)初定下的要求，即需要滿足:

結(jié)合式(3)可得約束條件為:

由于原木的數(shù)量是非負(fù)整數(shù)，故所采用的切割方案的各設(shè)計變量也均為非負(fù)整數(shù)。對于該問題的目標(biāo)，對應(yīng)的整數(shù)規(guī)劃的數(shù)學(xué)模型P1為:

P1:目標(biāo)函數(shù)為(1)

約束條件如公式(4):

xi≥0且取整數(shù)值。

第(2)種理解:

假設(shè)切割后所剩余的總長度W為:

同理，對于該問題的目標(biāo)，對應(yīng)的整數(shù)規(guī)劃的數(shù)學(xué)模型P2為:

P2:目標(biāo)函數(shù)為(5)

約束條件見公式(4):

xi≥0且取整數(shù)值。

2 余料廢棄情況下的計算結(jié)果分析

2．1 余料廢棄情況下運用LINGO軟件求解

求解P1。運用LINGO算法進行求解，得到最優(yōu)解的結(jié)果如下。

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

根據(jù)運行結(jié)果可知，下料結(jié)果見表2。

表2 余料廢棄情況下原木切割方案Tab．2 The cutting stock problem without considering the surplus timber

即按照方案1切割17根原木，按照方案3切割5根原木，按照方案4切割12根原木，按照方案6切割6根原木，按照方案8切割10根原木，總共50根原木，總余料量24 m。

2．2 余料廢棄情況下運用MATLAB軟件求解

用intprog函數(shù)對P1進行求解的MATLAB代碼和運行結(jié)果如下:

%目標(biāo)函數(shù)所對應(yīng)的設(shè)計變量的系數(shù):

c=ones(1，8)。

%不等式約束:

1b= ［-20;-40;-80］。

%設(shè)計變量的邊界約束:

1b=zeros(1，8)。

%所有變量均為整數(shù)變量，故將所有序號組成向量M:

M= ［1;2;3;4;5;6;7;8］。

%判定為整數(shù)的誤差限:

Tol=1e-8。

%求最優(yōu)解x和目標(biāo)函數(shù)值fval，并返回狀態(tài)指示:

［x，fval］ =intprog(c，A，b， ［］， ［］，1b，［］，M，Tol)。

%求出此時的余料長度:

l= ［0 0．1 0．2 0．3 0．8 0．9 1．1 1．4］*x

%最優(yōu)解向量:

x=［5，5，5，0，0，10，10，10］

%在最優(yōu)解處的目標(biāo)函數(shù)值:

fval=

45．000 0‰。

l=

45‰。

根據(jù)上述結(jié)果可以知道，所需原木的最少數(shù)目為45根，其中采用各個方案切割原木的數(shù)目如最優(yōu)解向量中的各分量值，此時的余料為35．5 m。

表3 余料廢棄情況下時兩種方案對比Tab．3 Comparison of the two cutting methods without considering the surplus timber

通過表3可知，原來的方法和現(xiàn)在的方法比較可得:在該種理解情況下，余料不可用作他用，運用LINGO算法得出需要原木50根，而通過MATLAB算法得出需要原木45根，因此能夠作出改進。

3 余料再利用情況下的計算結(jié)果分析

3．1 余料再利用情況下運用LINGO軟件求解

求解P2。運用LINGO算法進行求解，得到最優(yōu)解的結(jié)果如下:

可選擇變量值

根據(jù)運行結(jié)果可知，下料結(jié)果見表4。

表4 余料再利用情況下原木切割方案Tab．4 The cutting stock problem while utilizing the surplus timber

即按照方案1切割5根原木，按照方案2切割5根原木，按照方案4切割10根原木，按照方案5切割10根原木，按照方案6切割14根原木，按照方案8切割4根原木，總共48根原木，總余料量29．9 m。

3．2 余料再利用情況下運用MATLAB軟件求解

用intprog函數(shù)對P2進行求解的MATLAB代碼和運行結(jié)果如下:

%目標(biāo)函數(shù)所對應(yīng)的設(shè)計變量的系數(shù):

c= ［0;0．1;0．2;0．3;0．8;0．9;1．1;1．4］。

%不等式約束:

b= ［-20;-40;-80］。

%設(shè)計變量的邊界約束:

1b=zeros(1，8)。

%所有變量均為整數(shù)變量，故將所有序號組成向量M:

M= ［1;2;3;4;5;6;7;8］。

%判定為整數(shù)的誤差限:

Tol=1e-8。

%求最優(yōu)解x和目標(biāo)函數(shù)值fval，并返回狀態(tài)指示:

［x，fval］ =intprog(c，A，b， ［］， ［］，1b，［］，M，Tol)。

%求出此時所需原木的數(shù)目:

s=sum(x)

x=［5，5，5，0，0，10，10，10］

fval=

45．000‰。

%原木數(shù)量:

s=

45‰。

根據(jù)上述結(jié)果可以知道，采用各個方案切割原木的數(shù)目最優(yōu)解向量x中的各分量值，此時所用原木的數(shù)目為45根，余料為35．5 m。

表5 余料再利用情況下兩種方案對比Tab．5 Comparison of the two cutting methods with the surplus timber reused

通過表5可知，原來的方法和現(xiàn)在的方法比較可得:在該種理解情況下，余料可用作別的用途，運用LINGO算法得出需要原木48根，總余料量為29．9 m，而通過MATLAB算法得出需要原木45根，總余料量為35．5 m，因此能夠作出改進。

4 結(jié)束語

通過以上分析，可以得出如下結(jié)論:

(1)第一種是余料廢棄情況下，如果運用LINGO算法，最終算出總共需要消耗原木50根，余料總和為24 m，而通過MATLAB算法算出總共需要消耗原木45根，余料總和為35．5 m，由于余料廢棄，可以看出運用MATLAB得出的結(jié)果消耗的原木數(shù)量較少，在制材業(yè)中對原木利用率較高，因此能夠得到改進。

(2)第二種是余料再利用情況下，如果運用LINGO算法，最終算出總共需要消耗原木48根，余料總和為29．9 m，而通過MATLAB算法算出總共需要消耗原木45根，余料總和為35．5 m，由于余料能夠再利用，可以看出運用MATLAB得出的結(jié)果消耗的原木數(shù)量較少，而且余料量也較多，在制材業(yè)中對原木利用率較高，因此能改進實際的下料問題。

(3)通過MATLAB和LINGO的計算比較可以看出，在制材業(yè)中，運用MATLAB算法都比運用LINGO算法更優(yōu)，對于提高原木的利用率都有顯著的效果。

［1］袁忠良．下料優(yōu)化方法與程序［M］．天津:天津大學(xué)出版社，1989．

［2］王敏娜．通過整數(shù)規(guī)劃來優(yōu)化半導(dǎo)體企業(yè)的主生產(chǎn)計劃［J］．商場現(xiàn)代化，2010，60(17):32-33．

［3］田 園，宋維明，程寶棟．中國木材市場供給結(jié)構(gòu)分析［J］，森林工程，2005，21(5):20-23．

［4］唐加冕，周京徽．線性規(guī)劃問題在經(jīng)濟生活中的應(yīng)用［J］．商業(yè)時代，2011，8(76):54-56．

［5］ Chen-Ritzo C，Ervolina T，Terry P．Harrison T P，et al．Sales and operations planning in systems with order configuration uncertainty［J］．European Journal of Operational Research，2010，3(205):604-614．

［6］ Wang R C，F(xiàn)ang H H．Aggregate production planning with multiple objectives in a fuzzy environment［J］．European Journal of Operational Research，2001，133(3):521-536．

［7］胡 明，黃 營．基于動態(tài)規(guī)劃的生產(chǎn)計劃優(yōu)化模型研究與應(yīng)用［J］．現(xiàn)代計算機，2009，48(6):91-112．

［8］王 睿．生產(chǎn)計劃的數(shù)學(xué)模型［J］．平頂山學(xué)院學(xué)報，2007，22(5):67-68．

［9］曲中憲，武文華，宋代清．生產(chǎn)計劃優(yōu)化模型的研究［J］．武漢理工大學(xué)學(xué)報，2008，30(8):185-188．

［10］張 鵬，夏 蓓．線性規(guī)劃在生產(chǎn)計劃制定中的應(yīng)用［J］．信息技術(shù)，2010，3(8):102-103．

［11］鐘曉玉，董希斌．我國森林資源生態(tài)效益補償機制的探討［J］，森林工程，2008，24(1):18-21．