一維型材合理下料的數(shù)學(xué)模型

李 明

（蘇州工業(yè)職業(yè)技術(shù)學(xué)院 公共教學(xué)部，江蘇 蘇州 215104）

一維型材合理下料的數(shù)學(xué)模型

李 明

（蘇州工業(yè)職業(yè)技術(shù)學(xué)院 公共教學(xué)部，江蘇 蘇州 215104）

一維型材合理下料問題的解決是多維下料問題優(yōu)化的基礎(chǔ)。從模型建立的角度出發(fā)，以材料利用率高達(dá)97.84%為目標(biāo)，用非線性規(guī)劃模型Ⅱ改進(jìn)整數(shù)規(guī)劃模型Ⅰ，解決整數(shù)規(guī)劃模型Ⅰ中人工枚舉下料方案而導(dǎo)致的決策變量偏多的問題，減少生產(chǎn)過程的復(fù)雜性，降低生產(chǎn)成本和管理成本，提高切割方案的生成速度。非線性規(guī)劃模型Ⅱ解決了多種型材下料問題的最優(yōu)化，使企業(yè)效益達(dá)到最大化。

一維型材；優(yōu)化下料；整數(shù)規(guī)劃；非線性規(guī)劃

1 相關(guān)研究背景及問題的提出

所謂“下料問題”就是把規(guī)格相同的一些原材料進(jìn)行合理分割后再組合，確定切割下來材料的排樣方案，以達(dá)到材料利用率最高。這類問題可分為三大類：切割問題（Cutting Stock Problem）、排樣問題（Assortement Problem）和裝箱問題（Bin Packing Problem）。切割問題如棒材或型材的下料，在造船業(yè)、建筑業(yè)中鋼筋、鋁合金、圓鋼的下料，以及家具制造業(yè)中板材的下料；排樣問題如印刷業(yè)中書刊、報紙的排版或電子工業(yè)中集成電路的排布問題；裝箱問題如物流行業(yè)中集裝箱載物時，將貨物裝入有限空間的排布等[1]。優(yōu)化下料問題，可以最大限度地節(jié)約資源，降低生產(chǎn)成本，提高企業(yè)的競爭力，給企業(yè)帶來直接的經(jīng)濟(jì)效益，因而對一維型材下料問題的研究具有重要的現(xiàn)實意義和應(yīng)用價值。

目前，國內(nèi)外在優(yōu)化下料問題的研究上，較多是從算法改進(jìn)的角度上進(jìn)行的。如文獻(xiàn)[2]針對原材料利用率最高的切割方式優(yōu)先選擇策略，設(shè)計了貪心算法；文獻(xiàn)[3]針對大規(guī)模一維型材下料問題很難找到最優(yōu)解，設(shè)計了啟發(fā)式算法；文獻(xiàn)[4]針對各算法容易陷入局部最優(yōu)的缺點，采用了自適應(yīng)廣義粒子群優(yōu)化算法來達(dá)到優(yōu)化的高效性。此外，還有遺傳算法、模擬退化算法、蜂群遺傳算法等。倘若從模型建立的角度出發(fā)，用科學(xué)的方法取代人工篩選，降低工人的工作量，減少企業(yè)成本，提高材料利用率，那么也是一種有效解決問題的好思路。以下從典型實例出發(fā)進(jìn)行探討和研究。

如某單位需要加工制作100套工架，每套工架需要用2.9m、2.1m、1.5m的圓鋼各一根。已知原材料長7.4m，問如何下料才使得所用的原材料最省？

2 問題的分析

如果按照單一截材方案，將一根7.4m原材料切割為2.9m、2.1m、1.5m的型材各一根，最后余料是0.9m，小于原材料中尺寸規(guī)格最小的1.5m，那么生產(chǎn)100套這樣的工架，最后余料總和為90m，材料利用率只有87.84%，并造成一定量的浪費和生產(chǎn)成本的增加。因此，以余料最少或使用的原材料最省為目標(biāo)，針對7.4m長的原材料，排列出所有切割可能性的8種方案（見表1）。

表1 一根7.4m原材料切割的8種方案m

3 模型的建立與求解

設(shè)決策變量為xi，代表第i種方案下使用原材料的數(shù)量，i=1,2,…,8；目標(biāo)是切割下來的余料最少或使用的原材料最省；約束條件是切割出來的型材需求量都是100根，故可以建立如下的整數(shù)規(guī)劃模型Ⅰ。通過LINGO9.0軟件實現(xiàn)過程如下：

!建立數(shù)據(jù)段，確定各方程的系數(shù)矩陣和常數(shù)項矩陣的數(shù)據(jù);

通過LINGO9.0軟件計算得到求解報告，如圖1所示。經(jīng)過6次迭代得出余料最少為16m，切割方案為：第2方案截取40根，第3方案截取30根，第4方案截取20根，原材料合計使用了90根，就能完成整個任務(wù)的要求。此時原材料的利用率為97.84%，比單一截材時的利用率提高了10%。

如果以原材料使用最省為目標(biāo)，那么目標(biāo)函數(shù)應(yīng)該為：

在其他的約束條件不變的情況下，得到的是同樣的結(jié)論[5]。

4 對整數(shù)規(guī)劃模型Ⅰ的再思考

整數(shù)規(guī)劃模型Ⅰ固然好，但排列出所有的切割方案需要時間、人力和物力，當(dāng)型材規(guī)格較多或原材料類型較復(fù)雜時，采取整數(shù)規(guī)劃模型Ⅰ會無形間加大工人工作量，增加生產(chǎn)工序的復(fù)雜性，降低工作效率。從表1余料的數(shù)據(jù)結(jié)果以及最優(yōu)化后8種方案選中3種，表現(xiàn)出兩個較為突出的問題，成為對整數(shù)規(guī)劃模型Ⅰ進(jìn)行改進(jìn)的突破口。

問題1：假如從7.4m原材料中各截取2.9m、2.1m、1.5m的型材各一根，剩下的余料是0.9m，那么8種方案中余料比0.9m少的，對提高利用率無意義，因而不予考慮，這樣就將8種方案濃縮為5種備選方案（見表2），也就是將變量由原來的8個減少到5個。

據(jù)此，將整數(shù)規(guī)劃模型Ⅰ更改為：

圖1 整數(shù)規(guī)劃模型Ⅰ的求解報告

表2 一根7.4m原材料切割的5種方案m

在其他的約束條件不變的情況下，依據(jù)更改后的整數(shù)規(guī)劃模型Ⅰ會得到與前面同樣的結(jié)論。

問題2：假如原材料類型較多，需要的型材規(guī)格也比較多樣的時候，采用枚舉的方法工作量比較大，而且生產(chǎn)部門采用不同的切割模式越多，越會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而會無形增加生產(chǎn)和管理成本。整數(shù)規(guī)劃模型Ⅰ雖有8種方案，但優(yōu)化過后僅選擇了其中的3種方案，由此以切割方案的選取不超過4種為原則，可以降低生產(chǎn)和管理成本，建立更為便捷、合理、科學(xué)而高效的數(shù)學(xué)模型[6-10]。

5 對整數(shù)規(guī)劃模型Ⅰ的改進(jìn)

評判一個好的下料模型，首先考慮的是提高原材料的利用率；其次要求切割方案盡可能少。因而在切割方案不超過4種的原則下，增設(shè)決策變量，表示第i種型材使用第j種切割方案時的數(shù)量；xi仍然代表第j種方案下使用原材料的數(shù)量，目標(biāo)是切割下來的余料最少或使用的原材料最省；約束條件是切割出來的型材需求量都是100根，同時余料應(yīng)該小于型材中的最小尺寸1.5m，故可以建立如下的非線性規(guī)劃模型Ⅱ[11]。

其中，型材矩陣為A=(2.11.52.9)，切割方案矩陣為R=(rij)3×4。由于4種方案的排列順序無關(guān)緊要，可在程序運行時增加約束條件，以縮小變量搜索的時間，減少程序運行時間。

通過LINGO9.0軟件實現(xiàn)過程如下：

!建立集合段，確定各量的下標(biāo);

!建立數(shù)據(jù)段，確定各方程的系數(shù)矩陣和常數(shù)項矩陣的數(shù)據(jù);

通過LINGO9.0軟件計算得到求解報告，如圖2所示。經(jīng)過5924次迭代，解得最省的原材料需要使用90根，余料總和為16m，原材料的利用率仍為97.84%，同時得到切割方案（見表3）。其中方案2和方案4切割方式相同，可整合為表4。與整數(shù)規(guī)劃模型Ⅰ結(jié)論相比，證實了非線性規(guī)劃模型Ⅱ的可行性。

圖2 非線性規(guī)劃模型Ⅱ的求解報告

非線性規(guī)劃模型Ⅱ的最大優(yōu)勢是：在保證和提高原材料利用率為97.84%的情況下，增設(shè)了切割方案下型材使用的數(shù)量為變量，解決了整數(shù)規(guī)劃模型Ⅰ由人工枚舉方案而導(dǎo)致的決策變量偏多、工作量較大的問題。為精簡生產(chǎn)過程，降低生產(chǎn)成本，加快切割方案的生成速度，提高企業(yè)排樣效率，尋找到了一種合二為一解決問題的思路和方法，為多種型材下料優(yōu)化模型奠定了基礎(chǔ)。

6 結(jié)束語

下料問題隨著實際情況的不同，約束條件會有所變化，但無論條件怎么改變，一定要注重對問題做層層深入的分析，對模型進(jìn)行不斷改進(jìn)，使得模型具有更加廣泛的通用性。非線性規(guī)劃模型Ⅱ及LINGO程序的求解方法，不但具有較好的通用性，而且能夠?qū)崿F(xiàn)較大規(guī)模一維型材下料優(yōu)化問題，使企業(yè)效益達(dá)到最大化。

表3 一根7.4m原材料切割的4種方案 根

表4 合并表3中的方案2和方案4根

[1]胡玉珠.一種型材優(yōu)化下料方法的研究與應(yīng)用[D].長春:長春理工大學(xué)，2009.

[2]陳煉，馬永生，劉光明.一維下料方案的貪心算法優(yōu)化[J].南昌大學(xué)學(xué)報:工科版，2005，27(4):71-73，84.

[3]劉蓉.一維下料問題的一種啟發(fā)式算法及其應(yīng)用[D].合肥:合肥工業(yè)大學(xué)，2006.

[4]沈顯君，楊進(jìn)才，應(yīng)偉勤，等.一維下料問題的自適應(yīng)廣義粒子群優(yōu)化求解[J].華南理工大學(xué)學(xué)報:自然科學(xué)版，2007，35(9):113-117.

[5]代西武，李美娥.線材合理下料的數(shù)學(xué)模型[J].北京建筑工程學(xué)院學(xué)報，2005，21(2):61-62.

[6]劉睿，嚴(yán)玄，許道云，等.一種有效的求解一維下料問題的啟發(fā)式算法[J].計算機應(yīng)用，2009，29(4):1180-1181，1187.

[7]沈飛，陳杰，陳峰.循環(huán)取料下的多道口分配問題及其算法研究[J].物流技術(shù)，2009，28(9):46-48.

[8]王建，閆立梅.型材下料表的參數(shù)提取和管理[J].計算機輔助工程，2008，17(3):65-68.

[9]王連杰.基于線性規(guī)劃的一維優(yōu)化下料系統(tǒng)研究與開發(fā)[D].大連:大連理工大學(xué)，2003.

[10]韓中庚.實用運籌學(xué)——模型、方法與計算[M].北京:清華大學(xué)出版社，2007:12.

[11]孫曉雅.整數(shù)非線性規(guī)劃方法優(yōu)化下料問題[J].機械工程師，2006(10):100-101.

Mathematical Model of Rational Cutting of One Dimensional Profile

LI Ming
(Public Courses Department, Suzhou Institute of Industrial Technology, Suzhou,215104,China)

The solution of the rational cutting of one dimensional profile lays the foundation for solving the issue of multidimensional cutting. From the view of model building, this article, setting a goal of97.84% of material utility, uses the nonlinear programming model II to change the integer programming model I, which solves the extra decision variable caused by the enumeration in integer programming model I, decreases the complexity of the working process, reduces the cost of production and management and improves the speed of cutting plan. The nonlinear programming model II optimizes the issue of multidimensional cutting and enterprises can gain the highest profit.

One dimensional profile; Cutting Optimization; Integer programming; Nonlinear programming

O224

A

1671-4326(2011)04-0056-05

2011-10-31

李 明（1975—），女，新疆石河子人，蘇州工業(yè)職業(yè)技術(shù)學(xué)院公共教學(xué)部講師，碩士.

喬維德]