CAN-File-10-10-08-13-线性规划对偶.ppt
《CAN-File-10-10-08-13-线性规划对偶.ppt》由会员分享,可在线阅读,更多相关《CAN-File-10-10-08-13-线性规划对偶.ppt(39页珍藏版)》请在三一文库上搜索。
1、,第03章 线性规划:对偶 Linear Programming: duality,对偶理论 对偶问题 对偶定理 与单纯形法的关系 互补松弛KKT条件 基于对偶的方法 对偶单纯形法(概念、步骤、收敛性),对偶理论, 食谱问题:确定食品数量,满足营养需求,花费最小?,对偶问题:举例,n种食品,m种营养成份; 第 j 种食品的单价,每单位第 j 种食品所含第 i 种营养的数量,为了健康,每天必须食用第i 种营养的数量, 模型:,对偶问题:经济解释, 保健品公司:药剂师、营养丸、定价问题, 对偶问题,对偶问题:对称形式的对偶对,注:对偶是相互的,即对偶问题的对偶是原问题, 原始问题(primal):
2、,给定数据,原问题的变量,对偶问题:非对称形式的对偶对,注:为了确定任一线性规划问题的对偶,可以利用 对称形式或非对称形式的对偶对!, 原始问题(primal):,给定数据,原问题的变量,对偶问题:一般问题的对偶,给定数据c, A, b;记 A 的第 j 行为 aj,A 的第 i 列为 ai, 原问题(primal):, 对偶问题(dual):,对偶问题:例子,对偶定理:弱对偶定理,弱对偶定理. 设 和 分别是原始问题和对偶问题的可行 解,则,推论2. 如果原始问题与对偶问题之一无界,则另一个问题 没有可行解.,对偶定理:强对偶定理,对于一般形式的线性规划利用凸集分离定理证明!,强对偶定理.
3、如果原始问题和对偶问题之一有解,则另一个问题也有解,且最优值相等.,与单纯形法的关系:定理,如何由原始问题的解得到对偶问题的解?,与单纯形法的关系:例子,考虑问题,引入松弛变量标准形利用单纯形法求解,对偶问题,与单纯形法的关系:例子(续),原问题最优解,对偶问题 最优解,与单纯形法的关系:单纯形乘子, 与基 B 对应的单纯形乘子(simplex multiplier), 经济解释 记 A 的列向量为 aj,对应费用为 cj,j=1 , , n,解释为单位向量 ei 的合成价格!,解释为aj 的相对费用系数, 最优性:对所有的 i 有,与单纯形法的关系:单纯形乘子(续),灵敏度(sensitiv
4、ity,工程上),假设该问题的最优基是 B. 则,假设非退化!,问题:当向量 b 变化时,最优值如何变化?,与单纯形法的关系:单纯形乘子(续),影子价格(shadow price,经济上),称 为分量 所对应资源的边际价格(marginal price) 或者影子价格(shadow price),互补松弛 Complementary Slackness,互补松弛定理,定理. 设 和 分别是对称形式原始问题和对偶问题的可行解. 则它们是各自最优解的充要条件是:对所有的 i 和 j 有,对偶单纯形法 Dual Simplex Method,对偶单纯形法:概述, 适用问题:标准形问题有一个不可行的基
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CAN File 10 08 13 线性规划 对偶
链接地址:https://www.31doc.com/p-2201004.html