单纯形法求解线性规划问题示例-Toy模板网

这篇具有很好参考价值的文章主要介绍了单纯形法求解线性规划问题示例。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引言

今天被一个人问到了一个线性规划问题，这个问题我印象中只有在数学建模中会出现，于是就研究了一下，这里做一个记录。

示例

线性规划问题如下：
$\text{max} \quad z = 90x_1 + 70x_2 \\ \begin{align} s.t.\left\{\begin{matrix} x_1 + x_2 &\le 16 \\ 3x_1 + 2x_2 &\le36 \\ 5x_2 &\le 65\\ x_1, x_2 &\ge 0 \end{matrix}\right. \nonumber \end{align} \tag{1}$
先将模型化为标准型：
$\text{max} \quad z = 90x_1 + 70x_2 \\ \begin{align} s.t.\left\{\begin{matrix} x_1 + x_2 + x_3 &= 16 \\ 3x_1 + 2x_2 + x_4 &= 36\\ 5x_2 + x _5 &= 65\\ x_1, x_2,x_3,x_4,x_5 &\ge 0 \nonumber \end{matrix}\right. \end{align} \tag{2}$
标准形式下的约束条件系数矩阵的增广矩阵可以表示为：
$\begin{bmatrix} 1 & 1 & 1 & 0 & 0 &| 16\\ 3 & 2 & 0 & 1 & 0 &|36 \\ 0 & 5 & 0 & 0 & 1 &|65 \end{bmatrix}$
显然，我们应将 $x_3, x_4, x_5$ 视为基变量，且将 $x_1, x_2$ 视作非基变量。接下来，令 $x_1, x_2 = 0$ ，找到初始基可行解 $\left(0, 0, 16, 36, 65\right)$ ，列出初始的单纯形表：

$x_B$	b	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$\theta$
$x_3$	16	1	1	1	0	0	16
$x_4$	36	3	2	0	1	0	12
$x_5$	65	0	5	0	0	1
z	0	90	70	0	0	0

观察（2）式可知，其中只有两个关于 $x_1$ 的约束条件：
$\begin{align} x_1 + x_2 + x_3 &= 16 \tag{3} \\ 3x_1 + 2x_2 + x_4 &= 36 \tag{4} \end{align}$
现在我们要对 $x_1$ 进行研究，因此，首先令 $x_2 = 0$ 。

对于（3）式，如果我们令 $x_3$ 减小到 0，那么 $x_1$ 最大可以取到 16。对于（4）式，如果我们令 $x_4$ 减小到 0，那么 $x_1$ 最大可以取到 12。因为两个约束条件共同作用，因此， $x_1$ 最大只能增加到 12。如上述表格中的 $\theta$ 所示。

此时，我们需要将 $x_1$ 作为换入变量，将 $x_4$ 作为换出变量。那么当完成替换后，z 值的增量为：
$z_{\text{increase}} = 12 \times 90 = 1080$
我们需要将上表中所有 $x_4$ 对应行中的 $x_1$ 的系数化简为 1，其余行 $x_1$ 的系数化 0，因此，我们需要进行行列式变换，变换后，我们得到新的单纯形表为：

$x_B$	b	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$\theta$
$x_3$	4	0	$\frac{1}{3}$	1	- $\frac{1}{3}$	0	16
$x_1$	12	1	$\frac{2}{3}$	0	$\frac{1}{3}$	0	12
$x_5$	65	0	5	0	0	1
z	1080	0	10	0	-35	0

对于（4）式，当 $x_3 = 0$ ， $x_2$ 每增大 1， $x_1$ 需要减小 $\frac{2}{3}$ ，因此， $x_2$ 每增大 1，对应 z 值的变化量为：
$\begin{align} z_{\text{variation}} &= z_{x_1} + z_{x_2} \nonumber \\ &= 90 \times (-\frac{2}{3}) + 70 \times 1 \nonumber \\ & = -60 + 70 \nonumber \\ &= 10 \nonumber \end{align}$
对于（4）式，当 $x_1 = 0$ ， $x_2$ 每增大 1， $x_2$ 需要减小 $\frac{1}{2}$ ，因此， $x_4$ 每增大 1，对应 z 值的变化量为：
$\begin{align} z_{\text{variation}} &= -\frac{1}{2} \times 70 \nonumber \\ &= -35 \nonumber \end{align}$
替换完成后的非基变量变成了 $x_2, x_4$ ，接下来需要考虑将 $x_2$ 换入，三个约束条件均包含 $x_2$ 变量：
$\begin{align} x_1 + x_2 + x_3 &= 16 \tag{5} \\ 3x_1 + 2x_2 + x_4 &= 36 \tag{6} \\ 5x_2 + x _5 &= 65 \tag{7} \end{align}$
现在我们要对 $x_2$ 进行研究，因此，首先令 $x_1 = 0$ 。

对于（5）式，当 $x_3$ 减小到 0 时， $x_2$ 最大可以取到 16。对于（6）式，当 $x_4$ 减小到 0 时， $x_2$ 最大可以取到 18。对于（7）式，当 $x_5$ 减小到 0 时， $x_2$ 最大可以取到 13。因此， $x_2$ 的最大值只能取到 13。

类比上面相同的行列式操作，最终我们可以得到的单纯形表为：

$x_B$	b	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
$x_3$	$\frac{1}{3}$	0	0	1	- $\frac{1}{3}$	$\frac{1}{15}$
$x_1$	$\frac{10}{3}$	1	0	0	$\frac{1}{3}$	- $\frac{2}{15}$
$x_2$	13	0	1	0	0	$\frac{1}{5}$
z	1210	0	0	0	-14	-2

对应上述单纯表，最终我们可以将标准模型变为：
$\text{max} \quad z = 90x_1 + 70x_2 \\ \begin{align} s.t.\left\{\begin{matrix} x_3 - \frac{1}{3}x_4 + \frac{1}{15}x_5&= \frac{1}{3} \\ x_1 + \frac{1}{3}x_4 - \frac{2}{15}x_5 &= \frac{10}{3} \\ x_2 + \frac{1}{5}x _5 &= 13 \\ x_1, x_2,x_3,x_4,x_5 &\ge 0 \nonumber \end{matrix}\right. \end{align} \tag{8}$
对于（7）式， $x_5$ 每增大 1， $x_2$ 需要减小 $\frac{1}{5}$ ，因此， $x_5$ 每增大 1，对应 z 值的变化量为：
$\begin{align} z_{\text{variation}} &= -\frac{1}{5} \times 10 \nonumber \\ &= -2 \nonumber \end{align}$
对于（7）式， $x_5$ 每增大 1， $x_2$ 需要减小 $\frac{1}{5}$ ，再考虑约束（6）式， $x_2$ 每减小 1， $x_4$ 需要增加 $\frac{2}{5}$ ，对应 z 值的变化量为：
$\begin{align} z_{\text{variation}} &= -\frac{2}{5} \times 35 \nonumber \\ &= -14 \nonumber \end{align}$
最终，z 值的最大值为：
$z_{\text{increase}} = 1080 + 10 \times 13 = 1080 + 130 = 1210$
因此，我们说，我们求解的原始线性规划问题等同于求解方程 $y = 1210 -14x_4 - 2x_5$ 的最大值问题。