③据表2-5得对偶规划 minG= 5W1+(4)W2-W3 W+2H2-W3≥2 W-W,=1 s{W+3W2+W≥1 ,-W=1 W,H≥0,无非负性要求 定理2若X,W分别为互为对偶规划(I)与(Ⅱ)的可行解,则minG≥maxz 证:因为G=bW≥(AX)W=XAW=X(AW)≥XC=(CX)=CX=所以 minG≥maxz。 定理3若X,W分别为互为对偶规划(I)与(Ⅱ)的可行解,并且CX'=bW, 则X与W·分别为(Ⅰ)与(Ⅱ)的最优解。 因为,由定理2知,对(1)与()的任一可行解X,W都有G≥Z(CX≤bW 所以,特别的对可行解X也有bW≥CX成立。 又因为,CX'=bW,故对任何可行解W都有bW≥CX’=bW”从而由极小值 的最优解的定义知,W是(Ⅱ)的最优解。同理可证,X是规划(Ⅰ)的最优解 定理4对偶问题的对偶是问题 证:设原问题是maxf(X)=CX;AX≤b,X≥0根据对偶问题的标准形式可找到它的 对偶问题minG=bW;AW≥C,W≥0对上式的目标函数两边取负号-minG=-bW 又因为-minG=max(-G),所以max(-G)=-bW,给约束条件两边取负号,得 AW≤-C7,W≥0合起来有线性规划 max(-G)=-b'w AW≤-C W≥0 根据标准形式的对偶关系,上式的对偶问题是 min(-C)=-CX;-AX≥-b;X≥0 又因为min(-G')=-maxW 所以,-maxW=-CX;-AX≥-b,X≥0 即maxf(X)=CX;AX≤b,X≥0即是原问题。 定理5设X为线性规划(Lp)的基本最优解,对应基阵为B,并且其检验数全 部非正,则W=CBB-是对偶规划(Dp)的最优解 证明:由线性代数的知识知(LP)对应于X的典型式为 XB=XR-B-NXN =B-b-BNXN f=f-(CBB-N-CN)XN=f-1rN③据表 2-5 得对偶规划 1 2 3 1 2 3 1 2 1 2 3 1 3 1 3 2 min 5 ( 4) 2 2 1 3 1 1 , 0, G W W W W W W W W s t W W W W W W W W = + − −  + − ≥  − =  ⋅ +  + ≥  − =   ≥ 无非负性要求 定理 2 若 X ,W分别为互为对偶规划（Ⅰ）与（Ⅱ）的可行解，则min G ≥ max z 证：因为G 所以， 。 b W AX W X A W X A W X C CX CX z T T T T T T T T T = ≥ ( ) = = ( ) ≥ = ( ) = = min G ≥ max z 定理 3 若 （Ⅰ）与（Ⅱ）的可行解，并且CX ， 则 X ∗ ,W ∗ 分别为互为对偶规划 ∗ ∗ = b W T ∗ ∗ X 与W 分别为（Ⅰ）与（Ⅱ）的最优解。 因为，由定理 2 知，对（Ⅰ）与（Ⅱ）的任一可行解 X ,W 都有 ， 所以，特别的对可行解 G Z(CX b W ) T ≥ ≤ X ∗ 也有bT W ≥ CX ∗ 成立。 又因为， ，故对任何可行解W 从而由极小值 的最优解的定义知，W 是（Ⅱ）的最优解。同理可证， ∗ ∗ CX = b W T ∗ ,都有 ∗ ∗ b W ≥ CX = b W T T ∗ X 是规划（Ⅰ）的最优解。 定理 4 对偶问题的对偶是问题 证：设原问题是max f (X ) = CX; AX ≤ b; X ≥ 0 W; A W ≥ C ,W ≥ 0 T T max( G), max( G) b W, T − 所以 − = − 0 根据对偶问题的标准形式可找到它的 对偶问题 min 对上式的目标函数两边取负号 又因为 给约束条件两边取负号，得 ，W 合起来有线性规划 G = bT − min G = T −C ≥ G b W T − min = − − A W ≤    ≥ − ≤ − ⋅ − = − 0 max( ) W A W C s t G b W T T T 根据标准形式的对偶关系，上式的对偶问题是 min(−C′) = −CX; − AX ≥ −b; X ≥ 0 又因为min( −G ′) = − max W ′ 所以，− maxW′ = −CX; − AX ≥ −b; X ≥ 0 即max f (X ) = CX; AX ≤ b; X ≥ 0即是原问题。 定理 5 设 ∗ X 为线性规划（L,p）的基本最优解，对应基阵为 B，并且其检验数全 部非正，则W ∗ = CB B−1是对偶规划（D,p）的最优解。 证明：由线性代数的知识知（L,P）对应于 ∗ X 的典型式为 B B N N B N X N X = X − B NX = B b − BNX f = f − C B N − CN X = f − λ ∗ −1 −1 0 −1 0 ( )