单纯形法示例
【例题】求 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 |
……我不想算了,鸽了,明天再写