基于整數(shù)規(guī)劃下木板排樣優(yōu)化問題的研究

吳雨婷　張玉

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

關(guān)鍵詞：遺傳算法;整數(shù)線性規(guī)劃;木板排樣優(yōu)化模型;Matlab

1 概述

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

2 問題分析

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

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

3 算法設(shè)計(jì)

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

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

4 結(jié)語

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

參考文獻(xiàn)：

[1]劉詠.基于梯形和平行四邊形的圓片下料算法設(shè)計(jì)與實(shí)現(xiàn)[D].2016.05.19.

[2]余鵬.生成矩形毛坯最優(yōu)四塊排樣方式的精準(zhǔn)算法[D].2008.04.01.

[3]司守奎，孫兆亮.數(shù)學(xué)建模算法與應(yīng)用.北京：國防工業(yè)出版社，2019.1.

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

[5]譚漢松，彭迎春.板材最優(yōu)切割算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)與應(yīng)用，2003（18）：95.

[6]袁哲，王永振，趙漢馳.矩形石板優(yōu)化排樣及切割路徑規(guī)劃研究[J].制造業(yè)自動(dòng)化.

作者簡介：吳雨婷（2000-），女，漢族，安徽銅陵人，本科在讀，主要研究方向?yàn)橛?jì)算機(jī)科學(xué)與技術(shù);張玉（1976-），女，漢族，安徽淮南人，講師，主要研究方向?yàn)槟Ｊ阶R(shí)別、數(shù)據(jù)挖掘、線性優(yōu)化。