内容发布更新时间 : 2024/9/19 20:00:18星期一 下面是文章的全部内容请认真阅读。

1对偶问题的形式 设原线性规划问题为：

maxZ??cixi

i?1n?a11x1?a12x2???a1nxn?b1??a21x1?a22x2???a2nxn?b2? s..t???ax?ax???ax?bmnnm?m11m22??xj?0,j?1,2,?,n则称下面线性规划问题：

minW??biyi

i?1m?a11y1?a21y2???am1ym?c1??a12y1?a22y2???am2ym?c2? s..t???ay?ay???ay?cmnmn?1n12n2??yj?0,j?1,2,?,m为其对偶问题，其中yj(j?1,2,?,m)称为对偶变量。上述对偶问题称为对称型对偶问题。原问题简记为（P），对偶问题简记为（D）。 原问题（P）矩阵形式：

maxZ?cTx

?Ax?bs..t? ?xi?0,i?1,2,?,n对偶问题（D）矩阵形式：

maxW?bTy

T??Ay?cs..t? ??yj?0,j?1,2,?,m2对偶关系对应表

形式 目标函数类型 目标函数系与右边项系数

右边项系数 变量数n

变量数与约束数

约束数m ≥0

原问题变量类型与对偶问题约束类型

≤0 无限制 ≥0

原问题约束类型与对偶问题变量类型

≤0 =

2对偶问题的基本性质

定理1：对偶问题的对偶就是原问题；

定理2 （弱对偶定理）：若x?，y?分别为（P），（D）的可行解，则有

cTx??y?Tb；

原问题 max

对偶问题 min

目标函数系数 右边项系数

目标函系数 约束数n 变量数m ≥0 ≤0 = ≥0 ≤0 无限制

推论1：若（P），（D）都有可行解，则（P），（D）必定都有最优解。 推论2：若（P）有可行解，但无有限最优解，则（D）无可行解。 定理3：若x?，y?分别为（P），（D）的可行解，且有cTx?=y?Tb，则x?，，（D）的最优解； y?分别为（P）

定理4（主对偶定理）：若（P），（D）都有可行解，则（P），（D）必

定都有最优解，且目标函数的最优值必定相等；

推论：若（P），（D）中任意一个有最优解，则（P），（D）必定都有最优解，且目标函数的最优值必定相等。

定理5：若x?，y?分别为（P），（D）的可行解，则x?，y?分别为（P），

?T???y(b?Ax)?0（D）的最优解的充要条件是?T?T?同时成立。

??(Ay?c)x=0