线性规划的最钝角CRISS-CROSS算法  

MOST-OBTUSE-ANGLE CRISS-CROSS ALGORITHMS FOR LINEAR PROGRAMMING

作　　者：颜红彦[1] 潘平奇[2] 

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

出　　处：《高等学校计算数学学报》2009年第4期302-309,共8页Numerical Mathematics A Journal of Chinese Universities

基　　金：国家自然科学基金资助(10371017)

摘　　要：引言考虑如下标准线性规划问题minimize c^Tx(1)subject to Ax=b,x≥0,其中A∈R^(m×n)(m<n),rank(A)=m.传统的原始或对偶单纯形法在求解线性规划问题时通常需要通过一阶段算法获得一个原始或对偶可行解。Zionts＇ （1969） criss-cross algorithm [17] performs primal and dual iterations alternately until obtaining a primal/dual feasible solution, and passes to the primal/dual simplex method to achieve optimality. To improve computational efficiency, a new criss-cross algorithm based on the most-obtuse-angle rule is presented. In computional tests with 25 standard test problems from NETLIB, a code base on a dense implementation of the proposed algorithm outperformed Minos5.51, with the total iteration ration 1.24.

关 键 词：线性规划 最钝角CRISS-CROSS算法 双曲规划 数值试验 

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