两阶段单纯形法（RHS=0）求解遇阻，求线性规划问题解法指导

没问题，我来一步步帮你走完这个两阶段单纯形法的求解过程，咱们从你已经完成的第一阶段初始框架开始梳理～

你已经把原线性规划问题转化为带松弛变量和人工变量的等式系统，这一步是完全正确的：

• 原问题：$\text{min } Z = y$，约束 $\begin{cases} x \ge 1 \ -2x + y \ge 0 \end{cases}$
• 转化为等式系统：$\begin{cases} x - s_1 + a_1 = 1 \quad (\text{引入松弛变量}s_1, \text{人工变量}a_1) \ -2x + y - s_2 = 0 \quad (\text{仅引入松弛变量}s_2) \end{cases}$

第一阶段的目标是最大化 $p = -a_1$（通过消除人工变量得到原问题的可行解），代入第一个约束的 $a_1 = 1 - x + s_1$，得到 $p = x - s_1 - 1$，这个推导也没问题。

我们先把初始单纯形表列清楚（变量顺序：$x, y, s_1, s_2, a_1$，基变量为 $a_1$ 和 $s_2$）：

接下来执行单纯形迭代：

1. 选进基变量：对于最大化 $p$，我们计算检验数 $\sigma_j = c_j - z_j$（$c_j$ 是 $p$ 中变量的系数，$z_j$ 是基变量系数乘对应列系数之和）。这里 $p$ 中只有 $a_1$ 的系数为 $-1$，其他变量系数为0，所以 $\sigma_x = 0 - (-1 \times 1 + 0 \times -2) = 1 > 0$，说明增加 $x$ 能让 $p$ 增大，选 $x$ 作为进基变量。
2. 选离基变量：计算各基变量行中 $x$ 的正系数对应的 $\text{RHS}/\text{系数}$，只有 $a_1$ 行的系数为1，比值为 $1/1=1$，所以 $a_1$ 作为离基变量。
3. 行变换：将 $x$ 行（原 $a_1$ 行）保持不变，把其他行的 $x$ 系数消为0：
   • $s_2$ 行：原行 $+2 \times x$ 行 → $0x + 1y + 0s_1 -1s_2 +2a_1 = 2$
   • $p$ 行：原行 $+1 \times x$ 行 → $1p +0x +0y +0s_1 +0s_2 +1a_1 = 0$

得到第一阶段结束后的单纯形表：

此时 $p=0$，人工变量 $a_1$ 成为非基变量（值为0），说明我们已经得到了原问题的可行解：$x=1, y=2, s_1=0, s_2=0$。

去掉人工变量 $a_1$，目标转为最小化 $Z=y$，构造第二阶段的单纯形表（变量顺序：$x, y, s_1, s_2$，基变量为 $x$ 和 $y$）：

对于最小化问题，我们需要检验所有非基变量的检验数 $\sigma_j = z_j - c_j$（$z_j$ 是基变量系数乘对应列系数之和，$c_j$ 是 $Z$ 中变量的系数）：

• $\sigma_{s_1} = (0 \times -1 + 1 \times 2) - 0 = 2 \ge 0$
• $\sigma_{s_2} = (0 \times 0 + 1 \times 1) - 0 = 1 \ge 0$

所有非基变量的检验数都≥0，说明当前可行解 $x=1, y=2$ 就是原问题的最优解，此时 $Z_{\text{min}}=2$。

为什么不能继续迭代？因为任何增加非基变量 $s_1$ 或 $s_2$ 的操作，都会导致 $y=2+2s_1+s_2$ 增大，从而让 $Z=y$ 变大，无法得到更小的目标值。

内容的提问来源于stack exchange，提问作者KarelPeeters