【摘要】：切割與布局問題是一種極具代表性的組合優(yōu)化問題,在求解的復(fù)雜性上屬于典型的NP難問題。布局問題具有很強的實用性,在實際生活、生產(chǎn)中經(jīng)常遇到,它的求解對理論研究和實際應(yīng)用都有著重要的價值,因此布局問題是計算機領(lǐng)域、運籌學(xué)領(lǐng)域和組合數(shù)學(xué)領(lǐng)域中的重要話題。 對于二維下料布局,目前在學(xué)術(shù)界主要側(cè)重對規(guī)則零件和完全不規(guī)則零件的研究,然而在實際工業(yè)生產(chǎn)中存在一種介于二者之間的直角邊零件,它的輪廓是由直角邊組成,并且任意相連兩邊的夾角都是直角。對于這種零件的布局研究稱為直角邊零件下料問題。本文對直角邊零件下料問題進行深入的研究,目的是尋求最優(yōu)化的下料方案以提高板材利用率。本文的主要內(nèi)容歸納如下： 首先,總結(jié)歸納了布局問題的分類和國內(nèi)外研究現(xiàn)狀,提出了本課題的研究內(nèi)容。 然后,通過對直角邊零件下料問題的分析及其常見求解方法的研究,本文提出了利用啟發(fā)式方法對直角邊零件進行下料規(guī)劃的求解方案,即：首先建立用于規(guī)劃直角邊零件下料問題的混合整數(shù)規(guī)劃模型(mixed integer programming model,簡稱MIP模型),并求出其松弛問題的解；而后將其解建模為最小頂點覆蓋問題(minimum vertex cover problem,簡稱MVC問題)；最后使用基因遺傳算法求解MVC問題并將其解還原成為直角邊零件下料問題的解。 最后本文對上述求解方案給予了實現(xiàn),其過程是：(1)利用C++語言與IBM公司開發(fā)的CPLEX軟件相結(jié)合,生成帶有干涉區(qū)域的排樣方案,將此方案作為初始模型,再通過C++語言將模型轉(zhuǎn)化為MVC問題。(2)利用基因遺傳算法求解MVC問題,根據(jù)變量個數(shù)等已知條件,選取最優(yōu)的種群大小、最大迭代數(shù)、變異率等參數(shù)數(shù)值,利用MATLAB軟件中的遺傳算法工具箱進行優(yōu)化,求得MVC問題的可行解。(3)利用C++語言編寫程序,將求得的MVC問題的可行解還原為下料問題的優(yōu)化排樣方案,利用計算機輔助繪圖軟件輸出求解圖形,從而得到了本文所要求得的直角邊零件下料問題的可行解。 與以往文獻中純粹基于混合整數(shù)規(guī)劃的求解方法相比,本文的方法擴大了直角邊零件下料問題的可求解規(guī)模,縮短了計算時間。與現(xiàn)行人工布排相比,本文提出的方法能夠平均提高待布局板材的利用率約15%左右,增加了板材使用價值,提高了企業(yè)的經(jīng)濟效益。
[Abstract]:The problem of cutting and layout is a kind of representative combinatorial optimization problem, which belongs to the typical NP problem in the complexity of its solution. Layout problem has strong practicability and is often encountered in real life and production. Its solution is of great value to both theoretical research and practical application, so the layout problem is a computer field. An important topic in the field of operational research and combinatorial mathematics. For the layout of two-dimensional blanking, at present, the academic circles mainly focus on the research of regular parts and completely irregular parts. However, in the actual industrial production, there is a kind of right-sided part between the two parts, whose outline is composed of right-angled edges. And the angles on either side are right angles. The research on the layout of this kind of parts is called the cutting problem of right side parts. In this paper, the cutting problem of right side parts is studied in order to find the optimal cutting scheme to improve the utilization ratio of sheet metal. The main contents of this paper are summarized as follows: firstly, the classification of layout problems and the current research situation at home and abroad are summarized, and the research content of this subject is put forward. Then, based on the analysis of the right edge part cutting problem and the research of its common solving methods, this paper puts forward a method to solve the right edge part cutting planning by using the heuristic method. That is to say, the mixed integer programming model (mixed integer programming model, for short MIP model), which is used to plan the right side part blanking problem, is first established, and the solution of its relaxation problem is obtained. Then the solution is modeled as the minimum vertex covering problem (minimum vertex cover problem,), and the genetic algorithm is used to solve the MVC problem and the solution is reduced to the solution of the right edge part blanking problem. Finally, the above solution is implemented in this paper. The process is as follows: (1) using C language and CPLEX software developed by IBM company, the layout scheme with interference region is generated, and this scheme is regarded as the initial model. Then the model is transformed into MVC problem by C language. (2) the genetic algorithm is used to solve the MVC problem. According to the known conditions such as the number of variables, the optimal population size, maximum iteration number, variation rate and other parameters are selected. The feasible solution of the MVC problem is obtained by using the genetic algorithm toolbox in MATLAB software. (3) the feasible solution of the MVC problem is reduced to the optimal layout scheme of the feedstock problem by programming in C language. The computer aided drawing software is used to output and solve the graph, and the feasible solution of the right side part feeding problem is obtained. Compared with the previous methods based on mixed integer programming, this method expands the solvable scale and shortens the calculation time. Compared with the current artificial layout, the method proposed in this paper can increase the utilization ratio of the plate to be laid out by about 15%, increase the use value of the plate and increase the economic benefit of the enterprise.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP18;TH16

【參考文獻】

相關(guān)期刊論文 前10條

1 唐曉君,查建中,陸一平;布局問題的復(fù)雜性和建模方法[J];北方交通大學(xué)學(xué)報;2003年01期

2 賈志欣;排樣問題的分類研究[J];鍛壓技術(shù);2004年04期

3 王竹婷;;一種改進的遺傳算法在矩形排樣問題中的應(yīng)用[J];電腦知識與技術(shù);2012年32期

4 崔振勇,印建平,高雪強,張躍華;利用SCR文件開發(fā)AutoCAD參數(shù)化繪圖的研究[J];河北科技大學(xué)學(xué)報;2003年03期

5 張國強;彭曉明;;自適應(yīng)遺傳算法的改進與應(yīng)用[J];艦船電子工程;2010年01期

6 包奇金寶;姜靜清;宋初一;梁艷春;;基于粒子群與模擬退火算法的板材優(yōu)化下料[J];計算機工程與應(yīng)用;2008年26期

7 陳仕軍;曹炬;;矩形件優(yōu)化排樣的一種啟發(fā)式算法[J];計算機工程與應(yīng)用;2010年12期

8 黃少麗;楊劍;侯桂玉;崔耀東;;解決二維下料問題的順序啟發(fā)式算法[J];計算機工程與應(yīng)用;2011年13期

9 李國成;吳濤;周本達;;改進的遺傳算法及其在求解MVCP中的應(yīng)用[J];計算機工程;2010年07期

10 梁昔明;秦浩宇;龍文;;一種求解約束優(yōu)化問題的遺傳算法[J];計算機工程;2010年14期

，

本文編號：2369752