第2章 线性规划(灵敏度分析).ppt

《第2章 线性规划(灵敏度分析).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章灵敏度分析线性规划续知识点熟悉灵敏度分析概念和内容；分别掌握限制常数、价值系数、约束条件系数的变化对原最优解的影响；掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素的灵敏度范围。灵敏度分析问题的提出：系数（aij,bi,cj）往往是估计值和预测值，且不是稳定的。当系数中的一个或几个发生变化时，已求得的规划问题的最优解会发生什么变化？如果最优解发生了变化，又怎样用最简便的方法找到新的最优解？解决这些问题就是灵敏度分析的任务。价值系数c的变化对于LP：maxZ=CTXS.t.AX=b,X0当从最终的单纯形表上得到最优基B时，其最优结果为：(XBT,X

2、RT)=(B-1bT,0T)MaxZ=CBTB-1b相应的检验数为：=(z-c)=CBTB-1A-C其中：基变量的检验数为0，非基变量的检验数为：R=CBTB-1R-CRT第j个为：j=(zj-cj)=CBTB-1Pj-cj(1)非基变量系数cj的变化设cj’=cj+c，则有：j’=CBTB-1Pj-(cj+cj)=j-cj这时，若cjj，原最优解保持不变。若cj>j,则原最优解就不再是最优的了，这时要以为xj换入变量，把最终单纯形表上的j换成j’，cj换成cj’，继续迭代，以求最优解。例：P6，例１中，最终单纯形表为：cj43000C

3、BXBbx1x2x3x4x5034x5x2x1200600200000.5-0.41011-0.4010-0.50.40zjzj-cj26004310.400010.40x４（剩余工时）的价值系数c4的变化范围为：0~0.4。当c4的变化超过0.4时，就要重新计算。(2)基变量的价值系数cl的变化：这种情形下，cl是CB的一个分量，当cl变化了cl后，就会引起CB改变CB，从而引起最终单纯形表中全部非基变量的检验数和目标函数值的变化。改变以后的非基变量的检验数为：j’=(CB+CB)TB-1Pj-cj=j+CBTB-1Pj=j+clalj’其中，alj

4、’是非基变量xj在基变量为xl时该行的系数。若：则所有的j’0，即最优解不变。例：在汽车生产的例子中，如果x2的价值系数由3变成3+c2，要使最优解不变，求c2的取值范围。1+c200.4-0.4c20从而：-1c21cj43+c2000CBXBbx1x2x3x4x503+c24x5x2x1200600200000.5-0.41011-0.4010-0.50.40zjzj-cj2600+600Δc243+Δc21+Δc20.4-0.4Δc20001+Δc20.4-0.4Δc20直接按公式：约束方程常数项b的变化设第k个约束方程的右端常数项

5、由原来的bk变为bk’=bk+Δbk，其它系数不变。设原最优解为：XB=B-1b=(XB1,…,XBm)T若原最优基B仍是最优的，则新的最优解满足：X’B=B-1b’=B-1b+B-1Δb=XB+ΔbkDk0式中，Dk是B-1的第k列，有：Dk=(d’1k,…,d’mk)T从而最优解可写成：XBi+Δbkd’ik0因此，bk的允许变动范围是：如果bk超过上述范围，则新得到的解为不可行解。但由于bk的变化不影响检验数，故仍保持所有的检验数I0，即满足对偶可行性，这时，可在原最优表的基础上，换上改变后的常数及相应的Z值，用对偶单纯形法迭代，以求出新的最优解。例：

6、生产汽车用的钢材由1600吨变成1600+b1吨，则问题变为：0.5-0.411600+Δb12000.5X=B-1b=1-0.402500=600+1Δb1-0.50.40400200-0.5为了使最后的解仍为可行解，应满足各分量为正。200+0.5Δb10600+Δb10200-0.5Δb10从而：-400Δb1400根据公式：k:B-1的第k列i:第k列的第i个元素如果b1’=1800；最优解不变，直接求X’BX’B=B-1b’如果b1’=2200cj43000CBXBbx1x2x3x4x5034x5x2x15001200-100000.5-0

7、.41011-0.4010-0.50.40zjzj-cj32004310.400010.40用对偶单纯形法求解得cj43000CBXBbx1x2x3x4x5030x5x2x34001000200100012100.40-201-0.80zjzj-cj30006301.202001.20技术系数变化的影响当aij是非基变量的系数时，它的变化不会引起B-1的变化，所以计算相对容易；当aij是基变量的系数，它的变化会引起B-1的变化，所以最终单纯形表也要发生变化。例：假定生产大轿车所用的钢材由2吨/辆变成3吨/辆，求最优解的变化。解：a11由2变成3，x