线性规划的改进行旋转算法

The row pivoting method is a direct and efficient method for solving any system of linear inequalities and provides a uniform and efficient way to solve many kinds of problems which are closely associated with systems of linear inequalities in the big data era. Dantzig thought that solving a linear programming problem is really all about solving a linear inequality system; therefore the row pivoting method for a system of linear inequalities can be directly applied to solving a linear programming problem. Unlike column pivoting methods such as the simplex method, the row pivoting method for linear programming is based on row geometry (or row vectors), and its core idea is to solve a system of linear inequalities corresponding to the constraints of a linear programming problem while keeping the optimality condition always being true. The revised row pivoting method retains all the characteristics of the row pivoting method for linear programming. The improvement of the new method lies in applying the inverse matrix (called the characteristic inverse matrix) of the non-singular matrix formed by the coefficients of partial variables of the constraints and the original data to calculating the pivot row and the pivot column, which completes a pivoting operation. Since the order of the characteristic inverse matrix is generally much smaller than the number of constraints and variables, the revised pivoting method only needs to calculate a small fraction of necessary elements coming from the corresponding computational tableau in the row pivoting method for each iteration. Therefore, the revised method can significantly improve computational efficiency compared with the row pivoting method for linear programming.