一自对偶线性规划问题的性质

首先考虑以下的标准形式的线性规划问题(LP)及其相应的对偶规划(LD):(LP) min c~Tx,s.t.Ax=b,x≥0;(LD) max b~Ty,s.t.A~Ty+s=c,s≥0,其中A∈R~(m×n)(m≤n),c,x,s∈R~n,b,y∈R~m,并且rank(A)=m.以T表示相应于LP和LD中所有可行的x和(y,s)的集合.T~0={(x,y,s):(x,s)>0,(x,y,s)∈T}.由于近年来对线性规划内点方法所进行广泛和深入的研究,人们在理论上对各种不同形式的内点方法的计算复杂性、收敛性质等有较清楚的了解.大量的数值试验表明应用预纠正的原始-对偶内点方法(primal-dual method)是求解实际线性规划问题的最有效的方法之