线性规划（Linear Programming）：灵敏度分析

• 线性规划（Linear Programming）：灵敏度分析
  • 基本思想
  • 资源系数变化分析
    • 例
  • 价值系数分析
    • 非基变量价值系数发生变化
      • 例
    • 基变量价值系数发生变化
  • 技术系数变化分析

基本思想

本处系数指：价值系数$c_j$、资源系数$b_i$、技术系数$a_{ij}$。

• 系数在什么范围内变化，不会影响已获得的最优基（即最优解或最优解结构不变）。
• 如果系数的变化超过以上范围，如何在用最简便的方法在原来最优解的基础上求得新的最优解。
• 当线性规划问题增加一个新的变量或新的约束，如何在原有最优解的基础上获得新的最优解。

原问题	对偶问题	方法	备注
可行解	可行解	已是最优解
可行解	非可行解	单纯形法	$c_j$变化过大
非可行解	可行解	对偶单纯形法	$b_j$变化过大
非可行解	非可行解	引入人工变量

资源系数变化分析

$\left[\begin{array}{c} B & I \end{array}\right] \left[\begin{array}{c} x_B \\ x_I \end{array}\right] =b \,\,\, ⇒ \,\,\, x_B = B^{-1}b - B^{-1}Ix_I$

当资源限制变化为$Δb$，得新解$\hat{x}_B$

$\hat{x}_B = B^{-1}(b+Δb) - B^{-1}Ix_I = x_B + B^{-1}Δb$

即新的解相当于在原有解的基础上加上$B^{-1}Δb$。

• $\hat{x}_B≥0$：最优基不变，$x_I=0$，$x_B = \hat{x}_B$。
• $\hat{x}_B<0$：最优基变化，需要代入新$b$，继续用对偶单纯形法求新解。

例

$\min \,\,\, ω =-5x_1 - 12x_2 - 4x_3 + 0x_4 + Mx_5$
$\begin{cases} x_1 + 2x_2 + x_3 + x_4 = 5 \\ 2x_1 - x_2 + 3x_3 + x_5 = 2 \\ x_j≥0, j=1,2,3,4,5 \end{cases}$

	$c_j$	-5	-12	-4	0	M
$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$
0	$x_4$	1	2	1	1	0	5
$M$	$x_5$	2	-1	3	0	1	2
	$σ_j$	-5-2$M$	-12+$M$	-4-3$M$	0	0

计算结果为

	$c_j$	-5	-12	-4	0	M
$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$
-12	$x_2$	0	1	-$\frac{1}{5}$	$\frac{2}{5}$	-$\frac{1}{5}$	$\frac{8}{5}$
-5	$x_1$	1	0	$\frac{7}{5}$	$\frac{1}{5}$	$\frac{2}{5}$	$\frac{9}{5}$
	$σ_j$	0	0	$\frac{3}{5}$	$\frac{29}{5}$	-$\frac{2}{5}$+$M$

• $ω = -5⋅\frac{9}{5} - 12⋅\frac{8}{5} = -\frac{141}{5}$

注：使用单纯形法求解后$\left[\begin{array}{c} B & I \end{array}\right]$转化为$\left[\begin{array}{c} I & B^{-1} \end{array}\right]$。

即$B^{-1} = \left[\begin{array}{c} \frac{2}{5} & -\frac{1}{5} \\ \\ \frac{1}{5} & \frac{2}{5} \end{array}\right]$

问

1. $b_2$在什么范围内变化时，最优解保持不变。
2. $b_2$由2变为15，求最新最优解。

解

（1）

设$b_2$的变化为$Δb_2$，有

$\hat{x}_B = \left[\begin{array}{c} \frac{8}{5} \\ \\ \frac{9}{5} \end{array}\right] + \left[\begin{array}{c} \frac{2}{5} & -\frac{1}{5} \\ \\ \frac{1}{5} & \frac{2}{5} \end{array}\right] \left[\begin{array}{c} 0 \\ \\ Δb_2 \end{array}\right] = \left[\begin{array}{c} \frac{8-Δb_2}{5} \\ \\ \frac{9+2Δb_2}{5} \end{array}\right]$

要保持最优解不变，有$\hat{x}_B ≥ 0$

• $\frac{8-Δb_2}{5} ≥ 0$
• $\frac{9+2Δb_2}{5} ≥ 0$

故$Δb_2∈[-\frac{5}{2}, 10]$

（2）

$\hat{x}_B = B^{-1}b_{current} = \left[\begin{array}{c} \frac{2}{5} & -\frac{1}{5} \\ \\ \frac{1}{5} & \frac{2}{5} \end{array}\right] \left[\begin{array}{c} 5 \\ \\ 15 \end{array}\right] = \left[\begin{array}{c} -1 \\ \\ 7 \end{array}\right]$

最优基变化，使用对偶单纯形法，$b = \hat{x}_B$

	$c_j$	-5	-12	-4	0	M
$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$
-12	$x_2$	0	1	-$\frac{1}{5}$	$\frac{2}{5}$	-$\frac{1}{5}$	-1
-5	$x_1$	1	0	$\frac{7}{5}$	$\frac{1}{5}$	$\frac{2}{5}$	7
	$σ_j$	0	0	$\frac{3}{5}$	$\frac{29}{5}$	-$\frac{2}{5}$+$M$
	$c_j$	-5	-12	-4	0	M
$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$
-4	$x_3$	0	-5	1	-2	1	5
-5	$x_1$	1	7	0	3	-1	0
	$σ_j$	0	3	0	7	1+$M$

• $ω = -4 × 5 = -20$

价值系数分析

非基变量价值系数发生变化

例

$\min \,\,\, ω =-2x_1 - 3x_2 - x_3 + 0x_4 + 0x_5$
$\begin{cases} x_1 + x_2 + x_3 + x_4 = 3 \\ x_1 + 4x_2 + 7x_3 + x_5 = 9 \\ x_j≥0, j=1,2,3,4,5 \end{cases}$

计算结果为

	$c_j$	-2	-3	-1	0	0
$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$
-2	$x_1$	1	0	-1	$\frac{4}{3}$	-$\frac{1}{3}$	1
-3	$x_2$	0	1	2	-$\frac{1}{3}$	$\frac{1}{3}$	2
	$σ_j$	0	0	3	$\frac{5}{3}$	$\frac{1}{3}$

问

1. $c_3$在什么范围内变化时，最优解保持不变。
2. $c_3$由-1变为-6，求最新最优解。

解

（1）$x_3$在最终单纯形表中是非基变量，因此$c_3$的变化只会影响自身检验系数$σ_3$，而与其他变量的检验数无关。计算$σ_3$后，令其非负，即可保证最优解不变。

$σ_3 = c_3 - \left[\begin{array}{c} -2 & -3 \end{array}\right]\left[\begin{array}{c} -1 \\ 2 \end{array}\right] = c_3 + 4 ≥ 0$

即只要保证$c_3≥-4$，则最优解保持不变。

（2）在最终单纯形表中，将$c_3$替换为-6，继续用单纯形法求解。

	$c_j$	-2	-3	-1 $→$ -6	0	0
$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$
-2	$x_1$	1	0	-1	$\frac{4}{3}$	-$\frac{1}{3}$	1
-3	$x_2$	0	1	2	-$\frac{1}{3}$	$\frac{1}{3}$	2
	$σ_j$	0	0	-2	$\frac{5}{3}$	$\frac{1}{3}$
$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$
-2	$x_1$	1	$\frac{1}{2}$	0	$\frac{7}{6}$	-$\frac{1}{6}$	2
-6	$x_3$	0	$\frac{1}{2}$	1	-$\frac{1}{6}$	$\frac{1}{6}$	1
	$σ_j$	0	1	0	$\frac{4}{3}$	$\frac{2}{3}$

• $ω =-2x_1 - 3x_2 - x_3 + 0x_4 + 0x_5 = -2(-2) - (-6) = 10$

基变量价值系数发生变化

基变量的价值系数发生变化，会引起$C_B$的变化，进而引起所有检验数的改变（值可能不变）。

重新计算所有检验数，看是否有负检验数产生，如果没有，则原解不变；如果有，则继续使用单纯形法求解。

技术系数变化分析

略