对偶理论与灵敏度讲解.ppt

例、用对偶单纯形法求解线性规划问题： 使对偶问题基变量可行, 换出 换出 换出 例、用对偶单纯形法求解线性规划问题： 最优解 例、用对偶单纯形法求解线性规划问题： 对偶单纯形法的优点： 不需要人工变量； 当变量多于约束时，用对偶单纯形法可减少迭代次数； 在灵敏度分析中，有时需要用对偶单纯形法处理简化。 对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。 因此，对偶单纯形法一般不单独使用。 练习 用对偶单纯形法求解线性规划问题： 返回 对偶单纯形法 3.2.1 灵敏度问题及其图解法 灵敏度问题 灵敏度分析——图解法 灵敏度问题 背景： 线性规划问题中， 都是常数，但这些系数是估计值和预测值。 市场的变化 值变化； 工艺的变化 值变化； 资源的变化 值变化。 问题： 当这些系数中的一个或多个发生变化时，原最优解会怎样变化？ 当这些系数在什么范围内变化时，原最优解仍保持不变？ 若最优解发生变化，如何用最简单的方法找到现行的最优解？ 研究内容： 研究线性规划中， 的变化对最优解的影响。 研究方法： 图解法 对偶理论分析 仅适用于含2个变量的线性规划问题 在单纯形表中进行分析 Max Z = 34 x1 + 40 x2 4 x1 + 6 x2 ? 48 2 x1 + 2 x2 ? 18 2 x1 + x2 ? 16 x1、 x2 ? 0 线性规划模型 灵敏度分析——图解法 x2 18 — 16 — 14 — 12 — 10 — 8 — 6 — 4 — 2 — 0 | | | | | | | | | 2 4 6 8 10 12 14 16 18 x1 4x1 + 6x2 ? 48 2x1 + 2x2 ? 18 2x1 + x2 ? 16 A B C D E (8,0) (0,6.8) 最优解 (3,6) 4x1+ 6x2=48 2x1+ 2x2 =18 灵敏度分析——图解法 灵敏度分析 —图解法 18 — 16 — 14 — 12 — 10 — 8 — 6 — 4 — 2 — 0 | | | | | | | | | 2 4 6 8 10 12 14 16 18 x1 4x1 + 6x2 ? 48 2x1 + 2x2 ? 18 2x1 + x2 ? 16 A B C D E 目标函数的系数 34x1 + 40x2 = Z 40x2 = - 34x1 + Z x2 = - + 34x1 Z 40 40 灵敏度分析 —图解法 18 — 16 — 14 — 12 — 10 — 8 — 6 — 4 — 2 — 0 | | | | | | | | | 2 4 6 8 10 12 14 16 18 x1 4x1 + 6x2 ? 48 2x1 + 2x2 ? 18 2x1 + x2 ? 16 A B C D E 目标函数的系数 34x1 + 40x2 = Z 40x2 = - 34x1 + Z x2 = - + c1x1 Z c2 c2 若 c1增加（c2 不变） 新的最优解 灵敏度分析 —图解法 18 — 16 — 14 — 12 — 10 — 8 — 6 — 4 — 2 — 0 | | | | | | | | | 2 4 6 8 10 12 14 16 18 x1 4x1 + 6x2 ? 48 2x1 + 2x2 ? 18 2x1 + x2 ? 16 A B C D E 目标函数的系数 34x1 + 40x2 = Z 40x2 = - 34x1 + Z x2 = - + c1x1 Z c2 c2 若 c1减少 新的最优解 18 — 16 — 14 — 12 — 10 — 8 — 6 — 4 — 2 — 0 | | | | | | | | | 2 4 6 8 10 12 14 16 18 x1 4x1 + 6x2 ? 48 2x1 + 2x2 ? 18 2x1 + x2 ? 16 A B C D E (斜率 = - 1) (斜率 = - 2/3) 灵敏度分析 —图解法 最优解不变的范围 （设c1固定c2可变） 3.2.1 灵敏度问题及其图解法 3.2.2 灵敏度分析 一、分析 的变化