§3对偶问题的基本性质 性质2弱对偶原理（弱对偶性）：设X和Y分别是问题(P)和 (D)的可行解，则必有 CX°≤Yb即： 推论1：原问题任一可行解的目标函数值是其对偶问题目标函数值 的下届；反之，对偶问题任意可行解的目标函数值是其原问题目 标函数值的上界。 推论2：在一对对偶问题(P)和(D)中，若其中一个问题可行但 目标函数无界，则另一个问题无可行解；反之不成立。这也是对 偶问题的无界性。 2014-12-15
2014-12-15 16 §3 对偶问题的基本性质 性质2 弱对偶原理(弱对偶性)：设 和 分别是问题(P)和 (D)的可行解，则必有 0 X 0 Y n j m i j j i bi CX Y b c x y 1 1 0 0 即 ： 推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值 的下届；反之，对偶问题任意可行解的目标函数值是其原问题目 标函数值的上界。 推论2: 在一对对偶问题（P）和（D）中，若其中一个问题可行但 目标函数无界，则另一个问题无可行解；反之不成立。这也是对 偶问题的无界性
证明： max CY minW=Yb AX≤b← YA≥C s.t. X≥0 Y≥0 CX0≤yAX0≤Yb 2014-12-15 17
证明： 2014-12-15 17 max Z CX 0 . . X AX b st minW Yb 0 . . Y YA C st CX Y AX Y b 0 0 0 0
§3对偶问题的基本性质 推论3：在一对对偶问题(P)和(D)中，若一个可行（如 P),而另一个不可行（如D),则该可行的问题目标函 数值无界。 性质3最优性定理：如果X是原问题的可行解，Y是其对偶 问题的可行解，并且： CX=YB 即：z=w 则X是原问题的最优解，Y是其对偶问题的最优解。 2014-12-15 18
2014-12-15 18 §3 对偶问题的基本性质 推论3：在一对对偶问题（P）和（D）中，若一个可行（如 P），而另一个不可行（如D），则该可行的问题目标函 数值无界。 性质3 最优性定理：如果 是原问题的可行解， 是其对偶 问题的可行解，并且: 0 X 0 Y : z w CX 0 Y 0 B 即 ＝ 则 X 0 是原问题的最优解， Y 0 是其对偶问题的最优解
证明： 由弱对偶性可知，对任意可行解有 CX≤B 因此，对于X和y也将分别有： CX≤B CX≤YOB 又因为 CXo=YB 故有 YOB≤YB CX≤Cr0 则X是原问题的最优解，Y是其对偶问题的最优解。 2014-12-15 19
证明： 由弱对偶性可知，对任意可行解有 因此，对于 和 也将分别有： 又因为 故有 2014-12-15 19 CX YB 0 X 0 Y CX YB 0 CX Y B 0 CX Y B 0 0 Y B YB 0 0 CX CX 则 X 0 是原问题的最优解， Y 0 是其对偶问题的最优解
§3对偶问题的基本性质 性质4强对偶性：若原问题具有最优解，则其对偶问题也具 有最优解，且它们最优解的目标函数值相等。 2014-12-15 20
2014-12-15 20 §3 对偶问题的基本性质 性质4 强对偶性：若原问题具有最优解，则其对偶问题也具 有最优解，且它们最优解的目标函数值相等