线性规划的一个新的多项式算法——Karmarkar方法

假设我们已经知道: (Ⅰ)问题有最优解,且最小值为零 (Ⅱ)x=a,y=g是问题的一个可行解,且满足a>0,g>0定义: 作1,2节中的投影变换: 问题就可化为如下的Karmarkar标准型:求满足是问题的一个可行解。现在,让我们考虑形式稍广些的问题     

线性规划的一个新的多项式算法——Karmarkar方法

本文详细介绍了Karmarkar算法,并论述了算法的适应性。对Karmarkar文章中个别说得不够清楚的地方,本文已进行了补充和修正。     

线性规划的一个新的多项式算法——Karmarkar方法(续)

四、基本定理的证明为了需要,先证明下面有关对数函数的三个分析性质。性质11 若y_j≥0(j=1,2,…,n),则有证明所有性质证明利用中值定理,可得：性质13证明因此有取,应有性质12,可得：因为故有下面开始证明基本定理。