线性规划的灵敏度分析示例
题目描述
假设某工厂生产两种产品 A 和 B，每件产品利润分别为 60 元和 40 元。生产过程中需要两种资源：电力（每天最多供应 200 单位）和人力（每天最多供应 240 小时）。已知每件 A 产品消耗电力 2 单位、人力 4 小时；每件 B 产品消耗电力 3 单位、人力 2 小时。工厂希望最大化利润。
建立线性规划模型如下：
\[\text{最大化 } Z = 60x_1 + 40x_2 \]
\[\text{约束条件：} \begin{cases} 2x_1 + 3x_2 \leq 200 \quad (\text{电力约束}) \\ 4x_1 + 2x_2 \leq 240 \quad (\text{人力约束}) \\ x_1, x_2 \geq 0 \end{cases} \]
问题：若产品 A 的利润系数从 60 变为 \(c_1\)，分析 \(c_1\) 在什么范围内变化时，最优解结构不变（即最优基不变）。
解题过程
步骤 1：求解原始问题的最优解
引入松弛变量 \(s_1, s_2\)，将模型转化为标准型：
\[\begin{aligned} \text{最大化 } Z = 60x_1 + 40x_2 \\ 2x_1 + 3x_2 + s_1 = 200 \\ 4x_1 + 2x_2 + s_2 = 240 \\ x_1, x_2, s_1, s_2 \geq 0 \end{aligned} \]
使用单纯形法求解：
- 初始单纯形表（基变量为 \(s_1, s_2\)）：
\[\begin{array}{c|ccccc} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 2 & 3 & 1 & 0 & 200 \\ s_2 & 4 & 2 & 0 & 1 & 240 \\ \hline Z & -60 & -40 & 0 & 0 & 0 \\ \end{array} \]
- 选择 \(x_1\) 入基（检验数最负），计算比值：
\(s_1: 200/2 = 100\), \(s_2: 240/4 = 60\) → \(s_2\) 出基。
行变换使主元（第 2 行第 1 列）变为 1：
\[\text{新 } s_2 \text{行} = \text{旧 } s_2 \text{行} / 4 \rightarrow [1, 0.5, 0, 0.25, 60] \]
更新其他行：
- \(s_1 \text{行} = \text{旧 } s_1 \text{行} - 2 \times \text{新 } s_2 \text{行} \rightarrow [0, 2, 1, -0.5, 80]\)
- \(Z \text{行} = \text{旧 } Z \text{行} + 60 \times \text{新 } s_2 \text{行} \rightarrow [0, -10, 0, 15, 3600]\)
新表（基变量 \(s_1, x_1\)）：
\[\begin{array}{c|ccccc} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 0 & 2 & 1 & -0.5 & 80 \\ x_1 & 1 & 0.5 & 0 & 0.25 & 60 \\ \hline Z & 0 & -10 & 0 & 15 & 3600 \\ \end{array} \]
- \(x_2\) 入基（检验数 -10），计算比值：
\(s_1: 80/2 = 40\), \(x_1: 60/0.5 = 120\) → \(s_1\) 出基。
主元为第 1 行第 2 列，化为 1：
\[\text{新 } s_1 \text{行} = \text{旧 } s_1 \text{行} / 2 \rightarrow [0, 1, 0.5, -0.25, 40] \]
更新其他行：
- \(x_1 \text{行} = \text{旧 } x_1 \text{行} - 0.5 \times \text{新 } s_1 \text{行} \rightarrow [1, 0, -0.25, 0.375, 40]\)
- \(Z \text{行} = \text{旧 } Z \text{行} + 10 \times \text{新 } s_1 \text{行} \rightarrow [0, 0, 5, 12.5, 4000]\)
最终表（基变量 \(x_2, x_1\)）：
\[\begin{array}{c|ccccc} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline x_2 & 0 & 1 & 0.5 & -0.25 & 40 \\ x_1 & 1 & 0 & -0.25 & 0.375 & 40 \\ \hline Z & 0 & 0 & 5 & 12.5 & 4000 \\ \end{array} \]
最优解：\(x_1 = 40, x_2 = 40, Z = 4000\)。
步骤 2：灵敏度分析（目标函数系数 \(c_1\) 变化）
设 \(c_1\) 变为 \(c_1'\)，最终表中 \(Z\) 行的检验数由公式计算：
\[\text{检验数} = c_N' - c_B' B^{-1} N \]
其中 \(c_B' = [c_2, c_1'] = [40, c_1']\)（基变量 \(x_2, x_1\) 对应的系数），\(c_N' = [0, 0]\)（松弛变量 \(s_1, s_2\) 的系数）。
从最终表直接读取 \(B^{-1} N\) 对应的系数（即 \(s_1, s_2\) 在最终表中的系数列）：
\[\text{对于 } s_1: [0.5, -0.25]^T, \quad \text{对于 } s_2: [-0.25, 0.375]^T \]
检验数计算：
- \(s_1\) 的检验数：
\[0 - [40, c_1'] \begin{bmatrix} 0.5 \\ -0.25 \end{bmatrix} = -20 + 0.25 c_1' \]
- \(s_2\) 的检验数：
\[0 - [40, c_1'] \begin{bmatrix} -0.25 \\ 0.375 \end{bmatrix} = 10 - 0.375 c_1' \]
步骤 3：保持最优基的条件
检验数需满足非负（最大化问题）：
\[\begin{cases} -20 + 0.25 c_1' \geq 0 \\ 10 - 0.375 c_1' \geq 0 \end{cases} \Rightarrow \begin{cases} c_1' \geq 80 \\ c_1' \leq 26.67 \end{cases} \]
矛盾！说明计算需复核。
修正计算：
最终表中 \(Z\) 行松弛变量的系数实际已包含 \(c_B'\) 的影响，正确方法是直接利用最终表结构：
原始最终表 \(Z\) 行系数为 \([0, 0, 5, 12.5]\)，对应 \(c_1 = 60\)。当 \(c_1\) 变化时，仅 \(Z\) 行中非基变量检验数变化：
非基变量为 \(s_1, s_2\)，其检验数公式为：
\[\sigma_j = c_j - c_B B^{-1} A_j \]
但更简单的方式是利用最终表敏感性分析：
设 \(c_1\) 变化 \(\Delta c_1\)，则 \(c_B\) 变为 \([40, 60 + \Delta c_1]\)。
非基变量检验数变化量：
\[[\Delta \sigma_{s_1}, \Delta \sigma_{s_2}] = - \Delta c_B B^{-1} N \]
其中 \(\Delta c_B = [0, \Delta c_1]\)，\(B^{-1} N\) 为最终表中 \(s_1, s_2\) 的系数矩阵：
\[B^{-1} N = \begin{bmatrix} 0.5 & -0.25 \\ -0.25 & 0.375 \end{bmatrix} \]
计算：
\[\Delta c_B B^{-1} N = [0, \Delta c_1] \begin{bmatrix} 0.5 & -0.25 \\ -0.25 & 0.375 \end{bmatrix} = [-0.25 \Delta c_1, 0.375 \Delta c_1] \]
因此检验数变化：
\[\sigma_{s_1}' = 5 - (-0.25 \Delta c_1) = 5 + 0.25 \Delta c_1 \\ \sigma_{s_2}' = 12.5 - (0.375 \Delta c_1) = 12.5 - 0.375 \Delta c_1 \]
保持最优性需 \(\sigma_{s_1}' \geq 0, \sigma_{s_2}' \geq 0\)：
\[5 + 0.25 \Delta c_1 \geq 0 \Rightarrow \Delta c_1 \geq -20 \\ 12.5 - 0.375 \Delta c_1 \geq 0 \Rightarrow \Delta c_1 \leq 33.33 \]
所以 \(c_1\) 的范围为：
\[60 - 20 \leq c_1 \leq 60 + 33.33 \Rightarrow 40 \leq c_1 \leq 93.33 \]
结论：当产品 A 的利润系数 \(c_1\) 在区间 \([40, 93.33]\) 内时，最优基（即生产方案 \(x_1 > 0, x_2 > 0\)）不变。