一种新的线性规划多项式时间算法  

A NEW POLYNOMIAL-TIME ALGORITHM FOR LP

作　　者：张青富 肖高奚 陈开周 

机构地区：[1]西安电子科技大学数学系

出　　处：《应用数学学报》1996年第1期33-38,共6页Acta Mathematicae Applicatae Sinica

摘　　要：本文给出了一种新的线性规划多项式时间算法．在此算法中，每步可沿一族方向中的一个进行线性搜索，同时，还使用了开关策略，从而大大减少了求逆矩阵的次数，最后，证明了算法经Ｏ（ｎＬ）次选代结束．in this paper, we present a new polynomial-time algorithm for linear programming, which has a family of feasible directions at each iteration step. Meanwhile, the switchstrategy is used. By all these means, it is possible to reduce the amount of inverse matrix calculations greatly. Finally, it is proved that the algorithm can be stopped in O(nL)iterations.

关 键 词：线性规划 KARMARKAR算法 多项式时间算法 

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