基于组合方的单纯形算法.doc

摘要 线性规划是运筹学中研究较早、发展较快、应用广泛的一个重要分支,它是辅助人们进行科学管理的一种数学方法广泛应用。Operations Research which is earlier researched, rapidly developed and widely used, Linear programming is a mathematic method which can help people to achieve a scientific management. It is a mathematic theory whose purpose is to gain an optimal solution under some constraints. Linear programming has been widely used in the military、 economic、management and so on. It can provide the deciders a reliable scientific proof according to the limited human, material and financial resources. So how to calculate the Linear programming problem better and faster has been to an attractive and essential task. In 1947, G.B.Dantzig propose the first algorithm to solve the Linear programming problem which is Simplex algorithm. It became the classic algorithm in solving the Linear programming problem. Since then, the algorithm of Linear programming problem can be devided into two aspects. The first one is the algorithms which walk along with the feasible edge direction, from one extreme point to the adjacent one,and get the basic feasible solution which is optimal. The other is the algorithms which don’t follow the traditional iterative method. They don’t walk along with the edge of feasible solution area,they walk inside or outside the feasible solution area, most of them choose the former and find the optimal solution at last. In the first category,the main work is to select the element.Apart from the simplex algorithm rule ,now the popular selecting rules are rule based the most obtuse angle, or rule based the steepest edge. In the second category, The mian work is to seclet the direction which is different from the feasible descent(ascend)edge direction. In several steps later, It can get the optimal solution. Such algorithms have certain advantages in solving large scale problem, because these algorithms can dodge a lot of extreme point when the feasible solution area which has a lot of edges, So they can limit the it