本文選題：線性規(guī)劃 + 矩陣變化��； 參考：《廣西大學(xué)》2017年碩士論文

【摘要】：產(chǎn)品的緊湊型布局是實(shí)現(xiàn)降低制造成本、提高材料利用率的有效途徑,針對多規(guī)格大規(guī)模的二維矩形件下料存在求解難、計算量大等問題,如何快速獲得合理科學(xué)的布局方式,提高材料的利用率,一直是學(xué)者們和企業(yè)追求的目標(biāo)。在布局過程中需結(jié)合數(shù)學(xué)方法進(jìn)行規(guī)劃,而高效的數(shù)學(xué)方法對布局結(jié)果的好壞和快慢有著關(guān)鍵性的影響,故探求一種精確度高、計算量低的數(shù)學(xué)迭代方法來處理多規(guī)格大規(guī)模矩形件的下料問題是非常有必要的。本學(xué)位論文綜合考慮計算時間和材料利用率兩方面因素,旨在尋求一種高效的數(shù)學(xué)方法,獲得排樣過程中信息數(shù)據(jù)(如排樣材料的數(shù)量),為得到高效合理的布局方式提供一個有效的指導(dǎo)。文章在充分研究二維矩形件下料問題排樣過程和目標(biāo)基礎(chǔ)上,分析對比布局過程中常用的動態(tài)規(guī)劃法、背包問題算法和列生成的線性規(guī)劃法在二維矩形下料問題中存在優(yōu)缺點(diǎn),研究分析基于列生成的數(shù)學(xué)方法對二維矩形排樣方式的生成的重要性,研究分析傳統(tǒng)列生成的線性規(guī)劃法的尋優(yōu)過程存在迭代次數(shù)多,且需求解逆矩陣等問題,提出一種矩陣變化列生成的線性規(guī)劃法,可提高計算速度、減少了迭代次數(shù),充實(shí)矩形件下料問題優(yōu)化的理論與方法。研究分析二維矩形件下料問題中線性規(guī)劃模型,創(chuàng)新提出矩陣變化列生成方法,建立線性規(guī)劃的迭代模型,并根據(jù)該模型求解計算的結(jié)果,獲取排樣的信息數(shù)據(jù),研究制定相對應(yīng)的布局策略和具體的排樣步驟。重點(diǎn)研究該模型在考慮布局約束情況下,對下料布局問題的線性規(guī)劃模型進(jìn)行求解的過程,通過以未知向量的形式參與布局矩陣的變化,推導(dǎo)發(fā)現(xiàn)布局矩陣變化過程中未知向量(列生成)的變化規(guī)律,為簡化矩陣變化計算的繁瑣過程,提出采用矩陣來記錄未知向量中元素之間線性關(guān)系,再結(jié)合MATLAB中單純形法函數(shù)來進(jìn)行求解優(yōu)化,可避免繁瑣的逆矩陣的求解,減少迭代次數(shù),降低計算時間。以MATLAB為程序編寫工具,實(shí)現(xiàn)矩陣變化列生成算法的求解過程,并用隨機(jī)實(shí)例和相關(guān)文獻(xiàn)案例進(jìn)行計算與對比,其中與文獻(xiàn)[31]中案例對比結(jié)果顯示:本文算法的計算迭代次數(shù)是4次,而文獻(xiàn)方法的迭代次數(shù)是10次,最后,根據(jù)求解優(yōu)化的結(jié)果制定較好的排樣策略,可有效指導(dǎo)矩形件的排樣,從而驗(yàn)證算法的可行性與有效性。
[Abstract]:The compact layout of the product is an effective way to reduce the manufacturing cost and improve the material utilization ratio. In view of the problems such as difficult to solve and large amount of calculation for the large scale two-dimensional rectangular parts with many specifications, how to quickly obtain a reasonable and scientific layout mode is proposed. Improving the utilization rate of materials has been the goal pursued by scholars and enterprises. In the process of layout, it is necessary to plan with mathematical methods, and efficient mathematical methods have a key influence on the quality and speed of layout results. It is necessary to solve the blanking problem of large scale rectangular parts with many specifications by using the mathematical iterative method with low computational complexity. In order to find an efficient mathematical method, this thesis considers two factors of calculating time and material utilization ratio synthetically. Obtaining the information data (such as the quantity of layout materials) during the layout process provides an effective guidance for the efficient and reasonable layout. On the basis of fully studying the layout process and objectives of the two-dimensional rectangular blanking problem, this paper analyzes and compares the advantages and disadvantages of dynamic programming, knapsack problem algorithm and linear programming method of column generation in the two-dimensional rectangular blanking problem, which are commonly used in the layout process. In this paper, the importance of column generating mathematical method to the generation of two-dimensional rectangular layout is studied, and the problems of solving inverse matrix and iterative times in the optimization process of traditional linear programming based on column generation are studied and analyzed. This paper presents a linear programming method for generating matrix change columns, which can improve the calculation speed, reduce the number of iterations, and enrich the theory and method of the optimization of the blanking problem for rectangular parts. This paper studies and analyzes the linear programming model in the two-dimensional rectangular blanking problem, innovates the method of generating matrix change column, establishes the iterative model of linear programming, and obtains the information data of layout according to the result of solving the calculation of the model. Study the corresponding layout strategy and specific layout steps. This paper focuses on the process of solving the linear programming model of the layout problem under the condition of considering the layout constraints, and participates in the change of the layout matrix in the form of unknown vectors. In order to simplify the complicated process of matrix change calculation, the matrix is used to record the linear relationship between the elements in the unknown vector. By combining the simplex method in MATLAB to solve the problem, the complicated inverse matrix solution can be avoided, the number of iterations can be reduced, and the computation time can be reduced. Using MATLAB as a programming tool, the algorithm of matrix change column generation is solved, and the calculation and comparison are carried out with random examples and related literature cases. The results of comparison with the cases in reference [31] show that the number of iterations calculated in this algorithm is 4, and the number of iterations in the literature method is 10. Finally, a better layout strategy is made according to the results of optimization. It can effectively guide the layout of rectangular parts and verify the feasibility and effectiveness of the algorithm.
【學(xué)位授予單位】：廣西大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O221

【參考文獻(xiàn)】

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

1 陳秋蓮;宋仁坤;崔耀東;;考慮余料價值的三階段二維剪切下料算法[J];圖學(xué)學(xué)報;2017年01期

2 曾兆敏;王繼紅;管衛(wèi)利;;二維板材切割下料問題的一種確定性算法[J];圖學(xué)學(xué)報;2016年04期

3 易向陽;仝青山;潘衛(wèi)平;;矩形件二維下料問題的一種求解方法[J];鍛壓技術(shù);2015年06期

4 梁秋月;崔耀東;游凌偉;;應(yīng)用三塊排樣方式求解二維下料問題[J];廣西師范大學(xué)學(xué)報(自然科學(xué)版);2014年03期

5 程春英;包蘭英;包春花;;改進(jìn)的人工魚群算法在二維板材下料問題中的應(yīng)用[J];遼寧工程技術(shù)大學(xué)學(xué)報(自然科學(xué)版);2014年07期

6 羅丹;崔耀東;李秋蓉;;生成勻質(zhì)塊排樣方式的遞推算法[J];計算機(jī)工程與設(shè)計;2013年03期

7 季君;陸一平;查建中;;基于單毛坯條帶的矩形件最優(yōu)兩段排樣方式[J];北京交通大學(xué)學(xué)報;2012年01期

8 王曉慶;李尚芳;崔耀東;;矩形毛坯最優(yōu)層排樣方式的動態(tài)規(guī)劃算法[J];計算機(jī)應(yīng)用研究;2010年06期

9 馬炫;劉慶;;求解多背包問題的人工魚群算法[J];計算機(jī)應(yīng)用;2010年02期

10 謝友寶;羅婷婷;李凌輝;呂永海;;混合遺傳算法在飛機(jī)鈑金零件排樣中的應(yīng)用[J];機(jī)械與電子;2009年12期

相關(guān)博士學(xué)位論文 前1條

1 季君;基于同形塊的剪切下料布局算法研究[D];北京交通大學(xué);2012年

，

本文編號：1968974