一种改进的单调增强单纯形算法

An Improved Monotonic Build-Up Simplex Algorithm for Linear Programming

考察单调增强单纯形算法的实际计算性能,并解析其计算效率较低的原因.该文提出一种改进方法,即从第一阶段算法开始,每旋出一个人工变量,就使非负缩减费用系数的个数得到单调增加;在第二阶段算法中,放松对枢轴行的选择要求,从而可使驱动变量尽快旋入基中,产生一个对偶可行解,然后再应用对偶单纯形算法获得问题的最优解或无可行解的结论.大规模数值试验对改进算法进行检验的结果表明,这种改进算法的计算效率优于经典单纯形算法,单调增强单纯形算法理论具有实用价值.

This paper examines the computational performance of the monotonic build-up （MBU） simplex algorithm, and analyzes the reasons for its inefficiency. For this reason, we present an improvement of MBU simplex algorithm, where it makes the number of non-negative reduced costs increase monotonically with the exiting of every artificial variable at each iteration by phase 1. In phase 2, the requirement for choosing the pivot row is relaxed. So, the driving variable can enter the basis as quickly as possible so as to generate a dual feasible solution. Then the dual simplex algorithm is applied to achieve the optimal solution of the problem or the conclusion that there is no feasible solution. Finally, our improved algorithm is tested on some large-size numerical examples by a computer implementation, showing that it outperforms the classical simplex algorithm in computational efficiency, and hence the practical value of the theory on MBU simplex algorithm.