Degradation Of Linear Programming Problems

Linear programming theories have gotten the extensive application in the areas of engineering design, produce management, transportation problem, the national defense, and a lot of branches of natural sciences. Although linear programming problem is an ancient problem, the method of its solution is continuously developing. The methods to solve linear programming problem include the simplex method, dual simplex method, ellipsoid method as well as the interior-point method etc. Although there are many methods to solve linear programming problem, the simplex method in all the methods is still the main method.As linear programming problem is degenerate, the simplex method may be circulating. Therefore, to study the problem of degeneracy in linear programming problem becomes very important.In 1952, Charnes1'91 reported a method named "the perturbation method" to solve the degenerate linear programming. In 1954, Dantzig[33] gave another method called "the lexicographical order method" to solve this problem. In 1976, "Bland rule" was developed by Bland' . It can avoid circulation to solve the degenerate linear programming based on the simple method. After that time, there are no methods of avoiding circulation based on the frame of the simplex method reported.The thesis studies the method of avoiding circulation based on the frame of the simplex method to solve degenerate linear programming problem. We analyze some disadvantages of methods mentioned above. We give some our own standpoints, and develop some new methods to avoid circulation. The works include the following three parts.Firstly, we study the perturbation method of Charnes'. This perturbation method add whole coefficient perturbation to the constrain equations. We find that some variables do not need perturb. So. we develop a new perturbation method that is a basis perturbation for the constrain equations and get a theorem of minimal perturbation. We give the relevant lexicographical order method as well.Secondly, we consider the degenerate linear programming problem with upper bounded variable constrained. In this part, we give a perturbation method and get a theorem of minimal perturbation for degenerate linear programming problem withupper bounded variable constrained. Then we also give the relevant lexicographical order method.Thirdly, we analyze the Bland rule. The Bland rule is a method of passivity to destroy circulation. We point out that the lack of two aspects for the Bland rule. Based on the analysis, we develop an improved method. We prove that according to these rules, the new method can certainly avoid circulation, and have obvious high efficiency.Finally, after summarizing the contents in the thesis, we point out the further directions to study the degenerate linear programming problem.