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

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

A Simplex Method Based on Kernel Matrix of Linear Program

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.