Site Overlay

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

单纯形法示例

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

$$
\left\{\begin{aligned}
2 x_{1}+2 x_{2} & \leq 12 \\
x_{1}+2 x_{2} & \leq 8 \\
4 x_{1} & \leq 16 \\
4 x_{2} & \leq 12 \\
x_{1}, x_{2} \geq 0
\end{aligned}\right.
$$

【解答】

由于有四个约束式,引入四个松弛变量 $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}$

约束矩阵为:

$$
\begin{bmatrix}2&2&1&0&0&0\\ \:\:1&2&0&1&0&0\\ \:\:4&0&0&0&1&0\\ \:\:0&4&0&0&0&1\end{bmatrix}\begin{bmatrix}x_1\\ \:\:x_2\\ \:\:x_3\\ \:\:x_4\\ \:\:x_5\\ \:\:x_6\end{bmatrix}=\begin{bmatrix}12\\ \:\:8\\ \:\:16\\ \:\:12\end{bmatrix}
$$

(2)画单纯形表。

Cj 2 3 0 0 0 0 theta_i
CB XB b x1 x2 x3 x4 x5 x6
0 x3 12 2 2 1 0 0 0
0 x4 8 1 2 0 1 0 0
0 x5 16 4 0 0 0 1 0
0 x6 12 0 4 0 0 0 1

然后写检验数$c_j - z_j$

Cj $\color{blue}2$ 3 0 0 0 0 theta_i
CB XB b x1 x2 x3 x4 x5 x6
$\color{orange}0$ x3 12 $\color{purple}2$ 2 1 0 0 0
$\color{orange}0$ x4 8 $\color{purple}1$ 2 0 1 0 0
$\color{orange}0$ x5 16 $\color{purple}4$ 0 0 0 1 0
$\color{orange}0$ x6 12 $\color{purple}0$ 4 0 0 0 1
$c_j - z_j$ $\color{red}2$ 3 0 0 0 0

检验数从何而来?以上面红色的 $\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。

Cj 2 3 0 0 0 0 theta_i
CB XB b x1 x2 x3 x4 x5 x6
0 x3 12 2 2 1 0 0 0 6
0 x4 8 1 2 0 1 0 0 4
0 x5 16 4 0 0 0 1 0 -
0 x6 12 0 4 0 0 0 1 3
cj-zj 2 3 0 0 0 0

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

Cj 2 3 0 0 0 0 theta_i
CB XB b x1 x2 x3 x4 x5 x6
0 x3 12 2 2 1 0 0 0 6
0 x4 8 1 2 0 1 0 0 4
0 x5 16 4 0 0 0 1 0 -
0 x6 12/4 0 4/4 0 0 0 1/4 3/4
cj-zj 2 3 0 0 0 0

得到:

Cj 2 3 0 0 0 0 theta_i
CB XB b x1 x2 x3 x4 x5 x6
0 x3 12 2 2 1 0 0 0 6
0 x4 8 1 2 0 1 0 0 4
0 x5 16 4 0 0 0 1 0 -
0 x6 3 0 1 0 0 0 1/4 3/4
cj-zj 2 3 0 0 0 0

注意到 $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$ 行:

Cj 2 3 0 0 0 0 theta_i
CB XB b x1 x2 x3 x4 x5 x6
0 x3 12-6 2 2-2 1 0 0 0-1/2
0 x4 8-6 1 2-2 0 1 0 0-1/2
0 x5 16 4 0 0 0 1 0
0 x6 3 0 1 0 0 0 1/4 3/4
cj-zj 2 3 0 0 0 0

所得为:

Cj 2 3 0 0 0 0 theta_i
CB XB b x1 x2 x3 x4 x5 x6
0 x3 6 2 0 1 0 0 -1/2
0 x4 2 1 0 0 1 0 -1/2
0 x5 16 4 0 0 0 1 0
0 x6 3 0 1 0 0 0 1/4
cj-zj 2 3 0 0 0 0

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

Cj 2 $\color{blue}3$ 0 0 0 0 theta_i
CB XB b x1 x2 x3 x4 x5 x6
0 x3 6 2 0 1 0 0 -1/2
0 x4 2 1 0 0 1 0 -1/2
0 x5 16 4 0 0 0 1 0
$\color{red}3$ $\color{red}x_2$ 3 0 1 0 0 0 1/4
cj-zj 2 3 0 0 0 0

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

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

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

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

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

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

$$
\begin{array}{l}
\max Z=3 x_{1}+4 x_{2}+x_{3} \\
\left\{\begin{array}{l}
2 x_{1}+3 x_{2}+x_{3} \leq 1 \\
x_{1}+2 x_{2}+2 x_{3} \leq 3 \\
x_{j} \geq 0, j=1,2,3
\end{array}\right.
\end{array}
$$

大 M 法(人工变量法)示例

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

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

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

$$
\left\{\begin{array}{l}
x_{1}+x_{2}+x_{3} \leq 4 \\
-2x_{1}+x_{2}- x_{3} \geq 1 \\
3x_2+x_3 = 9
\end{array}\right.
$$

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

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

$$
x_{1}+x_{2}+x_{3} + {\color{red}x_4}\leq 4
$$

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

$$
-2x_{1}+x_{2}- x_{3} - {\color{red}x_5 }\geq 1
$$

这样,标准形式为:

$$
\left\{\begin{array}{l}
x_{1}&+x_{2}&+x_{3}& + x_4&=& 4 \\
-2x_{1}&+x_{2}&- x_{3}& - x_5&=& 1 \\
&3x_2&+x_3& &=& 9
\end{array}\right. \tag{2.1}
$$

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

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

$$
\left\{\begin{array}{l}
x_{1}&+x_{2}&+x_{3}& + x_4&&&=& 4 \\
-2x_{1}&+x_{2}&- x_{3}&& - x_5 + a_1&&=& 1 \\
&3x_2&+x_3&&& +a_2&=& 9
\end{array}\right. \tag{2.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 标注进出基的变量)

Cj -3 0 1 0 0 -M -M theta_i
cb xb b x1 x2 x3 x4 x5 a1 a2
0 x4 4 1 1 1 1 0 0 0 4
-M a1 1 -2 1 -1 0 -1 1 0 1 v
-M a2 9 0 3 1 0 0 0 1 3
ci-zj -3-2M 4M 1 0 -M 0 0
v
Cj -3 0 1 0 0 -M -M theta_i
cb xb b x1 x2 x3 x4 x5 a1 a2
0 x4 3 3 0 2 1 1 -1 0 3/2
0 x2 1 -2 1 -1 0 -1 1 0 -1
-M a2 6 6 0 4 0 3 -3 1 3/2 v
ci-zj -3+6M 0 1+4M 3M -4M -2M
v
Cj -3 0 1 0 0 -M -M theta_i
cb xb b x1 x2 x3 x4 x5 a1 a2
0 x4 0 0 0 0 1 -1/2 1/2 -1/2
0 x2 5/2 -1/2 1 0 0 -1/4 1/4 1/4
1 x3 3/2 3/2 0 1 0 3/4 -3/4 1/4
ci-zj -9/2 0 0 0 -3/4 -M+3/4 -M-1/4

所有检验数都不大于零了。从而我们得到了最优解(终于口算算对一次,呜呜呜):

$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$。约束标准型依旧是:

$$
\left\{\begin{array}{l}
x_{1}&+x_{2}&+x_{3}& + x_4&&&=& 4 \\
-2x_{1}&+x_{2}&- x_{3}&& - x_5 + a_1&&=& 1 \\
&3x_2&+x_3&&& +a_2&=& 9
\end{array}\right. \tag{2.2}
$$

第一次迭代:

Cj 0 0 0 0 0 -1 -1 theta_i
cb xb b x1 x2 x3 x4 x5 a1 a2
0 x4 4 1 1 1 1 0 0 0 4
-1 a1 1 -2 1 -1 0 -1 1 0 1 V
-1 a2 9 0 3 1 0 0 0 1 3
ci-zj -2 4 0 0 -1 0 0
V

第二次迭代:

Cj 0 0 0 0 0 -1 -1 theta_i
cb xb b x1 x2 x3 x4 x5 a1 a2
0 x4 3 3 0 2 1 1 -1 0 1
0 x2 1 -2 1 -1 0 -1 1 0 -1/2
-1 a2 6 6 0 4 0 3 -3 1 1 v
ci-zj 6 0 4 0 3 -4 0
v

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

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注