对偶问题的基本性质
写于：2024年1月3日晚
修改于：
原规划与对偶规划
| 原规划 | 对偶规划 |
|---|---|
| max z = C T X s.t. { A X ≤ b , 其中 X ( m ∗ 1 ) X ≥ 0 \begin{aligned} & \max \mathrm{z}=\mathbf{C}^T \mathbf{X} \\ & \text { s.t. }\left\{\begin{array}{l}\mathbf{A X} \leq \mathbf{b}, \quad \text { 其中 } \mathrm{X}_{\left(\mathrm{m}^* 1\right)} \\ \mathbf{X} \geq \mathbf{0}\end{array}\right.\end{aligned} maxz=CTX s.t. {AX≤b, 其中 X(m∗1)X≥0 | min w = Y b s.t. { Y A ≥ C T , 其中 Y ( 1 ∗ n ) Y ≥ 0 \begin{aligned} & \min w=\mathbf{Y b} \\ & \text { s.t. }\left\{\begin{array}{l}\mathbf{Y A} \geq \mathbf{C}^T, \text { 其中 } \mathrm{Y}_{\left(1^* \mathrm{n}\right)} \\ \mathbf{Y} \geq 0\end{array}\right.\end{aligned} minw=Yb s.t. {YA≥CT, 其中 Y(1∗n)Y≥0 |
| max z = ∑ j = 1 n c j x j s.t. { ∑ j = 1 n a i j x j ≤ b i ( i = 1 , 2 , … , m ) x j ≥ 0 ( j = 1 , 2 , … , n ) \begin{aligned} & \max \mathrm{z}=\sum_{j=1}^n c_j x_j \\ & \text { s.t. }\left\{\begin{array}{l}\sum_{j=1}^n a_{i j} x_j \leq b_i(i=1,2, \ldots, m) \\ x_j \geq 0(j=1,2, \ldots, n)\end{array}\right.\end{aligned} maxz=j=1∑ncjxj s.t. {∑j=1naijxj≤bi(i=1,2,…,m)xj≥0(j=1,2,…,n) | min w = ∑ i = 1 m b i y i s.t. { ∑ i = 1 m a i j y i ≥ c j ( j = 1 , 2 , … , n ) y i ≥ 0 ( i = 1 , 2 , … , m ) \begin{aligned} & \min w=\sum_{i=1}^m b_i y_i \\ & \text { s.t. }\left\{\begin{array}{l}\sum_{i=1}^m a_{i j} y_i \geq c_j(j=1,2, \ldots, n) \\ y_i \geq 0(i=1,2, \ldots, m)\end{array}\right.\end{aligned} minw=i=1∑mbiyi s.t. {∑i=1maijyi≥cj(j=1,2,…,n)yi≥0(i=1,2,…,m) |
对称性：对偶问题的对偶问题是原问题。任何一个线性规划问题存在且有唯一的对偶问题。
弱对偶性：若 X ‾ \overline{\mathbf{X}} X 是原问题的可行解， Y ‾ \overline{\mathbf{Y}} Y 是对偶问题的可行解，则存在 C X ‾ ⩽ Y ‾ b \mathbf{C} \overline{\mathbf{X}} \leqslant \overline{\mathbf{Y}} \mathbf{b} CX⩽Yb。
原问题最优目标函数值是对偶目标函数值的下界，对偶问题最优目标函数值是原问题目标函数值的上界。
坐标轴理解: 坐标轴自左向右逐渐增大。如果原问题和对偶问题都有可行解 X ‾ 、 Y ‾ \overline{\mathbf{X}} 、 \overline{\mathbf{Y}} X、Y，那么说明原问题和对偶问题都存在某个可行解对应的函数值，而因为原问题为 max \max max 类型，则更优解会在 Z ∗ \mathrm{Z}^* Z∗ 右侧，而对偶问题为 m i n \mathrm{min} min 类型，更优解会在 W ∗ \mathrm{W}^* W∗ 左侧，两者一定会在某一处取得相同的最优目标函数值，因此存在 C X ‾ ⩽ Y ‾ b \mathbf{C} \overline{\mathbf{X}} \leqslant \overline{\mathbf{Y}} \mathbf{b} CX⩽Yb 。
将原问题和对偶问题看做是两个人在角力，目标函数值视为擂台。原问题自左向右冲，对偶问题自右向左冲，如果问题有可行解，那么就在擂台上，如果有无界解，那么就将对方挤出擂台。
无界性：
-
若原问题/对偶问题有无界解，那么对偶问题/原问题无可行解
如果原问题有无界解，说明原问题最优值随着坐标轴一直向右延伸，对偶问题被挤出擂台，所以对偶问题无可行解。 -
若原问题/对偶问题无可行解，那么对偶问题/原问题无可行解或有无界解
-
若原问题有可行解，而对偶问题无可行解，那么原问题有无界解
-
若对偶问题有可行解，而原问题无可行解，那么对偶问题有无界解
补充：原问题和对偶问题中有一个为无穷多/唯一最优解，无法退出另一个最优解的情况。
最优性：设 X ^ \widehat{\mathbf{X}} X 是原问题的可行解， Y ^ \widehat{\mathbf{Y}} Y 是对偶问题的可行解，当 C X ^ = Y ^ b \mathbf{C} \hat{\mathbf{X}}=\hat{\mathbf{Y}} \mathbf{b} CX^=Y^b 时， X ^ \hat{\mathbf{X}} X^、 Y ^ \hat{\mathbf{Y}} Y^ 是最优解。
对偶定理：
表述1：若原问题和对偶问题都有可行解，则都有最优解，而且最优解的目标函数值相等。
表述2：若原问题有最优解，则对偶问题也有最优解，而且目标函数值相等。
互补松驰定理：线性规划问题的最优解中，如果对应某一约束条件的对偶变量值非零，那么该约束条件取严格等式；反之如果约束条件取严格不等式，那么对应的对偶变量一定为零。也即：
{ y i ∗ ( ∑ j = 1 n a i j x j − b i ) = 0 ( i = 1 , 2 , … , m ) x j ∗ ( ∑ i = 1 m a i j y i − c j ) = 0 ( j = 1 , 2 , … , n ) \left\{\begin{array}{l} y_i *\left(\sum_{j=1}^n a_{i j} x_j-b_i\right)=0(i=1,2, \ldots, m) \\ x_j *\left(\sum_{i=1}^m a_{i j} y_i-c_j\right)=0(j=1,2, \ldots, n) \end{array}\right. {yi∗(∑j=1naijxj−bi)=0(i=1,2,…,m)xj∗(∑i=1maijyi−cj)=0(j=1,2,…,n)
应用：由原/对偶问题最优解求对偶/原问题最优解