例9:设线性规划问题1为Mx=1=CX,Y是其对偶问题的最优解; aX<6 st X≥0 又设线性规划问题2为Max2=CY,其中k是已知常向量。 AX<6+k s. t X≥0 求证:Max,≤Max=1+Yk 证:问题1与问题2的对偶问题分别是 Minw=yb (ii Minw=yb+yk YA≥C YA≥C Y≥0 (Ⅰ)与(I)的约束相同,故(I)的最优解Y是(Ⅱ)的可行解。 由弱对偶性,Mαxx≤Yb+Y‘k,而由解的最优性,Yb=Maxz, 得证
1 2 2 1 9 1 , . . 0 2 , 0 Maxz CX Y AX b s t X Maxz CX k AX b k s.t. X Maxz Maxz Y = = + + 例 ：设线性规划问题 为 是其对偶问题的最优解； 又设线性规划问题 为 其中 是已知常向量。 求证： k 。 = = + 0 . . 0 . . 1 2 Y Y A C s t Y Y A C s t （ ）M inw Y b （ ）M inw Y b Y k 证：问题 与问题 的对偶问题分别是 （）与（）的约束相同，故（）的最优解Y 是（）的可行解。 由弱对偶性，M axz Y b +Y k，而由解的最优性，Y b = M axz， 得证
4对偶定理若(P)有最优解,则(D)也有最优解, 且最优值相同。 Maxz=cx 证:对(P)增加松弛变量Xs,化为 AX+ⅠX=b X.X≥0 O 设其最优基为B,终表为 X B-b B-4 B- C-CBA0-CB-I 其检验数为ja=C-CBAs0 取Y=CB-,则Y满足 O=0-CB-Ⅰ≤0 YA≥C Y≥0 即Y是(D)的可行解,且Yb=CBb 由性质3,Y=Y
4.对偶定理 若（P）有最优解，则（D）也有最优解， 且最优值相同。 证：对（P）增加松弛变量Xs，化为 + = = , 0 . . X X A X I X b s t M axz CX 设其最优基为B，终表为 X X C 0 B A B I 1 1 − − C B b − C C B A 0 C B I − − − − = − = − − − 0 0 0 C B I C C B A 其检验数为 取Y =C B −1 ,则Y 满足 Y 0 Y A C − Y Y b =C B b = z 1 即 是（D）的可行解，且 3 . 由性质 ，Y =Y
可题:(1)由性质4可知,对偶问题最优解的表达式Y*=? B (2)求Y*是否有必要重新求解(D)? 不必。可以从原问题(P)的单纯形终表获得。 例如,在前面的练习中已知Manz=2.5x+x2的终表为 3x1+5x2≤15 st5x1+2x2≤10 x1.x2≥0 X=(2,0,9,0 2.5x12 5 000-0.5 Y=(0,0.5) 请指出其对偶问题的最优解和最优值 5
问题：(1) 由性质4可知，对偶问题最优解的表达式 Y* =？ (2) 求Y*是否有必要重新求解（ D）？ —— CBB -1 —— 不必。可以从原问题（P）的单纯形终表获得。 + + , 0 2 5 . . 1 2 1 2 1 2 x x x x x x s t 5 10 3 15 例如，在前面的练习中已知 Maxz = 2.5x 1 + x 2 的终表为 5 1 0 5 2 1 5 3 1 - 5 19 0 2 9 1 3 x x 2.5 0 0 0 0 - 0.5 X = (2, 0, 9, 0) = 5 z 请指出其对偶问题的最优解和最优值。 5 (0,0.5) = = w Y
5.互补松弛定理 若ⅹ与Y分别是(P)D)的可行解,则X和Y是(P)(D) 最优解的充要条件是YX=FX=0。 证:将(P)D)的约束化为等式:AX+X,=b,YA-Y=C, →因为X、Y是最优解,所以CX=乃b即 (4-Y1)X=Y(AX+)而YX,X≥0, 故只有YX=YX=0 <(自证)
5.互补松弛定理 最优解的充要条件是 。 若 与 分别是 、 的可行解，则 和 是 、 0 (P) (D) ( ) ( ) YX = Y X = X Y X Y P D s s （自证）。 故只有 。 而 因为 、 是最优解，所以 即 证：将 、 的约束化为等式： = = − = + = + = − = 0 ( ) ( ), , 0, , (P) (D) , , YX Y X YA Y I X Y AX IX YX Y X X Y CX Yb A X IX b YA Y I C s s s s s s s s
直观上 原始问题的变量原始问题的松弛变量 X X n n+1 n+m y1…yi m ym+1…ym+i.y ntm 对偶问题的变量对偶问题的松弛变量 Xym=0yxn+=0(i=1,2…m,=1,2, 在一对变量中,其中一个大于0,另一个一定等于0
y1… yi… ym ym+1 … ym+j … yn+m x1 … xj … xn xn+1…xn+i…xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量 xjym+j=0 yixn+i=0 (i=1,2,…,m; j=1,2,…,n) 在一对变量中，其中一个大于0，另一个一定等于0 直观上