运筹学课件-第五节--灵敏度分析

1、第五节 灵敏度分析 一、灵敏度分析的含义和内容 1、灵敏度分析：对系统或事物因周围条件变化显示出来的敏感程度。 研究线性规划模型某些参数或限制量的变化对最优解的影响称为灵敏度分析。2、灵敏度分析的内容：目标函数的系数变化对最优解的影响；约束方程右端系数变化对最优解的影响；约束方程组系数阵变化对最优解的影响 ； 回答两个问题： 这些系数在什么范围内发生变化时，最优基不变（即最优解或最优解结构不变）？系数变化超出上述范围时，如何用最简便的方法求出新的最优解？ 二、 进行灵敏度分析的基本原则 1、在最优单纯形表的基础上进行； 2、尽量减少附加计算工作量； 3、灵敏度分析的步骤：（1）将参数的改变通过

2、计算反映到单纯形表。参数aij,bi,cj的变化引起的单纯形表上的有关数字的变化：（2）、检查原问题是否仍为可行解。（3）、检查对偶问题是否仍为可行解。原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题最优解或最优基不变单纯形求解最优解对偶单纯形求解最优解引进人工变量，新单纯形表重新计算 三、 灵敏度分析举例：例1-1 引入非负的松弛变量x3, x4,x5, 将该LP化为 标准型： 用单纯形法求解如下：Cj 2 1 0 0 0CB 基 b X1 x2 x3 x4 x50 x3 15/22 x1 7/21 x2 3/20 0 1 5/4 -15/21

3、0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4 -1/21、价值系数Cj变化（1）当cj是非基变量的价值系数它的变化只影响 一个检验数。 例：c4发生变化时， ，最优解不变否则 0,可使用原单纯形法继续迭代求出新的最优解。 （2）当cj是基变量的价值系数它的变化将影响所有非基变量的检验数. 当cj变化时，如能保持 ，则当前解仍为最优解，否则可用单纯形法继续迭代求出新的最优解。例1-1:(1)如果产品1的利润降至1.5元/件，产品2的利润增加至2元/件，工厂的最优生产计划？（2）如果产品1的利润不变，则产品的利润在什么范围内变化，工厂的最优生产计划不变？Cj 1.5

4、 2 0 0 0CB 基 b X1 x2 x3 x4 x50 x3 15/21.5 x1 7/2 2 x2 3/20 0 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 1/8 -9/4解（1）将产品1，2的利润变化直接反映到单纯形表Cj 1.5 2 0 0 0CB 基 b X1 x2 x3 x4 x50 x4 61.5 x1 22 x2 30 0 4/5 1 -61 0 -1/5 0 10 1 1/5 0 0 Cj-Zj0 0 -1/10 0 -3/2随利润的变化，调整如下：生产产品1为2件，产品2为3件。解（2）设产品2的利润1+ 直接反映到单

5、纯形表Cj 2 1 + 0 0 0CB 基 b X1 x2 x3 x4 x50 x3 15/22 x1 7/21+ x2 3/20 0 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4+ /4 -1/2-3 /22、分析bi（右端常数）变化： 当bi发生变化时，将影响所有基变量的取值。因为：若bi的变化 保持B-1b0,当前的基仍为最优基，最优解的结构不变（取值改变）；（B-1b）12，不满足该约束，所以原问题的最优解不是现在LP的最优解；将约束条件标准化后加入原最优表格， 3x1+x2 +x6 =12，进行初等行变换，然后用对偶单纯形法迭

6、代求出新的最优解。Cj 2 1 0 0 0 0CB 基 b X1 x2 x3 x4 x5 x60 x3 15/22 x1 7/2 x2 3/20 x6 120 0 1 5/4 -15/2 01 0 0 -1/2 00 1 0 -1/4 3/2 03 2 0 0 0 1Cj-Zj0 0 0 -1/4 -1/2 0X1,x2列非单位向量r2x(-3)+r4r3x(-1)+r4Cj 2 1 0 0 0 0CB 基 b X1 x2 x3 x4 x5 x60 x3 15/22 x1 7/2 x2 3/20 x6 -3/20 0 1 5/4 -15/2 01 0 0 -1/2 00 1 0 -1/4 3/

7、2 00 0 0 -1/4 -3/2 1Cj-Zj0 0 0 -1/4 -1/2 0对偶问题为可行解，原问题为非可行解，采用对偶单纯形法计算。Cj 2 1 0 0 0 0CB 基 b X1 x2 x3 x4 x5 x60 x3 152 x1 4 x2 00 x5 10 0 1 5/2 0 -51 0 0 1/3 0 -1/30 1 0 -1/2 0 10 0 0 1/6 1 -2/3Cj-Zj0 0 0 -1/6 0 -1/3添加试验工序后，最优的生产计划仅生产1产品4件。小结：1、线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析。 2、分析价值系数Cj的变化、bi（右端常数）变化