基于线性规划核心矩阵的单纯形算法

A Simplex Method Based on Kernel Matrix of Linear Program

本文讨论了线性规划中的核心矩阵及其特性，探讨了利用核心矩阵实现单纯形算法的可能性，并进一步提出了一个基于核心矩阵的两阶段原始一对偶单纯形方法，该方法通过原始和对偶两个阶段的迭代，可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界．在试验的22个问题中，该算法的计算效率总体优于基于传统单纯形方法的MINOS软件．

We discuss the characteristics of kernel matrix of LP and the possibility of applying thekernel matrix to the simplex method. We introduce a primal-dual simplex method basedon the kernel matrix, hich will converge to the optimal solution or prove the infeasibilityor unboundedness within a finite number of iterations through a two-phase primal-dualalgorithm. Among the preliminary test of 22 problems, the computation efficiency of the newalgorithm is totally superior to MINOS which is based on the traditional simplex method.