线性规划问题规范型算法的改进及计算机实现

摘要

A new algorithm for the normalized form of linear programming starts from an initial basis and then uses the simplex variant to achieve a feasible basis. This paper presents a method for finding an initial basis of the equality constraints, which does not need to compute the reduced costs of the auxiliary objective function, and under the assumption of no redundancy uses at most m iterations (equal to the number of equality con⁃straints) to get an initial basis or the conclusion of no feasible basis. Furthermore, an improved algorithm of the normalized form is proposed to achieve a feasible basis conveniently and quickly. In the improvement, one is to keep the equality constraint with the most negative right-hand side unchanged, and the other is to apply the rule of the classical simplex method to choose the pivot column. Finally, a computer implementation is accom⁃plished to test the computational performance of our improvement in comparison with the classical simplex algo⁃rithm. The computational results show that our improved algorithm averagely spends less executive time at each iteration than the classical simplex algorithm.%　　线性规划的规范性算法是从一个初始基出发，通过一种单纯形变式求得可行基的方法。提出了求等式约束方程的初始基的方法，该方法不需要计算辅助目标函数的缩减费用，在约束无冗余的假定下经过至多m(等式个数)次迭代后一定得到一个初始基或者问题无可行基的结论，并对规范型算法进行了简化。为了验证改进的规范型算法的计算性能，通过MATLAB编程在计算机上实现大规模数值试验，结果表明，与经典单纯形算法相比，改进的算法平均每次迭代花费更少的执行时间，因而具有更高的计算效率，且随着问题规模的扩大，其计算优越性更明显。