约束与极小化函数一致时的两阶段单纯形法求解技术问询

我来一步步带你拆解这个线性规划问题的两阶段单纯形法求解过程，每一步的逻辑都讲得明明白白：

原问题明确 #

首先先把问题摆清楚：

目标函数：最大化 $Z = x - y$
约束条件：
$$-x + y \ge 1$$
$$x \ge 0,\ y \ge 0$$

步骤1：约束条件转化（引入剩余/人工变量） #

因为约束是$\ge$型，我们需要减去剩余变量$s$（用于把不等式转成等式），同时加上人工变量$a$（用来构造初始基可行解，人工变量仅在第一阶段使用），转化后的等式约束为：
$$-x + y - s + a = 1$$
其中$s \ge 0$，$a \ge 0$。

第一阶段：消去人工变量，验证原问题可行性 #

第一阶段的核心目标是最大化$W = -a$（等价于最小化人工变量$a$，当$W=0$时，$a=0$，说明原问题存在可行解）。

我们从约束式中解出$a = 1 + x - y + s$，代入$W$的表达式得：
$$W = -a = -1 -x + y -s$$

对应的初始单纯形表如下（基变量为$a$）：

|   | x  | y  | s  | a  | b  |
|---|----|----|----|----|----|
| a | -1 | 1  | -1 | 1  | 1  |
|---|----|----|----|----|----|
| W | -1 | 1  | -1 | 0  | 1  |

找进基变量 #

最大化$W$时，我们要选目标行（W行）中系数为正的非基变量（因为增加这类变量能让$W$变大）。这里$y$的系数是1，是唯一的正系数，所以选$y$作为进基变量。

找出基变量 #

进基变量确定后，看$y$列的约束行系数（只有$a$行的系数是1，为正），计算右端项除以该系数：$1/1 = 1$，所以出基变量是$a$。

转轴运算（围绕$a$行$y$列的1进行变换） #

• 首先把$a$行替换为$y$行，该行元素不变：-1, 1, -1, 1, 1
• 然后更新$W$行：用$W$行减去$y$行的1倍，把$y$列的系数消为0：
  • x列：$-1 - (-1)*1 = 0$
  • y列：$1 - 1*1 = 0$
  • s列：$-1 - (-1)*1 = 0$
  • a列：$0 - 1*1 = -1$
  • b列：$1 - 1*1 = 0$

转轴后的单纯形表：

|   | x  | y  | s  | a  | b  |
|---|----|----|----|----|----|
| y | -1 | 1  | -1 | 1  | 1  |
|---|----|----|----|----|----|
| W | 0  | 0  | 0  | -1 | 0  |

第一阶段结论 #

此时$W=0$，说明人工变量$a=0$，原问题可行，基变量变为$y$，非基变量为$x、s、a$（$a$已退化为0）。

第二阶段：求解原问题的最优解 #

现在回到原目标函数$Z = x - y$，我们基于第一阶段的最终表，把$W$行替换为$Z$行，进行最优性判断。

首先把原目标函数整理为：$Z - x + y = 0$。因为当前基变量是$y$，我们需要把$Z$行中$y$的系数消为0：
用$Z$行加上$y$行的1倍，计算后得到新的$Z$行：

• x列：$1 + (-1)*1 = 0$
• y列：$-1 + 1*1 = 0$
• s列：$0 + (-1)*1 = -1$
• b列：$0 + 1*1 = 1$

同时，人工变量$a$已经没用了，我们可以去掉$a$列，得到第二阶段的单纯形表：

|   | x  | y  | s  | b  |
|---|----|----|----|----|
| y | -1 | 1  | -1 | 1  |
|---|----|----|----|----|
| Z | 0  | 0  | -1 | 1  |

最优性判断与结论 #

观察$Z$行的非基变量系数：

• $s$的系数是-1（负的），增加$s$会让$Z$变小，不符合最大化目标；
• $x$的系数是0，说明增加$x$不会改变$Z$的值，同时看$x$列的约束行系数是-1，意味着我们可以任意增加$x$的值（只要保证$y = 1 + x + s \ge 0$，而$s$取0时，$y = 1 + x$，满足$y \ge 0$）。

这说明原问题存在无穷多最优解，最优值为$Z=-1$，所有最优解满足：
$$y = x + 1$$
$$x \ge 0,\ y \ge 0$$

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