文档介绍：§,当把单纯形法应用于下列LP问题时,(1979)LP与严格线性不等式组的关系以下都假定A、b、c均为整数(1)Proof:Th.:存在求解LP问题的多项式时间算法的充分必要条件是存在求解形如的线性不等式组的多项式时间算法。令,写出与(1)有关的LP:行向量c可任意给定,如取c=0(2)若有多项式时间的LP算法,则可判定:问题(2)不可行→这时不等式组(1)(2)的最优解或判定(2)无界→这时必可得(1)的一个解在多项式时间内求解了问题(1)反之,若有一多项式时间方法求解闭(弱)的线性不等式组(1)考虑问题(2)的对偶:对偶Th求解问题(2)可归结为求解关于变量的下述弱不等式组否则,再考虑另一个弱不等式组:若它有解→则问题(2)无界否则→问题(2)不可行总之,最多求解两个弱不等式组就完全解决了LP问题(2)从而得到求解LP问题的一个多项式时间算法若该联立不等式组有解则为问题(2)的最优解,为其对偶最优解.(1)与严格(强)线性不等式组的关系:(3)令则由线代行列式理论易证设,且(否则LP问题很容易求解)引理:设B是矩阵的任一子方阵,则记为A的第i个行向量,.代替(3),考察不等式组其中令显然,x为弱不等式组(1)的解引理:对中任一点,必定存在一个,使得::若有一个求解严格线性不等式组的多项式时间算法,.:弱不等式组(1)可行严格不等式组(3)可行