Some New Algorithms For Linear Programming

The research of linear programming algorithm can be divided into three main types of shape: one is the simplex type algorithm, that is, according to certain rules, following the boundaries of the feasible region, from a vertex (basic feasible solution) to another better vertex; second is interior point algorithm, which iterative path is within the feasible region. The third is the external point method, that is, iterative point converge to the optimal solution of the original problem from the outside the feasible region.The most classical algorithm which iterate along the boundary of the feasible region is the Dantzig's simplex algorithm. 1998 PAN.PQ presents a creative new concept - Deficient Basis, the algorithm extends the concept of the base and is no longer required for the square base. On this basis, this paper propose a deficit based one phase of big M algorithm for solving linear programming problems, which only need to introduce an artificial variable, greatly reducing the scale of the problem, and in the iteration process can determine the feasibility of the original problem in advance, and computational examples show that the new algorithm is more effective than Dantzig's simplex method in judging the feasibility of the original problem. In addition, by modifying the rules of selecting variables into the basic, it improves the deficit-based simplex algorithm, and some examples also verify the efficiency of the algorithm.Interior point method is polynomial time algorithm for solving linear programming problems, there are three types: Karmarkar projection scaling algorithm, Affine scaling algorithm, Path following method. 1990 Indian scholar V. CH VENKAIAH describes a new interior point algorithm. It uses the same projection matrix in each of iterations. But there are counter-example shows the same projection matrix interior point algorithm only convergence to the problem feasible solution rather than the optimal solution. By analyzing the same projection matrix interior point algorithm, combined with the idea of potential function, this paper constructs a new same projection matrix interior point algorithm that can guarantee the convergence to the optimal solution.On the basis of the ideas of logarithmic penalty function, the paper presents a new interior point algorithm about a combination of directions. The new interior point algorithm also composes the steepest descent direction and"Vertical direction"in each of iterations, but the weights of every direction are random and not fixed. The steepest descent direction is obtained by the same projection matrix interior point algorithm, and"Vertical direction"is obtained by the potential function method. And the new algorithm only calculates one projection matrix. Thus it reduces the computation of the algorithms. Preliminary example shows the correctness and validity. In 1993, Konstantinos Paparrizos describes one simplex algorithm of external point. External point method has two main shortcomings: (1) how to choose a "good direction of movement"; (2) it does not know whether there is a path leading to the interior of the feasible region. And a "good direction of movement" even more dependent on the choice of the dual initial feasible basis. For the initial interior feasible solution, this paper is obtained through two phase method in the interior point algorithm. And for dual feasible basis corresponding to the regular solutions, the paper are mainly based on the most obtuse angle ideas, and construct a dual phase-one algorithm in case of deficit basis, and finally get a good dual feasible basis corresponding to regular solutions. Thereby an effective external point algorithm has been got.