线性规划Karmarkar算法的一种改进算法及其数值检验  

An Improred Karmarkar Algorithm for Linear Programming and Its Numerical Tests

作　　者：徐树荣[1] 姚宏兵 陈有青[1] 

机构地区：[1]中山大学计算机科学系,广州510275

出　　处：《应用数学》1992年第1期14-21,共8页Mathematica Applicata

基　　金：国家自然科学基金;中山大学高等学术研究中心基金

摘　　要：本文给出求解线性规划问题的一种改进的Karmarkar算法IKA.本算法通过施行仿射变换,将已给定的一个可行内点,变成另一空间可行域中所有分量为1的点e,然后从e出发,沿梯度方向进行一维搜索,使问题的目标函数单调下降,并收敛于最优值,因而不需假定目标函数最优值为已知.几个有数百个约束方程和变量的实际算例表明本算法比Karmarkar算法有效.In this paper an improved version of Karmarkar algorithm (IKA) for linear programming and its convergence analysis are given. Numerical examples with several hundred variables and constraint equations show that improved algorithm IKA is superior to Karmarkar algorithm (KA.)

关 键 词：线性规划 投影变换 Karmarkar法 

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