一个新的最钝角单纯形算法  

A New Most-Obtuse-Angle Simplex Algorithm for Linear Programming

作　　者：金婷[1] 潘平奇[2] 

机构地区：[1]南京林业大学理学院,江苏南京210037 [2]东南大学数学系,江苏南京210096

出　　处：《淮北煤炭师范学院学报（自然科学版）》2010年第2期14-18,共5页Journal of Huaibei Coal Industry Teachers College(Natural Science edition)

摘　　要：给出了一个新的主元规则.它按最钝角原理给予一组非基本变量较高优先权,先在其中选择进基变量,直到其相应的检验数均满足符号条件;如果此时剩下的检验数均已满足条件,则已达到最优.否则再确定一组新的非基本变量赋予较高优先权,重复上述过程,从对偶问题的角度,该算法可以看成是按最钝角原理进行某种松弛,可望有效地减少迭代次数.This paper offers a new pivot rule.A set of non-basic variables is given priority under the most-obtuse-angle principle.Entering variables are selected within this set,until all reduced costs associated with the set have correct signs.At this moment,reduced costs associated with the remaining non-basis variables are examined.If they all have correct signs,then optimality is achieved.Otherwise,a new set of non-basis variables is determined to have higher priority,and the preceding process is repeated.In view of the dual problem,the proposed algorithm may be regarded as a kind of relaxation approach based on the most-obtuse-angle principle.The algorithm is promising in reduction of the number of iterations.

关 键 词：线性规划 主元标 最钝角原理 单纯形方法 有限规则 

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