线性规划的最钝角松弛算法

A Most-obtuse-angle Relaxation Algorithm for Linear Programming

本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。

Based on the most-obtuse-angle principle, a relaxation algorithm is proposed in this paper to solve linear programming problems. Some constraints are selected, and omitted according to the most-obtuse-angle principle. The smaller problem is solved with the simplex method. Then the omitted constraints are added to restore the original problem. If all the constraints are satisfied, then a basic optimal solution is reached. In the other case, the dual simplex method is used to obtain the basic optimal solution. Our preliminary computational tests demonstrate that the new algorithm is much faster than the conventional two-phase simplex algorithm.