如果x,，y,i=l..,m,j=l...n分3、最优性别是原问题和对偶问题的可行解，且有Zc,=Zbji-1则又,，，i=l..,m，j=1...n分别是原问题和对偶问题的最优解。设x"j, yi, i=l..m, j=l..n证明分别是原问题和对偶问题的最优解,n则由弱对偶性mZea, sZexsbyiZbyj-1i=1i=1j-1Zc,,=bj又1=，所以Eet-Eex-Zbyi-bii=1-2025/4/517
2025/4/5 17 3、最优性 如果 分 别是原问题和对偶问题的可行解，且有 则 分别是原问题和对偶问题的 最优解。 ˆ , j x y ˆ i , i =1,.,m, j =1,.n = = = m i i i n j j j c x b y 1 1 ˆ ˆ ˆ , j x y ˆ i , i =1,.,m, j =1,.n 证明 设 分别是原问题 和 对偶问题的最优解，则由弱对偶性， 又 ，所以 x j , y i , i =1,.,m, j =1,.n = = = = m i i i m i i i n j j j n j j j c x c x b y b y 1 1 1 1 ˆ ˆ = = = m i i i n j j j c x b y 1 1 ˆ ˆ = = = = = = = m i i i m i i i n j j j n j j j c x c x b y b y 1 1 1 1 ˆ ˆ
4、强对偶性如果原问题有最优解，则其对偶问题也必有最优解，且两者最优目标函数值相等，即 max z = min w证明设有线性规划问题max Z =CX: AX +X. =b: X,X. ≥0经单纯形法计算后，令Y=C,B-1 >O,最终表中基可行解基变量非基变量B-1b'N"19,→O=Cβ-C,B"'BOn =CN-CβB-'N-Y=-C,B"YA≥C,即:所以 =C-YA≤OCX = C,B-"b = Yb,由此可知是对偶问题的可行解，又Y就是最优解。2025/4/518
2025/4/5 18 4、强对偶性 如果原问题有最优解，则其对偶问题也必有最优解， 且两者最优目标函数值相等，即 max z = min w 。 证明 设有线性规划问题 经单纯形法计算后，令 ， 最终表中 所以 ,即： 由此可知 是对偶问题的可行解，又 ， 就是最优解。 max Z = CX; AX + Xs = b; X, Xs 0 基可行解 基变量 非基变量 0 1 = − Y CB B b −1 I N B j → N CN CB B N −1 = − −1 C C B B −Y = −CB B B B 1 0 − = − =C−YA 0 YAC Y CX = CB B b = Yb −1 Y
5、互补松弛性：在线性规划的最优解中，如果对应某一约束条件的对偶变量值非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对偶变量一定为零。即若,>0,则ajx,=b;若ajx,<b，则,=0.j=1证明由弱对偶性知：e,abi=1==1=又因在最优解中c,,=b，，于是上式应为等式，即有Yj=1i=1Zza,->-b=(a,-b),=0i=1i=l j=li=l j=l2025/4/519
2025/4/5 19 5、互补松弛性：在线性规划的最优解中，如果对应某一约束条件的 对偶变量值非零，则该约束条件取严格等式；反之，如果约束条件取 严格不等式，则其对偶变量一定为零。即 若 ˆ 0, ; 若 1 i n j yi aijxj = b = 则 , ˆ 0. 1 = = i i n j ij j a x b 则y 证明 由弱对偶性知： 又因在最优解中 ，于是上式应为等式，即有 = = = = m i i i m i j i n j i j n j j j c x a x y b y 1 1 1 1 ˆ ˆ ˆ ˆ = = = m i i i n j j j c x b y 1 1 ˆ ˆ ˆ ˆ ˆ ( ˆ ) ˆ 0 1 1 1 1 1 − = − = = = = = = i m i j i n j i j m i i i m i j i n j i j a x y b y a x b y
而 aj,-b,≤0;J>0，故要使得上式成立，必有j=1Zab. = 0:=b即j=1j=1后半部分是前一命体的逆否命题，自然成立。X.Y,=0互补松驰性还可写为Y·X、=0 ;对偶问题的相应的互补松弛性见书P58。例书P76，习题2-42025/4/520
2025/4/5 20 ˆ 0; 1 − = = j i n j aijx b 而 ，故要使得上式成立，必有 即 ˆ 0; 1 − = j i n j aijx b ˆ 0 i y ˆ . 1 j i n j aijx = b = 后半部分是前一命体的逆否命题，自然成立。 互补松弛性还可写为 对偶问题的相应的互补松弛性见书P58。 例 书P76 ，习题2-4 0 ; ˆ = XS Y 0 ˆ =S X Y