运筹学第7讲 线性规划的对偶理论和灵敏度分析3

1、运 筹 学（Operations Research）上 海 海 事 大 学 20131009任课教师：邓 伟邮 箱：灵敏度分析灵敏度分析在前面的讨论中，都认为线性规划模型中的各个系数都是确定的常数，但是实际上由于多种原因，这些系数有时很难确定，一般都是估计量。所以，在对问题求解之后，需要对这些估计量进行一些分析，以决定是否需要调整。另外，周围环境的变化也会使模型中的系数发生变化，这些系数很可能会影响已求得的最优解。因此，在解决实际问题时，只求出最优解是不够的，一般还需要研究最优解对变化的反映程度，以使决策者全面地考虑问题，以适应各种偶然的变化，这就是灵敏度分析(Sensitivity Anal

2、ysis)所研究的内容。灵敏度分析灵敏度分析对于上述变化，如果将问题从头进行计算求解，当然是一种方法，但是这种方法比较麻烦而且也得不到很多有用的信息。灵敏度分析采用的方法，是从已得到的最优解出发，通过对变化数据进行一些简单的计算，便可迅速得到所需要的结果，以及变化后的最优解。因此，灵敏度分析也称为优化后分析。灵敏度分析灵敏度分析在进行灵敏度分析之前，先给出将要用到的一些矩阵表达式和向量表达式。在讨论线性规划的对偶性质时，已经给出了以矩阵形式表示的检验数其中B为可行基，设B=(P1,P2,Pm),N=(Pm+1 ,Pn),Pj为系数矩阵A的第j列向量，CB，CN分别表示为基变量和非基变量的目标函

3、数系数向量，CB是m维，CN为n-m维。1.检验数的向量表示1NNBCC B N灵敏度分析灵敏度分析的展开形式为因此得到检验数的向量表示为N111111111111(,)(,)(,)(,)(,)(,)NmnmnBmnmnBmBnmBmnBnccC BPPccC B PC B PcC B PcC B P1,1,jjBjcC B P jmn若令 ， 则得到检验数的另一向量表示形式:1TBYC B,1,TjjjcY P jmn灵敏度分析灵敏度分析2.基本解的矩阵表示由矩阵B对应的典式形式，可以得到基本解的矩阵表示为10BNXB bXX其对应的目标函数值为1BZC B b研究最优解受数据变化的影响情况

4、主要考虑两个方面:一是解的最优性，即检验数是否仍然非正;一是解的可行性，即基本解的各个分量是否非负。 灵敏度分析灵敏度分析 目标函数系数的变化假设只有一个系数 ，其他系数均保持不变。 jcjc的变化只影响检验数，而不影响解的非负性。下面分别就 是非基变量系数和基变量系数两种情况进行讨论。jc 1. 是非基变量的系数jc根据检验数的向量表示1,1,jjBjcC B P jn 非基变量的系数 的变化，只影响与 有关的一个检验数 的变化，对其他 没有影响，故只需考虑 。kckcjjk灵敏度分析灵敏度分析 目标函数系数的变化 1. 是非基变量的系数jc1kk1kkk(cc )cccBkBkC B PC

5、 B Pkkk+k设 变为 ，即 为该变量，此时 的变化为kckc,kkkkkccccck为了保持最优解不变， 必须满足 ，即k0kkckkkkkkc,cccc kk=+由此可知 为 变化的上限。当 变化超过此上限时，最优解将发生变化，此时应求出新的检验数 的值。取 为进基变量，继续迭代求新的最优解。 kckckkx灵敏度分析灵敏度分析 目标函数系数的变化 2. 是基变量的系数lc根据检验数的构成形式，当 为基变量的系数时，它的变化将使n-m个非基变量的检验数都发生变化。（可以证明: 此时仍保证基变量的检验数为零。）设 为改变量，记m维向量lcllllccc , c+lC=(0,0, c ,0

6、,0)此时有1llCC(0 ,c ,0 )cjm jljaaa - 1jjjBj- 1- 1jBjjjj= c - ( C+) BP , jl= cCBPBP其中 为构成lja -1jBPl的第 个分量。灵敏度分析灵敏度分析 目标函数系数的变化 2. 是基变量的系数lc为使最优解不变，要保证n-m个 ，即要使下面不等式同时成立:0j(0)(0)jlljljjlljljcaacaamax|0min|0jjljlljljljacaaa 即:灵敏度分析灵敏度分析 目标函数系数的变化 2. 是基变量的系数lc此即为保持最优解不变 的变化范围，当 超过此范围时，应求出n-m个新检验数 ，选择其中大于零的

7、检验数对应的变量为进基变量，继续迭代求新的最优解。lclcj灵敏度分析灵敏度分析 目标函数系数的变化例 7.1 下面线性规划模型的实际背景为： 某工厂用两种设备生产3种产品，目标函数为求最大利 润(单位：元)123123123123max20121084760033400,0zxxxxxxxxxx x x此规划的最优单纯形表如下，其中 为引入的松弛变量。45,x x灵敏度分析灵敏度分析 目标函数系数的变化123123123123max20121084760033400,0zxxxxxxxxxx x x由表可知，最优解为生产第1种产品10件，第2种产品130件，不生产第3种产品，最大利润为176

8、0元。现对目标函数系数c3=10和c1=20进行灵敏度分析。灵敏度分析灵敏度分析 目标函数系数的变化这就是说，当第3种产品的单位利润 时，不宜安排生产它，只有在它的利润大于19.2时，生产第3种产品才能变得有利可图。解 (1)c3是非基变量的目标系数。设 ，根据上面的分析，当时，最优解保持不变，仍为非基变量。3333cc =c + c333cc - =10+9.2=19.23c19.2灵敏度分析灵敏度分析 目标函数系数的变化下面进一步考虑当 超过19.2时，如何在最优表上求出新的最优解。3c设 此时有102033c， c =109.2 100.803333c现在要用0.8替换检验数 ，并以 为

9、进基变量进行迭代，求新最优解。9.2 3x3新最优解为（0,1000/9,200/9）T,最优值为1777元。这说明当 变为20后，应该调整产品结构，不再生产第1种产品而生产第2、3种产品，并且最大利润比原最优值增加了17元。3c灵敏度分析灵敏度分析 目标函数系数的变化灵敏度分析灵敏度分析 目标函数系数的变化 (2) cl是非基变量的目标系数。设1111,jjcccc 根据前面的分析和理论推导，为保持最优基不变，应使下列不等式成立:31415199 .202 032 .402 010 .805ccc 解得:1164c 灵敏度分析灵敏度分析 目标函数系数的变化由于 所以为保持最优解不变，应该有

10、当 超过此范围时， 就是使检验数 中的某一个大于零，此时要取相应的变量为进基变量，进行迭代，求新的最优解。 lc = 2 0 ，24cll4ccc345、 、例如: 当 时， 此时: 25lc5lc，34599 .251 1 .4 52 032 .453 .1 52 010 .850 .25 灵敏度分析灵敏度分析 目标函数系数的变化因为 不满足最优性准则，应将求出的 替换相应的检验数，并以 为进基变量，迭代求新的最优解。 50，345、 、5x灵敏度分析灵敏度分析 目标函数系数的变化新最优解为(75,0,0)T,最优值为25*75=1875元，这说明，当c1变为25以后，不再生产第2种产品，只

11、生产第1种产品，最大利润为1875元，比原方案利润增加了115元。 灵敏度分析灵敏度分析 右端常数的变化假设只有一个常数br 变化，其他数据均保持不变。 br的变化将会影响解的可行性，但不会引起检验数的符号变化。根据基本可行解的矩阵表示，XB=B-1b，所以，只要br变化必定引起最优解的数值发生变化，但最优解的变化分为两类：一类是保持B-1b0，最优基B不变；一类是B-1b 中出现负分量，这将使最优基B变化。 灵敏度分析灵敏度分析 右端常数的变化若最优基不变，则只需将变化后的br代入XB的表达式重新计算即可；若B-1b 出现负分量，则要通过迭代求新的最优基和最优解。1111111,00rrrr

12、rBBrrrrrBrrmrmmrbbbbbbXXBBbBbbbbmbXbbb 设为 改 变 量 ， 此 时 有灵敏度分析灵敏度分析 右端常数的变化其中 为原最优解， 为 的第i个分量， 为 的第i行第r列元素。为了保持最优基不变，应使 即BXib BXir-1B0BX ，1100rrmmrbbb 据此，可导出m个不等式0,1,2,irirbbim由此， 应满足右边式子rbmax|0min|0iiirriririrbbb 当 超过此范围时，应使最优解中某个分量小于零，使最优解发生变化。此时，可用对偶单纯形法继续迭代求新的最优解。rb灵敏度分析灵敏度分析 右端常数的变化例7.2 对例7.1中的b1

13、进行灵敏度分析。解 由上面的最优单纯形表可以看出，最优解XB和B-1的值为1B103/201/5X =,1301/202/5B设 为保持最优基不变，应使下式成立 111bbb ，11103/201/5001301/202/500bb -1BX +B整理后解出 1200/32600b 1b在此范围内，最优基保持不变。 灵敏度分析灵敏度分析 右端常数的变化设 求新最优解。此时 没有超出上面的变化范围，最优基不变，所以不用迭代，可直接计算: 1600540b ，160b ，11103/201/560101301/202/50133BBbXXB 新最优解为 此时最优值为 20*1+12*133=161

14、6比原最优值1760减少了144元。利用影子价格的概念，也可以直接用 *X(1,133,0) .T11*60 2.4144b y 得出总利润的减少量。灵敏度分析灵敏度分析 右端常数的变化设 求新最优解。此时 超出了上面解出的 的变化范围，最优基变化，需要迭代求新的最优解:其中出现了负的分量，破坏了解的可行性，现在用 替换单纯形表中的最右侧列元素，用对偶单纯形法继续迭代。1b =60032201b =2620，1bB103/20403X =26201301/20-1403-1灵敏度分析灵敏度分析 右端常数的变化得到新的最优解为（400,0,0）T，最优值为20*400=8000，比原目标值1760增加了6240.注: 此时这个总利润增量不能用影子价格 与 直接相乘得到，因为 已经超出了规定的变化范围，影子价格可能已发生变化了。y1*1b1b灵敏度分析灵敏度分析 约束条件中的系数变化假设只有一个系数aij 变化，其他系数均保持不变，并且只讨论aij 为非基变量xj的系数的情况。因此, aij 的变化只影响一个检验数 。 设 为改变量。由检验数的另一种表示形式 j,ijijijijaaaa1*00jTTTjijijjjjjjiijijmjaaacYcY PYy aaa其中 为对偶最优解， 为 的第 个分量。 Y*iyYi灵敏度分析灵敏