③据表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 ( )
又因为A=(,A2…,n)=C-CBA 由A≤0知,C-CBA≤0,从而WA≥C 即W是(DP)的可行解。 又因为,Wb=CBb=CBX=CX”由定理3知W是对偶规划的最优解 2.3对偶单纯形法 2.3.1问题引出 例2.4求解线性规划 max f=-x-3 3x1+2x2≥4 +2x2 x1,x,≥0 解:先把问题标准化: f x3=3 x1+2x2-x4 ≥0(j=12,…,5) 若取x3,x4,x3为基变量,所得基本解X°=(0,00-3-4-1)不是可行解,故它不能 作单纯形法的初始解,为了得到初始可行解,按前章办法引入人工变量x6,x1x3然后 采用两阶段或大M法求解,这样一来,增加了变量的数目。 显然麻烦,眼看一个负的单位阵,但不能作基阵使用,实在遗憾。在这种情况下 能否找到比两阶段法更为简便的方法呢? 也许有的同学们会想到先求其对偶问题 min g=3W,+ 4w,+w 2W1+3H,+W3≤-1 s1W+2W,+2W3≤-3 W1,W2,W3≥0 此对偶问题可用单纯性法求解 但是我们还嫌太麻烦,我们还是希望利用原问题进行迭代求解,这当然不是单纯形 迭代而必须是一种新的迭代方法,这就是对偶单纯形法。 2.2.2方法的基本思想 在本例中,X0=(0,00-3-4-1)虽然不是原问题的可行解,但却是基本解,且对
又因为 1 1 2 ( ,,, ) λ λ λ λm B C C B A− = = " − 1 0 , 0 λ C CB B A− 由 ≤ − 知 ≤ ，从而W A∗ ≥ C 。 即W ∗ 是（D,P）的可行解。 又因为，W ∗ b = CB B−1 b = CB X B ∗ = CX ∗ 由定理 3 知W ∗ 是对偶规划的最优解。 2.3 对偶单纯形法 2.3.1 问题引出 例 2.4 求解线性规划 ≥ + ≥ + ≥ + ≥ ⋅ = − − , 0 2 1 3 2 4 2 3 max 3 1 2 1 2 1 2 1 2 1 2 x x x x x x x x s t f x x 解：先把问题标准化： ≥ = + − = + − = + − = ⋅ = − − 0 ( 1,2, ,5) 2 1 3 2 4 2 3 max 3 1 2 5 1 2 4 1 2 3 1 2 xj j " x x x x x x x x x s t f x x 若取 为基变量，所得基本解 不是可行解，故它不能 作单纯形法的初始解，为了得到初始可行解，按前章办法引入人工变量 ,然后 采用两阶段或大 M 法求解，这样一来，增加了变量的数目。 3 4 5 x , x , x T X (0,0,0, 3, 4, 1) 0 = − − − 6 7 8 x , x , x 显然麻烦，眼看一个负的单位阵，但不能作基阵使用，实在遗憾。在这种情况下， 能否找到比两阶段法更为简便的方法呢？ 也许有的同学们会想到先求其对偶问题。 ≥ + + ≤ − + + ≤ − ⋅ = + + , , 0 2 2 3 2 3 1 min 3 4 1 2 3 1 2 3 1 2 3 1 2 3 W W W W W W W W W s t g W W W 此对偶问题可用单纯性法求解。 但是我们还嫌太麻烦，我们还是希望利用原问题进行迭代求解，这当然不是单纯形 迭代而必须是一种新的迭代方法，这就是对偶单纯形法。 2.2.2 方法的基本思想 在本例中， X 0 = (0,0,0,−3,−4,−1) T 虽然不是原问题的可行解，但却是基本解，且对