《管理运筹学》02-6灵敏度分析.pptx

Sensitivity Analysis 第三节 对偶与灵敏度 分析 第3节 对偶与灵敏度分析 2 一、 线性规划的对偶关系 二、 线性规划的对偶性质 三、灵敏度分析 四、对偶关系的经济解释 第3节 对偶与灵敏度分析 灵敏度分析 以前讨论线性规划问题时，假定αij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。 因此，所谓灵敏度分析，是指当线性规划问题中的参数发生变化后，引起最优解如何改变的分析。 灵敏度分析 灵敏度分析是要在求得最优解以后，解决以下几方面的问题： （1）线性规划问题中的各系数在什么范围内变化，不会影响已获得的最优基。 （2）如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解。 （3）当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。 1.目标函数系数C的变化范围 目标函数系数变化，只会影响最优解中检验数行，不会影响基变量的取值。即C中元素的变化只会影响最优解的对偶可行性而不会影响原始可行性。 （1）非基变量在目标函数中系数的灵敏度分析 m个基变量xBr（r=1,2,…,m）在目标函数中的系数为： n-m个非基变量xj在目标函数中的系数为： 因此，当非基变量xk的系数ck 变化成为ck’=ck+ 时，基变量的检验数仍为0。 在最优解中只会影响这个非基变量XK的检验数，其他非基变量的检验数不会变化。 针对目标函数极大化的线性规划问题： ★如果变化后的xk的检验数仍然为非负，则原来的最优基仍保持为最优基。 ★如果变化后的xk的检验数为负数，则原来的最优基不再是最优基，新的最优基可以通过将xk进基，并进行后续的单纯形迭代，得到新的最优基和最优解。 min z= -2x1 +x2 -x3 s.t. x1 +x2 +x3 ≤6 -x1 +2x2 ≤4 x1, x2, x3 ≥0 目标函数 约束条件： 求c2在什么范围内变化，原来的最优基保持不变； 当c2=-3时，最优基是否变化，如果变化，求新的最优基和最优解。 线性规划问题例题 例1 首先用单纯形法得到原问题的最优单纯形表， C -2 1 -1 0 0 z x1 x2 x3 x4 x5 RHS z 1 0 -3 -1 -2 0 -12 x1 -2 1 1 1 1 0 6 x5 0 0 3 1 1 1 10 由于x2在最优单纯形表中是非基变量，因此只影响它本身的检验数 得到 C -2 c2 -1 0 0 z x1 x2 x3 x4 x5 RHS CB z 1 0 -2-c2 -1 -2 0 -12 -2 x1 0 1 1 1 1 0 6 0 x5 0 0 3 1 1 1 10 由于最优解XB=B-1b以及最优解的目标函数值z=CBB-1b与非基变量在目标函数中的系数CN无关，其他变量在目标函数中的系数都不变。x2在目标函数中的系数从原来的值1减少到 -2时，最优基保持不变。相应的单纯形表如下： 当c2=-3时，已经超出保持最优基不变的范围，因此单纯形表不再是最优单纯形表。将c2=-3代入单纯形表，得到以下单纯形表： z x1 x2 x3 x4 x5 RHS z 1 0 1 -1 -2 0 -12 x1 -2 1 1 1 1 0 6 x5 0 0 [3] 1 1 1 10 x2进基 X5离基 得到新的最优解：x1=8/3，x2=10/3，x3=0，x4=0，x5=0，min z=-46/3 z x1 x2 x3 x4 x5 RHS z 1 0 0 -4/3 -7/3 -1/3 -46/3 x1 -2 1 0 2/3 2/3 -1/3 8/3 x2 -3 0 1 1/3 1/3 1/3 10/3 得到最终单纯形表： （2）基变量在目标函数中系数的灵敏度分析 例2： 在下面线性规划问题中，分析c1在什么范围内变化时，原问题的最优基不变。 max z= 2x1 +x2 s.t. 5x2 ≤15 6x1 +2x2 ≤24 X1 +x2 ≤5 x1, x2, ≥0 首先得到以上问题的最优单纯形表： C 2 1 0 0 0 z x1 x2 x3 x4 x5 RHS z 1 0 0 0 1/4 1/2 17/2 x3 0 0 0 1 5/4 -15/2 15/2 x1 2 1 0 0 1/4 -1/2 7/2 x2 1 0 1 0 -1/4 3/2 3/2 当c1’=c1+时，相应的单纯形表为：