2.7 54灵敏度分析

运筹学

运筹学

本节内容安排资源数量变化的分析 目标函数中价值系数的变化分析 技术系数的变化分析

运筹学

背景： 背景：a 线性规划问题中， 都是常数， 线性规划问题中， ij , bi , cj都是常数，但 这些系数往往是估计值和预测值： 这些系数往往是估计值和预测值： 值变化； 市场的变化 c j值变化； 值变化； 工艺的变化 aij值变化； 值变化。 资源的变化 bi 值变化。 定义: 灵敏度分析( 定义: 灵敏度分析(Sensitivity Analysis)又称为优化后分析( 又称为优化后分析(Postoptimality Analysis), 就是分析研究线性规划模型参数的取值变化时， 就是分析研究线性规划模型参数的取值变化时， 对最优解或最优基的影响。 对最优解或最优基的影响。 它在应用线性规划解决实际问题的过程中是非常有用的。 它在应用线性规划解决实际问题的过程中是非常有用的。

运筹学

解决的问题： 解决的问题： 当这些参数中的一个或多个发生变化时， (1)当这些参数中的一个或多个发生变化时， 原最优解会怎样变化？ 原最优解会怎样变化？ 当这些参数在什么范围内变化时， (2)当这些参数在什么范围内变化时， 原最优解仍保持不变？ 原最优解仍保持不变？ 若最优解发生变化， (3)若最优解发生变化， 如何用最简单的方法找到现行的最优解？ 如何用最简单的方法找到现行的最优解？

运筹学

灵敏度分析步骤 求出LP LP的最终单纯形表 1 求出LP的最终单纯形表项目 CB XB cj-zj B -1b 基变量 XB I 0 非基变量 XN B -1N C N- C B B -1N Xs B -1 - C B B -1

2.将参数的改变计算反映到最终单纯形表上来； 2.将参数的改变计算反映到最终单纯形表上来； 将参数的改变计算反映到最终单纯形表上来 检验原问题是否仍为可行解; 3.检验原问题是否仍为可行解; 检验对偶问题是否仍为可行解； 检验对偶问题是否仍为可行解； 4.按下表所列情况得出结论 和决定继续计算的步骤. 和决定继续计算的步骤.

运筹学

系数变化后最终表的几种情况原问题 可行解 可行解 非可行解 非可行解 对偶问题 可行解 非可行解 可行解 非可行解 结论或继续计算的步骤 表中的解仍为最优解 用单纯形法继续迭代求最优解 用对偶单纯形法继续迭代 引入人工变量, 引入人工变量,编制新的单纯 形表, 形表,求最优

注意： 注意： LP模型的参数发生变化后 模型的参数发生变化后， 当LP模型的参数发生变化后， 可不必对线性规划问题重新求解， 可不必对线性规划问题重新求解， 直接在原LP取得最优解的基础上进行分析或求解， LP取得最优解的基础上进行分析或求解 直接在原LP取得最优解的基础上进行分析或求解， 既减少计算量， 既减少计算量

, 又可根据参数变化范围及时对原决策作出调整和修正， 又可根据参数变化范围及时对原决策作出调整和修正，

运筹学

一 资源数量 bi变化的灵敏度分析项目 CB XB cj-zj B b-1

基变量 XB I 0

非基变量 XN B N CN- CB B-1N-1

Xs B-1

- CB B-1

XB=B-1b , z=CBB-1b, σ=C-CBB-1A =C由最终单纯形表可知， 的变化， 由最终单纯形表可知，资源数量 bi 的变化，会影 响到原最优解的可行性与目标函数值， 响到原最优解的可行性与目标函数值，但不会影响 检验数。 检验数。

运筹学

1. bi变化后，原最优解怎样变化；若最优解发 变化后，原最优解怎样变化； 生变化，则变化后，如何求出新的最优解？ 生变化，则变化后，如何求出新的最优解？ 变化后，仍保持B (1)若bi变化后，仍保持B-1b≥0,则当前基仍为 最优基，最优解的结构不变，但是取值改变. 最优基，最优解的结构不变，但是取值改变. 变化后， (2)若bi变化后，有B-1b<0,当前基为非可行基 ，又因为bi的变化不影响检验数，所以仍然保持为对 又因为b 的变化不影响检验数， 偶可行基，此时可以用对偶单纯形法 对偶单纯形法求出新的最优解 偶可行基，此时可以用对偶单纯形法求出新的最优解 变化后，可行性不变，则原最优解结构不变。 若bi变化后，可行性不变，则原最优解结构不变。

结 变化后，可行性改变，则原最优解结构改变， 论 若bi变化后，可行性改变，则原最优解结构改变， 用对偶单纯形法，找出新的最优解。 对偶单纯形法，找出新的最优解。

运筹学

例 对线性规划问题m ax z = 2x1 + 3x2 2x1 + 2x2 ≤ 12 + λ1 4x 16 + λ2 ≤ 1 s.t. 5x2 15 + λ3 ≤ x1 , x2 ≥ 0

分别分析λ 在什么范围内变化， 分别分析λ1、λ2、λ3在什么范围内变化， 问题的最优基不变. 问题的最优基不变.

运筹学

m ax

z = 2x1 + 3x2 2x1 + 2x2 ≤ 12 + λ1 4x 16 + λ2 ≤ 1 s.t. 5x2 15 + λ3 ≤ x1 , x2 ≥ 0

最终表: 最终表:2 x1 2 0 3 x1 x4 x2 3 4 3 1 0 0 0 3 x2 0 0 1 0 0 x3 1/2 -2 0 -1 0 x4 0 1 0 0 0 x5 - 1/5 4/5 1/5 - 1/5

cj - zj

方法一： 解： 方法一：

1 1/ 2 0 1/ 5 λ1 2 λ1 * b1 = B 1 b1 = 2 1 4 / 5 0 = 2λ1 0 0 1/ 5 0 0

先分析λ 的变化. 先分析λ1的变化.

运筹学

使问题最优基不变的条件是 1 3 + 2 λ1 * * 1 4 2λ ≥ 0 XB = B b + b1 = 1 3 由此推得- 由此推得-6≤λ1≤2. 方法二： 方法二：

1/ 2 0 1/ 5 12 3 * …… 此处隐藏：3427字，全部文档内容请下载后查看。喜欢就下载吧 ……