运筹学 第2版 教学课件 作者 孔造杰OR1-Ch4-LP灵敏度.ppt

《运筹学 第2版 教学课件 作者 孔造杰OR1-Ch4-LP灵敏度.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章LP灵敏度分析SensitivityAnalysisofLP§4-1目标函数系数的变化§4-2右端常数项的变化§4-3系数矩阵A的变化§4-4灵敏度报告和影子价格§4-1目标函数系数的变化通过单纯形方法或计算软件求得了LP问题的最优解，应该明确所得到的最优解是在系数项A、b、C的当前值条件下得到的。当其中某一个系数发生改变时会对当前最优解产生怎样的影响则是本章所要研究的内容。首先讨论目标函数系数C的变化所产生的影响。Cj是非基变量xj的目标系数由单纯形方法可知，非基变量的目标系数cj的变化仅仅影响到xj的检验数。非基变量xj的检验数为：当变化了后：如果变

2、化后当前最优解不变，则：2021/9/192河北工业大学管理学院孔造杰制作§4-1目标函数系数的变化——基变量目标系数Cr的变化Cr是基变量xr的目标系数由此可见，向小的方向变，不会影响最优解；向大的方向变，其最大值为。单纯形表中的检验数为:由于是基变量的系数，所以它的变化不仅影响其对应变量的检验数，而且影响到CB的变化，进而影响除基变量之外的所有变量的检验数。2021/9/193河北工业大学管理学院孔造杰制作§4-1目标函数系数的变化——基变量目标系数Cr的变化变化后的检验数为：若当前最优基不变，则应有，由此得：其中为最终单纯形表中对应基变量的第r行第j列的

3、数值，j=1,…,n2021/9/194河北工业大学管理学院孔造杰制作§4-1目标函数系数的变化——基变量目标系数Cr的变化由此得到的变化范围为：②大于等于负值中最大，小于等于正值中最小；③计算过程可以在单纯形表中完成。注：①；2021/9/195河北工业大学管理学院孔造杰制作§4-1目标函数系数的变化——基变量目标系数Cr的变化例4-1：以第一章例1-1为例，求c2的变化范围。其最终单纯形表如下：Cj23000CBXBx1x2x3x4x5bθ203x1x5x21011/4000－21/21011/2－1/80442cj－zj00－3/2－1/8014Cj23

4、+△C2000CBXBx1x2x3x4x5bθ203+△C2x1x5x21011/4000－21/21011/2－1/80442cj－zj00－3/2-1/2△C2－1/8+1/8△C2014加入△C22021/9/196河北工业大学管理学院孔造杰制作§4-1目标函数系数的变化——基变量目标系数Cr的变化若当前最优基不变，则所有检验数仍大于等于零，所以有：∴基变量的目标系数的取值范围为[0，4]，在此范围内变化，可以不影响当前最优解。∴基变量在目标函数的系数当前值的可变化范围是：2021/9/197河北工业大学管理学院孔造杰制作§4-2右端常数项的变化在单纯形

5、表的最终表中，基变量的取值为：若b中第r个分量br变化了Δbr，即新的右端项为：其中：则变化后的基变量取值为：2021/9/198河北工业大学管理学院孔造杰制作§4-2右端常数项的变化若保持当前最优基不变，则应有：特别注意：①第个约束右端项的变化对应于中的第列；②相除之后加负号；③大于等于负值中最大，小于等于正值中最小。2021/9/199河北工业大学管理学院孔造杰制作§4-2右端常数项的变化——例题例4-2：在例1-1中，求第二个约束条件的变化范围。解：设变化了，则变化后的右端常数项为：最终表中为：的取值范围为：的变化范围是[8,32]。（注的当前值为16）

6、2021/9/1910河北工业大学管理学院孔造杰制作§4-3系数矩阵A的变化A中某个变化范围的确定假定A中非基列向量Pj的某个分量变化了，其它数字不变。由于属于非基变量的系数列向量，所以它的变化仅仅影响到该非基变量的检验数在单纯形最终计算表中，非基变量的检验数为：当变化了后，检验数是：2021/9/1911河北工业大学管理学院孔造杰制作§4-3系数矩阵A的变化——列变化因为，所以当时有：注：为对应于中第列的相应检验数（一般是第个约束松弛变量的检验数）的负值。A中某列向量变化后的分析单纯形方法只需利用下面矩阵运算就能计算出每步迭代时各表中的数字。当其中某些系数发

7、生变化后，也可用这些表达式计算出最终单纯形表中相应的修正数字。Pj为A中的非基列向量则Pj的改变仅影响相应变量的检验树，变化后的检验数为：2021/9/1912河北工业大学管理学院孔造杰制作§4-3系数矩阵A的变化——列变化如果，则说明变化后并不影响当前解；如果，则说明变化后要影响到当前解。Pj为A中的基列向量因Pj变化后不仅影响变量的检验数，而且影响到最终表中的不再是单位列向量，即和都要变。这时要做的是求出最终表中列的数值，并通过迭代使该列恢复单位向量，再根据恢复后的状态予以处理。2021/9/1913河北工业大学管理学院孔造杰制作§4-3系数矩阵A的变化—

8、—列变化例题例4-3：借助第一章例1-