一、互补松弛性

---

${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 可行解 ,

这两个解各自都是对应 线性规划问题 的 最优解

的 充要条件是 : $\{\begin{array}{l}{\mathrm{Y}}^0{\mathrm{X}}_{\mathrm{s}}=0\\ \\ {\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=0\end{array}$

其中 ${\mathrm{X}}_{\mathrm{s}},{\mathrm{Y}}_{\mathrm{s}}$ 是 松弛变量 或 剩余变量 ;

二、证明 互补松弛性

---

原问题 :

$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=\mathrm{C}\mathrm{X}\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}\mathrm{A}\mathrm{X}\le \mathrm{b}\\ \\ \mathrm{X}\ge 0\end{array}\end{array}$

对偶问题 :

$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}={\mathrm{b}}^{\mathrm{T}}\mathrm{Y}\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}{\mathrm{A}}^{\mathrm{T}}\mathrm{Y}\ge {\mathrm{C}}^{\mathrm{T}}\\ \\ \mathrm{Y}\ge 0\end{array}\end{array}$

松弛变量 与 剩余变量 :

将原问题的约束方程变为等式 , $\mathrm{A}\mathrm{X}\le \mathrm{b}$ , 添加 松弛变量 , $\mathrm{A}\mathrm{X}+{\mathrm{X}}_{\mathrm{s}}=\mathrm{b}$ ; 其中 ${\mathrm{X}}_{\mathrm{s}}\ge 0$ ;

将对偶问题的约束方程变为等式 , ${\mathrm{A}}^{\mathrm{T}}\mathrm{Y}\ge {\mathrm{C}}^{\mathrm{T}}$ , 减去 剩余变量 , ${\mathrm{A}}^{\mathrm{T}}\mathrm{Y}-{\mathrm{Y}}_{\mathrm{s}}={\mathrm{C}}^{\mathrm{T}}$ ; 其中 ${\mathrm{Y}}_{\mathrm{s}}\ge 0$ ;

代入可行解到约束方程中 :

${\mathrm{X}}^0$ 是原问题的可行解 , ${\mathrm{Y}}^0$ 是对偶问题的可行解 ;

将 ${\mathrm{X}}^0$ 代入到 $\mathrm{A}\mathrm{X}+{\mathrm{X}}_{\mathrm{s}}=\mathrm{b}$ 等式中 , 可以得到 ${\mathrm{X}}_{\mathrm{s}}^0$ 的一个可行解 ,

将 ${\mathrm{Y}}^0$ 代入到 ${\mathrm{A}}^{\mathrm{T}}\mathrm{Y}-{\mathrm{Y}}_{\mathrm{s}}={\mathrm{C}}^{\mathrm{T}}$ 等式中 , 可以得到 ${\mathrm{Y}}_{\mathrm{s}}^0$ 的一个可行解 ;

根据 对偶理论中的 强对偶定理 , 只要 " ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 最优解 "

那么其目标函数就是最大值与最小值的界限值 , 将这两个最优解代入到对应的目标函数中 , 求得的两个值是相等的 ;

将 ${\mathrm{X}}^0$ 代入到 $\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=\mathrm{C}\mathrm{X}$ 目标函数中 , 得到 $\mathrm{C}{\mathrm{X}}^0$ ;

将 ${\mathrm{Y}}^0$ 代入到 $\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}={\mathrm{b}}^{\mathrm{T}}\mathrm{Y}$ 目标函数中 , 得到 ${\mathrm{b}}^{\mathrm{T}}{\mathrm{Y}}^0$ ;

上述两个值相等 :

$$\mathrm{C}{\mathrm{X}}^0={\mathrm{b}}^{\mathrm{T}}{\mathrm{Y}}^0$$

将 $\mathrm{A}\mathrm{X}+{\mathrm{X}}_{\mathrm{s}}=\mathrm{b}$ 和 ${\mathrm{A}}^{\mathrm{T}}\mathrm{Y}-{\mathrm{Y}}_{\mathrm{s}}={\mathrm{C}}^{\mathrm{T}}$ 代入到上述等式中 , 得到 ${\mathrm{Y}}^0{\mathrm{X}}_{\mathrm{s}}=-{\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0$

其中 ${\mathrm{Y}}^0,{\mathrm{X}}_{\mathrm{s}},{\mathrm{Y}}_{\mathrm{s}},{\mathrm{X}}^0$ 都是大于等于 $0$ 的 , 但上述等式 ${\mathrm{Y}}^0{\mathrm{X}}_{\mathrm{s}}=-{\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0$ 中符号相反 , 说明 等号两边的值都是 $0$ ;