运筹学对偶理论幻灯片.ppt
第1页，共63页，编辑于2022年，星期三线性规划及单纯型法线性规划及单纯型法 对偶问题的提出对偶问题的提出 第一节第2页，共63页，编辑于2022年，星期三1 对偶问题的实际意义对偶问题的实际意义背景背景1 最优化问题的两个侧面：最优化问题的两个侧面：周长给定，周长给定，求面积最大求面积最大 面积给定，面积给定，求周长最小求周长最小 容积给定，容积给定，求表面积最小求表面积最小 表面积给定，表面积给定，求容积最大求容积最大 资源给定，资源给定，求挣钱最多求挣钱最多 收益给定，收益给定，求用资源最少求用资源最少对偶问题对偶问题第3页，共63页，编辑于2022年，星期三背景背景2 出租机器还是搞生产？卖产品还是卖资源？出租机器还是搞生产？卖产品还是卖资源？第4页，共63页，编辑于2022年，星期三第5页，共63页，编辑于2022年，星期三背景背景3 从数学公式中推导：从数学公式中推导：复习单纯形表的矩阵形式：复习单纯形表的矩阵形式：第6页，共63页，编辑于2022年，星期三第7页，共63页，编辑于2022年，星期三第8页，共63页，编辑于2022年，星期三第9页，共63页，编辑于2022年，星期三线性规划及单纯型法线性规划及单纯型法 原问题与对偶问题 第二节第10页，共63页，编辑于2022年，星期三2 原问题与对偶问题原问题与对偶问题 A b c x A c b y第11页，共63页，编辑于2022年，星期三第12页，共63页，编辑于2022年，星期三一般形式的对偶规划一般形式的对偶规划第13页，共63页，编辑于2022年，星期三解：解：先化为规范形式，再对偶转换先化为规范形式，再对偶转换第14页，共63页，编辑于2022年，星期三解：直接对偶转换解：直接对偶转换例例2：第15页，共63页，编辑于2022年，星期三线性规划及单纯型法线性规划及单纯型法 对偶问题的基本性质 第三节第16页，共63页，编辑于2022年，星期三3 对偶的基本性质对偶的基本性质第17页，共63页，编辑于2022年，星期三3 对偶的基本性质对偶的基本性质第18页，共63页，编辑于2022年，星期三3 对偶的基本性质对偶的基本性质第19页，共63页，编辑于2022年，星期三3 对偶的基本性质对偶的基本性质第20页，共63页，编辑于2022年，星期三第21页，共63页，编辑于2022年，星期三第22页，共63页，编辑于2022年，星期三第23页，共63页，编辑于2022年，星期三 例例例例2 2 基互补性基互补性基互补性基互补性第24页，共63页，编辑于2022年，星期三原问题变量原问题变量原问题松弛变量原问题松弛变量对偶问题变量对偶问题变量对偶问题剩余变量对偶问题剩余变量基互补性基互补性第25页，共63页，编辑于2022年，星期三对偶问题变量对偶问题变量对偶问题剩余变量对偶问题剩余变量原问题变量原问题变量原问题松弛变量原问题松弛变量基互补性基互补性第26页，共63页，编辑于2022年，星期三线性规划及单纯型法线性规划及单纯型法 影 子 价 格 第四节第27页，共63页，编辑于2022年，星期三背景：卖产品还是卖设备（资源）背景：卖产品还是卖设备（资源）影子价格影子价格第28页，共63页，编辑于2022年，星期三第29页，共63页，编辑于2022年，星期三影子价格的内涵影子价格的内涵影子价格的内涵影子价格的内涵第30页，共63页，编辑于2022年，星期三线性规划及单纯型法线性规划及单纯型法 对偶单纯形法 第五节第31页，共63页，编辑于2022年，星期三5 对偶单纯形法对偶单纯形法第32页，共63页，编辑于2022年，星期三第33页，共63页，编辑于2022年，星期三第34页，共63页，编辑于2022年，星期三解：解：化为极大目标，并标准化：化为极大目标，并标准化：第35页，共63页，编辑于2022年，星期三第36页，共63页，编辑于2022年，星期三线性规划及单纯型法线性规划及单纯型法 灵敏度分析 第六节第37页，共63页，编辑于2022年，星期三6 灵敏度分析灵敏度分析|概况概况|改变价值向量改变价值向量|改变右端向量改变右端向量|信息的变化：信息的变化：价值向量变化价值向量变化市场变化市场变化 右端向量变化右端向量变化资源变化资源变化 系数矩阵变化系数矩阵变化技术进步技术进步 信息的变化对模型有什么影响？信息的变化对模型有什么影响？第38页，共63页，编辑于2022年，星期三灵敏度分析灵敏度分析|基本任务基本任务:确定参数的影响范围确定参数的影响范围,即保持某即保持某LP问题的最优问题的最优基不变的条件下该参数单独变化的最大范围基不变的条件下该参数单独变化的最大范围|一个参数的影响范围越小一个参数的影响范围越小,最优基对这一参数的变化就越敏感最优基对这一参数的变化就越敏感,最优基对该参数而言就越不稳定最优基对该参数而言就越不稳定|另一个任务另一个任务:当最优解随参数变化时如何简便地求得新最当最优解随参数变化时如何简便地求得新最优解优解第39页，共63页，编辑于2022年，星期三1、价值向量的改变、价值向量的改变第40页，共63页，编辑于2022年，星期三原问题最优解：原问题最优解：第41页，共63页，编辑于2022年，星期三可以看出价值可以看出价值1变化的影响：变化的影响：第42页，共63页，编辑于2022年，星期三可以看出价值可以看出价值2变化的影响：变化的影响：第43页，共63页，编辑于2022年，星期三2、右端向量、右端向量 b 的改变的改变第44页，共63页，编辑于2022年，星期三原问题最优解：原问题最优解：初始基初始基第45页，共63页，编辑于2022年，星期三第46页，共63页，编辑于2022年，星期三3、增加一个变量、增加一个变量第47页，共63页，编辑于2022年，星期三原问题最优解：原问题最优解：第48页，共63页，编辑于2022年，星期三继续迭代继续迭代影响表中第影响表中第6列：列：第49页，共63页，编辑于2022年，星期三第50页，共63页，编辑于2022年，星期三4、增加一个约束条件、增加一个约束条件第51页，共63页，编辑于2022年，星期三解：解：第52页，共63页，编辑于2022年，星期三第53页，共63页，编辑于2022年，星期三使用对偶单纯形法：使用对偶单纯形法：第54页，共63页，编辑于2022年，星期三第55页，共63页，编辑于2022年，星期三线性规划及单纯型法线性规划及单纯型法 参数线性规划 第七节第56页，共63页，编辑于2022年，星期三解：解：第57页，共63页，编辑于2022年，星期三 1、为使最优基不变：、为使最优基不变：第58页，共63页，编辑于2022年，星期三第59页，共63页，编辑于2022年，星期三第60页，共63页，编辑于2022年，星期三第61页，共63页，编辑于2022年，星期三第62页，共63页，编辑于2022年，星期三第63页，共63页，编辑于2022年，星期三
