【运筹学】对偶理论 : 总结 ( 对偶理论 | 原问题与对偶问题对应关系 | 对偶理论的相关结论 ) ★★★

大家好，欢迎来到IT知识分享网。

一、对偶理论

1、对称性定理

对称性定理 :

• 原问题 ( $LP$ ) 的 对偶 是 对偶问题 ( $DP$ )
• 对偶问题 ( $DP$ ) 的 对偶 是 原问题 ( $LP$ )

原问题 和 对偶问题 互为对偶 ;

对偶问题是对称的

原问题 $LP$ :

$$\begin{array}{l}maxZ=CX\\ \\ s.t\{\begin{array}{l}AX\le b\\ \\ X\ge 0\end{array}\end{array}$$

对偶问题 $DP$ :

$$\begin{array}{l}minW=b^{T}Y\\ \\ s.t\{\begin{array}{l}{A}^{T}Y\ge C^T\\ \\ Y\ge 0\end{array}\end{array}$$

2、弱对偶定理

弱对偶定理 :

假设 ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 问题 $(\mathrm{P})$ ( 目标函数求最大值 ) 和 问题 $(\mathrm{D})$ ( 目标函数求最小值 ) 的 可行解 , 则必有 $\mathrm{C}{\mathrm{X}}^0\le {\mathrm{Y}}^0\mathrm{b}$ ,

展开后为 ${\sum }_{\mathrm{j}=1}^{\mathrm{n}}{\mathrm{c}}_{\mathrm{j}}{\mathrm{x}}_{\mathrm{j}}\le {\sum }_{\mathrm{i}=1}^{\mathrm{m}}{\mathrm{y}}_{\mathrm{i}}{\mathrm{b}}_{\mathrm{i}}$

弱对偶定理推论 1 :

原问题 任何一个 可行解 的目标函数值 , 都是其对偶问题 目标函数值的下界 ;

反之 ,

对偶问题 任何一个 可行解 的目标函数值 , 都是其原问题 目标函数的上界 ;

弱对偶定理推论 2 : ( 对偶问题的无界性 )

在一对 对偶问题 $(\mathrm{P})$ 和 $(\mathrm{D})$ 中 ,

如果其中 一个线性规划问题可行 , 但是 目标函数无界 , 则 另外一个问题没有可行解 ;

如果其中 一个线性规划问题不可行 , 其 对偶问题不一定不可行 ;

弱对偶定理推论 3 :

在一对 对偶问题 $(\mathrm{P})$ 和 $(\mathrm{D})$ 中 ,

如果其中 一个线性规划问题可行 , 而 另一个线性规划问题不可行 , 则 该可行问题的目标函数是无界的;

3、最优性定理

最优性定理 :

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

并且 两个可行解对应的目标函数值相等 , 即 $\mathrm{C}{\mathrm{X}}^0=\mathrm{B}{\mathrm{Y}}^0$ , 即 $\mathrm{z}=\mathrm{w}$ ,

则 ${\mathrm{X}}^0$ 是原问题的最优解 , ${\mathrm{Y}}^0$ 是对偶问题的最优解 ;

4、强对偶性

强对偶性 : 如果 原问题 与 对偶问题 都有可行解 , 只要有一个问题有最优解 , 则 两个问题都有最优解 , 二者的最优解的目标函数值相等 ;

5、互补松弛定理

${\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}}$ 是 松弛变量 或 剩余变量 ;

互补松弛定理简写 :

” ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 最优解 ” $\iff$ $\{\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}}$ 是 松弛变量 或 剩余变量 ;

二、原问题与对偶问题对应关系

原问题与对偶问题对应关系 :

如果 原问题 有最优解 , 对偶问题也 有最优解 ;

如果 原问题 有 无界解 , 对偶问题 无可行解 ;

如果 原问题 无可行解 , 对偶问题 无法判断 ;

上述是根据弱对偶定理总结的 ;

二、对偶理论的相关结论

1、对偶问题存在

任何 线性规划问题 , 都有一个对应的 对偶线性规划问题 ;

2、对偶问题转化

原问题 $\mathrm{P}$ : $\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}$ ;              \ \ \ \ \ \ \ \ \ \ \,            对偶问题 $\mathrm{D}$ : $\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}$

原问题与对偶问题对应关系 :

原问题第 $i$ 个约束条件是 $\le$ 约束 , 其对偶问题的第 $i$ 个变量的符号不确定 , 可能大于等于 $0$ , 也可能小于等于 $0$ ;

查看 约束变量的符号 与 其另外一个对偶问题的 约束方程的符号 一致性 , 来确定对偶问题的约束方程符号 ;

约束方程符号 :

如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 $\ge$ , 因此 对偶问题的约束方程符号 与 原问题变量 符号一致 ;

如果当前线性规划问题 目标函数是求最小值 , 原问题就是下面的问题 , 其对偶问题 ( 上面的 ) 的约束方程符号是 $\le$ , 因此 对偶问题的约束方程符号 与 原问题变量 符号相反 ;

变量符号 :

如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 $\ge$ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号相反 ;

如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 $\ge$ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号一致 ;

3、对偶问题的解

① 互为对偶的两个问题 , 或者同时都有最优解 , 或者同时都没有最优解 ;

② 对偶问题 有可行解 , 原问题 不一定有可行解 , 因为对偶问题的可行解可能是 无界解 , 原问题可能 无可行解 ;

③ 原问题有 多重解 , 对偶问题 可能有多重解 , 也 可能有唯一解 ; 多重解是 有无穷多最优解 ;

④ 对偶问题 有可行解 , 原问题 无可行解 , 则对偶问题 有无界解 ; 一对问题中 , 一个有可行解 , 一个无可行解 , 则有可行解的是无界解 ;

⑤ 原问题 没有最优解 , 对偶问题无法判断 ; 没有最优解有两种情况 , 一种是 无界解 , 一种是 无可行解 ; 如果原问题有无界解 , 则对偶问题无可行解 ; 如果原问题无可行解 , 则对偶问题无可行解 ;

⑥ 如果对偶问题没有可行解 , 对偶问题无法判断 , 无界解 或 无可行解 两种情况都有可能 ;

⑦ 如果原问题与对偶问题 都有可行解 , 则 都有最优解 ;

如果 原问题 有最优解 , 对偶问题也 有最优解 ;

如果 原问题 有 无界解 , 对偶问题 无可行解 ;

如果 原问题 无可行解 , 对偶问题 无法判断 ;

4、互补松弛定理

如果 ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是原问题与对偶问题的最优解 , 则 ${\mathrm{Y}}^0{\mathrm{X}}_{\mathrm{s}}={\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=0$ ;

” ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 最优解 ” $\iff$ $\{\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}}$ 是 松弛变量 或 剩余变量 ;