运筹学灵敏度分析1

1、什么是灵敏度分析？

是指研究线性规划模型的某些参数(bi,cj,aij）或限制量（xj,约束条件）的变化对最优解的影响及其程度的分析过程<也称为优化后分析>。一、含义和研究对象s.t.回答两个问题：

①这些系数在什么范围内发生变化时，最优解不变？②系数变化超出上述范围，如何用最简便的方法求出新的最优解？2、灵敏度分析的研究对象：目标函数的系数cj变化对最优解的影响；约束方程右端系数bi变化对最优解的影响；约束方程组系数矩阵A变化对最优解的影响；

一、含义和研究对象

1、在最终单纯形表的基础上进行；2、尽量减少附加的计算工作量；

二、进行灵敏度分析的基本原则将参数的改变通过计算反映到最终单纯形表上来.检查是否仍为原问题的可行解.检查是否仍为对偶问题的可行解.4.依据不同情况决定继续计算或得到结论.三、灵敏度分析的步骤原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算4.分析增加一个约束条件的变化四、灵敏度分析的主要内容1.分析

cj

的变化2.分析

bi

的变化3.分析增加一个变量

xj的变化5.分析系数

aij的变化系数矩阵As.t.

对偶问题决策变量的最优解<影子价格>：初始单纯形表最优单纯形表X*=B-1bCN－CBB-1N≤0－CBB-1≤0

原问题基变量的最优解：Z*=CBB-1b最优值：Y*T=CBB-1Y*T=CBB-1

XB

I

0基变量非基变量XB基变量基变量基可系数行解

CN－CBB-1NB-1NB-1XNXsB-1bCBB-1b－CBB-1Z*=CBB-1b分析cj

的变化原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算最优值可能已变

x1,x2≥0maxs.t.

2x1+2x2≤12z=2x1+3x2

4x1≤

165x2≤

15变化

x1,x2≥0maxs.t.

2x1+2x2≤12z=(2+λ1)x1+(3+λ2)x2

4x1≤

165x2≤

15qi分析λ1和λ2分别在什么范围变化时，最优解不变？例1-1

x1,x2≥0maxs.t.

2x1+2x2≤12z=2x1+3x2

4x1≤

165x2≤

15变化

x1,x2≥0maxs.t.

2x1+2x2≤12z=(2+λ1)x1+(3+λ2)x2

4x1≤

165x2≤

15qi当λ2=0时，将λ1反映在最终单纯形表中，可得从而，表中解仍为最优解的条件是即当时问题的最优解不变。例1-1分析λ1和λ2分别在什么范围变化时，最优解不变？

x1,x2≥0maxs.t.

2x1+2x2≤12z=2x1+3x2

4x1≤

165x2≤

15变化

x1,x2≥0maxs.t.

2x1+2x2≤12z=(2+λ1)x1+(3+λ2)x2

4x1≤

165x2≤

15qi当λ1=0时，将λ2

反映在最终单纯形表中，可得从而，表中解仍为最优解的条件是即当时问题的最优解不变。例1-1分析λ1和λ2分别在什么范围变化时，最优解不变？美佳公司计划生产I、II两种产品，每天生产条件如表，问(1)该公司应如何安排生产计划才能使总利润最多?(2)若产品Ⅰ的利润降至1.5百元/单位，而产品Ⅱ的利润增至2百元/单位，最优生产计划有何变化

？(3)若产品Ⅰ的利润不变，则产品Ⅱ的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？例2-1设备A(h)设备B(h)调试工序(h)利润(百元)ⅠⅡ每天可用能力资源产品0562112115245例2-1如何安排生产计划才能使总利润最多？解：(1)设x1,x2分别表示Ⅰ、Ⅱ两种产品的生产数量，得LP模型maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0用单纯形法求解得最终单纯形表设备A(h)设备B(h)调试工序(h)利润(百元)ⅠⅡ每天可用能力资源产品0562112115245例2-1如何安排生产计划才能使总利润最多？解：(1)设x1,x2分别表示Ⅰ、Ⅱ两种产品的生产数量，得LP模型maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0用单纯形法求解得最终单纯形表得最优解为：X*=(7/2,3/2,15/2,0,0)Tzmax=8.5(百元)。即每天生产3.5单位产品Ⅰ，1.5单位产品Ⅱ时总利润最多，且maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0例2-1产品Ⅰ利润降至1.5百元/单位，产品Ⅱ的利润增至2百元/单位，生产计划如何变化？解：(2)将产品Ⅰ、Ⅱ的利润变化反映在最终单纯形表中，可得maxz=1.5x1+2x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0因有非基变量的检验数大于零需继续用单纯形法迭代计算，maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0例2-1产品Ⅰ利润降至1.5百元/单位，产品Ⅱ的利润增至2百元/单位，生产计划如何变化？解：(2)将产品Ⅰ、Ⅱ的利润变化反映在最终单纯形表中，可得maxz=1.5x1+2x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0因有非基变量的检验数大于零需继续用单纯形法迭代计算，得最优解为：X*=(2,3,0,6,0)T说明随产品利润的改变，为获得最高利润，应将生产计划调整为每天生产2单位产品Ⅰ，3单位产品Ⅱ，且zmax=9(百元)。maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0例2-1解：(3)将产品Ⅱ的利润变化反映在最终单纯形表中，可得maxz=2x1+(1+△c2)x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0表中解仍为最优解的条件是产品Ⅱ的利润在什么范围内变化时，最优生产计划不会发生变化？即故当产品Ⅱ的利润在范围变化时，最优生产计划不变。1→1+△c2Y*T=CBB-1

XB

I

0基变量非基变量XB基变量基变量基可系数行解

CN－CBB-1NB-1NB-1XNXsB-1bCBB-1b－CBB-1Z*=CBB-1b分析cj

的变化原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算B-1NB-1Y*T=CBB-1

XB

I

0基变量非基变量XB基变量基变量基可系数行解

CN－CBB-1NXNXsB-1bCBB-1b－CBB-1Z*=CBB-1b原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算分析bi的变化最优解或最优值可能已变

x1,x2≥0maxs.t.

2x1+2x2≤12z=2x1+3x2

4x1≤

165x2≤

15变化

x1,x2≥0maxs.t.

2x1+2x2≤12+λ1z=2x1+3x2

4x1≤

16+λ25x2≤

15+λ3分析λi分别在什么范围变化时，最优基不变？例1-2qi

x1,x2≥0maxs.t.

2x1+2x2≤12z=2x1+3x2

4x1≤

165x2≤

15变化

x1,x2≥0maxs.t.

2x1+2x2≤12+λ1z=2x1+3x2

4x1≤

16+λ25x2≤

15+λ3例1-2解：先分析λ1的变化范围:为使最优基不变，则需,即从而得到同理可得λ2与λ3的取值范围分析λi分别在什么范围变化时，最优基不变？

美佳公司计划生产I、II两种产品，每天生产条件如表，问(4)设备A和调试工序每天能力不变，而设备B能力增加到32，问最优生产计划如何变化？(5)若设备A和B的能力不变，调试工序能力在什么范围内变化时，问题的最优基不变？例2-2设备A(h)设备B(h)调试工序(h)利润(百元)ⅠⅡ每天可用能力资源产品0562112115245maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0得最优解为：X*=(7/2,3/2,15/2,0,0)Tmaxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0例2-2解：(4)由最终单纯形表，可得maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24+8

x1+x2≤5x1,x2≥0设备B可用能力增加到32，生产计划如何变化？maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0例2-2解：(4)由最终单纯形表，可得maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24+8

x1+x2≤5x1,x2≥0设备B可用能力增加到32，生产计划如何变化？反映到最终单纯形表可得maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0例2-2解：(4)由最终单纯形表，可得maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24+8

x1+x2≤5x1,x2≥0设备B可用能力增加到32，生产计划如何变化？反映到最终单纯形表可得maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0例2-2解：(4)由最终单纯形表，可得maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24+8

x1+x2≤5x1,x2≥0设备B可用能力增加到32，生产计划如何变化？表中原问题为非可行解，用对偶单纯形法继续计算得出基入基表中原问题为非可行解，用maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0例2-2解：(4)由最终单纯形表，可得maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24+8

x1+x2≤5x1,x2≥0设备B可用能力增加到32，生产计划如何变化？对偶单纯形法继续计算得最优解为：X*=(5,0,15,2,0)T说明随设备B能力的增加，为获得最高利润，应将生产计划调整为每天仅生产5单位产品Ⅰ，且zmax=10(百元)。例2-2解：调试工序能力在什么范围变化，最优基不变？maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5+△b3x1,x2≥0(5)由最终单纯形表，可得例2-2解：maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5x1,x2≥0maxz=2x1+x2

s.t.

5x2≤15

6x1+2x2≤24

x1+x2≤5+△b3x1,x2≥0(5)由最终单纯形表，可得由，计算得调试工序能力在什么范