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

The revised row pivoting method for linear programming

行旋转算法是求解线性不等式组的一种直接、有效的算法,为大数据时代众多与线性不等式组紧密相关的问题提供了统一、高效的解决思路.求解线性规划问题本质上是求解线性不等式组,因而行旋转算法可以作为基础算法直接应用于求解线性规划.不同于以单纯形法为代表的列旋转算法,线性规划的行旋转算法以行几何(或行向量)为基础,其核心思想是在保证最优性条件始终成立的前提下求解约束条件对应的线性不等式组.改进的行旋转算法保持了原算法的所有特色.该算法的改进之处在于利用约束条件变量的部分系数构成的非奇异矩阵的逆矩阵(称为特征逆矩阵)和原始数据计算出枢轴行和枢轴列,从而完成一次旋转运算.特征逆矩阵的阶数一般要比约束的数目和变量的数目小很多,在每次迭代过程中只需要计算原算法算表中的小部分必要元素,因而能够显著提高计算效率.

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 eficiency compared with the row pivoting method for linear programming.