对偶性质 Page 16 性质1对称性定理：对偶问题的对偶是原问题 max Z=CX min W=Y b s.t.AX≥b s.t.YA≥C X≥0 Y≤0
对偶性质 Page 16 性质1 对称性定理：对偶问题的对偶是原问题 min W= Y b s.t. YA ≥ C Y ≤ 0 max Z=C X s.t. AX≥b X ≥0
对偶性质 Page 17 性质2弱对偶原理（弱对偶性）：设X和Y分别是问题(P)和 (D)的可行解，则必有 CX≤YbI 即： 2ex,≤2yb 推论：原问题任一可行解的目标函数值是其对偶问题目标函数值 的下届；反之，对偶问题任意可行解的目标函数值是其原问题目 标函数值的上界。 推论2：在一对对偶问题(P)和(D)中，若其中一个问题可行但 目标函数无界，则另一个问题无可行解；反之不成立。这也是对 偶问题的无界性
对偶性质 Page 17 性质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）中，若其中一个问题可行但 目标函数无界，则另一个问题无可行解；反之不成立。这也是对 偶问题的无界性
对偶性质 Page 18 推论3：在一对对偶问题(P)和(D)中，若一个可行（如 P),而另一个不可行（如D),则该可行的问题目标函数 值无界。 性质3最优性定理：如果X是原问题的可行解，Y是其对偶 问题的可行解，并且： CX°=BY°即：z=w 侧X是原问题的最优解，Y是其对偶问题的最优解
对偶性质 Page 18 推论3：在一对对偶问题（P）和（D）中，若一个可行（如 P），而另一个不可行（如D），则该可行的问题目标函数 值无界。 性质3 最优性定理：如果 是原问题的可行解， 是其对偶 问题的可行解，并且: 0 X 0 Y : z w CX 0 = BY 0 即 ＝ 则 X 0 是原问题的最优解， Y 0 是其对偶问题的最优解
对偶性质 Page 19 性质4强对偶性：若原问题及其对偶问题均具有可行解，则 两者均具有最优解，且它们最优解的目标函数值相等。 还可推出另一结论：若(LP)与(DP)都有可行解，则两者 都有最优解，若一个问题无最优解，则另一问题也无最优解。 性质5互补松弛性：设X和Y分别是P问题和D问题的可行 解，则它们分别是最优解的充要条件是： YX,=0 YX°=0 其中：X、Y,为松弛变量
对偶性质 Page 19 性质4 强对偶性：若原问题及其对偶问题均具有可行解，则 两者均具有最优解，且它们最优解的目标函数值相等。 还可推出另一结论：若（LP）与（DP）都有可行解，则两者 都有最优解，若一个问题无最优解，则另一问题也无最优解。 性质5 互补松弛性：设X0和Y0分别是P问题和 D问题 的可行 解，则它们分别是最优解的充要条件是： = = 0 0 0 s s 0 Y X Y X 其中：Xs、Ys为松弛变量
对偶性质 Page 20 性质5的应用： 该性质给出了已知一个问题最优解求另一个问题最优解 的方法，即已知Y*求X*或已知X*求Y* Y*X、=0 Y、X·=0 互补松弛条件 由于变量都非负，要使求和式等于零，则必定每一分量为零， 因而有下列关系： 若Y*0,则X,必为0；若X*0,则Y必为0 利用上述关系，建立对偶问题（或原问题）的约束线性方程组， 方程组的解即为最优解
对偶性质 Page 20 性质5的应用： 该性质给出了已知一个问题最优解求另一个问题最优解 的方法，即已知Y＊求X＊或已知X＊求Y＊ = = 0 0 s s Y X Y X 互补松弛条件 由于变量都非负，要使求和式等于零，则必定每一分量为零， 因而有下列关系： 若Y＊≠0，则Xs必为0；若X＊≠0，则Ys必为0 利用上述关系，建立对偶问题（或原问题）的约束线性方程组， 方程组的解即为最优解