整數(shù)線性規(guī)劃模型在切割問題中的應(yīng)用

俞雅靜　錢峰

摘要：本文利用整數(shù)線性規(guī)劃理論，討論了單樣矩形構(gòu)件切割優(yōu)化模型的建立與求解問題，并利用仿真實(shí)驗(yàn)證明了最優(yōu)切割結(jié)果的合理性和有效性。

關(guān)鍵詞：整數(shù)線性規(guī)劃模型;分枝定界法;仿真實(shí)驗(yàn)

1.引言

切割問題在各領(lǐng)域中都有著廣泛的應(yīng)用，如汽車、船舶等金屬材料的分割，服裝、玩具、鞋子制造過程中布匹或皮革的下料等[1]。優(yōu)化切割問題的排樣方案，可以減少切割過程中存在的資源浪費(fèi)現(xiàn)象，是企業(yè)降低生產(chǎn)成本，增大生產(chǎn)效率，承擔(dān)環(huán)境責(zé)任要解決的關(guān)鍵問題[2]。切割問題的核心是規(guī)劃產(chǎn)品在原件上的排列布局，從原件中分離出產(chǎn)品進(jìn)行加工和制造使用。很多學(xué)者對(duì)矩形件排樣進(jìn)行研究，提出多種切實(shí)可行的排放算法和優(yōu)化算法[3]。

2.整數(shù)線性規(guī)劃原理和方法

整數(shù)線性規(guī)劃（ILP問題）是要求變量取整數(shù)值的線性規(guī)劃問題。它以線性規(guī)劃的最優(yōu)解為出發(fā)點(diǎn)，運(yùn)用多種基本算法求解。ILP問題的一般形式如下：

變量取整實(shí)質(zhì)上是一種非線性約束，這使得求解困難程度加大，其中分支定界法是求解ILP問題的有效方法，其基本思想是枚舉ILP問題的可行解。

3.矩形構(gòu)件切割問題的整數(shù)線性規(guī)劃模型

單樣矩形產(chǎn)品構(gòu)件切割問題通常是將一塊矩形產(chǎn)品構(gòu)件，互不重疊的排布在一個(gè)大的矩形原料上，在滿足一定的工藝要求的前提下，充分利用原料的各個(gè)邊，直到原料的利用率達(dá)到最高。切割時(shí)要在產(chǎn)品不超過原件邊界，產(chǎn)品不互相重合的情況下，盡量多的滿足產(chǎn)品擺放數(shù)量最多，且原料的邊角余料最少且不可以再利用，就要設(shè)計(jì)出適合不同約束條件下的矩形排列優(yōu)化方案。

為建立產(chǎn)品構(gòu)件切割問題的數(shù)學(xué)模型，首先定義變量：L、W是原料的長寬;l、w是產(chǎn)品的長寬;X1是橫向上產(chǎn)品橫向排列的個(gè)數(shù);X2是橫向上產(chǎn)品縱向排列的個(gè)數(shù);Y1是縱向上產(chǎn)品橫向排列的個(gè)數(shù);Y2是縱向上產(chǎn)品縱向排列的個(gè)數(shù);在切割產(chǎn)品的時(shí)候，通常從原件的邊界開始切割，使邊的利用率達(dá)到最高。最外層排列完之后，再向內(nèi)部剩余的面積以相同的方式進(jìn)行切割，如此循環(huán)往復(fù)，直到剩余原件的面積無法進(jìn)一步的切割，從而達(dá)到原件利用率最大。

其中約束（2）表示在原件橫向上排列X11個(gè)矩件，縱向上排列X12個(gè)矩件，要保證橫向上排列的長度小于原件的長;要求存在都是橫排或縱排的矩件的長度要小于原件的寬，從而使切割產(chǎn)品的面積占原件面積得到最大值。

利用LINGO軟件實(shí)現(xiàn)分枝定界法的求解（見圖1），求出的切割最優(yōu)解為，即原件橫向上產(chǎn)品橫

向排列有1個(gè);縱向上產(chǎn)品橫向排列有7個(gè);橫向上產(chǎn)品縱向排列有13個(gè);縱向上產(chǎn)品縱向排列有4個(gè)。共計(jì)需要59個(gè)，其中產(chǎn)品構(gòu)件的最大利用率約為98.3%

4.切割問題模型仿真

為了有效驗(yàn)證上述模型解的最優(yōu)性，利用玻璃切割優(yōu)化軟件將切割問題模型得到了實(shí)現(xiàn)。分別在一塊原件中模擬切割54-59塊產(chǎn)品，并設(shè)計(jì)算出橫豎切割的產(chǎn)品個(gè)數(shù)和原件的優(yōu)化率，見軟件切割的仿真模擬圖：

通過玻璃切割優(yōu)化軟件的仿真模擬，可以得出最優(yōu)的產(chǎn)品構(gòu)件切割方案：切59個(gè)產(chǎn)品，原件的利用率最大：98.30%

5.結(jié)論

本文圍繞著整數(shù)線性規(guī)劃模型在切割問題中的應(yīng)用進(jìn)行研究，從理論和方法上面進(jìn)行探討，并利用玻璃優(yōu)化切割軟件將切割模型得到進(jìn)一步的驗(yàn)證。因此得出該模型可操作性性強(qiáng)，具有很強(qiáng)的適應(yīng)性和可變性，可在市場(chǎng)上推廣使用。

參考文獻(xiàn)

[1]Dagli.C.H，and tatoglu， M.Y.An approach to two dimcnsional cutting stock problems[J].Intcrantional Journal of Production Rcscarch， 1987，25： 175-190.

[2]刁在筠，劉桂真，戎曉霞，王光輝.運(yùn)籌學(xué)[M].4版.北京：高等教育出版社，2016.07.

[3]陳仕軍.矩形件下料優(yōu)化算法研究[D].華中科技大學(xué)碩士論文，2009.

作者簡介：俞雅靜（1998-），女，本科生，主要研究方向：應(yīng)用統(tǒng)計(jì);

錢峰（1975-），男，副教授，主要研究方向：高等數(shù)學(xué)，概率論與數(shù)理統(tǒng)計(jì)，運(yùn)籌學(xué)整數(shù)線性規(guī)劃。