第5讲 灵敏度分析.docx

第5讲灵敏度分析灵敏度分析是指对系统因环境变化显示出来的敏感程度的分析性规划问题中讨论灵敏度分析，目的是描述 一种能确定线性规划模型结构中元素变化对问题解的影响的分析方法前面的讨论都假定价值系数、资源系数和技术 系数向量或矩阵中的元素是常数，但实际上这些系数往往只是估计值，不可能十分准确和一成不变这就是说，随着 时间的推移或情况的改变，往往需要修改原线性规划问题中的若干参数因此，求得线性规划的最优解，还不能说问 题已得到了完全的解决决策者还需要获得这样两方面的信息：一是当这些系数有一个或几个发生变化时，已求得的 最优解会有什么变化；二是这些系数在什么范围内变化时，线性规划问题的最优解（或最优基）不变显然，当线性 规划问题中的某些量发生变化时，原来已得的结果一般会发生变化在单纯形法迭代时，每次运算都和基B有关，所 以可以把发生变化的量经过一定计算，直接反映进最终单纯形表并按表5-1处理表5-1原问题对偶问题结论或继续计算的步骤可行解可行解最优解可行解非可行解用单纯形法求解最优解非可行解可行解用对偶单纯形法求解最优解非可行解非可行解引入人工变量求解最优解4.1资源系数变化的分析资源系数发生变化，即b发生变化的灵敏度分析；该类问题关键是如何将b的变化直接反映进原问题的最终单纯 形表。

单纯形法的迭代过程，其实不过就是矩阵的初等变换过程；而线性代数的知识告诉我们，对分块矩阵B I」 进行初等变换，当矩阵B变为单位矩阵I时，单位矩阵I将变为矩阵B-1，即：I B-1」由此可知，如果已知最终单纯形表中基可行解所对应的基“ B ”（最终单纯形表中的基变量在初始单纯形表中的列 向量所构成的矩阵），即可在最终单纯形表中找到“ B-1 ”（初始单纯形表中的单位矩阵I在最终单纯形表中所对应的 矩阵），而最终单纯形表中的每一列均可用其在初始单纯形表中的相应列左乘B-1来得到；即b' = B-1b［例5-1］已知LP问题x+ 2 x+ x+ x = 512342 x—x +3x+ x = 21235x・,x ,x ,x , x> 0123451 2 3 4 5单纯形求解可得如表5-1所示的最终单纯形表，问⑴b2在什么范围内变化时，最优解（在此实际上是最优基）min w = -5 x —12 x — 4 x + 0 x + Mx保持不变；（2）b2由2增加至15,求新的最优解表 3-11为保持最优解不变，应有b f> 0，即： f > 0，虹蚂> 0，5 5所以有气的变化范围应在［二，10］之内。

解（2）：将b2 = 15直接反映进最终单纯形表，得表3-122 , 「2/5 -1/5一b =1/5 2/5-115c.-5 -12 -4 0 MbCJ X,x, x° x， x, x.B-12 -5Bx2x,1 2 3 4 50 1 -1/5 2/5 -1/51 0 7/5 1/5 2/58/59/51b0 0 -3/5 -29/5 2/5-Mw=-141/5解（1）：给b 一个增量Ab并利用b' = B-1b将变化直接反映进最终单纯形表2 2「2/5-1/51「 5 18-Abb =1/52/52 + Ab=5 z9+2 AhL 2」25表 3-12C.-5-12-40MbCBX”xx.x?x4x.-12Bx2x110213-1/542/55-1/5-1-5107/51/52/571 b.00-3/5-29/52/5-Mw=-23利用对偶单纯形法继续迭代，可得如表3-13所示的新的最优解表 3-13c.-5-12-40MbC/ xcxzx.x.x.x_-fBx3 x.102-5314-2515-51703-101 b.0-30-71-Mw=-20j4.2价值系数变化的分析将原迭代过程继承下来，价值系数的变化只会对最终单纯形表中的检验数发生影响，而与其他量无关。

因此，将 变化的价值系数反映进最终单纯形表，只需对检验数行进行修正［情况1］价值系数发生变化的变量在最终单纯形表中为非基变量价值系数发生变化的变量在最终单纯形表中为非基变量，所以将变化的价值系数反映进最终单纯形表只会影响此 变量自身的检验数，而与其他变量的检验数无关［例3-7］已知LP问题min w = -2x - 3x - x + 0x + 0x{x + x + x + x = 3气 + 4 x2 +7 x + x = 9x , x , x , x , x > 01 2 3 4 5单纯形求解可得如表3-14所示的最终单纯形表，问（1）%在什么范围内变化时，最优解保持不变；（2）%由“-1” 减少至“-6”，求新的最优解 3 3解（1）：由于x3在最终单纯形表中是非基变量，因此匕的变化只会影响x3自身的检验数b/而与其他变量的检 验数无关计算变化后的b3并令其非负，即可求得保持最优解不变％的变化范围表 3-14c.-2-3-100bCB'Xbx1x2x3x4x5BBx1x~11203-144/35 -1/31-3012-1/31/322b.0035/31/3w=-8b 3 *3-（-2，-3［ 2 尸％+ 4 > 0C3 >-4，即只要C3 >-4，就可以保持最优解不变。

解（2）：将C3 =-6直接反映进最终单纯形表，用单纯形法继续迭代即可得到新的最优解，过程见表3-15表 3-15c.-2-3-600bCjx„xzx.x.x.x_BBx1x^11203-144/35-1/31-301⑵-1/31/32b.200-25/31/3w=-8-2jx1 x?11/207/6-1/62-601/21-1/61/61b.30104/32/3w=-10j［情况2］价值系数发生变化的变量在最终单纯形表中为基变量因为基变量的价值系数发生变化会引起CB的变化，进而可能引起整个检验数行的变化［例3-8］对于例3-7中的线性规划问题，问：（1）气在什么范围内变化时，最优解保持不变；（2）气由“-2”减少至“-6”，求新的最优解 1 1表 3-16c.-6 -3 -1 0 0bCB'X.X, X, X? X, X5-6-3B x1 x12 3 4 51 0 -1 4/3 -1/30 1 [2] -1/3 1/312匕°,0 0-17 -1w=-12-6-1Jx1 x 1 1/2 0 7/6 -1/60 1/2 1 -1/6 (1/6)21°0 1/2 0 41/6 -5/6w=-13-6 0JxX-111 1 00 3 6 -1 1365°0 3 5 6 0w=-18 j 解（1）：由最终单纯形表（表3-10）可知，为保持原最优解不变应有:一 一 5 一 一 一° 3 =T 一邕,一3)2 =七+5 > 0 — c >-5I 2 )° 4 = 0 — (c1 '—3)]— 1/3I J)〔SiI)=—4 c — 1 > 0 r c < — 3=1 c1 +1 > 0 r c1 >-3即保持原最优解不变应有c1 e ［—3'— 了］。

解（2）：将气=-6直接反映进最终单纯形表，用单纯形法继续迭代即可得到新的最优解，过程见表3-164.3技术系数变化的分析如果将原迭代过程继承下来，我们就可以通过B -1将技术系数的变化反映进最终单纯形表需要强调的是，如果 发生变化的变量在最终单纯形表中为非基变量，那么只需在将变化反映进最终单纯表后，重新计算该非基变量的检验 数即可完成对问题的求解；如果发生变化的变量在最终单纯形表中为基变量，那么必须在将变化反映进最终单纯表后， 首先围绕该变量进行初等变换，将该基变量的列向量变为单位向量，再重新计算各个变量的检验数，才能完成对问题 的求解［情况1］技术系数发生变化的变量在最终单纯形表中为非基变量—1/3丫 1 i1/3 J〔>—223° 3 = c3 — CB -1P = —1 — (—2'—3)［例3-9］对于例3-7中的线性规划问题，问a在什么范围内变化时，最优解保持不变〔-1/3° = 1 a + 2 > 0 -r a3 3 23 3即保持原最优解不变应有a23 e ［-2,+8］［情况2］技术系数发生变化的变量在最终单纯形表中为基变量由于基变量的技术系数发生了变化，将变化的量反映进最终单纯形表，必将破坏基变量在最终单纯形表中的单位 向量形式；为获得变化后新问题的基解，必须首先将基变量对应的列向量转化为单位向量。

转化后的结果可能是原问 题与对偶问题都可行，也可能是原问题和对偶问题只有之一是可行的，还可能原问题与对偶问题均不可行；然而无论 出现哪种结果，我们均可按表3-10进行处理［例3-10］对于例3-7中的线性规划问题，问当a11由1变为3时，原最优解是否发生改变，如果改变求新的最优 解解：首先将变化反映进最终单纯形表，形成表3-17P:=(4/3 -1/3) "1/3 1/3 /(3}1 —V7(11/3 } 厂 2/3/表 3-17c.-2 -3 -1 0 0bCJ X.X, X X, X-B-3Bx1Xc1 2 J 4 511/3 0 -1 4/3 -1/3-2/3 1 2 -1/3 1/3122-2-3X1 X.1 0 -3/11 4/11 -1/110 1 20/11 -1/11 3/113/11 24/112b0 0 43/11 5/11 7/11w=-78/11 j 由表3-17可以看出，当a］］由1变为3时，原最优基并未发生改变，而最优解变为X*= (3/11,24/11,0,0,0)t［例3-11］对于例3-6中的线性规划问题，问当a11由1变为5时，原最优解是否发生改变，如果改变求新的最优解。

解：首先将变化反映进最终单纯形表，形成表3-182/5-1/5}(5 }(8/5 }P：=^ 1/52/5 /< 2 /=-9。