线性规划的原始松弛——对偶MBU单纯形算法

A primal relaxation and dual MBU simplex algorithm for linear programming

线性最优化广泛应用于经济与管理的各个领域.对于含有等式约束的线性规划问题,单纯形算法需要构造辅助的第一阶段问题求得问题的一个可行基.本文提出了一种原始松弛—对偶MBU单纯形算法(来求解第一阶段问题).首先,忽略不等式约束构造一个原始可行的松弛子问题,再用原始单纯形法求解该子问题;然后用对偶MBU单纯形法求解第一阶段问题.通过大规模数值试验对这种算法进行计算检验,数值结果表明,与经典单纯形算法相比,本文所提出的算法简便可行且具有更高的计算效率.

Linear programming has been widely used in the various areas of economics and management.If there are equality constraints in the linear programming model,the auxiliary phase 1 problem has to be solved for finding a feasible basis.This paper proposes a primal relaxation-dual MBU simplex algorithm.Firstly,the phase 1 subproblem with only the equality constraints is constructed,then it is solved with the primal simplex algorithm.Next,the dual MBU simplex algorithm is applied to find the solution to the original problem.Finally,it is found that the algorithm presented in this paper is convenient and efficient in computation,compared with the classical primal simplex method,by the numerical test on some large-scale examples.