运筹学-灵敏度分析

第四章灵敏度分析运筹学灵敏度分析使用LP求解管理问题时，管理者需要了解当环境和数据发生变化时，线性规划得出的结论还是否有效；资源供应发生变化会有什么影响?成本变化后利润会发生什么变化?如果模型使用的数据不精确会有什么影响，数据允许在什么范围内变化?如果结论无效如何快速求解？现在睡觉的话会做梦,而现在学习的话会让梦实现

哈佛图书馆的训言1灵敏度分析主要内容1.目标函数系数变化的灵敏度分析2.右边项变化的灵敏度分析3.约束条件中的系数变化的灵敏度分析4.求解新的最优解5.增加新变量的灵敏度分析6.增加约束条件的灵敏度分析7.灵敏度分析的几何意义1.目标函数系数变化的灵敏度分析假定只有一个cj变化，假定cj从cj变到cj’=cj+Δcj，当Δcj在什么范围内变化时，不会影响最优解。(1)分析什么？(2)怎么分析？最优解不变的充要条件是：假定只有一个cj变化，分两种情况讨论：1）cj是非基变量的系数

设cj变化量为cj，若希望cj变化后最优基不变，检验数应满足以下条件：

j’

=cBB-1pj-(cj+cj)

=

cBB-1pj

-cj-cj=j-

cj

0 得到: cj

j

由cj

j及最优条件j0，cj只在增加方向受限制，在下降方向不受限制：cj增加时，变量对目标函数的贡献增加，增加足够大时，检验数会大于零，使该变量入基而引起最优基改变;cj下降时，变量对目标函数的贡献下降，检验数变得更正，最优基不会变化。非基变量目标系数允许变化范围为: -

cj

j

jJN

满足以上条件，解和目标值不会改变。例:对最优表如下表对c1进行敏感性分析。解：c1:x1非基c11

c1

3/42)cj是基变量的系数

基变量的cB变化会引起cBB-1变化,从而引起所有检验数变化。若要使所有检验数满足最优条件,有以下条件:

k=(cB+cB)B-1pk-ck

0kJN假定cj是当前基的第r个基变量，即： cj=(cB)r cB=(0,...,(cB)r,...,0) =(0,...,cj,...,0)从而有：

k’

=(cB+cB)B-1pk-ck =cBB-1pk+(0,..,(cB)r,..,0)B-1pk-ck =k+cj(B-1pk)r0 kJN令rk=(B-1pk)r得：

k’

=k+cjrk0 kJN在上述变化范围内：目标函数值的改变量：z=cj

xj

对偶解的改变量：y=cBB-1

原问题的最优基和最优解不会改变。解不等式组k’

=k+cjrk0kJN

得cj

的变化范围：

maxk

{-,-k/rkrk>0}cj

mink{+,-k/rkrk<0}例:对范例的目标函数系数进行敏感性分析。解：生产计划问题的最优单纯形表：c1:x1在基的第三行(r=3),非基变量下标k=4和5,34=-2/3,35=1/3,可得:max{-,-1/（1/3）}c1min{+,-1/2/（-2/3)}-3

c1

3c2：x2在基的第二行，r＝2，24＝1/2，

25＝0，可得：max{-,(-1/2/(1)}c2min{+,(-1)/(0)}-1/2

c22.右边项发生变化的灵敏度分析(1)分析什么？假定只有一个br变化，假定br从br变到br*=br+Δbr，当Δbr在什么范围内变化时，不会影响最优基。（不改变产品种类，只调整数量）(2)怎么分析？最优基不变的充要条件是：为了保持最优基不变，应使，即

解不等式组，得例:对范例的右边项进行敏感性分析。1)对b1进行分析：

i=1对应基的第一列，11=13=1，21=23=0，31=33=0

max{-,-4/1，-6/0，-4/0}

b1

4

b12) 对b2进行分析：i=2对应基的第二列，12=14=2/3，22=24=½，32=34=-2/3

max{-,-4/（2/3），-6/（1/2）}

b2

min{+,-4/(-2/3)}

6

b2

6灵敏度分析一览表3、约束条件中的系数变化假设只有一个aij变化。其他数据不变，并且只讨论aij为非基变量的系数的情况。因此，aij的变化只影响一个检验数。当Δaij在什么范围内变化时，不会影响最优解(1)分析什么？(2)怎么分析？最优解不变的充要条件是：其中Y为对偶最优解，yi为Y的第i个分量。为使最优解不变，要使，即例:对最优表如下表对α31进行敏感性分析。解：α31:x1非基4.参数变化后求解新的最优解在管理中经常遇到的问题：当参数变化后，通过灵敏度分析知原最优方案已经不是最优方案。在原有最优生产计划的基础上，怎样最方便地决定新的最优方案？基本思路：利用A’=B-1A，j’

=cBB-1pj

-cj重新计算单纯形表，进行迭代求解。改变资源系数例范例中b2=24时的最优方案解:代入原单纯形表解的一列，得新单纯形表为非优，继续迭代改变非基变量的系数例:在上题基础上改变x1的系数c1=7/2，p=[1,0,2]T解：求解新的单纯形表中系数第一列：代入原单纯形表，得新单纯形表为非优，继续迭代改变基变量系数例范例中改变x1的系数c1=4，p=[1,1,2]T时的最优方案解:代入原单纯形表解的一列，得新单纯形表为非优且无基变量，因此先得到基变量，继续迭代5.增加新变量的灵敏度分析在管理中经常遇到的问题：已知一种新产品的技术经济指标，在原有最优生产计划的基础上，怎样最方便地决定该产品是否值得投入生产？可在原线性规划中引入新的变量；相当于改变了非基变量的系数。无论增加什么样的新变量，新问题的目标函数只能向好的方向变化。6.增加一个新约束的分析当出现新的资源限制时，模型要加入新约束，可在原最优解的基础上进行分析：

最优解满足新约束，最优解不变；

最优解不满足新约束，应继续寻找新的最优解；

无论加入什么类型约束，目标函数值都不会改善。例:考虑范例，如果对甲、乙产品又增加用电不超过24百度的限制，而每件甲、乙分别耗电2、3百度，则原最优生产方案是否需要改变？解：加入新约束为： 2x1+3x2

24， 引入松弛变量x6并令其入基，加入原最优表后得到的不是标准单纯形表，需要通过矩阵的初等变换将其化为标准表，再进一步用对偶单纯形法求解。该厂需要做以下敏感性分析：1.至少生产A产品30件，会有什么变化？2.要留下300公斤原料丙，对生产会有什么样的影响？3. C产品已滞销，不能再生产，会有什么变化？4. 新产品D消耗原料甲3公斤、乙2公斤、丙1公斤，问如何定价工厂才能获利?如果单价定为55元，是否应进行生产？1. 强制生产30件A

x1必须等于30目标值下降;下降程度可用x1的检验数进行计算：

z=x1检验数变化数量=-1530=-450

x2=400-130=370生产B产品370件

x3=50-1/330=40 生产C产品40件

x4=350-5/330=300 甲剩余300公斤新方案生产30件A，370件B，40件C，甲原料剩余300公斤。2. 丙原料剩余300

资源减少300，目标改变量=影子价格资源改变数量：

z=yb=25(-300)=-7500。 还可理解为松弛变量x6300，目标改变量=检验数x6改变数量：

z=6x6=-25300=-7500。

x2=400-1/2300=250生产250件B

x3=50-(-1/6)300=100生产100件C

x4=350-1/6300=300剩300公斤甲3. 产品C不生产

x3=0

x3出基,选转轴系数为正变量入基，x3行中只有x1和x5系数为正。

x1的变化：50/(1/3)=150

x1变化的损失：150(-15)=-2250 x5的变化：50/(1/3)=150

x5变化的损失：150(-10)=-1500

x5变化的损失小，因此令x5入基。

新的方案：只生产B产品400件，原料甲剩余400公斤，原料乙剩余150公斤。4. 新产品D的影子成本为：

ypj=(0)3+(10)2+(25)1=45 销售价格应大于45元/件，每件55元有利可图。按增加一个变量处理：各方案分析汇总表7.灵敏度分析的几何意义目标系数变化

目标线倾角改变；右边项变化

约束线位置平移；在不引起最优解改变的前提下允许变化的范围。x2

x1

4050302x1+x2

5020101020304x1+3x2

120z=50x1+30x2z=40x1+30x2z=60x1+30x2价格发生变化x1的系数可以在40-60范围内变动x2

x1

4050302x1+x2

5020101020304x1+3x2

120z=50x1+30x2z=50x1+37.5x2z=50x1+25x2价格发生变化x2系数可在25-37.5范围内变动x2

x1

4050302x1+x2

5020101020304x1+3x2

120

4x1+3x2150

4x1+3x2100

资源发生变化x2

x1

4050302x1+x2

5020101020304x1+3x2

120

2x1+x2602x1+x240资源发生变化某厂准备生产A、B、C三种产品，它们都消耗劳动力和材料，有关数据见下表。ABC拥有量（单位）劳动力63545材料34530单位产品利润（元）314利用单纯形法求得最优单纯形表为：bX1X2X3X4X5