矩形件下料问题的创新线性规划布局方法研究与应用

发布时间：2018-06-02 13:44

本文选题：线性规划 + 矩阵变化　；参考：《广西大学》2017年硕士论文

【摘要】：产品的紧凑型布局是实现降低制造成本、提高材料利用率的有效途径,针对多规格大规模的二维矩形件下料存在求解难、计算量大等问题,如何快速获得合理科学的布局方式,提高材料的利用率,一直是学者们和企业追求的目标。在布局过程中需结合数学方法进行规划,而高效的数学方法对布局结果的好坏和快慢有着关键性的影响,故探求一种精确度高、计算量低的数学迭代方法来处理多规格大规模矩形件的下料问题是非常有必要的。本学位论文综合考虑计算时间和材料利用率两方面因素,旨在寻求一种高效的数学方法,获得排样过程中信息数据(如排样材料的数量),为得到高效合理的布局方式提供一个有效的指导。文章在充分研究二维矩形件下料问题排样过程和目标基础上,分析对比布局过程中常用的动态规划法、背包问题算法和列生成的线性规划法在二维矩形下料问题中存在优缺点,研究分析基于列生成的数学方法对二维矩形排样方式的生成的重要性,研究分析传统列生成的线性规划法的寻优过程存在迭代次数多,且需求解逆矩阵等问题,提出一种矩阵变化列生成的线性规划法,可提高计算速度、减少了迭代次数,充实矩形件下料问题优化的理论与方法。研究分析二维矩形件下料问题中线性规划模型,创新提出矩阵变化列生成方法,建立线性规划的迭代模型,并根据该模型求解计算的结果,获取排样的信息数据,研究制定相对应的布局策略和具体的排样步骤。重点研究该模型在考虑布局约束情况下,对下料布局问题的线性规划模型进行求解的过程,通过以未知向量的形式参与布局矩阵的变化,推导发现布局矩阵变化过程中未知向量(列生成)的变化规律,为简化矩阵变化计算的繁琐过程,提出采用矩阵来记录未知向量中元素之间线性关系,再结合MATLAB中单纯形法函数来进行求解优化,可避免繁琐的逆矩阵的求解,减少迭代次数,降低计算时间。以MATLAB为程序编写工具,实现矩阵变化列生成算法的求解过程,并用随机实例和相关文献案例进行计算与对比,其中与文献[31]中案例对比结果显示:本文算法的计算迭代次数是4次,而文献方法的迭代次数是10次,最后,根据求解优化的结果制定较好的排样策略,可有效指导矩形件的排样,从而验证算法的可行性与有效性。
[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.
【学位授予单位】：广西大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221

【参考文献】