运筹学OR1-Ch4-LP灵敏度课件

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

2、，则：*Page 2 of 43 4-1 目标函数系数的变化基变量目标系数Cr的变化Cr是基变量xr的目标系数由此可见， 向小的方向变，不会影响最优解；向大的方向变，其最大值为 。 单纯形表中的检验数为 :由于 是基变量的系数，所以它的变化不仅影响其对应变量的检验数，而且影响到CB的变化，进而影响除基变量之外的所有变量的检验数。 *Page 3 of 43 4-1 目标函数系数的变化基变量目标系数Cr的变化变化后的检验数为：若当前最优基不变，则应有 ，由此得： 其中 为最终单纯形表中对应基变量 的第r行第j列的数值，j=1,n *Page 4 of 43 4-1 目标函数系数的变化基变量目标系

3、数Cr的变化由此得到 的变化范围为： 大于等于负值中最大，小于等于正值中最小； 计算过程可以在单纯形表中完成。 注： ； *Page 5 of 43 4-1 目标函数系数的变化基变量目标系数Cr的变化例4-1：以第一章例1-1为例，求c2的变化范围。其最终单纯形表如下： Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 2 0 3 x1 x5 x2 1 0 1 1/4 0 0 0 2 1/2 1 0 1 1/2 1/8 0 4 4 2 cjzj 0 0 3/2 1/8 0 14 Cj 2 3+C2 0 0 0 CBXB x1 x2 x3 x4 x5 b 2 0 3 +C2

4、x1 x5 x2 1 0 1 1/4 0 0 0 2 1/2 1 0 1 1/2 1/8 0 4 4 2 cjzj 0 0 3/2-1/2C2 1/8+1/8C2 0 14加入C2 *Page 6 of 43 4-1 目标函数系数的变化基变量目标系数Cr的变化若当前最优基不变，则所有检验数仍大于等于零，所以有：基变量 的目标系数 的取值范围为0，4，在此范围内变化，可以不影响当前最优解。 基变量 在目标函数的系数 当前值的可变化范围是： *Page 7 of 43 4-2 右端常数项的变化在单纯形表的最终表中，基变量的取值为： 若b中第r个分量br变化了br，即新的右端项为： 其中： 则变化后

5、的基变量取值为： *Page 8 of 43 4-2 右端常数项的变化若保持当前最优基不变，则应有： 特别注意： 第 个约束右端项 的变化对应于 中的第 列； 相除之后加负号； 大于等于负值中最大，小于等于正值中最小。 *Page 9 of 43 4-2 右端常数项的变化例题例4-2：在例1-1中，求第二个约束条件 的变化范围。 解：设 变化了 ，则变化后的右端常数项为： 最终表中为： 的取值范围为： 的变化范围是8,32。（注 的当前值为16） *Page 10 of 43 4-3 系数矩阵A的变化A中某个 变化范围的确定 假定A中非基列向量Pj的某个分量 变化了 ，其它数字不变。由于 属于

6、非基变量的系数列向量，所以它的变化仅仅影响到该非基变量的检验数 在单纯形最终计算表中，非基变量 的检验数为： 当 变化了 后， 检验数是： *Page 11 of 43 4-3 系数矩阵A的变化列变化因为 ，所以当 时有： 注： 为对应于 中第 列的相应检验数（一般是第 个约束松弛变量的检验数）的负值。 A中某列向量变化后的分析 单纯形方法只需利用下面矩阵运算就能计算出每步迭代时各表中的数字。当其中某些系数发生变化后，也可用这些表达式计算出最终单纯形表中相应的修正数字。 Pj为A中的非基列向量 则Pj的改变仅影响相应变量的检验树，变化后的检验数为：*Page 12 of 43 4-3 系数矩阵

7、A的变化列变化如果 ，则说明 变化后并不影响当前解； 如果 ，则说明 变化后要影响到当前解。Pj为 A中的基列向量因Pj变化后不仅影响变量 的检验数，而且影响到最终表中的 不再是单位列向量，即 和 都要变。这时要做的是求出最终表中 列的数值，并通过迭代使该列恢复单位向量，再根据恢复后的状态予以处理。 *Page 13 of 43 4-3 系数矩阵A的变化列变化例题例4-3：借助第一章例1-1。若计划生产的产品甲的工艺结构有了改进，相应的生产单位产品所需的设备A、B、C的台时由过去的（1，4，0）变为（2，5，2）。试分析已求得的最优计划有何变化？ 解：由于对应于产品甲的决策变量 在上面的最终单

8、纯形表中是基变量，该列在最终表的数字为： 将以上数据取代原单纯形表 列的各相应数据，得下表： *Page 14 of 43 4-3 系数矩阵A的变化列变化例题 Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 2 0 3 x1 x5 x2 5/4 0 1 1/4 0 1/2 0 2 1/2 1 3/8 1 1/2 1/8 0 4 4 2 cjzj 0 3/2 1/8 0 14 Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 2 0 3 x1 x5 x2 1 0 0 1/5 0 0 0 2 2/5 1 0 1 1/2 1/5 0 16/512/5 4/5

9、 cjzj 0 0 3/2 1/5 0 44/5恢复x1列的单位阵*Page 15 of 43 4-3 系数矩阵A的变化列变化特别注意： 以上只是变换后的可能结果之一，变换后的结果还可能是：； 原问题为可行解，对偶问题为非可行解。用单纯形法继续迭代。 原问题为非可行解，对偶问题为可行解。用对偶单纯形法求解。 还可能原问题和对偶问题均为非可行解。这时就要引进人工变量，重新列出单纯形表 进行计算求解。 *Page 16 of 43 4-3 系数矩阵A的变化增加一列A中增加一列的分析例4-4：在例1-1中，若该企业除生产产品甲、乙之外，还有第三种产品丙可供选择。生产产品丙每件需要使用A、B、C设备的

10、台时分别为2、6、3；每件利润5元，问该企业的计划中要不要安排这种产品的生产？若要安排，应生产多少？解：对应产品丙的决策变量记为 分析是否应安排生产产品丙。将产品丙的工艺数据作为列向量，把它当作单纯形表的一列填入，则对应 的检验数为： *Page 17 of 43 4-3 系数矩阵A的变化增加一列可见安排生产产品丙能使目标值增大，故应安排生产。 分析应安排生产的方案 求出在最终单纯形表中的列向量： 将 及其检验数 作为新的一列加入到最终单纯形表中，以 作为进基变量继续迭代。 *Page 18 of 43 4-3 系数矩阵A的变化增加一列 Cj 2 3 0 0 0 5 CBXB x1 x2 x3

11、 x4 x5 x6 b 2 0 3 x1 x5 x2 1 0 1 1/4 0 1.5 0 0 2 1/2 1 2 0 1 1/2 1/8 0 0.25 4 4 2 cjzj 0 0 3/2 1/8 0 1.25 8/328 Cj 2 3 0 0 0 5 CBXB x1 x2 x3 x4 x5 x6 b 2 5 3 x1 x6 x2 1 0 1.5 0.125 0.75 0 0 0 1 0.25 0.5 1 0 1 0.75 1875 0.125 0 1 2 1.5 cjzj 0 0 0.25 0.4375 0.625 0 16.5 由此得到最优解：x1=1，x2=1.5，x6=2，目标值Z=1

12、6.5 *Page 19 of 43 4-3 系数矩阵A的变化增加一行A中增加一行例4-6，仍以例1-1为前提，若企业为了提高产品质量，考虑给产品甲、乙增加一道精加工工序，并在设备D上进行加工。甲、乙两种产品分别需要的加工台时为（2，2.4）。已知设备D的可用工作时间为12个台时，试问增加这道精加工工序以后，对原最优计划方案有何影响？解：增加一道工序等于在原模型中增加了一个约束条件。表达式为：式中x6为松弛变量，并以 x6为基变量，将此约束条件反映在原模型规划问题的最终计算表中，得到表如下： *Page 20 of 43 4-3 系数矩阵A的变化增加一行A中增加一行（续） Cj 2 3 0 0

13、 0 0 CBXB x1 x2 x3 x4 x5 x6 b 2 0 3 0 x1 x5 x2 x6 1 0 1 1/4 0 0 0 0 2 1/2 1 0 0 1 1/2 1/8 0 0 2 2.4 0 0 0 1 4 4 2 12 cjzj 0 0 3/2 1/8 0 0 14由此所产生的结果是原基变量的列向量不在是单位列向量。因此，首先将其恢复为单位列向量，结果如下表： *Page 21 of 43 4-3 系数矩阵A的变化增加一行A中增加一行（续） Cj 2 3 0 0 0 0 CBXB x1 x2 x3 x4 x5 x6 b 2 0 3 0 x1 x5 x2 x6 1 0 1 1/4

14、0 0 0 0 2 1/2 1 0 0 1 1/2 1/8 0 0 0 0 1.2 0.2 0 1 4 4 20.8 cjzj 0 0 3/2 1/8 0 0 14 5/4 5/8由于 b 列存有负值，原问题为非可行解，用对偶单纯形法求解，为出基变量，根据 规则确定 为进基变量，继续迭代求解如下： *Page 22 of 43 4-3 系数矩阵A的变化增加一行A中增加一行（续） Cj 2 3 0 0 0 0 CBXB x1 x2 x3 x4 x5 x6 b 2 0 3 0 x1 x5 x2 x4 1 0 1 0 0 1.25 0 0 2 0 1 2.5 0 1 1/2 0 0 0.625 0

15、0 1.2 1 0 5 3 2 2.5 4 cjzj 0 0 3/2 1/8 0 0 13.5 由此得到最优解：x1=3，x2=2.5，由此得最大利润 Z=13.5元。 *Page 23 of 43 4-3 系数矩阵A的变化总结总结从上面的分析可以体会到：只要知道初始的和最终的单纯形表，就可以利用 计算出每一步的数据以及最初数据变化后的数据。从分析过程还可以看出： 若修正后的原问题与对偶问题的解都是可行解，则修正后的解仍是可行解； 若出现原问题是可行解，对偶问题是非可行解，则按单纯形法继续迭代求出最优解； 若对偶问题是可行解，原问题是非可行解，则按对偶单纯形法继续求出最优解； 若原问题与对偶问

16、题的解均是非可行解，这时就要引入人工变量，建立新的单纯形表重新计算。 *Page 24 of 43 4-4 Excel灵敏度报告和影子价格敏感性分析就是研究规划模型在其部分数据发生改变的前提下对最优方案的影响。敏感性分析涉及很多内容，所给问题模型中的每一个数据都有敏感性问题，在这里仅讨论资源约束的右端项的敏感性分析。约束的影子价格重新考虑上述案例2的GTC问题，根据该问题的Excel分析表可以看到：最优方案为：W=12,P=9;目标利润=$2460注意到钢材约束的RHS为27，而实际消耗也为27，即为等式；假如现在又得到了1千磅的钢材，那么目标利润会增加多少呢？*Page 25 of 43 约

17、束的敏感性分析和影子价格在Excel表格中做出处理，将钢材约束的RHS由27该为28，重新求解得到新解：W=14,P=7,目标利润=$2520目标利润的增加量为：25202460=$60也就是说，钢材增加1个单位量，目标函数值就增加$60定义：影子价格就是某个约束的右端项增加一个单位所引起的目标函数值的增量。（注：其它数据保持不变）即钢材的影子价格为60，同样的方法可以求的其它右端项的影子价格如下表（阴影价格）GTC问题的影子价格约束影子价格钢材60模型40装配0W-需求量0P-需求量0*Page 26 of 43 约束的敏感性分析和影子价格从Excel表格中获得影子价格手工计算影子价格只能是远离说明的一种演示，对于较复杂的实际问题用手工计算往往是不可行的。而在Excel电子表各种或其他规划软件中都可以很方便地得到影子价格和敏感性分析信息。从Excel中获得影子价格的步骤如下：用规划求解功能选项求解规划模型；当显示求解结果窗口时，在其右端的报告选项框中选定敏感性报告，点击OK完成，并出现敏感性报告单，其中下部