对偶理论和灵敏度分析

《对偶理论和灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划的对偶理论线性规划的对偶理论对偶问题的提出对偶关系对偶问题的基本性质对偶单纯形法对偶问题的提出ExampleKgKg对偶问题的提出primal对偶问题的提出对偶问题的提出（*）对偶问题的提出dual线性规划的对偶理论对偶问题的提出对偶关系对称形式的对偶关系非对称形式的对偶关系对偶问题的基本性质对偶单纯形法对称形式的对偶关系对称形式的对偶关系对称形式的对偶关系对称形式的对偶关系非对称形式的对偶关系定理非对称形式的对偶关系定理非对称形式的对偶关系定理相同相反线性规划的对偶理论对偶问题的提出对偶关系对偶问题的基本

2、性质对偶单纯形法对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质（弱对偶性）对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质例对偶问题无可行解，原问题无可行解。当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。对偶问题的基本性质关于无界解、无可行解有如下结论：无界解无可行解无可行解无界解对偶问题原问题对偶问题的基本性质（强对偶性）对偶问

3、题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质互补松弛性对偶问题的基本性质例对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质例对偶问题的基本性质对偶解的经济解释——影子价格对偶解的经济解释

4、影子价格对偶解的经济解释

5、影子价格对偶解的经济解释

6、影子价格对偶解的经

7、济解释----影子价格对偶解的经济解释----影子价格对偶解的经济解释----影子价格对偶解的经济解释----影子价格KgKg对偶解的经济解释----影子价格对偶解的经济解释----影子价格对偶解的经济解释----影子价格线性规划的对偶理论线性规划的对偶理论线性规划的对偶理论线性规划的对偶理论对偶问题的提出对偶关系对偶问题的基本性质对偶单纯形法对偶单纯形法原始单纯形法当P与DP均有可行解时，P与DP均得到最优解。单纯形方法：保持P可行解的同时，逐步将DP非可行解变为可行解。对偶单纯形方法：保持DP可行解的同时，逐步

8、将P非可行解变为可行解。对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法例用对偶单纯形法求解对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法优点当初始基解不是基可行解且检验数都为负数时，可以采用对偶单纯形法，不需要加入人工变量，简化了计算。对偶单纯形法优点在灵敏度分析和求解整数规划的分支定界法中，有时需要对偶单纯形法，使问题简化。对偶单纯形法缺点对大多数线型规划问题，很难满足对偶单纯形法的适用条件。所以不是一种主要方法。对偶单纯形法灵敏度分析灵敏度分析灵敏度分析所要解决的问题：系数在什么范围内变化，不会

9、影响已获得的最优解。如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解。当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。灵敏度分析的变化分析的变化分析问题：若该厂从其它处抽调4台时用于生产产品I、II。求该厂的最优生产计划。最优单纯形表的变化分析解：的变化分析的变化分析的变化分析的变化分析的变化分析最优解不变，最优值变化！的变化分析的变化分析原问题增加一个新变量的变化分析新问题增加一个新变量的变化分析增加一个新变量的变化分析增加一个新变量的变化分析增加一个新变量的变

10、化分析增加一个新变量的变化分析增加一个新变量的变化分析增加一个新变量的变化分析增加一个新变量的变化分析增加一个新变量的变化分析增加一个新变量的变化分析小结改进单纯形法对偶单纯形法原始单纯形法对偶问题最优解-影子价格灵敏度分析对偶理论小结