对偶线性规划
极大化的变量与极小化的约束条件之间有一个对应,其它都是取反号即可.
弱对偶性定理
定理 极小化线性规划的目标函数值大于等于其对偶目标线性规划的目标函数值
证明: 设该线性规划为 $$\begin{array}{ll}\min & C^T X\\ \text{s.t.}&A X= B\\ &X\ge 0\end{array}$$ 则其对偶线性规划为 $$\begin{array}{ll}\max & B^T Y\\ \text{s.t.}&A^T Y\le C\\ &Y\ \text{无约束}\end{array}$$ 容易得知 $$B^T Y = X^T A^T Y \le X^T C$$ 即得
强对偶性定理
定理 若原始线性规划与对偶线性规划中有一个有最优解, 则两个线性规划都有最优解, 且它们的目标函数最优值相同.
证明:
对偶线性规划解的情况
两个互为对偶的线性规划的解的情况
- 两个都有可行解$\iff$两个都有最优解,最优值相等$\iff$一个有最优解
- 两个都无可行解
- 一个有可行解,无最优解(目标函数无界),则另一个无可行解
