《运筹学》课程教学资源（试卷习题）第3章 线性规划的对偶理论

$ 3.2线性规划的对偶理论·考虑下面一对对偶问题Pmax z = CT XD min w= bTYATY≥CAX≤ bs.t.s.t.X≥0Y ≥0A为mXn阶矩阵，A的秩为m。引入松弛变量Xs，得到原规划（P）的标准型为（Pi）

§3.2 线性规划的对偶理论 • 考虑下面一对对偶问题： P max z = CT X D min w = b TY s.t. AX  b s.t. ATY  c X  0 Y  0 A为m×n阶矩阵，A的秩为m。引入松弛变 量Xs，得到原规划（P）的标准型为（P1）

max Z =CTX +OTXsAX+IX_ = b(P,X≥0,Xs ≥01其中0,和I分别为m维的零向量和m维的单位矩阵Xx =记 A=(A,I)C=X则上面的标准型可记为（P2）max z = CTxAx = b(P2 ×≥02

     + = = + s 1 s 1 S T X O ,X O A X I X b C X O X (P1 ) T max Z 其中01和I分别为m维的零向量和m维的单位矩阵。 ( )         =         = = Xs X A A ,I ,C ,X ˆ 0 ˆ ˆ 1 C 记 则上面的标准型可记为（P2）     = = 2 T X O AX b C X ˆ ˆ ˆ max ˆ ˆ (P2 ) Z

设B为一可行基，并记(XBA-(B,N), C-(Cb), x=CnXN)得到模型（P,）的另一表示形式max Z = CfXg +CX,BXg +NX = bXB ≥01,Xμ≥0

设B为一可行基，并记 ( )         =         = = N B N B X X , X C C A B ,N , C ˆ ˆ ˆ 得到模型（P2）的另一表示形式      + = = + X O ,X O B X N X b C X C X B 1 N B N N T B N T max Z B

对偶定理定理3.1(对称性定理)对偶问题的对偶就是原问题。·定理3.2（弱对偶定理）设XY分别是P和D的可行解，则CTX≤bTY。·证：由 P和 D 的约束条件AX<b,ATY≥C,X≥0yZ0 可直接推得 CTX≤YTAX≤YTb=bTY，证毕

对偶定理 •定理 3.1 (对称性定理) 对偶问题的对偶就是原 问题。 •定理 3.2（弱对偶定理）设 X, Y分别是P 和 D 的可行解，则 CTX  b TY。 •证：由 P 和 D 的约束条件AXb, ATYC, X0, y0 可直接推得 CTX  YT AX  YTb =b TY，证毕

推论1（对偶定理）天若X*.Y*分别是（P）和(D）的可行解，则它们分别是（P）和（D)的最优解的充要条件是：CTX*=bTY*。·证由定理3.1可知，对于规划（D）的任一可行解Y，都有bTY≥CTX*=bTY＊，因此Y*是规划（D）的最优解，类似地可证明，X*是规划（P）的最优解

推论1 （对偶定理）若X* , Y*分别是（P）和 （D）的可行解，则它们分别是（P）和（D） 的最优解的充要条件是： CTX* = b TY* 。 •证 由定理3.1可知，对于规划（D）的任一 可行解Y，都有b TY≧ CTX* = b TY* ，因此Y*是 规划（D）的最优解，类似地可证明， X*是 规划（P）的最优解