§1线性规划的对偶理论 Theorem 3 (对偶定理 poo役x*是(P)问题的最优解，它对应的基矩 阵为B, 引入松弛变量x,=(n+1xt2,…xm+T将 (P)问题化为标准形式。显然，该问题也有最优解 minz=cx+0x、 .t Ax-x、=b x,x,≥0 由最优性判别定理知 o=c.B'(A-I)-(c0)≤0 令w*=CBB-1l 则有(v*A-c-w*)≤0
§1 线性规划的对偶理论 Theorem 3 (对偶定理) proof 设: x*是（P）问题的最优解，它对应的基矩 阵为B，引入松弛变量 xs=(xn+1，xn+2，… ,xn+m) T 将 （P）问题化为标准形式. min 0 . . , 0 s s s z cx x s t Ax Ix b x x = + − = 显然，该问题也有最优解 * * * s x x x = 由最优性判别定理知 ( ) ( ) 1 0 0 B c B A I c − = − − 令 1 *w c BB − = 则有 (w A c w * * 0 − − )
§1线性规划的对偶理论 即w*A≤C 1*≥0 这表明w*=cB是(D) 问题的可行解 对应的目标函数值为： y*三w*b=CgBb 又因为x*是(P)问题的最优解， 其目标函数值为： *=cx*=cpBb 所以有 cx*=CpB-b=w*b 则由Corollary1知(D)问题有最优解，」 且两者的 目标函数的最优值相等。 同理可证，当(D)问题有最优解时，（P)问题也有 最优解，且目标函数相等 证挚毕
§1线性规划的对偶理论 即 w A c w * * 0 这表明 1 *w c BB − = 是（D）问题的可行解 对应的目标函数值为： 1 * * B y w b c B b− = = 又因为 x* 是（P）问题的最优解，其目标函数值为： 1 * * B z cx c B b− = = 所以有 1 * * B cx c B b w b − = = 则由 Corollary 1 知（D）问题有最优解，且两者的 目标函数的最优值相等。 同理可证，当（D）问题有最优解时，（P）问题也有 最优解，且目标函数相等。 证毕
§1线性规的对偶理论 Corollary 5对于对称形式(P)问题，如果有最优解 则在其最优单纯形表中，松弛变量n+1,xm+2…,x+m 的检验数(O+1,O+2,,O+m)的负值即为(D)问题的 一个最优解。 综上所述，(P)问题与（D)问题的解之间只有以 下三种可能的关系： (1)两个问题都有可行解，从而都有最优解，分别 设为X*,w*,则必有z*=Cx*=w*b=y*; (2)一个问题为无界，另一个问题必无可行解； (3)两个问题都无可行解
§1线性规划的对偶理论 Corollary 5 对于对称形式（P）问题，如果有最优解， 则在其最优单纯形表中，松弛变量x n+1 , x n+2 ,…, x n+m 的检验数（ ）的 负值即为（D）问题的 一个最优解。 1 2 , , , n n n m + + + cBs xBs c 0 xs 检验数 cB cN 0 xB xN xs B N -I -cB -cN 0 b b 0 cB cB xB xB I B-1N B-1b 0 cBB-1N -cN -cBB-1 cBB-1b w* = cBB-1 是最优解 此处记录了 B 的逆矩阵 -B -1 综上所述，（P）问题与（D）问题的解之间只有以 下三种可能的关系： （1）两个问题都有可行解，从而都有最优解，分别 设为 x*，w*,则必有 z* = cx* = w*b = y*； （2）一个问题为无界，另一个问题必无可行解； （3）两个问题都无可行解
第四章对偶理论及灵敏度分析 一个规划的某个约束成立严格不等式（约束条件为 松)，对应的对偶规划中变量取0（变量是紧），当 某个变量不为0时（变量是松），对应的对偶规划中 约束成立等式（约束条件是紧）。 proof 因为，w*≥0，Ax*≥b,/由w*Ax*-b)=0,有 wi(∑a,x-b,)F0, i=1,2,…m 由x*≥0，w*A≤c,(C-w*Ax*=0,有 ,y=0, 向前
第四章 对偶理论及灵敏度分析 Theorem 4 (互补松弛定理) 设 x* 和 w* 分别是（P）问题 和（D）问题的可行解，则它们分别是（P）、 （D） 问题的最优解的充要条件是： w* ( Ax*-b ) = 0；(c – w*A) x* = 0 同时成立。 proof 因为，w* ≥ 0 , Ax* ≥ b , 由 w* (Ax* – b ) = 0 ，有 1 ( ) 0, 1,2, n i ij j i j w a x b i m = − = = 由 x* ≥ 0 , w*A ≤ c ， (c– w*A) x* = 0，有 1 ( ) 0, 1,2, , m j ij i j i c a w x j n = − = = 一个规划的某个约束成立严格不等式（约束条件为 松），对应的对偶规划中变量取0（变量是紧），当 某个变量不为0时（变量是松），对应的对偶规划中 约束成立等式（约束条件是紧）。 向前
§1线性规划的对偶理论 Theorem4(互补松弛定理 pro0f:必要性 设x*、w*分别是(P)问题和(D)问题的最优解. 则 Ax*≥b,x*≥0w*A≤C,w*≥0，Cx*=w*b 所以由v*b≤w*Ax*冬cx*,推出Cx*=w*Ax*=m*b, 于是 w*(Ax*-b)=0,(C-1w*A)x*=0 充分性 由1w*(Ax*-b)=0,(C-w*A)x*=0 得 cx*=w*Ax*=w*b 又x*、w分别是(P)问题和(D)问题的可行解， 所以x*、w分别是(P)问题和(D)问题的最优解。 证毕
§1线性规划的对偶理论 Theorem 4 (互补松弛定理) proof : 必要性 设 x*、w*分别是(P)问题和(D)问题的最优解. 则 Ax b x w A c w cx w b * , * 0; * , * 0; * * , = 所以由 w b w Ax cx * * * *, 推出 cx w Ax w b * * * * , = = 于是 w Ax b c w A x *( * ) 0,( * ) * 0 − = − = 充分性 由 w Ax b c w A x *( * ) 0,( * ) * 0 − = − = 得 cx w Ax w b * * * * , = = 又 x*、w* 分别是（P）问题和（D）问题的可行解， 所以 x*、w* 分别是（P）问题和（D）问题的最优解。 证毕