对偶问题的基本性质

写于：2024年1月3日晚

修改于：

---

原规划与对偶规划

原规划	对偶规划
$\begin{array}{rl}& \max \mathrm{z}={\mathbf{C}}^T\mathbf{X}\\ & \text{ s.t. }\{\begin{array}{l}\mathbf{AX}\le \mathbf{b},\text{ 其中 }{\mathrm{X}}_{\left({\mathrm{m}}^{\ast }1\right)}\\ \mathbf{X}\ge 0\end{array}\end{array}$	$\begin{array}{rl}& \min w=\mathbf{Yb}\\ & \text{ s.t. }\{\begin{array}{l}\mathbf{YA}\ge {\mathbf{C}}^T,\text{ 其中 }{\mathrm{Y}}_{\left(1^{\ast }\mathrm{n}\right)}\\ \mathbf{Y}\ge 0\end{array}\end{array}$
$\begin{array}{rl}& \max \mathrm{z}=\sum _{j=1}^n{c}_j{x}_j\\ & \text{ s.t. }\{\begin{array}{l}{\sum }_{j=1}^n{a}_{ij}{x}_j\le b_i(i=1,2,\dots ,m)\\ x_j\ge 0(j=1,2,\dots ,n)\end{array}\end{array}$	$\begin{array}{rl}& \min w=\sum _{i=1}^m{b}_i{y}_i\\ & \text{ s.t. }\{\begin{array}{l}{\sum }_{i=1}^m{a}_{ij}{y}_i\ge c_j(j=1,2,\dots ,n)\\ y_i\ge 0(i=1,2,\dots ,m)\end{array}\end{array}$

对称性：对偶问题的对偶问题是原问题。任何一个线性规划问题存在且有唯一的对偶问题。

弱对偶性：若 $\overline{\mathbf{X}}$ 是原问题的可行解， $\overline{\mathbf{Y}}$ 是对偶问题的可行解，则存在 $\mathbf{C}\overline{\mathbf{X}}⩽\overline{\mathbf{Y}}\mathbf{b}$。

原问题最优目标函数值是对偶目标函数值的下界，对偶问题最优目标函数值是原问题目标函数值的上界。

坐标轴理解: 坐标轴自左向右逐渐增大。如果原问题和对偶问题都有可行解 $\overline{\mathbf{X}}、\overline{\mathbf{Y}}$，那么说明原问题和对偶问题都存在某个可行解对应的函数值，而因为原问题为 $\max$ 类型，则更优解会在 ${\mathrm{Z}}^{\ast }$ 右侧，而对偶问题为 $\min$ 类型，更优解会在 ${\mathrm{W}}^{\ast }$ 左侧，两者一定会在某一处取得相同的最优目标函数值，因此存在 $\mathbf{C}\overline{\mathbf{X}}⩽\overline{\mathbf{Y}}\mathbf{b}$ 。

将原问题和对偶问题看做是两个人在角力，目标函数值视为擂台。原问题自左向右冲，对偶问题自右向左冲，如果问题有可行解，那么就在擂台上，如果有无界解，那么就将对方挤出擂台。

无界性：

1. 若原问题/对偶问题有无界解，那么对偶问题/原问题无可行解
   
   如果原问题有无界解，说明原问题最优值随着坐标轴一直向右延伸，对偶问题被挤出擂台，所以对偶问题无可行解。

2. 若原问题/对偶问题无可行解，那么对偶问题/原问题无可行解或有无界解

3. 若原问题有可行解，而对偶问题无可行解，那么原问题有无界解

4. 若对偶问题有可行解，而原问题无可行解，那么对偶问题有无界解

补充：原问题和对偶问题中有一个为无穷多/唯一最优解，无法退出另一个最优解的情况。

最优性：设 $\hat{\mathbf{X}}$ 是原问题的可行解， $\hat{\mathbf{Y}}$ 是对偶问题的可行解，当 $\mathbf{C}\hat{\mathbf{X}}=\hat{\mathbf{Y}}\mathbf{b}$ 时，$\hat{\mathbf{X}}$、$\hat{\mathbf{Y}}$ 是最优解。
对偶定理：
表述1：若原问题和对偶问题都有可行解，则都有最优解，而且最优解的目标函数值相等。
表述2：若原问题有最优解，则对偶问题也有最优解，而且目标函数值相等。

互补松驰定理：线性规划问题的最优解中，如果对应某一约束条件的对偶变量值非零，那么该约束条件取严格等式；反之如果约束条件取严格不等式，那么对应的对偶变量一定为零。也即：
$$\{\begin{array}{l}{y}_i\ast \left({\sum }_{j=1}^n{a}_{ij}{x}_j-b_i\right)=0(i=1,2,\dots ,m)\\ x_j\ast \left({\sum }_{i=1}^m{a}_{ij}{y}_i-c_j\right)=0(j=1,2,\dots ,n)\end{array}$$

应用：由原/对偶问题最优解求对偶/原问题最优解