一、弱对偶性质

---

弱对偶定理 :

假设 ${\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}}$

二、弱对偶定理分析

---

弱对偶定理分析 :

问题 $(\mathrm{P})$ 与 问题 $(\mathrm{D})$ 互为对偶 , 其中

问题 $(\mathrm{P})$ 是 原问题 , 目标函数求 最大值 ,

问题 $(\mathrm{D})$ 是 对偶问题 , 目标函数求 最小值 ;

$\mathrm{C}{\mathrm{X}}^0$ 是 原问题 $(\mathrm{P})$ 目标函数 代入 ${\mathrm{X}}^0$ 可行解之后的值 ; 计算出一个具体的数值 ;

${\mathrm{Y}}^0\mathrm{b}$ 是 对偶问题 $(\mathrm{D})$ 目标函数 代入 ${\mathrm{Y}}^0$ 可行解之后的值 ; 计算出一个具体的数值 ;

只要互为对偶的两个问题都有可行解 , 目标函数求最大值的 $\mathrm{C}{\mathrm{X}}^0$ 值 ( 原问题 ) , 一定小于等于 , 目标函数求最小值的 ${\mathrm{Y}}^0\mathrm{b}$ 值 ( 对偶问题 ) ;

如果互为对偶的两个问题都有可行解 , 原问题求最大值 , 对偶问题求最小值 ,

求最大值的原问题一定都 在某个界限值之下 ,

求最小值的对偶问题一定都 在某个界限之上 ,

上述描述中的 界限值是同一个界限值 ;

三、弱对偶定理推论 1

---

弱对偶定理推论 1 :

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

反之 ,

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

问题 $(\mathrm{P})$ 与 问题 $(\mathrm{D})$ 互为对偶 , 其中

问题 $(\mathrm{P})$ 是 原问题 , 目标函数求 最大值 ,

问题 $(\mathrm{D})$ 是 对偶问题 , 目标函数求 最小值 ;

$\mathrm{C}{\mathrm{X}}^0$ 是 原问题 $(\mathrm{P})$ 目标函数 代入 ${\mathrm{X}}^0$ 可行解之后的值 , 该值是其对偶问题目标函数值的下界 ;

${\mathrm{Y}}^0\mathrm{b}$ 是 对偶问题 $(\mathrm{D})$ 目标函数 代入 ${\mathrm{Y}}^0$ 可行解之后的值 , 该值是其原问题目标函数值的上界 ;

四、弱对偶定理推论 2 对偶问题的无界性

---

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

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

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

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

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

如果目标函数求最小值的问题无界 , 则 取值一直可以减小 , 此时不存在一个界限值 ,

因此其对偶问题 一定没有可行解 ;

只要该问题有可行解 , 将可行解代入目标函数 , 即可获得一个 界限值 ;

这个界限值一定是另外对应对偶问题的可行解 ;

如果目标函数求最大值的问题无界 , 则 取值一直可以增大 , 此时不存在一个界限值 ,

因此其对偶问题 一定没有可行解 ;

只要该问题有可行解 , 将可行解代入目标函数 , 即可获得一个 界限值 ;

这个界限值一定是另外对应对偶问题的可行解 ;

一个线性规划是不可行的 , 其对偶问题不一定不可行 ;

一个线性规划不可行 , 其对偶问题可能有如下情况 :

• ① 有最优解 ( 不会成立 ) , 根据最优性定理 , 一个有最优解 , 另一个也有最优解 ;

• ② 无界解

• ③ 无可行解

原问题 与 对偶问题 ,

一个无界 , 另一个肯定不可行 ;

一个不可行 , 另一个不一定可行 , 有两种情况 ① 无界解 ② 无可行解 ;

五、弱对偶定理推论 3

---

弱对偶定理推论 3 :

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

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