基于整數規劃下木板排樣優化問題的研究

吳雨婷　張玉

摘 要：目前，大多數工業生產過程中主要使用人工神經網絡算法以及模擬退火等現代化算法來分割木材。而在實際排樣過程中，使用單一的算法往往得不到最優方案。故本文根據不同排樣問題的復雜程度，建立整數線性規劃模型、木板排樣優化模型，運用遺傳算法，并利用Matlab、C++進行編程求解，得出不同生產條件下板材的最優分割方案和最大利用率，易與實際生產聯系緊密。

關鍵詞：遺傳算法;整數線性規劃;木板排樣優化模型;Matlab

1 概述

在實際工程技術與工業生產中，將較大的矩形板材分割為若干個不同類型矩形零件的問題，對機器設備的制造成本以及生產周期有著非常深遠的影響。如何使板材的利用率最大化，是一個好的切割方案首先要解決的問題。板材優化問題就是規劃原材料與每個零件的最優布局問題，使板材余料盡可能的減少，從而減少資源浪費，降低成本，提高經濟效益。

2 問題分析

在解決板材分割問題時，首先要建立木板排樣優化模型，尋求木板切割的最優方案，再利用整數線性規劃模型做出進一步的劃分，得到目標函數方程及約束條件組，運用Matlab進行編程求解，即可求解出簡單的木板分割問題。為了簡化計算的復雜，我們假設木板的長、寬、生產任務等均為整數。

對于更復雜的問題，如目標產品種類過多，在這種情況下，通過整數線性規劃很難求出最優解，故本文引進了遺傳算法來計算木板的最大利用率，并采用整數編碼的方式來解決木板排樣問題。另外，在解決切割多種目標產品問題時，本文引進了一個新的概念—重要度。根據每塊木板上產品最多可切割的數量，得出各產品的重要度，每次進行板材切割時，按照板材的重要度依次切割，重要度靠前的板材盡可能多的切割，從而簡化問題的復雜程度。

3 算法設計

在算法設計過程中，不考慮木板厚度的影響，僅以長寬作為考量標準，并忽略切割時，因技術帶來的余料損失的誤差。假設木板分割方式均是按照橫向切割（沿木板長的方向）和縱向分割（沿木板寬的方向），不考慮其他切割方式。如在木板A切割產品x，由數學排列組合知識可得四種切割方式，分別如下圖所示。其中（1）（2）對A進行橫向切割，x分別縱向和橫向放置;（3）（4）對A的進行縱向切割，x分別縱向和橫向放置。

對于更復雜的問題，需要引入本文的核心算法—遺傳算法，并采用整數編碼的方式來解決木板排樣問題。遺傳算法的核心因子是染色體，待排產品的數目n與染色體的長度相同，產品P的排列序號記為染色體的基因編碼。因此，染色體的序號可以組成0～n-1的一個全排列。然后，按照編碼順序依次將產品Pi排入木板S中，這種方式也被稱為基因編碼。針對木板排樣優化問題，首先將系統進行初始化，木板S1和產品Pi尺寸數據讀入，然后對隨機生成的種群賦值，再評估染色體。通過不斷的循環，如果不滿足循環評估條件，則重新選擇染色體并進行染色體的交叉和變異，得到最優保持并回到評估染色體流程繼續循環。如果滿足，即可得到最優的染色體交叉情況，從而得出最優切割方案。

4 結語

本文通過建立木板排樣優化模型和整數線性規劃模型，引入遺傳算法，并運用Matlab，C++編程，從而求出木板的最大利用率和最優分割方案，在優化排樣時具有重大意義。

參考文獻：

[1]劉詠.基于梯形和平行四邊形的圓片下料算法設計與實現[D].2016.05.19.

[2]余鵬.生成矩形毛坯最優四塊排樣方式的精準算法[D].2008.04.01.

[3]司守奎，孫兆亮.數學建模算法與應用.北京：國防工業出版社，2019.1.

[4]朱銀龍，吳海云，劉琦.基于線性規劃的材料切割設計研究[J].技術與市場，2018（11）：95.

[5]譚漢松，彭迎春.板材最優切割算法的設計與實現[J].計算機科學與應用，2003（18）：95.

[6]袁哲，王永振，趙漢馳.矩形石板優化排樣及切割路徑規劃研究[J].制造業自動化.

作者簡介：吳雨婷（2000-），女，漢族，安徽銅陵人，本科在讀，主要研究方向為計算機科學與技術;張玉（1976-），女，漢族，安徽淮南人，講師，主要研究方向為模式識別、數據挖掘、線性優化。