第五、六节 影子价格和对偶单纯形法.pptVIP

Chapter 2 Duality Theory and Sensitivity Analysis 例题 课堂讨论 比较单纯形算法与对偶单纯形算法的异同 对偶单纯形法例子 单纯形法和对偶单纯形法的步骤 对偶单纯形法的适用范围 对偶单纯形法适合于解如下形式的线性规划问题 在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。 对偶单纯形法的优点 初始解可以是非可行的，检验数都为负数，可以进行基变换。（无需加入人工变量） 变量个数多于约束条件个数。（对偶化） 灵敏度分析中可以使问题简化。 小 结 ？ ？ 作业 P75/2.7/(1) /2.8/(1) * * 第2章 对偶理论与灵敏度分析 对偶问题的基本性质 对称性 弱对偶性 无界性 最优解性质 对偶定理 互补松驰性 原问题与对偶问题的关系 -Y -YS2 YS1 -CBB-1 CB-CBB-1N 0 XS XN XB 试用对偶理论找出原问题的最优解。 已知其对偶问题的最优解为： 练习 第三章 对偶理论与灵敏度分析 第五节 对偶问题的经济解释——影子价格 -Y -YS2 YS1 -CBB-1 CB-CBB-1N 0 XS XN XB 第五节 对偶问题的经济解释——影子价格 -Y -YS2 YS1 -CBB-1 CB-CBB-1N 0 XS XN XB 影子价格（shadow price)不同于一般意义上的市场价格，按照资源最优分配理论, 可定义为“机会成本的货币表现”，是指某种资源或劳务被用于一种用途, 而放弃另一种用途时的价值。 这正是资源利用问题的数学规划中对偶模型的最优解。这是著名的前苏联数学家线性规划创始人、诺贝尔经济学奖获得者康特罗维奇发现的。 检验 线性规划的图解法－例2-1Graphical solution of linear programming A（8，5） 第五节 对偶问题的经济解释——影子价格 第五节 对偶问题的经济解释——影子价格 第三章 对偶理论与灵敏度分析 写出下面问题的对偶问题，然后用单纯形法求解。 第三章 对偶理论与灵敏度分析 0 -8 －M 0 5M－34 M-2 zj -cj M －8 －M 8 5M+16 M+16 zj 5M+32 2 0 -1 0 1 2 2 4 y3 8 1 1 0 -1 0 [5] 1 5 y6 M y6 y5 y4 y3 y2 y1 b yB CB M 0 0 8 50 18 6.8-M -8 -6.8 0 0 4.8 zj -cj 6.8 -8 -6.8 8 50 22.8 zj 66 5/4 -2/5 -1 2/5 1 0 [8/5] 2 y3 8 5 1/5 0 -1/5 0 1 1/5 1 y2 50 8-M -5 -8 -3 0 0 zj -cj 8 -5 -8 5 50 18 zj 60 -1/4 -5/8 1/4 5/8 0 1 5/4 y1 18 1/4 1/8 -1/4 -1/8 1 0 3/4 y2 50 ? 第三章 对偶理论与灵敏度分析 第六节 对偶单纯形法 一、对偶单纯形法的基本原理 由原问题与对偶问题之间的关系知道，在单纯形表中进行迭代时，在 b 列得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。经过迭代计算，当检验数行得到的对偶问题的解也是基可行解时，则得到最优解。 第六节 对偶单纯形法 二、对偶问题的计算步骤 列出初始单纯形表； 若B-1b≥0，σj=cj –zj≤0，则问题得到最优解，否则进入下一步； 取 对应的基变量xi*为换出变量； 由 确定换 入变量xj*，当所有的ai*j ≥0时,问题无可行解； 5. 以ai*j*为主元素，按原单纯形法进行迭代，得到新的计算表； 6. 重复2~5步。 例：用对偶单纯形法求例3-4的解 第三章 对偶理论与灵敏度分析 0 0 -8 -50 -18 cj -zj -Z=0 1 0 -1 -2 -2 -4 y5 0 0 1 0 [-5] -1 -5 y4 0 y5 y4 y3