管理运筹学灵敏度分析.ppt

《管理运筹学灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、SensitivityAnalysis第三节对偶与灵敏度分析第3节对偶与灵敏度分析2一、线性规划的对偶关系二、线性规划的对偶性质三、灵敏度分析四、对偶关系的经济解释第3节对偶与灵敏度分析灵敏度分析以前讨论线性规划问题时，假定αij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。因此，所谓灵敏度分析，是指当

2、线性规划问题中的参数发生变化后，引起最优解如何改变的分析。灵敏度分析灵敏度分析是要在求得最优解以后，解决以下几方面的问题：（1）线性规划问题中的各系数在什么范围内变化，不会影响已获得的最优基。（2）如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解。（3）当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。1.目标函数系数C的变化范围目标函数系数变化，只会影响最优解中检验数行，不会影响基变量的取值。即C中元素的变化只会影响最优解的对偶可行性而不会影响原始可行性。（

3、1）非基变量在目标函数中系数的灵敏度分析m个基变量xBr（r=1,2,…,m）在目标函数中的系数为：n-m个非基变量xj在目标函数中的系数为：因此，当非基变量xk的系数ck变化成为ck’=ck+时，基变量的检验数仍为0。在最优解中只会影响这个非基变量XK的检验数，其他非基变量的检验数不会变化。针对目标函数极大化的线性规划问题：★如果变化后的xk的检验数仍然为非负，则原来的最优基仍保持为最优基。★如果变化后的xk的检验数为负数，则原来的最优基不再是最优基，新的最优基可以通过将xk进基，并进行后续的单纯形迭代，

4、得到新的最优基和最优解。minz=-2x1+x2-x3s.t.x1+x2+x3≤6-x1+2x2≤4x1,x2,x3≥0目标函数约束条件：求c2在什么范围内变化，原来的最优基保持不变；当c2=-3时，最优基是否变化，如果变化，求新的最优基和最优解。线性规划问题例题例1首先用单纯形法得到原问题的最优单纯形表，C-21-100zx1x2x3x4x5RHSz10-3-1-20-12x1-2111106x500311110由于x2在最优单纯形表中是非基变量，因此只影响它本身的检验数得到C-2c2-100zx1x2x3

5、x4x5RHSCBz10-2-c2-1-20-12-2x101111060x500311110由于最优解XB=B-1b以及最优解的目标函数值z=CBB-1b与非基变量在目标函数中的系数CN无关，其他变量在目标函数中的系数都不变。x2在目标函数中的系数从原来的值1减少到-2时，最优基保持不变。相应的单纯形表如下：当c2=-3时，已经超出保持最优基不变的范围，因此单纯形表不再是最优单纯形表。将c2=-3代入单纯形表，得到以下单纯形表：zx1x2x3x4x5RHSz101-1-20-12x1-2111106x500

6、[3]11110x2进基X5离基得到新的最优解：x1=8/3，x2=10/3，x3=0，x4=0，x5=0，minz=-46/3zx1x2x3x4x5RHSz100-4/3-7/3-1/3-46/3x1-2102/32/3-1/38/3x2-3011/31/31/310/3得到最终单纯形表：（2）基变量在目标函数中系数的灵敏度分析例2：在下面线性规划问题中，分析c1在什么范围内变化时，原问题的最优基不变。maxz=2x1+x2s.t.5x2≤156x1+2x2≤24X1+x2≤5x1,x2,≥0首先得到以上问

7、题的最优单纯形表：C21000zx1x2x3x4x5RHSz10001/41/217/2x300015/4-15/215/2x121001/4-1/27/2x21010-1/43/23/2当c1’=c1+时，相应的单纯形表为：C2+1000Zx1x2x3x4x5RHSz10001/4+/41/2-/217/2+7/2x300015/4-15/215/2x12+1001/4-1/27/2x21010-1/43/23/2C2+1000Zx1x2x3x4x5RHSz10001/4+/41/2-/2

8、17/2+7/2x300015/4-15/215/2x12+1001/4-1/27/2x21010-1/43/23/2为了表中解为最优，应有，1/4+/4≥0，1/2-/2≥0因此-1≤≤1，即当1c13时，最优基保持不变。当c1的变化超出以上范围时，至少会使一个检验数zj-cj<0，用单纯形法继续运行，就可以得到新的最优基和最优解。2、常数项的灵敏度分析当右边常数向量b发生变化，成为