线性规划的改进单纯形法求解示例
题目描述
考虑线性规划问题：
目标函数：最大化 \(z = 3x_1 + 5x_2\)
约束条件：
\[\begin{aligned} x_1 + x_3 &= 4 \\ 2x_2 + x_4 &= 12 \\ 3x_1 + 2x_2 + x_5 &= 18 \\ x_1, x_2, x_3, x_4, x_5 &\ge 0 \end{aligned} \]
其中 \(x_3, x_4, x_5\) 是松弛变量。
请用改进单纯形法逐步求解该问题，重点说明与标准单纯形法的差异。
解题过程
1. 问题分析与改进单纯形法的思想
标准单纯形法在每一步需要计算和更新整个单纯形表，而改进单纯形法通过更高效地处理基矩阵的逆矩阵 \(B^{-1}\)，减少计算量，尤其适用于大规模稀疏问题。
核心思想：
- 只显式维护基变量集合、非基变量集合和基矩阵的逆 \(B^{-1}\)。
- 通过矩阵运算计算单纯形法中的关键量（检验数、进基变量、出基变量、主元列、右端项更新）。
- 利用递推公式更新 \(B^{-1}\)（如乘积形式或LU分解），避免直接求逆。
2. 初始基与矩阵表示
从松弛变量易得初始基本可行解：
- 基变量：\(B = \{x_3, x_4, x_5\}\)，对应基矩阵 \(B = I\)（单位矩阵），基的逆 \(B^{-1} = I\)。
- 基变量的值：\(x_B = B^{-1} b = (4, 12, 18)^T\)，其中 \(b = (4, 12, 18)^T\)。
- 非基变量：\(N = \{x_1, x_2\}\)，对应系数矩阵 \(A_N = \begin{pmatrix} 1 & 0 \\ 0 & 2 \\ 3 & 2 \end{pmatrix}\)。
- 目标函数系数：基变量部分 \(c_B = (0, 0, 0)\)，非基变量部分 \(c_N = (3, 5)\)。
3. 计算检验数（进基变量选择）
检验数公式：\(\sigma_j = c_j - c_B B^{-1} A_j\)，其中 \(A_j\) 是变量 \(x_j\) 的系数列。
计算 \(c_B B^{-1} = (0,0,0)\)，故：
\[\sigma_1 = 3 - 0 = 3,\quad \sigma_2 = 5 - 0 = 5 \]
两者均正，选择最大正检验数对应变量进基：\(x_2\) 进基（对应 \(\sigma_2=5\) 最大）。
4. 计算进基列与最小比值（出基变量选择）
进基变量 \(x_2\) 在基下的系数列：\(A_2\) 在初始表中为 \((0, 2, 2)^T\)，但需转换为基下的表示：
实际计算 \(y = B^{-1} A_2 = I \cdot (0, 2, 2)^T = (0, 2, 2)^T\)。
用比值测试确定出基变量：
\[\theta = \min\left\{ \frac{(x_B)_i}{y_i} \mid y_i > 0 \right\} = \min\left\{ \frac{12}{2}, \frac{18}{2} \right\} = 6 \]
最小比值在 \(i=2\)（基变量 \(x_4\)）和 \(i=3\)（基变量 \(x_5\)）同时达到，这里选第一个最小下标：出基变量为 \(x_4\)。
5. 更新基、基逆与基变量值
- 新基变量：\(B_{\text{new}} = \{x_3, x_2, x_5\}\)。
- 进基列在基下的表示：\(y = (0, 2, 2)^T\)，出基变量位置 \(r=2\)（第二个基变量）。
- 更新基逆 \(B^{-1}\)：
设旧基逆为 \(B^{-1}_{\text{old}} = I = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\)。
计算变换矩阵 \(E\)：
\[ E = \begin{pmatrix} 1 & -\frac{y_1}{y_r} & 0 \\ 0 & \frac{1}{y_r} & 0 \\ 0 & -\frac{y_3}{y_r} & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \frac{1}{2} & 0 \\ 0 & -1 & 1 \end{pmatrix} \]
（因为 \(y_1=0, y_r=2, y_3=2\)）。
新基逆：\(B^{-1}_{\text{new}} = E \cdot B^{-1}_{\text{old}} = E\)。
- 更新基变量值：
\[ x_B^{\text{new}} = B^{-1}_{\text{new}} b = E \cdot (4, 12, 18)^T = (4, 6, 6)^T \]
对应基变量 \(x_3=4, x_2=6, x_5=6\)。
6. 第二次迭代：检验数计算
- 新基变量系数：\(c_B = (0, 5, 0)\)。
- 非基变量集合：\(N = \{x_1, x_4\}\)。
- 计算单纯形乘子：\(\pi = c_B B^{-1}_{\text{new}} = (0,5,0) E = (0, 5/2, 0)\)。
- 检验数：
\[ \sigma_1 = c_1 - \pi A_1 = 3 - (0, 5/2, 0) \cdot (1, 0, 3)^T = 3 - 0 = 3 \]
\[ \sigma_4 = c_4 - \pi A_4 = 0 - (0, 5/2, 0) \cdot (0, 1, 0)^T = -5/2 \]
\(\sigma_1=3>0\)，故 \(x_1\) 进基。
7. 第二次迭代：出基变量选择
- 计算进基列在基下的表示：\(y = B^{-1}_{\text{new}} A_1 = E \cdot (1, 0, 3)^T = (1, 0, 3)^T\)。
- 比值测试：\(\theta = \min\left\{ \frac{4}{1}, -, \frac{6}{3} \right\} = 2\)（排除 \(y_2=0\)）。
最小比值在 \(i=3\)（基变量 \(x_5\)）达到，故出基变量为 \(x_5\)。
8. 更新基、基逆与基变量值
- 新基变量：\(B = \{x_3, x_2, x_1\}\)。
- 出基位置 \(r=3\)。构造变换矩阵 \(E'\)：
\[ E' = \begin{pmatrix} 1 & 0 & -\frac{y_1}{y_r} \\ 0 & 1 & -\frac{y_2}{y_r} \\ 0 & 0 & \frac{1}{y_r} \end{pmatrix} = \begin{pmatrix} 1 & 0 & -1/3 \\ 0 & 1 & 0 \\ 0 & 0 & 1/3 \end{pmatrix} \]
（因为 \(y_1=1, y_2=0, y_r=3\)）。
- 新基逆：\(B^{-1}_{\text{new2}} = E' \cdot B^{-1}_{\text{new}} = E' E\)。
- 新基变量值：
\[ x_B^{\text{new2}} = B^{-1}_{\text{new2}} b = E' \cdot (4, 6, 6)^T = (2, 6, 2)^T \]
对应基变量 \(x_3=2, x_2=6, x_1=2\)。
9. 第三次迭代：检验数计算
- 新基变量系数：\(c_B = (0, 5, 3)\)。
- 非基变量：\(N = \{x_4, x_5\}\)。
- 计算乘子：\(\pi = c_B B^{-1}_{\text{new2}} = (0,5,3) E' E = (0, 5/2, 3) E' = (0, 5/2, 3) \cdot \begin{pmatrix}1&0&-1/3\\0&1&0\\0&0&1/3\end{pmatrix} = (0, 5/2, 1)\)。
- 检验数：
\[ \sigma_4 = 0 - \pi A_4 = 0 - (0,5/2,1) \cdot (0,1,0)^T = -5/2 \]
\[ \sigma_5 = 0 - \pi A_5 = 0 - (0,5/2,1) \cdot (0,0,1)^T = -1 \]
所有检验数非正，达到最优。
10. 最优解与目标值
- 最优解：\(x_1=2, x_2=6, x_3=2, x_4=0, x_5=0\)。
- 最优目标值：\(z = 3 \cdot 2 + 5 \cdot 6 = 36\)。
总结改进单纯形法的关键点
- 始终维护基矩阵的逆 \(B^{-1}\)，通过乘积形式更新，避免直接求逆。
- 计算量集中在矩阵-向量乘法，适用于大规模问题。
- 与标准单纯形法相比，不存储完整的单纯形表，减少了存储和计算开销。