运筹学04对偶理论.ppt

《运筹学04对偶理论.ppt》由会员分享，可在线阅读，更多相关《运筹学04对偶理论.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1页页线性规划及单纯型法线性规划及单纯型法线性规划的对偶理论 第二章第第2页页线性规划及单纯型法线性规划及单纯型法 对偶问题的提出对偶问题的提出 第一节第第3页页1 对偶问题的对偶问题的实际意义实际意义背景背景1 最优化问题的两个侧面：最优化问题的两个侧面：周长给定，周长给定，求面积最大求面积最大 面积给定，面积给定，求周长最小求周长最小 容积给定，容积给定，求表面积最小求表面积最小 表面积给定，表面积给定，求容积最大求容积最大 资源给定，资源给定，求挣钱最多求挣钱最多 收益给定，收益给定，求用资源最少求用资源最少对偶问题对偶问题第第4页页背景背景2 出租机器还是搞生产？卖产品还是卖资源？

2、出租机器还是搞生产？卖产品还是卖资源？第第5页页第第6页页背景背景3 从数学公式中推导：从数学公式中推导：复习单纯形表的矩阵形式：复习单纯形表的矩阵形式：第第7页页第第8页页第第9页页第第10页页线性规划及单纯型法线性规划及单纯型法 原问题与对偶问题 第二节第第11页页2 原问题与对偶问题原问题与对偶问题 A b c x A c b y第第12页页第第13页页一般形式的对偶规划一般形式的对偶规划第第14页页解：解：先化为规范形式，再对偶转换先化为规范形式，再对偶转换第第15页页解：直接对偶转换解：直接对偶转换例例2：第第16页页线性规划及单纯型法线性规划及单纯型法 对偶问题的基本性质 第三节第

3、第17页页3 对偶的基本性质对偶的基本性质第第18页页3 对偶的基本性质对偶的基本性质第第19页页3 对偶的基本性质对偶的基本性质第第20页页3 对偶的基本性质对偶的基本性质第第21页页第第22页页第第23页页第第24页页 例例2 基互补性基互补性第第25页页原问题变量原问题变量原问题松弛变量原问题松弛变量对偶问题变量对偶问题变量对偶问题剩余变量对偶问题剩余变量基互补性基互补性第第26页页对偶问题变量对偶问题变量对偶问题剩余变量对偶问题剩余变量原问题变量原问题变量原问题松弛变量原问题松弛变量基互补性基互补性第第27页页线性规划及单纯型法线性规划及单纯型法 影 子 价 格 第四节第第28页页背景

4、：卖产品还是卖设备（资源）背景：卖产品还是卖设备（资源）影子价格影子价格第第29页页第第30页页影子价格的内涵影子价格的内涵第第31页页线性规划及单纯型法线性规划及单纯型法 对偶单纯形法 第五节第第32页页5 对偶单纯形法对偶单纯形法第第33页页第第34页页第第35页页解：解：化为极大目标，并标准化：化为极大目标，并标准化：第第36页页第第37页页线性规划及单纯型法线性规划及单纯型法 灵敏度分析 第六节第第38页页6 灵敏度分析灵敏度分析|概况概况|改变价值向量改变价值向量|改变右端向量改变右端向量|信息的变化：信息的变化：价值向量变化价值向量变化市市场变化场变化 右端向量变化右端向量变化资源

5、变化资源变化 系数矩阵变化系数矩阵变化技术进步技术进步 信息的变化对模型有什么影响？信息的变化对模型有什么影响？第第39页页灵敏度分析灵敏度分析|基本任务基本任务:确定参数的影响范围确定参数的影响范围,即保持即保持某某LP问题的问题的最优基不变的条件下该参数单独变化的最大范围最优基不变的条件下该参数单独变化的最大范围|一个参数的影响范围越小一个参数的影响范围越小,最优基对这一参数的变化最优基对这一参数的变化就越敏感就越敏感,最优基对该参数而言就越不稳定最优基对该参数而言就越不稳定|另一个任务另一个任务:当最优解随参数变化时如何简便地求得当最优解随参数变化时如何简便地求得新最优解新最优解第第40

6、页页1、价值向量的改变、价值向量的改变第第41页页原问题最优解：原问题最优解：第第42页页可以看出价值可以看出价值1变化的影响：变化的影响：第第43页页可以看出价值可以看出价值2变化的影响：变化的影响：第第44页页2、右端向量、右端向量 b 的改变的改变第第45页页原问题最优解：原问题最优解：初始基初始基第第46页页第第47页页3、增加一个变量、增加一个变量第第48页页原问题最优解：原问题最优解：第第49页页继续迭代继续迭代影响表中第影响表中第6列：列：第第50页页第第51页页4、增加一个约束条件、增加一个约束条件第第52页页解：解：第第53页页第第54页页使用对偶单纯形法：使用对偶单纯形法：第第55页页第第56页页线性规划及单纯型法线性规划及单纯型法 参数线性规划 第七节第第57页页解：解：第第58页页 1、为使最优基不变：、为使最优基不变：第第59页页第第60页页第第61页页第第62页页第第63页页