哈工大考研管理运筹学对偶问题(四)——敏感性分析.pptVIP

第二章 对偶理论——敏感性分析 灵敏度分析内容 初始表和最优表的比较(一) 初始表和最优表的比较(二) 敏感性分析的三个公式 1.目标函数系数cj的改变 1.1 非基变量价值系数的灵敏度分析 1.2 基变量价值系数的灵敏度分析 例 3.增加一个新的变量 4.增加一个新的约束 * * 哈尔滨工业大学管理学院 韩伟一 wyhan@hit.edu.cn 灵敏度分析目的 灵敏度分析所要解决的问题： 系数在什么范围内变化，不会影响已获得的最优基。 如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解 当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。 ※目标函数系数cj的改变 ※常数项bi的改变 ※技术系数aij的改变 非基变量在目标函数中系数的灵敏度分析 基变量在目标函数中系数的灵敏度分析 max z= -x1 -x2 +4x3 ? s.t. ? x1 +x2 +2x3 ≤9 ? ? x1 +x2 -x3 ≤2 ? ? -x1 +x2 +x3 ≤4 ? ? x1, x2, x3 ≥0 在线性规划问题中，对c2进行灵敏度分析 。 得到以上问题的最优单纯形表： 当c2’=c2+?时，相应的单纯形表为： 要使原来的解仍保持最优解，就要zj-cj≤0（j=1,2,3,4,5），即 由此得到， ，即当c2?35/12时，最优解保持不变 max z= -x1 -x2 +4x3 ? s.t. ? x1 +x2 +2x3 ≤9 ? ? x1 +x2 -x3 ≤2 ? ? -x1 +x2 +x3 ≤4 ? ? x1, x2, x3 ≥0 在线性规划问题中，对c1进行灵敏度分析 。 得到以上问题的最优单纯形表： 当c1’=c1+?时，相应的单纯形表为： 要使原来的基仍保持最优基，就要zj-cj≤0（j=1,2,3,4,5），即 由此得到，-3???3，即当-2?c1?4时，最优基保持不变 2.右边常数的灵敏度分析 右边常数的灵敏度分析 max z= -x1 -x2 +4x3 ? s.t. ? x1 +x2 +2x3 ≤9 ? ? x1 +x2 -x3 ≤2 ? ? -x1 +x2 +x3 ≤4 ? ? x1, x2, x3 ≥0 在线性规划问题中，对b1进行灵敏度分析 。 最优单纯形表 初始单纯形表 对于上述最优解，最优基为： 当b1’=b1+?=9+?时，最后一张单纯形表中的右边常数将成为 最后一张单纯形表中的右边常数将成为： 原始可行条件为： ??-1，b1’=b1+??8时，原来的最优基仍为原始可行基 增加一个新的变量x7，它在目标函数中的系数c7=1，在约束条件中的系数向量为 ： 求新的最优基和最优解。 max z= -x1 -x2 +4x3 ? s.t. ? x1 +x2 +2x3 ≤9 ? ? x1 +x2 -x3 ≤2 ? ? -x1 +x2 +x3 ≤4 ? ? x1, x2, x3 ≥0 最优单纯形表 初始单纯形表 *