整數線性規劃模型在切割問題中的應用

俞雅靜　錢峰

摘要：本文利用整數線性規劃理論，討論了單樣矩形構件切割優化模型的建立與求解問題，并利用仿真實驗證明了最優切割結果的合理性和有效性。

關鍵詞：整數線性規劃模型;分枝定界法;仿真實驗

1.引言

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

2.整數線性規劃原理和方法

整數線性規劃（ILP問題）是要求變量取整數值的線性規劃問題。它以線性規劃的最優解為出發點，運用多種基本算法求解。ILP問題的一般形式如下：

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

3.矩形構件切割問題的整數線性規劃模型

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

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

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

利用LINGO軟件實現分枝定界法的求解（見圖1），求出的切割最優解為，即原件橫向上產品橫

向排列有1個;縱向上產品橫向排列有7個;橫向上產品縱向排列有13個;縱向上產品縱向排列有4個。共計需要59個，其中產品構件的最大利用率約為98.3%

4.切割問題模型仿真

為了有效驗證上述模型解的最優性，利用玻璃切割優化軟件將切割問題模型得到了實現。分別在一塊原件中模擬切割54-59塊產品，并設計算出橫豎切割的產品個數和原件的優化率，見軟件切割的仿真模擬圖：

通過玻璃切割優化軟件的仿真模擬，可以得出最優的產品構件切割方案：切59個產品，原件的利用率最大：98.30%

5.結論

本文圍繞著整數線性規劃模型在切割問題中的應用進行研究，從理論和方法上面進行探討，并利用玻璃優化切割軟件將切割模型得到進一步的驗證。因此得出該模型可操作性性強，具有很強的適應性和可變性，可在市場上推廣使用。

參考文獻

[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]刁在筠，劉桂真，戎曉霞，王光輝.運籌學[M].4版.北京：高等教育出版社，2016.07.

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

作者簡介：俞雅靜（1998-），女，本科生，主要研究方向：應用統計;

錢峰（1975-），男，副教授，主要研究方向：高等數學，概率論與數理統計，運籌學整數線性規劃。