[数学]Chap 4 灵敏度分析.ppt

1 第四章 灵敏度分析 线性规划研究的是一定条件下的最优化问题，采用优化方案可以达到节约资源、提高效益的目的，但是对“优化方案”必须要有全面的认识，不可机械地对待。 优化方案是建立在特定的资源环境和技术条件之上的，而环境和条件总是处在不断地变化之中，如产品价格、原材料成本、加工技术水平、资源消耗系数等时有波动，所以优化方案是个相对稳定的概念。当基础数据发生变化时，最优方案也就变了。 基础数据往往是测算估计的数值，虽然在运算过程中要求十分严格，但基础数据的误差是不可避免的。为了对优化结果有更全面的了解和恰当的运用，就需要进行灵敏度分析。 灵敏度分析的意义 2 第四章 灵敏度分析 灵敏度分析又称敏感性分析或优化后分析，它研究基础数据发生波动后对最优解的影响，以及在多大的范围内波动才不影响最优基。 灵敏度分析就是研究最优解对数据变化的敏感程度。 感性太强，则说明最优解的稳定性程度较低。 灵敏度分析解决的问题： 参数在什么范围变化而最优基不变。 已知参数的变化范围，考察最优解(最优基)是否改变。 灵敏度分析的概念 3 第四章 灵敏度分析 设问题 的最优单纯形表为： 表 4. 1 (4. 1) 4 第四章 灵敏度分析 一、当C发生变化时 由表 4. 1 可见，当C由C→C+ΔC时，最优表会发生改变的只是第m+1行。 设C=(c1, c2,…, cn)，C+ΔC=(c1+Δc1, c2+Δc2,…, cn+Δcn)。 则检验数应修改为 ( CB+ΔCB)B-1A -(C+ΔC) (4. 2) 目标函数应修改为 ( CB+ΔCB)B-1b (4. 3) 若(4. 2)中检验数仍保持 ≥ 0，则原最优解仍为最优解，但目标函数值已改变，由(4. 3)计算可得。 若(4. 2)中检验数不满足最优性条件(σ≥0), 则当前解已不是最优解，要从修改后的单纯形表出发，重新进行迭代，直到求到最优解为止。 5 第四章 灵敏度分析 一、当C发生变化时（续） 例 4. 1 已知线性规划问题的标准形为 其最优单纯形表见表4. 2。 问: (1) 当c1由-1变为c1+Δc1=4时，求新问题的最优解； (2) 讨论c2在什么范围内变化时，原有的最优解仍 是最优解。 6 第四章 灵敏度分析 一、当C发生变化时（续） 表 4. 2 cj -1 2 1 0 0 CB XB b x1 x2 x3 x4 x5 2 x2 6 1 1 1 1 0 0 x5 10 3 0 1 1 1 Z 12 3 0 1 2 0 最优基 最优基的逆 7 第四章 灵敏度分析 一、当C发生变化时（续） 8 第四章 灵敏度分析 一、当C发生变化时（续） cj 4 2 1 0 0 比 值 CB XB b x1 x2 x3 x4 x5 2 x2 6 1 1 1 1 0 0 x5 10 3 0 1 1 1 Z 12 -2 0 1 2 0 表 4. 3 2 x2 8/3 0 1 2/3 2/3 -1/3 4 x1 10/3 1 0 1/3 1/3 1/3 Z 56/3 0 0 5/3 8/3 2/3 6 10/3 9 第四章 灵敏度分析 (2) 要使原最优解仍为最优解，只要在新的条件下仍满足最优性准则： σ≥0。记c2’ = c2+Δc2 , 有 c2’ ≥ 1 或 c2+Δc2 ≥1 10 第四章 灵敏度分析 二、右端列向量b发生改变 当右端列向量从b→b+Δb时，由表 4. 1 可见，改变的只是表中第三列——右端列，即 基变量的取值由 XB = B-1b → XB’ = B-1(b+Δb), 目标函数值由 Z = CB B-1b → Z’ = CB B-1(b+Δb)。 若XB’ = B-1(b+Δb)≥0仍成立，则因为非基变量的检验数σj (j∈N)没有改变，因此最优解仍是最优解。此时XB’ 为新问题的最优解， Z’为新问题的最优值。 若XB’ = B-1(b+Δb)不大于等于0 ，但因σj ≥0 (j∈N)仍成立，故可用对偶单纯形法再次进行迭代，直到求得新的最优解。 11 第四章 灵敏度分析 二、右端列向量b发生改变（续） 例 4. 2 已知线性规划问题的标准形为 其最优单纯形表见表4. 4。若右端列向量从 求新问题的最优解。 12 第四章 灵敏度分析 二、右端列向量b发生改变（续