Fresh views on some recent developments in the simplex algorithm  

关于单纯形算法若干进展的新见解(英文)

作　　者：胡剑峰[1] 潘平奇[1] 

机构地区：[1]东南大学数学系,南京210096

出　　处：《Journal of Southeast University(English Edition)》2008年第1期124-126,共3页东南大学学报（英文版）

基　　金：The National Natural Science Foundation of China(No.10371017).

摘　　要：First, the main procedures and the distinctive features of the most-obtuse-angle（MOA）row or column pivot rules are introduced for achieving primal or dual feasibility in linear programming. Then, two special auxiliary problems are constructed to prove that each of the rules can be actually considered as a simplex approach for solving the corresponding auxiliary problem. In addition, the nested pricing rule is also reviewed and its geometric interpretation is offered based on the heuristic characterization of an optimal solution.首先回顾了采用最钝角行、列主元规则求解线性规画问题的原始、对偶可行解的主要过程,阐述了其与众不同的特性.然后构造了2个特殊的辅助问题,并证明了最钝角行、列主元规则的过程实际上分别等价于采用原始、对偶单纯形算法求解相应的辅助问题.此外,还对嵌套的pricing规则进行了回顾,并基于最优解的启发式特征刻画给出了该规则的一个几何解释.

关 键 词：linear programming simplex algorithm PIVOT mostobtuse-angle nested pricing large-scale problem 

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