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

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