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

俞雅靜　錢峰

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

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

1.引言

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

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

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

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

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

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