文章目录

• 对偶性质
• • 弱对偶性
  • 强对偶性
  • 对偶问题解之间的关系
  • 线性规划与其对偶规则的关系
  • 互补松弛定理

对偶性质

弱对偶性

原对偶问题任何可行解的目标值都是另一问题最优目标值的界。（推论：原对
偶问题目标值相等的一对可行解是各自的最优解）

强对偶性

原对偶问题只要有一个有最优解，另一个就有最优解，并且最优目标值相等。

对偶问题解之间的关系

线性规划与其对偶规则的关系

互补松弛定理

​ 原问题 max ⁡ C T X \max C^{T} X maxCTX 对偶问题 min ⁡ b ⃗ T Y \min \vec{b}^{T} Y minb TY
 s.t.  A X ≤ b ⃗  s.t.  A T Y ≥ C X ≥ 0 Y ≥ 0 \begin{array}{lll} \text { s.t. } A X \leq \vec{b} & \text { s.t. } A^{T} Y \geq C \\ X \geq 0 & \quad\quad Y \geq 0 \end{array}  s.t. AX≤b X≥0​ s.t. ATY≥CY≥0​
设 X ^ \hat{X} X^ 和 Y ^ \hat{Y} Y^ 分别是原问题和对偶问题的可行解，则它 们分别是各自问题最优解的充要条件是满足互补松弛定理等式
Y ^ T ( b ⃗ − A X ^ ) = 0 , X ^ T ( A T Y ^ − C ) = 0 \hat{Y}^{T}(\vec{b}-A \hat{X})=0, \hat{X}^{T}\left(A^{T} \hat{Y}-C\right)=0 Y^T(b −AX^)=0,X^T(ATY^−C)=0
含义：如果原问题某个不等式是松的（不等于0）， 则其相应的对偶变量必须是紧的（等于0）， 反之亦然。

本文地址：https://blog.csdn.net/qq_38800089/article/details/110955526