退化线性规划的一个新的改进的单纯形方法  

A NEW REVISED SIMPLEX METHOD FOR DEGENERATE LINEAR PROGRAMS

作　　者：赵海峰[1] 刘新为[1] 

机构地区：[1]河北工业大学理学院,天津300401

出　　处：《数值计算与计算机应用》2012年第2期109-120,共12页Journal on Numerical Methods and Computer Applications

基　　金：国家自然科学基金(10971047);河北省自然科学基金(A2010000011)

摘　　要：本文讨论退化线性规划单纯形方法最优解的判定准则和有限主元规则.首先改进简约价值系数向量,提出线性规划单纯形方法最优解的判定准则.并且利用本文的判定准则给出[3]中定理2.3.5(P.84)的一个新的证明.然后提出一种新的混合有限主元规则,在退化情形下通过对单纯形表使用新的混合有限主元规则进行迭代,可以判断当前退化基本可行解或为最优解或给出下次迭代的主元并且跳出循环.最后给出在一组经典的退化线性规划例子下,改进的单纯形方法好的计算表现.We consider optimality criterion and finite pivoting rule of the simplex method for degenerate linear programs （LP）. First, improving the reduced cost vector, we present a optimality criterion of the simplex method for LP. Moreover, we give a new proof of theorem 2.3.5 （page 84） in [3] with our optimality criterion. Then a new hybrid finite pivoting rule is proposed either to obtain a optimal basic solution for LP or to choice the pivot of the next iteration in the tableau under the degeneracy. Based on this new hybrid finite pivoting rule, cycling is avoided. In addition, we report on computing performance with this procedure which is promising via some classical degenerate LP problems in the literature.

关 键 词：线性规划 单纯形方法 退化问题 简约价值系数向量 最优解 有限主元规则 

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