一種求解直角邊零件下料問題的啟發(fā)式方法.pdf

1、切割與布局問題是一種極具代表性的組合優(yōu)化問題，在求解的復(fù)雜性上屬于典型的NP難問題。布局問題具有很強(qiáng)的實(shí)用性，在實(shí)際生活、生產(chǎn)中經(jīng)常遇到，它的求解對(duì)理論研究和實(shí)際應(yīng)用都有著重要的價(jià)值，因此布局問題是計(jì)算機(jī)領(lǐng)域、運(yùn)籌學(xué)領(lǐng)域和組合數(shù)學(xué)領(lǐng)域中的重要話題。
　　對(duì)于二維下料布局，目前在學(xué)術(shù)界主要側(cè)重對(duì)規(guī)則零件和完全不規(guī)則零件的研究，然而在實(shí)際工業(yè)生產(chǎn)中存在一種介于二者之間的直角邊零件，它的輪廓是由直角邊組成，并且任意相連兩邊的夾角都是直角

2、。對(duì)于這種零件的布局研究稱為直角邊零件下料問題。本文對(duì)直角邊零件下料問題進(jìn)行深入的研究，目的是尋求最優(yōu)化的下料方案以提高板材利用率。本文的主要內(nèi)容歸納如下:
　　首先，總結(jié)歸納了布局問題的分類和國(guó)內(nèi)外研究現(xiàn)狀，提出了本課題的研究?jī)?nèi)容。
　　然后，通過對(duì)直角邊零件下料問題的分析及其常見求解方法的研究，本文提出了利用啟發(fā)式方法對(duì)直角邊零件進(jìn)行下料規(guī)劃的求解方案，即:首先建立用于規(guī)劃直角邊零件下料問題的混合整數(shù)規(guī)劃模型(mixed

3、 integer programming model，簡(jiǎn)稱MIP模型)，并求出其松弛問題的解;而后將其解建模為最小頂點(diǎn)覆蓋問題（minimum vertex cover problem，簡(jiǎn)稱MVC問題）;最后使用基因遺傳算法求解MVC問題并將其解還原成為直角邊零件下料問題的解。
　　最后本文對(duì)上述求解方案給予了實(shí)現(xiàn)，其過程是:(1)利用C++語(yǔ)言與IBM公司開發(fā)的CPLEX軟件相結(jié)合，生成帶有干涉區(qū)域的排樣方案，將此方案作為初始模

4、型，再通過C++語(yǔ)言將模型轉(zhuǎn)化為MVC問題。(2)利用基因遺傳算法求解MVC問題，根據(jù)變量個(gè)數(shù)等已知條件，選取最優(yōu)的種群大小、最大迭代數(shù)、變異率等參數(shù)數(shù)值，利用MATLAB軟件中的遺傳算法工具箱進(jìn)行優(yōu)化，求得MVC問題的可行解。(3)利用C++語(yǔ)言編寫程序，將求得的MVC問題的可行解還原為下料問題的優(yōu)化排樣方案，利用計(jì)算機(jī)輔助繪圖軟件輸出求解圖形，從而得到了本文所要求得的直角邊零件下料問題的可行解。
　　與以往文獻(xiàn)中純粹基于混合整