运筹学笔记：单纯形法、大 M 法和两阶段法详解

单纯形法示例

【例题】求 max $Z = 2x_1 + 3x_2$。约束为：

【解答】

由于有四个约束式，引入四个松弛变量 $x_3, x_4, x_5, x_6$。

（1）化标准型。目标函数为：$\max Z=2 x_{1}+3 x_{2}+0 x_{3}+0 x_{4}+0 x_{5}+0 x_{6}$。

约束矩阵为：

（2）画单纯形表。

然后写检验数（$c_j - z_j$）

检验数从何而来？以上面红色的 $\color{red}2$ 为例，计算过程是 $\color{blue}2 - \color{orange}0 \times \color{purple}2- \color{orange}0 \times \color{purple}1 - \color{orange}0 \times \color{purple}4- \color{orange}0 \times \color{purple}0$ 。也即用此列的 $C_j$ 减去 $c_B$ 和 $x_1$ 两个列的点乘。

接下来我们要选列，由于求的是最大值，所以我们选择检验数最大的列。也即 $x_3$ 列。这意味着将要把 $x_3$ 作为新的基变量。

然后计算 b列 与所选列的比值，一个一个地比，结果放到 theta_i。

我们选择其中比值最小的行 $\min(6,4,3) = 3$，所以选择 $x_b=x_6$ 这一行，把这一行除以 $4$（也即： $x_b=x_6$ 与 $x_2$ 交叉之处），以进行单位化：

得到：

注意到 $x_2$ 这一列的构成是 $\begin{bmatrix}2\\2\\0\\1\end{bmatrix}$。我们要通过矩阵初等行变换，把它变成 $\begin{bmatrix}0\\0\\0\\1\end{bmatrix}$。具体来说，把 $x_3, x_4$ 行分别减去 2 倍 $x_6$ 行：

所得为：

于是我们得到了一个新的 $4\times 4$ 单位矩阵。此前的 $x_6$ 不再构成单位矩阵，称为 出基变量，新来的 $x_2$ 参与构成单位矩阵，称为 进基变量。上表改写为：

其中的 $x_2$ 是进基变量。$3$ 是进基变量对应的 $c_j$ 值（上面以蓝色标出）。

再次计算检验数（循环步骤），直到所有的检验数都小于零。即可得到最优解。

注意：如果 $\theta_i$ 出现负数，则不参与大小比较，记个 $\times$ 就行了。

此时的 $c_b$ 列与 $b$ 列点乘的值就是最优值。$x_b$ 与 $b$ 的对应组合就是最优解。具体的计算视频示例详见：

https://www.bilibili.com/video/BV1j7411d7Gm（本文只是记录了他的做法，以便快速复习）

【练习】用单纯形法求解：

大 M 法（人工变量法）示例

在单纯形法中，不等式都是 $\leq$ 符号，我们在不等式的左边引入 松弛变量。

但是，如果出现了 $\geq$ 符号，则需要引入 剩余变量。我们怎样做呢？

例如，求解 $\max Z = -3x_1 + x_3$，使得：

其中所有变量要求大于零。

对于第一个不等式 $ x_{1}+x_{2}+x_{3} \leq 4$，我们引入松弛变量 $x_4$：

对于第二个不等式 $-2x_{1}+x_{2}- x_{3} \geq 1$，我们引入剩余变量 $x_5$：（即在左边引入一个减去的变量）

这样，标准形式为：

我们需要从一个初始基本可行解开始求解。在常规的单纯形法中，我们可以找到一个基，也就是基本可行解构成的单位矩阵 $\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}$（列的位置可以置换）。但是在上面的标准型 $(2.1)$ 式中，无法找出这样一个单位阵。怎么办呢？

我们可以引入新的变量，叫做 人工变量，从而使得初始可行解单位矩阵能够构造出来。下面引入了 $a_1, a_2$

其中 $a_1, a_2 \geq 0$

为什么要这样引入呢？为什么不把 $-x_5$ 这一行乘以 $-1$ ，然后把所在列当作单位矩阵的一列呢？这是因为乘以 $-1$ 之后就破坏了 $x_5 > 0$ 的约束条件。所以我们利用 $x_4$ 构成单位矩阵的一个列，再增加 $a_1$ 和 $a_2$ 到第二个和第三个不等式，构成单位矩阵的另外两列。

而为了保证等式成立， $a_1, a_2$ 实际上只能取 $0$ 值，如果不取 $0$，会使得上面的等式不成立，代表 无可行解。

下面我们还要在目标函数中引入人工变量，使得所有人工变量取 0 时，目标函数的最大值和原来函数的最大值一样。

原来的目标函数：$\max Z = -3x_1 + x_3$，如果我们这样引入人工变量：

$\max Z = -3x_1 + x_3 - a_1 - a_2$，但 $a_1, a_2$ 很小的时候对 $Z$ 的影响不大，我们需要让它的影响足够大，从而让 $a_1, a_2$ 越小的时候，函数值越大，所以引入惩罚因子 $M$，$M$ 是一个极大的数值。引入之后是这样：

$\max Z = -3x_1 + x_3 - Ma_1 - Ma_2$

这样的话，即使 $a_1, a_2$ 很小，但被惩罚因子放大之后，对 $Z$ 的函数值就会起到很大的降低效果。从而逼迫 $a_1, a_2$ 趋近 0，从而尽可能取得 $Z$ 的最大值。

下面进行迭代计算：（我用 v 标注进出基的变量）

所有检验数都不大于零了。从而我们得到了最优解（终于口算算对一次，呜呜呜）：

$x_1 = 0, x_2 = 5/2, x_3 = 3/2$

$\max Z = 0 \times 0 + 0 \times 5/2 + 1 \times 3/2= 3/2$

不过同时，我们也发现了大 $M$ 法的缺点：计算检验数和选取检验数最大值的时候，存在一个 M 使得计算变得麻烦。于是我们引入 两阶段法。

两阶段法

我们的目标就是让 $a_1, a_2 = 0$ 的时候有可行解。所以目标函数可以设定为 $\min f = a_1 + a_2$（或者 $\max Z = -a_1 - a_2$）

在第二阶段，丢掉人工变量进行计算。

具体操作如下：

第一阶段

我们设目标函数为 $\max Z = -a_1 -a_2$。约束标准型依旧是：

第一次迭代：

第二次迭代：

……我不想算了，鸽了，明天再写