一种原始——对偶单纯形算法的枢轴准则选择

The Choice for the Pivoting Rules of a Primal——Dual Simplex Algorithm

Curet曾提出了一种有趣的原始一对偶技术,在优化对偶问题的同时单调减少原始不可行约束的数量,当原始可行性产生时也就产生了原问题的最优解.然而该算法需要一个初始对偶可行解来启动,目标行的选择也是灵活、不确定的.根据Curet的原始一对偶算法原理,提出了两种目标行选择准则,并通过数值试验进行比较和选择.对不存在初始对偶可行解的情形,通过适当改变目标函数的系数来构造一个对偶可行解,以求得一个原始可行解,再应用原始单纯形算法求得原问题的最优解.数值试验对这种算法的计算性能进行验证,通过与经典两阶段单纯形算法比较,结果表明,提出的算法在大部分问题上具有更高的计算效率.

Curet ever presented an interesting primal-dual approach that simultaneously drives towards primal feasibility while optimizing a dual program, and arrives at an optimal vertex as the primal feasibility comes true. However, the approach needs an initial dual feasible solution to start, and allows considerable flexibility in the choice for the target row. Based on principle of Curet＇s primal-dual algorithm, this paper presents two rules choosing the target row, and implement comparison and selection by numerical test. For this case of no initial dual feasible solution, we＇ll change appropriately the negative coefficients of objective function to construct it. Therefore a primal feasible solution can be obtained by Curet＇s algorithm, and then, the optimization achieved by the classical simplex algorithm. Finally, a computer implementation is accomplished to test the computational performance of our algorithm comparing to the classical two-phase simplex algorithm. The computational results show that our algorithm is more effective on most instances.