Linear Programming In A Probabilistic Sense Polynomial Algorithm

Linear programming problem is very broad in society practice. To resolve this problem, the simplex method is of good effect in practical application since it was advanced. But it has been proved that the simplex method is exponential computational complexity in theory.For many years, many scholars have been aiming to search for a polynomial algorithm of linear programming. Khanchian's ellipsoidal algorithm and Karmarkar's projective rescaling algorithm for linear programming were proved of polynomial time algorithm. But their superiority in theory can't be realized in practical application.Considering the inconsistency of simplex method's computational efficiency in practice and exponential computational complexity in theory, people put forward that whether there is an improved model of simplex method is polynomial algorithm? It has become a research focus of many scholars in recent years. In this paper, the author attempts to bring forward a polynomial algorithm in sense of probability, which is an improved model of simplex method.Some analyses indicate that using the algorithm advanced in this paper toresolve a linear programming problem with m constraints and n variables(m≥27,n≥2m) , the probability of getting the optimal solution is more than0.9864, and the iterative number needed is no more than m+8. This is a satisfying result.This paper can be divided into four parts:Chapter One: Briefly introduce the linear programming, and summarize the basic theory, development history and economical significance of linear programming.Chapter Two: Introduce the basic idea, compute process, and some problemsabout simplex method, which is effective in practical application.Chapter Three: Bring forward a polynomial algorithm of getting the optimal solution for linear programming in sense of probability, and give a specification of this algorithm,which includes the basic idea, compute process, explanation in theory, probability analysis of Gauss elimination iterative number, and the compute efficiency.Chapter Four: Summarize the algorithm advanced in this paper.