灵敏度分析13-10-16.ppt

第四章 灵敏度分析 前面讨论线性规划问题时，总是假设aij, bi , cj是不变的常数。 基本解X=（XB ,XN）T=(B-1b,0)T是最优解的条件是： ① XB = B-1b ≥0 ② σN = CN - CB B-1N ≤0 为什么要进行灵敏度分析： 灵敏度分析的内容 一、目标函数系数cj的改变 1，非基变量在目标函数中系数的灵敏度分析 非基变量在目标函数中系数的灵敏度分析 2，基变量在目标函数中系数的灵敏度分析 基变量在目标函数中系数的灵敏度分析 例： 三、增加一个新的变量-例 四、增加一个新的约束-例 灵敏度分析的综合应用: 例：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划 -3 2 -1 -5 x5 0 -1 0 0 0 -1 0 1 0 10 x2 4 1 0 0 1 35 x1 5 2 1 0 0 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 4 5 cj 得到该问题的最优单纯形表： * 当这些数据中有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化，或这些数据在什么范围内变化已求得的线性规划问题的最优解不变。 它是在已求得线性规划最优解的基础上，来讨论以上数据的变化对最优解的影响。 灵敏度分析也叫优化后分析。 Sensitivity analysis\Post optimality analysis ① 称为原始可行性条件 ② 原始最优性条件，或正则性条件 10 18 利润 170 100 150 5 2 2 3 1 5 A1 A2 A3 资源限制 甲 乙 资源 目标函数系数cj的改变 消耗系数aij的改变 右端常数bj的改变 ※目标函数系数cj的改变 ※右端常数项bi的改变 ※技术系数aij的改变 灵敏度分析所要解决的问题： 系数在什么范围内变化，不会影响已获得的最优基。 如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解 当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。 非基变量在目标函数中系数的灵敏度分析 基变量在目标函数中系数的灵敏度分析 +△ Ck 要使最优解不变，必须满足σk+△ck≥0 +△ Ck 即△ck≥ -σk 例：在线性规划问题中，对c2 进行灵敏度分析 。 max z= -x1 -x2 +4x3 ? s.t. ? x1 +x2 +2x3 ≤9 ? ? x1 +x2 -x3 ≤2 ? ? -x1 +x2 +x3 ≤4 ? ? x1, x2, x3 ≥0 -47/12 得到以上问题的最优单纯形表： 当c2 =c2+ △c2 时，相应的单纯形表为： -1+ △c2 要使原来的解仍保持最优解，就要σ2≤0（j=1,2,3,4,5），即 △c2 -47/12≤0 △c2 ≤ 47/12 由此得到， ，即当c2 ≤ 35/12时，最优解保持不变。 △c2 ≤ 47/12 -1+ △c2 CB XB C 当c2=4时，最优解是否改变？ c2=4时，超出变化范围，相应的单纯形表为： max z= -x1 -x2 +4x3 ? s.t. ? x1 +x2 +2x3 ≤9 ? ? x1 +x2 -x3 ≤2 ? ? - x1 +x2 +x3 ≤4 ? ? x1, x2, x3 ≥0 例：在线性规划问题中，对c1进行灵敏度分析 。 得到以上问题的最优单纯形表： -47/12 当c1 =c1+ △c1 时，相应的单纯形表为： -47/12-1/3△c1 -1+△c1 -1+△c1 -1+1/3△c1 -2-2/3△c1 要使原来的基仍保持最优基，就要σj ≤0（j=1,2,3,4,5），即 -47/12-1/3△c1 ≤0 -1+1/3△c1≤0 -2-2/3△c1≤0 △c1 ≥ - 47/4 △c1 ≤ 3 △c1 ≥ - 3 由此得到，-3 ≤ △c1 ≤ 3，即当-2 ≤ c1 ≤ 4时，最优基保持不变。 二、右端常数的灵敏度分析： 右端常数的灵敏度分析 资源供给条件发生变化后对原最优方案的影响 在初始单纯型表令bK = 则在最终单纯形表中XB的解就变成了 如要使XB成为可行解，只要使上述等式的右边≥0， 就可求出 的取值范围。 max z= -x1 -x2 +4x3 ? s.t