求解线性规划的极大熵方法  

A MAXIMUM ENTROPY METHOD FOR LINEAR PROGRAMMING

作　　者：唐焕文[1] 张立卫[1] 

机构地区：[1]大连理工大学应用数学系

出　　处：《计算数学》1995年第2期160-172,共13页Mathematica Numerica Sinica

基　　金：国家自然科学基金资助项目

摘　　要：极大熵方法是求解多约束非线性规划和极大极小问题的一种有效的方法.用它来求解多约束优化问题,一种途径是将多约束用单约束近似,再用增广Lagrange乘子法求解近似问题;另一种途径是用极大熵方法构造精确罚函数的近似.无论是哪一种途径都需要估计乘子的上界.能否构造不引入乘子估计的算法是很有意义的.Karmarkar算法是求解线性规划的一种有效的多项式内点方法.这种方法在每一次迭代时都要作变换,在像空间用内切球近似单纯形的近似问题得到像空间的新的近似解,再作逆变换求得原空间的新的近似解.An ε-optimal solution to a linear programming problem in Karmarkar standard form is given by reducing its dual problem to a differentiable strictly convex programming via the maximum entropy principle. A perturbation solution of the original linear programming can be achieved by solving this convex programming. Moreover, an algorithm for finding an ε-optimal solution is proposed and the algorithm is proved to be convergent as ε tends to zero. Numerical examples are given to show the high efficiency of the algorithm.

关 键 词：线性规划 极大熵法 最优解 

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