基于线性规划的Bland规则单纯形法求解示例
题目描述
考虑以下线性规划问题：
\[\begin{aligned} \text{最大化} \quad & 2x_1 + 3x_2 \\ \text{约束条件} \quad & x_1 + 2x_2 \leq 6 \\ & 2x_1 + x_2 \leq 8 \\ & x_1, x_2 \geq 0 \end{aligned} \]
要求使用Bland规则（即最小下标规则）的单纯形法求解，避免循环现象，并详细展示每一步的基变量选择、进基变量和离基变量的确定过程。
解题过程
步骤1：标准化问题
引入松弛变量 \(x_3, x_4 \geq 0\)，将不等式约束转化为等式：
\[\begin{aligned} x_1 + 2x_2 + x_3 &= 6 \\ 2x_1 + x_2 + x_4 &= 8 \\ x_1, x_2, x_3, x_4 &\geq 0 \end{aligned} \]
目标函数变为：
\[z = 2x_1 + 3x_2 + 0 \cdot x_3 + 0 \cdot x_4 \]
初始基变量为 \(x_3, x_4\)，初始单纯形表如下（格式：系数矩阵 | 右端项）：
\[\begin{array}{cccc|c} x_1 & x_2 & x_3 & x_4 & \text{RHS} \\ \hline 1 & 2 & 1 & 0 & 6 \\ 2 & 1 & 0 & 1 & 8 \\ \hline -2 & -3 & 0 & 0 & 0 \\ \end{array} \]
最后一行是目标函数的相反数（检验数 \(\sigma_j = c_j - z_j\)）。
步骤2：确定进基变量（Bland规则）
检验数中负值表示目标函数可改进。Bland规则选择下标最小的负检验数对应的变量进基。
检验数：\(\sigma_1 = -2, \sigma_2 = -3\)。最小下标为 \(j=1\)，故进基变量为 \(x_1\)。
步骤3：确定离基变量
计算比率（右端项 / 进基变量列系数），仅考虑正系数：
- 第一行：\(6 / 1 = 6\)
- 第二行：\(8 / 2 = 4\)
最小比率为 \(4\)，对应第二行，离基变量为 \(x_4\)。
步骤4：主元运算（以第二行第一列为主元）
将主元化为1，并消去其他行的 \(x_1\) 系数：
- 第二行除以2：
\[[1, 0.5, 0, 0.5, 4] \]
- 第一行减去新第二行：
\[[0, 1.5, 1, -0.5, 2] \]
- 更新检验数行（加2倍新第二行）：
\[[0, -2, 0, 1, 8] \]
新单纯形表：
\[\begin{array}{cccc|c} x_1 & x_2 & x_3 & x_4 & \text{RHS} \\ \hline 0 & 1.5 & 1 & -0.5 & 2 \\ 1 & 0.5 & 0 & 0.5 & 4 \\ \hline 0 & -2 & 0 & 1 & 8 \\ \end{array} \]
基变量：\(x_3, x_1\)，目标函数值 \(z = 8\)。
步骤5：第二次迭代
检验数中仅 \(\sigma_2 = -2\) 为负，进基变量为 \(x_2\)（最小下标）。
比率计算：
- 第一行：\(2 / 1.5 = 4/3\)
- 第二行：\(4 / 0.5 = 8\)
最小比率为 \(4/3\)，离基变量为 \(x_3\)。
步骤6：主元运算（以第一行第二列为主元）
- 第一行除以1.5：
\[[0, 1, 2/3, -1/3, 4/3] \]
- 第二行减去0.5倍新第一行：
\[[1, 0, -1/3, 2/3, 10/3] \]
- 更新检验数行（加2倍新第一行）：
\[[0, 0, 4/3, 1/3, 32/3] \]
新表：
\[\begin{array}{cccc|c} x_1 & x_2 & x_3 & x_4 & \text{RHS} \\ \hline 0 & 1 & 2/3 & -1/3 & 4/3 \\ 1 & 0 & -1/3 & 2/3 & 10/3 \\ \hline 0 & 0 & 4/3 & 1/3 & 32/3 \\ \end{array} \]
所有检验数非负，达到最优解。
步骤7：解读结果
最优解：
\[x_1 = \frac{10}{3}, \quad x_2 = \frac{4}{3}, \quad z = \frac{32}{3} \]
松弛变量 \(x_3 = x_4 = 0\)，表示两个约束均为紧约束。Bland规则通过固定变量选择顺序避免了循环，本例中仅需两次迭代。