第5讲 灵敏度分析.doc

系统工程讲义第5讲 灵敏度分析灵敏度分析是指对系统因环境变化显示出来的敏感程度的分析。在线性规划问题中讨论灵敏度分析，目的是描述一种能确定线性规划模型结构中元素变化对问题解的影响的分析方法。前面的讨论都假定价值系数、资源系数和技术系数向量或矩阵中的元素是常数，但实际上这些系数往往只是估计值，不可能十分准确和一成不变。这就是说，随着时间的推移或情况的改变，往往需要修改原线性规划问题中的若干参数。因此，求得线性规划的最优解，还不能说问题已得到了完全的解决。决策者还需要获得这样两方面的信息：一是当这些系数有一个或几个发生变化时，已求得的最优解会有什么变化；二是这些系数在什么范围内变化时，线性规划问题的最优解（或最优基）不变。显然，当线性规划问题中的某些量发生变化时，原来已得的结果一般会发生变化。在单纯形法迭代时，每次运算都和基有关，所以可以把发生变化的量经过一定计算，直接反映进最终单纯形表并按表5-1处理。表5-1原问题对偶问题结论或继续计算的步骤可行解可行解最优解可行解非可行解用单纯形法求解最优解非可行解可行解用对偶单纯形法求解最优解非可行解非可行解引入人工变量求解最优解4.1 资源系数变化的分析资源系数发生变化，即发生变化的灵敏度分析；该类问题关键是如何将的变化直接反映进原问题的最终单纯形表。单纯形法的迭代过程，其实不过就是矩阵的初等变换过程；而线性代数的知识告诉我们，对分块矩阵进行初等变换，当矩阵变为单位矩阵时，单位矩阵将变为矩阵，即：由此可知，如果已知最终单纯形表中基可行解所对应的基“”（最终单纯形表中的基变量在初始单纯形表中的列向量所构成的矩阵），即可在最终单纯形表中找到“”（初始单纯形表中的单位矩阵在最终单纯形表中所对应的矩阵），而最终单纯形表中的每一列均可用其在初始单纯形表中的相应列左乘来得到；即。例5-1 已知LP问题 + 2 = 5 + 3 = 2单纯形求解可得如表5-1所示的最终单纯形表，问（1）在什么范围内变化时，最优解（在此实际上是最优基）保持不变；（2）由2增加至15，求新的最优解。表3-11cj-5 -12 -4 0 MCBXBx1 x2 x3 x4 x5-12-5x2x1 0 1 -1/5 2/5 -1/5 1 0 7/5 1/5 2/58/59/5sj 0 0 -3/5 -29/5 2/5-Mw=-141/5解（1）：给一个增量并利用将变化直接反映进最终单纯形表。为保持最优解不变，应有，即：，所以有的变化范围应在之内。解（2）：将直接反映进最终单纯形表，得表3-12。表3-12cj-5 -12 -4 0 MCBXBx1 x2 x3 x4 x5-12-5x2x1 0 1 -1/5 2/5 -1/5 1 0 7/5 1/5 2/5-17sj 0 0 -3/5 -29/5 2/5-Mw=-23利用对偶单纯形法继续迭代，可得如表3-13所示的新的最优解。表3-13cj-5 -12 -4 0 MCBXBx1 x2 x3 x4 x5-4-5x3x1 0 -5 1 -2 1 1 7 0 3 -150sj 0 -3 0 -7 1-Mw=-204.2价值系数变化的分析将原迭代过程继承下来，价值系数的变化只会对最终单纯形表中的检验数发生影响，而与其他量无关。因此，将变化的价值系数反映进最终单纯形表，只需对检验数行进行修正。 情况1 价值系数发生变化的变量在最终单纯形表中为非基变量价值系数发生变化的变量在最终单纯形表中为非基变量，所以将变化的价值系数反映进最终单纯形表只会影响此变量自身的检验数，而与其他变量的检验数无关。 例3-7 已知LP问题 + + = 3 + 4 +7 = 9单纯形求解可得如表3-14所示的最终单纯形表，问（1）在什么范围内变化时，最优解保持不变；（2）由“-1”减少至“-6”，求新的最优解。解（1）：由于在最终单纯形表中是非基变量，因此的变化只会影响自身的检验数，而与其他变量的检验数无关。计算变化后的并令其非负，即可求得保持最优解不变的变化范围。表3-14cj-2 -3 -1 0 0CBXBx1 x2 x3 x4 x5-2-3x1x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/312sj 0 0 3 5/3 1/3w=-8，即只要，就可以保持最优解不变。解（2）：将直接反映进最终单纯形表，用单纯形法继续迭代即可得到新的最优解，过程见表3-15。表3-15cj-2 -3 -6 0 0CBXBx1 x2 x3 x4 x5-2-3x1x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/312sj 0 0 -2 5/3 1/3w=-8-2-6x1x3 1 1/2 0 7/6 -1/6 0 1/2 1 -1/6 1/621sj 0 1 0 4/3 2/3w=-10情况2 价值系数发生变化的变量在最终单纯形表中为基变量因为基变量的价值系数发生变化会引起的变化，进而可能引起整个检验数行的变化。例3-8 对于例3-7中的线性规划问题，问：（1）在什么范围内变化时，最优解保持不变；（2）由“-2”减少至“-6”，求新的最优解。表3-16cj-6 -3 -1 0 0CBXBx1 x2 x3 x4 x5-6-3x1x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/312sj 0 0 -1 7 -1w=-12-6-1x1x3 1 1/2 0 7/6 -1/6 0 1/2 1 -1/6 （1/6）21sj 0 1/2 0 41/6 -5/6w=-13-60x1x5 1 1 1 1 0 0 3 6 -1 136sj 0 3 5 6 0w=-18解（1）：由最终单纯形表（表3-10）可知，为保持原最优解不变应有： 即保持原最优解不变应有。解（2）：将直接反映进最终单纯形表，用单纯形法继续迭代即可得到新的最优解，过程见表3-16。4.3技术系数变化的分析如果将原迭代过程继承下来，我们就可以通过将技术系数的变化反映进最终单纯形表。需要强调的是，如果发生变化的变量在最终单纯形表中为非基变量，那么只需在将变化反映进最终单纯表后，重新计算该非基变量的检验数即可完成对问题的求解；如果发生变化的变量在最终单纯形表中为基变量，那么必须在将变化反映进最终单纯表后，首先围绕该变量进行初等变换，将该基变量的列向量变为单位向量，再重新计算各个变量的检验数，才能完成对问题的求解。 情况1 技术系数发生变化的变量在最终单纯形表中为非基变量例3-9 对于例3-7中的线性规划问题，问在什么范围内变化时，最优解保持不变。即保持原最优解不变应有。 情况2 技术系数发生变化的变量在最终单纯形表中为基变量由于基变量的技术系数发生了变化，将变化的量反映进最终单纯形表，必将破坏基变量在最终单纯形表中的单位向量形式；为获得变化后新问题的基解，必须首先将基变量对应的列向量转化为单位向量。转化后的结果可能是原问题与对偶问题都可行，也可能是原问题和对偶问题只有之一是可行的，还可能原问题与对偶问题均不可行；然而无论出现哪种结果，我们均可按表3-10进行处理。 例3-10 对于例3-7中的线性规划问题，问当a11由1变为3时，原最优解是否发生改变，如果改变求新的最优解。解：首先将变化反映进最终单纯形表，形成表3-17。表3-17cj-2 -3 -1 0 0CBXBx1 x2 x3 x4 x5-2-3x1x2 11/3 0 -1 4/3 -1/3 -2/3 1 2 -1/3 1/312-2-3x1x2 1 0 -3/11 4/11 -1/11 0 1 20/11 -1/11 3/113/1124/11sj 0 0 43/11 5/11 7/11w=-78/11由表3-17可以看出，当由1变为3时，原最优基并未发生改变，而最优解变为。例3-11 对于例3-6中的线性规划问题，问当a11由1变为5时，原最优解是否发生改变，如果改变求新的最优解。解：首先将变化反映进最终单纯形表，形成表3-18。表3-18cj-5 -12 -4 0 MCBXBx1 x2 x3 x4 x5-12-5x2x1 8/5 1 -1/5 2/5 -1/5 9/5 0 7/5 1/5 2/58/59/5-12-5x2x1 0 1 -13/9 2/9 1 0 （7/9） 1/901sj 0 0 -157/9 29/9w=-5-12-4x2x3 13/7 1 0 3/7 9/7 0 1 1/713/79/7sj157/7 0 0 40/7w=-192/7从表3-18可以看出，原最优解已发生改变，新的最优解为。例3-12 对于例3-7中的线性规划问题，问当a11由1变为0时，原最优解是否发生改变，如果改变求新的最优解。解：首先将变化反映进最终单纯形表，形成表3-19。表3-19cj-2 -3 -1 0 0CBXBx1 x2 x3 x4 x5-2-3x1x2 -1/3 0 -1 4/3 -1/3 1/3 1 2 -1/3 1/312-2-3x1x2 1 0 3 -4 1 0 1 1 1 0-33sj 0 0 8 -5 2w=-3表3-19所示的原问题及对偶问题均不可行，故需引入人工变量。首先将右端项为负值的约束方程拿出来：方程两侧同乘“-1”并引入人工变量：以人工变量为基变量，将该约束放回原位置，用前面处理人工变量的方法即可求解此问题，求解过程如表3-20所示。表3-20cj-2 -3 -1 0 0 MCBXBx1 x2 x3 x4 x5 x6M-3x6x2 -1 0 -3 4 -1 1 0 1 1 1 0 033sj M-2 0 3M+2 3-4M M 0w=3M-90-3x4x2 -1/4 0 -3/4 1 -1/4 1/4 1/4 1 7/4 0 1/4 -1/43/49/4sj -5/4 0 17/4 0 3/4 M-3/4w=-27/40-2x4x1 0 1 1 1 0 01 4 7 0 1 -139sj0 5 13 0 2 M-2w=-18表3-20给出了新的最优解，新的最优值。4.4增加一个新的变量的分析增加一个新的变量相当于在单纯形表中增加一列，只要新增变量在最终单纯形表中的检验数非负（min），原问题的最优解就不会改变，所以应首先计算新增变量的检验数。在实际问题中，增加一个新的变量相当于增加一种新的产品，分析的是在资源不变的前提下，新产品是否值得进入产品组合。 例3-13 对于例3-7中的线性规划问题，增加一个新的变量，已知该变量的价值系数，技术系数向量，问原最优解是否改变，如果改变求新的最优解。解：首先将新增加变量的技术系数向量反映进最终单纯形表：其次计算新增变量在最终单纯形表中的检验数：由于在最终单纯形表中的检验数，所以原最优解发生变化，新的最优解的求解过程见表3-21。表3-21cj-2 -3 -1 0 0 -3CBXBx1 x2 x3 x4 x5 x6-2-3x1x2 1 0 -1 4/3 -1/3 （1） 0 1 2 -1/3 1/3 012sj 0 0 3 5/3 1/3 -1w=-8-3-3x6x2 1 0 -1 4/3 -1/3 1 0 1 2 -1/3 1/3 012sj 1 0 2 3 0 0w=-9表3-21给出了新的最优解，新的最优值。由于非基变量的检验数为“0”，所以此最优解为无穷最优解中的一个。4.5增加一个新的约束的分析因增加约束条件不会使目标函数的最优值得到改善，所以若原最优解满足新增加的约束条件，那么它一定仍然是最优解；若原最优解已不能使新增加的约束条件成立，则需对问题做进一步的处理。例3-14 对于例3-7中的线性规划问题，分别增加如下约束条件：（1），（2）试分析其对最优解的影响。解（1）：将原问题的最优解代入新增加的约束条件，由于原最优解可以使新增约束成立，所以最优解不变。解（2）：将原问题的最优解代入新增约束，新增约束已不成立，所以原最优解要发生变化。在新增约束中引入松弛变量，并让充当基变量，将新增约束直接反映进最终单纯形表。由于在最终单纯形表中增加了一行，原来基变量的单位列向量可能遭到破坏；因此，首先需要将基变量所对应的系数列向量变为单位向量，然后再按表3-10处理，处理过程见表3-22。表3-22cj-2 -3 -1 0 0