论线性规划的原始—对偶单纯形算法  

A Primai-dual Simplex Algorithm for Linear Programming

作　　者：高培旺[1] 

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

出　　处：《嘉兴学院学报》2013年第3期24-28,共5页Journal of Jiaxing University

基　　金：闽江学院人才引进基金资助课题(MJU201201)

摘　　要：从一个既不是原始可行也不是对偶可行的初始基出发,提出了求解线性规划问题的原始—对偶单纯形算法.首先,将等式约束右手边向量取负值的项置为零,用原始单纯形算法求解相应的线性规划问题,如果存在最优解,则是原问题的一个正则解.在原始单纯形迭代过程中,一旦原问题右手边向量取负值的项转化为非负项,则恢复其原来的约束条件参与迭代计算,可使获得的正则解距原问题的最优解(如果存在)更近.接着,从所获得的正则解出发,用对偶单纯形算法求解原问题,直到获得原问题的最优解或无可行解的结论.最后,为了验证该算法的计算性能,通过MATLAB编程在计算机上进行大规模数值试验,结果表明,与经典单纯形算法相比,该算法在大部分问题上使用更少的迭代次数和执行时间,具有更高的计算效率.Starting from an initial basis with the primal and dual infeasibility,this paper presents a primal- dual simplex algorithm for linear programming. First, the primal simplex algorithm is applied to solve the associated linear programming problem with the negative entries of the right-hand side set equal to zero. If any,the optimal solution is a regular one to the original problem. In the simplex iterative process,once some negative entries of the right--hand side are transformed to take the nonnegative value, the corresponding original constraints are restored in the subsequent iterative computation. So,the regular solution obtained can be on the neighboring of the optimal solution of the original problem （if any）. Next,the dual simplex algorithm is applied to find the solution to the original problem or the conclusion that there is no feasible solution. Finally, a computer implementation is accomplished to test the computational performance of our algorithm comparing to the classical simplex algorithm. The computational results show that our algorithm uses fewer iterations and spends less executive time on most instances than the classical simplex algorithm.

关 键 词：线性规划 初始基 单纯形算法 对偶单纯形算法 计算效率 

分 类 号：O224[理学—运筹学与控制论]