ABSTRACT
It is well known that the G. B. Dantzig’s simplex method is not a good algorithm due to the reason that it is not a polynomial algorithm for use to handle computational complexity; however, it is the popular basic, most effective and widely used way to solve linear programming problems so far. Herewith, various improvements on the simplex procedure have filled many volumes of works. There are two key works that deserve our attention: how to get an initial feasible basis in the form of a unit matrix; how to get the optimal solution as quickly as possible. The basic thought of the simplex method is aimed at the standard form of a linear programming problem:
max { }, , , ,C X A X b X b m nT m n = ≥ ≤ (1)
Improving the optimal value of the object function via a transform from a basic feasible solution to another basic feasible solution start off at the point where a basic feasible solution is given in its feasible region; and then one obtains the optimal solution or arrives at a judgment that no optimal solution exists. This thought is realized by using a basis transformation in reality. The basis transformation is an operation of iteration by choosing a pivot via determining an entrance variable and an extraction variable according to a given rule. In practical uses, we find that the
Also, assume that B is a basis, and the iteration coefficients A and b are A j( )ai , b = (bi ). By letting XN = 0 , we obtain the corresponding basic solution (Editorial Group of Textbook of Operations Research. 1990, J. L. Xue. 1992, G. H. Wei, J. L. Fu, etc. 1987, Y. L. Niu, 1994)
X b b b B b
= ⎡⎣ ⎤⎦ = ⎡ ⎣⎢
⎤ ⎦⎥1 2
1 0 0
0 , , , , , ,…
the value of the object function Z C B bB T 1 , and
the criterion σ σ σ[ ,σ , , ]1 2 n T .
