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

Improvement and Its Computer Implementation of a New Algorithm for Linear Programming

作　　者：高培旺[1] 

机构地区：[1]闽江学院数学系,福建福州350108

出　　处：《常熟理工学院学报》2012年第10期18-22,共5页Journal of Changshu Institute of Technology

基　　金：闽江学院人才引进基金资助课题"线性规划枢轴算法的大规模计算比较分析及改进"(MJ2012001)

摘　　要：线性规划的规范性算法是从一个初始基出发,通过一种单纯形变式求得可行基的方法.提出了求等式约束方程的初始基的方法,该方法不需要计算辅助目标函数的缩减费用,在约束无冗余的假定下经过至多m(等式个数)次迭代后一定得到一个初始基或者问题无可行基的结论,并对规范型算法进行了简化.为了验证改进的规范型算法的计算性能,通过MATLAB编程在计算机上实现大规模数值试验,结果表明,与经典单纯形算法相比,改进的算法平均每次迭代花费更少的执行时间,因而具有更高的计算效率,且随着问题规模的扩大,其计算优越性更明显.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 eosts 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.

关 键 词：线性规划 可行基 单纯形算法 规范型 计算机实现 

分 类 号：O221.1[理学—运筹学与控制论]