应用同伦法求解原有-对偶线性规划问题  

An Application of Homotopy Method to Solving Primal-Dual Linear Programming Problems

作　　者：高培旺[1] 贺伟奇[1] 

机构地区：[1]中南大学铁道校区数学科学与计算技术学院,湖南长沙410075

出　　处：《系统工程》2004年第1期29-32,共4页Systems Engineering

摘　　要：根据线性规划对偶理论中的互补松弛性质,直接构造线性对偶问题的一个同伦模型,并提出相应的同伦算法求解。如果最优解存在,迭代过程常常是收敛的。尤其是在求解过程中,随着参数取值接近1,可获得原有问题的一个近似最优解。Based on the complementary relaxation property of dual linear programming theory, this paper directly constructs a homotopy model associated with dual linear programming problems to solve. The algorithm presented always converges if an optimal solution exists. Especially, In the computational process an optimal approximation would be obtained with the parameter approaching 1.

关 键 词：同伦法 原有-对偶线性规划 互补松弛性质 近似最优解 单纯形法 

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