Study On Condition Redundancy Of Linear Inequality Systems And Algorithm For Linear Programming Problem

Since the mathematician konterovitch and Koopmans, one from the former Soviet Union and the other from America, gave the linear programming problem and its model one after another, all the time, it has been regarded to be a great breakthrough that the America scholar G. B. Dantzig proposed the Simplex method in1947. There is every reason to say, the Simplex method provides the linear programming with a wide applied space. Today, there have been tremendous achievements in studying on linear programming theory, especially, in the field of studying on algorithm. Altogether, there are three main algorithm groups of linear programming to have been developed, that is. the pivoting algorithm group originating from the Simplex method by G. B. Dantzig, the cutting region algorithm group stemming from the ellipse algorithm by the soviet scholar khachiyan, and the interior point algorithm group coming from the Karmarkar projection algorithm by the America scholar N. Karmarkar. Obviously, among the three groups, the most fruitful group was the interior-point algorithm group.It is well known to us that the linear programming has two outstanding features—linear feature and geometric plane feature. However, it’s regretted that, at present, none of three algorithm groups has made good use of the two features. In fact, the Simplex method and its all improved algorithms, which were proposed only in basis of the linear feature of linear programming, could not enough to make good use of the geometric plane feature of linear programming, so, usually, their optimum efficiency are very easily to be influenced by basis degenerating phenomenon when they are applied to solving linear programming problem. In the same while, as to the ellipse algorithms and the interior-point algorithms, being polynomial-time algorithms at the angle of the pure theory, but they are belong to kinds of nonlinear methods, so, for the reason of their complexity of iterative calculation, their optimum efficiencies are seriously affected, moreover, in actual usage, their practical effects are even worse than the Simplex method!According to the present studying state of algorithm for linear programming, around the issue on algorithm studying of linear programming, based on the linear feature and geometric plane feature of linear programming, with the help of the analytic geometry, the linear space theory, the linear manifold theory, the sensitivity analysis theory in linear programming and the convex planning theory and so on, there are two algorithm frameworks to be established in this dissertation, one named as the basis-vertex directional transferring&searching framework, and, the other named as the eliminating-redundancy&reducing-order framework, they all are different from the traditional three algorithm groups. In order to reach the objective above, this dissertation mainly do the following studying works such as the redundancy analysis of constraints, the solution decision of linear inequality systems, the separable-features decision of two linear manifold cones, the algebra and geometry description of feasible region, the trandferring methods of degradation basis-vertex and so on. With these problems in depth of studying, several algorithms are proposed which could be apply to the solution to linear programming problem, the solution decision of linear inequality systems, and the redundancy analysis of condition constraint.This research mainly manifested in the following aspects:1. As to studying on algorithm, nothing is more important but obtaining a good operation platform, for this, a new operation platform, named as basis-vertex transferring matrix, is built together with its a special algebra operation. Based on above platform, a new basis-vertex directional transferring&searching framework is presented, by which the process of solution to linear programming is truely changed into a series of elementary column transformation of matrices, and several new algorithms, including the Vertex Steepest Extreme Direction Transition iteration algorithm, are proposed for solving linear programming problem in this dissertation.2. In order to make full use of the good transferring features of non-degenerate basis-vertex, and keep the bad influences, stemming from the degeneration of basis-vertex, away from simplex basis-vertex transition process, the simplex locally regularized method with the translation extension principle is proposed, by which the iteration transition of degenerate basis-vertex is changed into the iteration transition of non-degenerate basis-vertex, thus, the basis-cycling phenomenon is kept away from the process of solution to linear programming problem, forever.3. Around the issue on the redundancy of condition constraints, an algebra and geometry description for redundancy of some constraint is given, such that the redundancy decision of condition constraint is changed into the solution-decision of linear inequality systems. Based on the work above, in this dissertation, a new solution framework, named as eliminating redundancy&reducing order framework, is established for us to solve linear programming problem. Furthermore, several eliminating redundancy&reducing order algorithms for linear programming are proposed.4. Around the issue on the compatibility decision of linear inequality systems, in this dissertation, by conducting two new concepts of l-positive manifold cone and separable-features of l-positive manifold cone, the compatibility decision of linear inequality systems is changed into the separable-features decision of two l-positive manifold cone. Meanwhile, based on an axiom hypothesis to the separable-features of l-positive manifold cone, the principle system.of l-positive manifold cone separable-features is established, in which a series of decision theorems are developed. With the help of the work above, a new solution-decision method for linear inequality systems is given.