制材業原木生產計劃下料問題分析

王 巍，柯育軍

(東北林業大學工程技術學院，哈爾濱150040)

木材是人們日常生活中不可缺少的天然材料，我國天然森林資源比較貧乏，如何保護現有森林資源，充分挖掘資源潛力是緩解日趨緊張的木材供需矛盾的根本途徑［1-3］，其中，加強技術改造、提高原木和板材加工的利用率是一條主要途徑。我國制材工業落后，原木的綜合出材率一直很低，大部分原木都需要經過鋸割加工后才能使用，如何提高原木出材率和原木利用率，對推進制材技術的現代化有著極為重要的影響［4-7］。對木材加工性能的深入研究，對充分認識和開發實體木材的利用潛能，提高木材的利用水平和實現木材工業的可持續發展具有重要意義［8-11］。

1 原木下料問題模型構建

1．1 問題描述

本文是以制材業中的木門制造企業為對象研究原木下料問題，木門制造企業統一購進只有一種規格的原木，其固定長度為7．4 m。現在需要根據客戶的要求，對其進行切割，以便制成不同規格的木門，如果需要20根2．9 m長、40根2．1 m長和80根1．5 m長的該種特質原木，則應當如何對原木進行切割才能用料最省。

1．2 整數規劃方法

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

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

整數規劃問題根據對設計變量的取值要求的不同可以分為如下幾類:

整數線性規劃數學模型的一般形式如下:

1．3 問題分析并建模

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

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

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

接下來是確定設計目標，所謂的用料最省，可以有兩種理解:

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

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

在這兩種前提下的目標函數不同，解也可能不同。

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

第(1)種理解:

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

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

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

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

由于原木的數量是非負整數，故所采用的切割方案的各設計變量也均為非負整數。對于該問題的目標，對應的整數規劃的數學模型P1為:

P1:目標函數為(1)

約束條件如公式(4):

xi≥0且取整數值。

第(2)種理解:

假設切割后所剩余的總長度W為:

同理，對于該問題的目標，對應的整數規劃的數學模型P2為:

P2:目標函數為(5)

約束條件見公式(4):

xi≥0且取整數值。

2 余料廢棄情況下的計算結果分析

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

求解P1。運用LINGO算法進行求解，得到最優解的結果如下。

目標函數值

根據運行結果可知，下料結果見表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函數對P1進行求解的MATLAB代碼和運行結果如下:

%目標函數所對應的設計變量的系數:

c=ones(1，8)。

%不等式約束:

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

%設計變量的邊界約束:

1b=zeros(1，8)。

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

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

%判定為整數的誤差限:

Tol=1e-8。

%求最優解x和目標函數值fval，并返回狀態指示:

［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

%最優解向量:

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

%在最優解處的目標函數值:

fval=

45．000 0‰。

l=

45‰。

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

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

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

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

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

求解P2。運用LINGO算法進行求解，得到最優解的結果如下:

可選擇變量值

根據運行結果可知，下料結果見表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函數對P2進行求解的MATLAB代碼和運行結果如下:

%目標函數所對應的設計變量的系數:

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

%不等式約束:

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

%設計變量的邊界約束:

1b=zeros(1，8)。

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

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

%判定為整數的誤差限:

Tol=1e-8。

%求最優解x和目標函數值fval，并返回狀態指示:

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

%求出此時所需原木的數目:

s=sum(x)

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

fval=

45．000‰。

%原木數量:

s=

45‰。

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

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

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

4 結束語

通過以上分析，可以得出如下結論:

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

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

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

［1］袁忠良．下料優化方法與程序［M］．天津:天津大學出版社，1989．

［2］王敏娜．通過整數規劃來優化半導體企業的主生產計劃［J］．商場現代化，2010，60(17):32-33．

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

［4］唐加冕，周京徽．線性規劃問題在經濟生活中的應用［J］．商業時代，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，Fang H H．Aggregate production planning with multiple objectives in a fuzzy environment［J］．European Journal of Operational Research，2001，133(3):521-536．

［7］胡 明，黃 營．基于動態規劃的生產計劃優化模型研究與應用［J］．現代計算機，2009，48(6):91-112．

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

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

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

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