《对偶理论和灵敏度分析.ppt》由会员分享,可在线阅读,更多相关《对偶理论和灵敏度分析.ppt(112页珍藏版)》请在三一文库上搜索。
1、线性规划的对偶理论,线性规划的对偶理论,对偶问题的提出 对偶关系 对偶问题的基本性质 对偶单纯形法,对 偶 问 题 的 提 出,Example,对 偶 问 题 的 提 出,primal,对 偶 问 题 的 提 出,对 偶 问 题 的 提 出,(*),对 偶 问 题 的 提 出,dual,线性规划的对偶理论,对偶问题的提出 对偶关系 对称形式的对偶关系 非对称形式的对偶关系 对偶问题的基本性质 对偶单纯形法,对称形式的对偶关系,对称形式的对偶关系,对称形式的对偶关系,对称形式的对偶关系,非对称形式的对偶关系,定理,非对称形式的对偶关系,定理,非对称形式的对偶关系,定理,相同,相反,线性规划的对偶
2、理论,对偶问题的提出 对偶关系 对偶问题的基本性质 对偶单纯形法,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,(弱对偶性),对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,例 对偶问题无可行解,原问题无可行解。,当原问题(对偶问题)无可行解时,其对偶问题(原问题)或具有无界解或无可行解。,对 偶问题的基本性质,对 偶问题的基本性质,(强对偶性),对 偶问题的基本性质,对 偶问题的基
3、本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,互补松弛性,对 偶问题的基本性质,例,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,对 偶问题的基本性质,例,对 偶问题的基本性质,对偶解的经济解释影子价格,对 偶 解 的 经 济 解 释 | 影 子 价 格,对 偶 解 的 经 济 解 释 | 影 子 价 格,对
4、 偶 解 的 经 济 解 释 | 影 子 价 格,对偶解的经济解释-影子价格,对偶解的经济解释-影子价格,对偶解的经济解释-影子价格,对偶解的经济解释-影子价格,对偶解的经济解释-影子价格,对偶解的经济解释-影子价格,对偶解的经济解释-影子价格,线性规划的对偶理论,线性规划的对偶理论,线性规划的对偶理论,线性规划的对偶理论,对偶问题的提出 对偶关系 对偶问题的基本性质 对偶单纯形法,对 偶 单 纯 形 法,原始单纯形法,当P与DP均有可行解时, P与DP均得到最优解。,单纯形方法: 保持P可行解的同时,逐步将DP非可行解变为可行解。,对偶单纯形方法: 保持DP可行解的同时,逐步将P非可行解变为
5、可行解。,对 偶 单 纯 形 法,对 偶 单 纯 形 法,对 偶 单 纯 形 法,对 偶 单 纯 形 法,对 偶 单 纯 形 法,例 用对偶单纯形法求解,对 偶 单 纯 形 法,对 偶 单 纯 形 法,对 偶 单 纯 形 法,对 偶 单 纯 形 法,优点 当初始基解不是基可行解且检验数都为负数时,可以采用对偶单纯形法,不需要加入人工变量,简化了计算。,对 偶 单 纯 形 法,优点 在灵敏度分析和求解整数规划的分支定界法中,有时需要对偶单纯形法,使问题简化。,对 偶 单 纯 形 法,缺点 对大多数线型规划问题,很难满足对偶单纯形法的适用条件。所以不是一种主要方法。,对 偶 单 纯 形 法,灵敏度
6、分析,灵 敏 度 分 析,灵敏度分析所要解决的问题: 系数在什么范围内变化,不会影响已获得的最优解。 如果系数的变化超过以上范围,如何在原来最优解的基础上求得新的最优解。 当线性规划问题增加一个新的变量或新的约束,如何在原来最优解的基础上获得新的最优解。,灵 敏 度 分 析,的 变 化 分 析,的 变 化 分 析,问题:若该厂从其它处抽调4台时用于生产产品 I、II。求该厂的最优生产计划。,最优单纯形表,的 变 化 分 析,解:,的 变 化 分 析,的 变 化 分 析,的 变 化 分 析,的 变 化 分 析,的 变 化 分 析,最优解不变,最优值变化!,的 变 化 分 析,的 变 化 分 析,原问题,增 加 一 个 新 变 量 的 变 化 分 析,新问题,增 加 一 个 新 变 量 的 变 化 分 析,增 加 一 个 新 变 量 的 变 化 分 析,增 加 一 个 新 变 量 的 变 化 分 析,增 加 一 个 新 变 量 的 变 化 分 析,增 加 一 个 新 变 量 的 变 化 分 析,增 加 一 个 新 变 量 的 变 化 分 析,增 加 一 个 新 变 量 的 变 化 分 析,增 加 一 个 新 变 量 的 变 化 分 析,增 加 一 个 新 变 量 的 变 化 分 析,增 加 一 个 新 变 量 的 变 化 分 析,小结,小 结,