發(fā)布時(shí)間：2018-12-09 17:18

【摘要】：切割與布局問(wèn)題是一種極具代表性的組合優(yōu)化問(wèn)題,在求解的復(fù)雜性上屬于典型的NP難問(wèn)題。布局問(wèn)題具有很強(qiáng)的實(shí)用性,在實(shí)際生活、生產(chǎn)中經(jīng)常遇到,它的求解對(duì)理論研究和實(shí)際應(yīng)用都有著重要的價(jià)值,因此布局問(wèn)題是計(jì)算機(jī)領(lǐng)域、運(yùn)籌學(xué)領(lǐng)域和組合數(shù)學(xué)領(lǐng)域中的重要話題。 對(duì)于二維下料布局,目前在學(xué)術(shù)界主要側(cè)重對(duì)規(guī)則零件和完全不規(guī)則零件的研究,然而在實(shí)際工業(yè)生產(chǎn)中存在一種介于二者之間的直角邊零件,它的輪廓是由直角邊組成,并且任意相連兩邊的夾角都是直角。對(duì)于這種零件的布局研究稱為直角邊零件下料問(wèn)題。本文對(duì)直角邊零件下料問(wèn)題進(jìn)行深入的研究,目的是尋求最優(yōu)化的下料方案以提高板材利用率。本文的主要內(nèi)容歸納如下： 首先,總結(jié)歸納了布局問(wèn)題的分類和國(guó)內(nèi)外研究現(xiàn)狀,提出了本課題的研究?jī)?nèi)容。 然后,通過(guò)對(duì)直角邊零件下料問(wèn)題的分析及其常見求解方法的研究,本文提出了利用啟發(fā)式方法對(duì)直角邊零件進(jìn)行下料規(guī)劃的求解方案,即：首先建立用于規(guī)劃直角邊零件下料問(wèn)題的混合整數(shù)規(guī)劃模型(mixed integer programming model,簡(jiǎn)稱MIP模型),并求出其松弛問(wèn)題的解；而后將其解建模為最小頂點(diǎn)覆蓋問(wèn)題(minimum vertex cover problem,簡(jiǎn)稱MVC問(wèn)題)；最后使用基因遺傳算法求解MVC問(wèn)題并將其解還原成為直角邊零件下料問(wèn)題的解。 最后本文對(duì)上述求解方案給予了實(shí)現(xiàn),其過(guò)程是：(1)利用C++語(yǔ)言與IBM公司開發(fā)的CPLEX軟件相結(jié)合,生成帶有干涉區(qū)域的排樣方案,將此方案作為初始模型,再通過(guò)C++語(yǔ)言將模型轉(zhuǎn)化為MVC問(wèn)題。(2)利用基因遺傳算法求解MVC問(wèn)題,根據(jù)變量個(gè)數(shù)等已知條件,選取最優(yōu)的種群大小、最大迭代數(shù)、變異率等參數(shù)數(shù)值,利用MATLAB軟件中的遺傳算法工具箱進(jìn)行優(yōu)化,求得MVC問(wèn)題的可行解。(3)利用C++語(yǔ)言編寫程序,將求得的MVC問(wèn)題的可行解還原為下料問(wèn)題的優(yōu)化排樣方案,利用計(jì)算機(jī)輔助繪圖軟件輸出求解圖形,從而得到了本文所要求得的直角邊零件下料問(wèn)題的可行解。 與以往文獻(xiàn)中純粹基于混合整數(shù)規(guī)劃的求解方法相比,本文的方法擴(kuò)大了直角邊零件下料問(wèn)題的可求解規(guī)模,縮短了計(jì)算時(shí)間。與現(xiàn)行人工布排相比,本文提出的方法能夠平均提高待布局板材的利用率約15%左右,增加了板材使用價(jià)值,提高了企業(yè)的經(jīng)濟(jì)效益。
[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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP18;TH16

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2369752