Research And Application Of One-Dimensional Cutting Problem In A Random Environment

Column generation is suitable for solving large-scale linear programming problems and is widely used in important industrial fields,such as material problems,procurement problems,flight scheduling,transportation networks.This paper aims to explore a linear programming method based on matrix change in the next-dimensional blanking problem in stochastic environment,and to find an optimal model solving method with high precision and high computational efficiency,and try to apply it to deterministic one-dimensional cutting problem and the one-dimensional cutting random programming problem in a stochastic environment.In this paper,the linear programming method for column generation is theoretically analyzed and studied in deeply.Based on the in-depth study of the linear programming problem of the base column,based on the column generation,a column generation based on matrix variation is proposed.The column generation linear optimization model is established in the one-dimensional cutting problem and applied to the one-dimensional cutting random planning problems with the random environment.Using the principle of matrix change,the recursive relation is summarized in the process of transforming the integer linear programming model and generating the added column.In this paper,the key techniques of transforming integer linear programming model into column generating linear programming model,recursive matrix generating process,column generating algorithm and expectation value model are deeply analyzed and studied.A column generation optimization model and an expectation value model established in a random environment are established for the deterministic single-variant one-dimensional cutting problem.The program programming software MATLAB is used as a tool to write a matrix generation algorithm based on matrix change to solve the optimal solution of the problem.Get the blanking plan and raw material consumption.At the same time,compared with the calculation results of CAD system which is used by a large amount of references to solve the cutting stock problem,the algorithm greatly saves the calculation time and verifies the feasibility and efficiency of the proposed algorithm.Through the above analysis and research,a column-generation linear programming model is established for the deterministic one-dimensional cutting problem.The matrix-based column generation proposed in this paper is used to quickly obtain the blanking scheme and is applied to the one-dimensional cutting problem in the random environment.The computational engineering example proves that the proposed algorithm is feasible and efficient.It adds a new content to the column programming theory of linear programming and provides a new idea for solving stochastic programming problems.