第一阶段原有单纯形和对偶单纯形算法的计算比较

Computational Comparison of Primal and Dual Simplex Phase 1 Algorithms

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.

Linear optimization has been widely u^ed to solve small and large problems in the various areas of economics and management. If an initial basic feasible solution of the linear programming problem is not given, the two-phase simplex method should be applied to solve the problem. This paper discussed the solution to phase 1 auxiliary form with the ＂≥＂ inequality constra!n.tS by the primal and dual simplex algorithms. Furthermore, the dual pivoting rule was in＇proved according to the characteristic of the phase 1 auxiliary form. Finally, it found that the improved dual simplex algorithm is quicker in computation, compared with the classical primal simplex method. It is partially validated by the numerical test on some large-scale examples.