Combination Of Direction Algorithm For Linear Programming

Linear programming is an important branch of 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 iteration step under certain conditions. But there is a weakness in these algorithms. The algoriths efficiency is very slow while approaching the optimal point. The first kinds of algorithms spend too long time in the initial iteration stage.We will propose an algorithm which is based on the combined direction. The algorithm is starting from an extreme point. Through a combination of direction, Let the basic feasible solution iteration to a high-dimensional interface of feasible area, then purification or dimension reduction is done so that the current solution gradually became the basic feasible solution. Do this repeatedly, so let one of the basic feasible solutions satisfy the requirement of optimal solution. Using this kind of algorithms, not only considering the number of iterations, but also avoiding the weakness of the interior point algorithm that the convergence speed is too low at the end as much as possible . For the problem of stalling caused by degenerate will appear if the problem is very large, so we prepare to introduce the deficient basis and then propose the deficient basis algorithm base on the combined direction. At the same time, considering the combined direction, we proposed the dual simplex algorithm based on the combined direction.