对偶理论和灵敏度分析.ppt

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