对偶与对偶算法教学课件.ppt
《对偶与对偶算法教学课件.ppt》由会员分享,可在线阅读,更多相关《对偶与对偶算法教学课件.ppt(49页珍藏版)》请在三一文库上搜索。
1、对偶性与对偶算法 线性规划对偶性质 求解标准线性规划问题 最终要找到一个基阵 满足 而最优目标值等于 记 ,原问题有最优解时, 满足以下约束 可否在满足以上约束的解中找到 ,进而找到 ? 设 是原问题的任意一个可行解,即满足 对任何满足不等式约束 的 ,成立 下述线性规划问题的最优目标值不会 小于原问题任何可行解的目标函数值 当 是原问题最优基阵时, 满足 其中 是 决定的最优的基本可行解 求解上面的线性规划问题能找到原问题的最优基矩阵 定义:标准线性规划问题的对偶问题 原问题对偶问题 矩阵形式( ) 原问题和对偶问题之间的关系 强对偶性:若原问题有最优解 ,则对偶问题一定也 有最优解 ,并且
2、最优目标值相等,即 则 弱对偶性:若 和 分别是原、对偶问题可行解,即 规范形式线性规划问题的对偶问题 原问题 标准线性规划问题 标准线性规划对偶问题原问题对偶问题等价问题 标准线性规划问题对偶问题的对偶问题 原问题 对偶问题 对偶问题的对偶问题是原问题 结论:任何原问题和对偶问题之间都存在下述相互关系 弱对偶性:原对偶问题任何可行解的目标值都是另一问 题最优目标值的界(推论:原对偶问题目标 值相等的一对可行解是各自的最优解) 强对偶性:原对偶问题只要有一个有最优解,另一个就 有最优解,并且最优目标值相等 原 对偶 有最优解 有最优解 问题无界 问题无界 无可行解 无可行解 不会不会 不会不会
3、 不会 不会出现的情况: 原问题对偶问题 含义:如果原(对偶)问题某不等式是松的(不等于0) 则其相应的对偶(原)变量必须是紧的(等于0) 互补松弛性定理 若 、 分别是原(对偶)问题可行解,则它们分别 是各自问题最优解的充要条件是满足互补松弛性等式 等价于 证明充分性: 由以上两式可得 ,根据弱对偶性的 推论可知两者分别是各自问题的最优解 证明必要性 : 当 和 是原、对偶问题的最优解时, 所以 由强对偶性可知 ,再利用可行性条 件 可得 例原问题 对偶问题 已知原问题最优解 ,求对偶问题最优解 利用互补松弛定理 少一个方程,还有没有其它信息可以利用? 对偶问题 原问题最优解 影子价格 原问
4、题 如果增加某些 的数值,最优目标值应该增加 能否定量地刻划增加不同 的效果? 例1 最优目标值增量 第一个约束的常数项加1: 最优目标值增量 第二个约束的常数项加1 最优目标值增量 第三个约束的常数项加1 不同约束常数项对最优目标值的影响 例1对偶问题 最优解 对偶问题最优解正好是最优目标函数的增量! (用对偶性验证) 设对偶问题最优解为 ,由强对偶性知,原问题 的最优目标值为 所以,原问题最优目标关于 的偏导数 分别是 ,说明 增加一个单位可望增 加 的最优目标值,故称其为 的影子价格 原问题对偶问题 一般情况 原问题对偶问题 如果原问题的某个约束在最优解处不是严格等式, 例如 ,增加 不
5、会增加最优目标值, 所以其影子价格 等于0,因此有互补松弛等式 同样道理可得 设是原问题的最优解, 是对偶问题的最优解 物理意义为生产单位 产品的利润减去按影子价 格计算的资源的总成本,如果差值大于零,应继 续生产,所以最优解必须满足所有检验数非正 如果原问题为标准型 是最优基矩阵,在推导强对偶性时已说明其对 偶问题的最优解为 ,于是,非基变量 的检验数可写成 影子价格只能在局部范围内反映资源增长(即 增加约束的右边常数)可以产生的目标函数的 增值,一旦资源增长导致最优基矩阵改变,原 来的最优对偶变量值一般情况下不等于单位资 源增长带来的目标函数的增值,从而失去影子 价格的意义 注意 改变,但
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对偶 算法 教学 课件
链接地址:https://www.31doc.com/p-3113442.html