【管理运筹学】第 4 章

之前的线性规划问题中，目标函数系数 c j c_j cj​ ，右端资源列向量 b b b 和约束条件系数 a i j a_{ij} aij​ 都是固定的常数。但实际上由于市场的变化或者工艺条件的改善以及时间的推移，这些参数是会发生变化的，因此就会有如下问题产生：

以上就是 灵敏度分析（sensitivity analysis） 所要解决的问题。当原有的线性规划模型求出最优解后，对于某一个参数变化，如何不重新求解，就可以分析出最优解以及最优目标值的变化。本文只研究单个参数变化的情况。

为讨论某个参数的变化对最优解的构成以及最优值的影响，我们首先应了解，当单纯形法迭代到最优单纯形表时，各个参数的特征。

以线性规划问题的标准型为讨论对象： 一般我们会添加松弛变量形成等式，所以初始单纯形表中的系数矩阵 A A A 可以分为 ( B , N ) (B,N) (B,N) ，其中 B B B 为基变量对应的系数矩阵， N N N 为非基变量对应的系数矩阵。同理，变量可分为基变量 X B X_B XB​ ，非基变量 X N X_N XN​ 。基变量对应的目标函数系数为 C B C_B CB​ ，非基变量对应的目标函数系数为 C N C_N CN​ 。

单纯形法本质上是在对增广矩阵进行多次初等行变换，使得最后满足可行和最优性检验，且基变量对应的系数矩阵为单位阵 E E E 。根据线性代数的知识，我们知道，原来基变量对应的系数矩阵为 B B B ，想要最后成为一个单位阵，只需左乘上 B − 1 B^{-1} B−1 。因此，我们做了那么多次迭代，其实就相当于将增广矩阵左乘上一个 B − 1 B^{-1} B−1 。

初始的基变量为松弛变量对应的矩阵 N = E N=E N=E ，因此初始基变量在最优单纯形表中对应的系数矩阵即为 B − 1 N = B − 1 E = B − 1 B^{-1}N=B^{-1}E=B^{-1} B−1N=B−1E=B−1 。右端资源向量 b b b ，最终变为 B − 1 b B^{-1}b B−1b 。下表给出了达到最优单纯形表时各个参数的特征。

有了这些特征后，我们可以清晰知道某个参数变化会带来哪些影响。如当右端资源向量 b b b 变化时，只会影响最终基变量的取值 B − 1 b B^{-1}b B−1b 。

通过分析第一节给出的最优单纯性表各个参数的特征，可知，目标函数系数 c j c_j cj​ 的变化需要分情况讨论。因此 c j c_j cj​ 为 C B C_B CB​ 和 C N C_N CN​ 时，变化带来的影响不一。

此时 c j c_j cj​ 的改变，只会影响对应决策变量 x j x_j xj​ （非基）的检验数。为保证基变量不变，该非基变量检验数需保持非正，即变化后的 σ j ′ = c j + Δ c j − c B B − 1 c j ≤ 0 \sigma_j'= c_j+ \Delta c_j -c_BB^{-1}c_j \leq0 σj′​=cj​+Δcj​−cB​B−1cj​≤0 ，于是有： Δ c j ≤ − σ j . \Delta c_j \leq -\sigma_j. Δcj​≤−σj​. 当 c j c_j cj​ 的变化值满足上述条件时，原来的线性规划模型最优解不变。若 c j c_j cj​ 变动超过了上述范围，利用单纯形法继续求解。

此时 c j c_j cj​ 进入 C B C_B CB​ ，会影响所有决策变量的检验数，因此要保证所有非基变量检验数为非正。有： m a x ( σ j / a r j ‾ ∣ a r j ‾ > 0 ) ≤ Δ c r ≤ m i n ( σ j / a r j ‾ ∣ a r j ‾ < 0 ) max(\sigma_j / \overline{a_{rj}} | \overline{a_{rj}}>0) \leq \Delta c_r \leq min(\sigma_j / \overline{a_{rj}} | \overline{a_{rj}}0)≤Δcr​≤min(σj​/arj​​∣arj​​ 0 ) ≤ Δ b r ≤ m i n ( − b i ‾ / a i r ‾ ∣ a i r ‾ < 0 ) max(-\overline{b_i} / \overline{a_{ir}} | \overline{a_{ir}} > 0) \leq \Delta b_r \leq min(-\overline{b_i} / \overline{a_{ir}} | \overline{a_{ir}}0)≤Δbr​≤min(−bi​​/air​​∣air​​