一种基于核心矩阵的原始对偶算法  

A Primal-Dual Algorithm Based on Kernel Matrix in LP

作　　者：姜波[1] 蓝伯雄[1] 

机构地区：[1]清华大学经济管理学院,北京100084

出　　处：《运筹与管理》2008年第5期1-5,共5页Operations Research and Management Science

摘　　要：本文通过对线性规划问题中的核心矩阵的分析,提出了一种基于核心矩阵的原始对偶算法。该算法以核心矩阵为运算单元,一方面呈现了存储空间小,计算量小的特点;另一方面,该算法采用了一种新的转轴规则的外点算法,在保持原始可行的基础上,不断改善对偶解使其可行。数值实验结果表明该算法在迭代次数、转轴效率和存储空间上都有一定的提高。This paper analyzes the kernel matrix in the linear programming problem and proposes a new revised prime-dual algorithm based on the kernel matrix. Both low memory size and small-scale computation are showed in the new algorithm, on the other hand, a new pivot rule, which is an exterior point method, also makes the new algorithm more efficient. According to the experiment result, this algorithm is efficient in pivot efficiency and memory consuming.

关 键 词：线性规划 核心矩阵 原始对偶算法 

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