【运筹学】对偶理论 : 总结 ( 对偶理论 | 原问题与对偶问题对应关系 | 对偶理论的相关结论 ) ★★★
文章目录
一、对偶理论
1、对称性定理
对称性定理 :
- 原问题 (
) 的 对偶 是 对偶问题 (
)
- 对偶问题 (
) 的 对偶 是 原问题 (
)
原问题 和 对偶问题 互为对偶 ;
对偶问题是对称的
原问题
:
对偶问题
:
2、弱对偶定理
弱对偶定理 :
假设
和
分别是 问题
( 目标函数求最大值 ) 和 问题
( 目标函数求最小值 ) 的 可行解 , 则必有
,
展开后为
弱对偶定理推论 1 :
原问题 任何一个 可行解 的目标函数值 , 都是其对偶问题 目标函数值的下界 ;
反之 ,
对偶问题 任何一个 可行解 的目标函数值 , 都是其原问题 目标函数的上界 ;
弱对偶定理推论 2 : ( 对偶问题的无界性 )
在一对 对偶问题
和
中 ,
如果其中 一个线性规划问题可行 , 但是 目标函数无界 , 则 另外一个问题没有可行解 ;
如果其中 一个线性规划问题不可行 , 其 对偶问题不一定不可行 ;
弱对偶定理推论 3 :
在一对 对偶问题
和
中 ,
如果其中 一个线性规划问题可行 , 而 另一个线性规划问题不可行 , 则 该可行问题的目标函数是无界的;
3、最优性定理
最优性定理 :
如果
是 原问题的可行解 ,
是 对偶问题的可行解 ,
并且 两个可行解对应的目标函数值相等 , 即
, 即
,
则
是原问题的最优解 ,
是对偶问题的最优解 ;
4、强对偶性
强对偶性 : 如果 原问题 与 对偶问题 都有可行解 , 只要有一个问题有最优解 , 则 两个问题都有最优解 , 二者的最优解的目标函数值相等 ;
5、互补松弛定理
和
分别是 原问题
问题 和 对偶问题
的 可行解 ,
这两个解各自都是对应 线性规划问题 的 最优解
的 充要条件是 :
其中
是 松弛变量 或 剩余变量 ;
互补松弛定理简写 :
"
和
分别是 原问题
问题 和 对偶问题
的 最优解 "
其中
是 松弛变量 或 剩余变量 ;
二、原问题与对偶问题对应关系
原问题与对偶问题对应关系 :
如果 原问题 有最优解 , 对偶问题也 有最优解 ;
如果 原问题 有 无界解 , 对偶问题 无可行解 ;
如果 原问题 无可行解 , 对偶问题 无法判断 ;
上述是根据弱对偶定理总结的 ;
二、对偶理论的相关结论
1、对偶问题存在
任何 线性规划问题 , 都有一个对应的 对偶线性规划问题 ;
2、对偶问题转化
原问题
:
;
对偶问题
:
原问题与对偶问题对应关系 :
原问题第
个约束条件是
约束 , 其对偶问题的第
个变量的符号不确定 , 可能大于等于
, 也可能小于等于
;
查看 约束变量的符号 与 其另外一个对偶问题的 约束方程的符号 一致性 , 来确定对偶问题的约束方程符号 ;
约束方程符号 :
如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是
, 因此 对偶问题的约束方程符号 与 原问题变量 符号一致 ;
如果当前线性规划问题 目标函数是求最小值 , 原问题就是下面的问题 , 其对偶问题 ( 上面的 ) 的约束方程符号是
, 因此 对偶问题的约束方程符号 与 原问题变量 符号相反 ;
变量符号 :
如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是
, 因此 对偶问题的变量符号 与 原问题约束方程符号 符号相反 ;
如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是
, 因此 对偶问题的变量符号 与 原问题约束方程符号 符号一致 ;
3、对偶问题的解
① 互为对偶的两个问题 , 或者同时都有最优解 , 或者同时都没有最优解 ;
② 对偶问题 有可行解 , 原问题 不一定有可行解 , 因为对偶问题的可行解可能是 无界解 , 原问题可能 无可行解 ;
③ 原问题有 多重解 , 对偶问题 可能有多重解 , 也 可能有唯一解 ; 多重解是 有无穷多最优解 ;
④ 对偶问题 有可行解 , 原问题 无可行解 , 则对偶问题 有无界解 ; 一对问题中 , 一个有可行解 , 一个无可行解 , 则有可行解的是无界解 ;
⑤ 原问题 没有最优解 , 对偶问题无法判断 ; 没有最优解有两种情况 , 一种是 无界解 , 一种是 无可行解 ; 如果原问题有无界解 , 则对偶问题无可行解 ; 如果原问题无可行解 , 则对偶问题无可行解 ;
⑥ 如果对偶问题没有可行解 , 对偶问题无法判断 , 无界解 或 无可行解 两种情况都有可能 ;
⑦ 如果原问题与对偶问题 都有可行解 , 则 都有最优解 ;
如果 原问题 有最优解 , 对偶问题也 有最优解 ;
如果 原问题 有 无界解 , 对偶问题 无可行解 ;
如果 原问题 无可行解 , 对偶问题 无法判断 ;
4、互补松弛定理
如果
和
分别是原问题与对偶问题的最优解 , 则
;
"
和
分别是 原问题
问题 和 对偶问题
的 最优解 "
其中
是 松弛变量 或 剩余变量 ;
相关文章
- java 字符数组 合并_字符数组合并?c数组合并?java数组合并问题「建议收藏」
- activate-power-mode 写代码的时候体验狂拽酷炫的效果 (IntelliJ IDEA版安装过程及问题)「建议收藏」
- mysql查询语句left join和right join问题(日常工作遇到问题总结-仅供个人学习)
- 总结了一些有用的 Javascript 单行代码,能快速处理一些问题
- PHP编程遇到过的细节问题(总结)
- 等保测评:Centos超时退出问题
- MongoDB安装到windows服务的方法及遇到问题的完美解决方案
- 解决CentOS 7升级Python到3.6.6后yum出错问题总结
- Attempt to invoke virtual method ‘boolean java.lang.String.equals(java.lang.Object)’ on a null object reference xxx 的问题分析与解决方案详解手机开发
- 40个Java多线程问题总结,新手必备详解编程语言
- 排查Linux服务器缓慢问题:实用步骤总结(linux服务器很慢)
- 解决MySQL自增ID删除后重置问题(mysql删除自增id)
- 微软紧急发布带外更新:修复Win10中无法打开PDF文档问题
- 数据库解决Oracle数据库IP修改问题(oracle修改ip)
- 3704数据库操作错误!aspcms解决此问题方法大总结
- 解决Redis连接不上的问题(怎么连接上redis)
- MySQL数据库遇到1136错误问题的解决方法(mysql中1136错误)
- 解决MySQL查询时遇到的表中不存在的问题(mysql不在表中)
- 解决MySQL下载后空数据问题(mysql下载没有数据)
- 解决MySQL中文乱码问题(mysql不能打中文)
- 解决MySQL命令无法保存问题的方法(mysql不能保存命令)
- Oracle NSA技术解决数据安全问题(oracle nsa进程)
- ExtjsAjax乱码问题解决方案
- firefox火狐浏览器与与ie兼容的2个问题总结
- ChromeForm多次提交表单问题的解决方法
- ASP.Net开发常见的一些问题总结
- PHP变量内存分配问题记录整理