第二章对偶理论和灵敏度分析.pptVIP

对称性 对偶问题的对偶是原问题 2.4 对偶问题的基本性质-1 原问题 对偶问题 第二十九页，共七十页，2022年，8月28日 弱对偶性 若 X0 是原问题的可行解，Y0 是对偶问题的可行解，则存在 CX0≤Y0b。 2.4 对偶问题的基本性质-2 原问题 对偶问题 第三十页，共七十页，2022年，8月28日 无界性 若原问题存在无界解，则其对偶问题无可行解。 反证法：若对偶问题存在可行解 Y0，根据弱对偶性，可知 CX≤Y0b 而 Y0b 是一个定数，这与原问题无界相矛盾。 推论：若对偶问题存在无界解，则其原问题无可行解。 2.4 对偶问题的基本性质-3 为什么？ 第三十一页，共七十页，2022年，8月28日 若 X0 是原问题的可行解，Y0 是对偶问题的可行解，当 CX0=Y0b 时，X0 ，Y0 分别是原问题和其对偶问题的最优解。 根据弱对偶性可知，对原问题的任一可行解 X，均有 CX≤Y0b 由于 CX0=Y0b，可知 CX≤CX0 从而可知 X0 是原问题的最优解。 同理，可证 Y0 是其对偶问题的最优解。 2.4 对偶问题的基本性质-4 第三十二页，共七十页，2022年，8月28日 对偶定理 若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。 令 X* 为原问题的最优解，则 同时，检验数要满足 令 可知 Y* 是其对偶问题的一个可行解。 又 根据性质4，可知 Y* 是其对偶问题的最优解。 2.4 对偶问题的基本性质-5 第三十三页，共七十页，2022年，8月28日 互补松弛性 若 X* 和 Y* 分别为原问题和对偶问题的可行解，那么 其中 Xs* 和 Ys* 分别为松弛变量和剩余变量解的集合。 2.4 对偶问题的基本性质-6 第三十四页，共七十页，2022年，8月28日 例题：已知线性规划问题： 已知其对偶问题的最优解为 y1*= 4/5， y2*= 3/5；z=5。 试用对偶理论找出原问题的最优解 。 2.4 对偶问题的基本性质-6 第三十五页，共七十页，2022年，8月28日 基解的互补性 原问题的一个基解，对应其对偶问题的一个基解，并且该对互补基解的目标函数值相等； 当求得原问题在基 B 下的单纯形表后，表中检验数行相反的数（即－σ），就是其对偶问题的一个基解。 2.4 对偶问题的基本性质-7 第三十六页，共七十页，2022年，8月28日 将下列线性规划模型（例1）转化为对偶问题 2.5 对偶问题的经济解释—影子价格 用大M法求解 第三十七页，共七十页，2022年，8月28日 最终单纯形表为： 2.5 对偶问题的经济解释—影子价格 第三十八页，共七十页，2022年，8月28日 由例1可知： 2.5 对偶问题的经济解释—影子价格 设备增加1台时，总利润增加1.5元 原料A的供应增加1kg，总利润增加0.125元 原料B的供应增加1kg，总利润没有变化 第三十九页，共七十页，2022年，8月28日 将例1中设备限制增加1台时，则原线性规划问题变为： 2.5 对偶问题的经济解释—影子价格 用图解法求解 第四十页，共七十页，2022年，8月28日 将例1中原料B的供应量增加到20kg，则原线性规划问题变为： 2.5 对偶问题的经济解释—影子价格 用图解法求解 第四十一页，共七十页，2022年，8月28日 对偶问题的最优解往往代表对第 i 种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。 影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。 2.5 对偶问题的经济解释—影子价格 第四十二页，共七十页，2022年，8月28日 解决线性规划问题的另一种方法。 对偶单纯形法与单纯形法的区别： 2.6 对偶单纯形法 单纯形法 对偶单纯形法 前提 保持所有约束条件的常数 b≥0 保持所有的检验数σ符合目标函数的要求 思路 使所有的检验数σ符合目标函数的要求 使所有约束条件的常数 b≥0 出发点不同 第四十三页，共七十页，2022年，8月28日 在以下的情况中，用对偶单纯形法能更好地解决线性规划问题： 变量较少，而约束条件比较多的线性