运筹学的第一课：单纯形法

朱雀 2023-01-01 11:51 191阅读 0赞

### 文章目录 ###

*  导读
 *  单纯形法简介
 *  单纯形法的步骤简介
 *  单纯形法的一些说明
 *   *  决策变量
     *  基变量
     *  工艺常数
     *  右端常数
     *  空白处
     *   θ \\theta θ
     *  检验数
     *  把其中的一些部分组合起来
     *  约束方程
     *  典则形式
 *  计算步骤
 *   *  判断条件（一）
     *  出基和进基
     *  矩阵变换
     *  判断条件（二）
     *  写出结果
 *  总结

# 导读 #

运筹学第一课会给你讲**线性规划**，也就是从初中以来我们拿多元一次方程组做的“**旅游叫车问题**”、“**投资问题**”等等。相信在这个时候，每个人的第一印象是：**我感觉我行了**。然后老师就开始讲**单纯形法**。从那时候起，**理智直接归零**，再也没恢复，于是便**带着满脑子问号开始了除了上课以外的其他任何事情**。

这里就简单梳理一下单纯形法的**概念**和**步骤**。

# 单纯形法简介 #

> 单纯形法是求解线性规划问题最常用、最有效的算法之一。单纯形法最早由 George Dantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止 。
> 
> ——摘自[百度百科【单纯形法】][Link 1]

简单地说，单纯形法就是**解决线性规划的另一种选择**。毕竟，我们既然在大学的线性代数里面学习了**多元一次方程**和**增广矩阵**，那么单纯形法就单纯的是**用大学生的方法解决初中生的问题**。那这个锅老师就不该背了，**感觉难实际上是工具难用**。

# 单纯形法的步骤简介 #

题目一开始会给定约束方程，比如说：

\{ 5 x 1 + 6 x 2 ≤ 10 3 x 1 − 2 x 2 ≥ 6 x 1 , x 2 ≥ 0 \\left\\\{\\begin\{matrix\} 5x\_1&+&6x\_2&\\le&10\\\\ 3x\_1&-&2x\_2&\\ge&6\\\\ x\_1&,&x\_2&\\ge&0 \\end\{matrix\}\\right. ⎩⎨⎧5x13x1x1\+−,6x22x2x2≤≥≥1060

然后就让你求目标函数的最优解，就假设是：

z m a x = 9 x 1 + 8 x 2 z\_\{max\}=9x\_1+8x\_2 zmax=9x1\+8x2

如果单纯使用**线性规划**做，**两个**未知数的情况下是可以做的。但是**四个**呢？**十个**呢？这些就没有办法了。

而矩阵就是高维的抽象表达，可以参考我之前写的[多元函数的梯度下降][Link 2]。所以，这里就用我们大学里面最熟悉的**增广矩阵**来解决这些**非线性的多元一次方程组**。

但是直接做肯定是不可以的，因为使用条件是**方程组**，这就规定了**必须**得是**等式**。所以，人为的添加变量：

\{ 5 x 1 + 6 x 2 + x 3 = 10 3 x 1 − 2 x 2 − x 4 = 6 x 1 , x 2 , x 3 , x 4 ≥ 0 \\left\\\{\\begin\{matrix\} 5x\_1&+6x\_2&+x\_3&&=&10\\\\ 3x\_1&-2x\_2&&-x\_4&=&6\\\\ x\_1,&x\_2,&x\_3,&x\_4&\\ge&0 \\end\{matrix\}\\right. ⎩⎨⎧5x13x1x1,\+6x2−2x2x2,\+x3x3,−x4x4==≥1060

虽然第三个式子依然是不等式，但是这个**没什么影响**。我们可以**不考虑第三个不等式**然后**求出所有的解**，最后根据第三个不等式**筛选出全都是正数的解**就好了。

于是，整个方程组就剩下：

\{ 5 x 1 + 6 x 2 + x 3 = 10 3 x 1 − 2 x 2 − x 4 = 6 \\left\\\{\\begin\{matrix\} 5x\_1&+6x\_2&+x\_3&&=&10\\\\ 3x\_1&-2x\_2&&-x\_4&=&6 \\end\{matrix\}\\right. \{ 5x13x1\+6x2−2x2\+x3−x4==106

我们做出增广矩阵

\[ 5 6 1 0 10 3 − 2 0 − 1 6 \] \\left\[\\begin\{matrix\} 5&6&1&0&10\\\\3&-2&0&-1&6 \\end\{matrix\}\\right\] \[536−2100−1106\]

但是我们的目标是**找出最优**，而不是**求出解**。所以再加上一些行列：

突然蒙圈了？没有关系，看看下面的说明

# 单纯形法的一些说明 #

简介不需要明白太多，毕竟几十年前的东西了。这里就直接开始说明矩阵的构成。

由于市面上不同的书有着不同的版本，我这里就选择[西安邮电大学史新峰老师的教学视频][Link 3]里使用的矩阵格式进行说明，因为**这个矩阵是我认为最简洁最好懂的**。

另外说明一点：我会把需要说明的部分**高亮**标记，但是这**并不代表文字对应的意义**，而应当**是表格的该位置对应的意义**。

## 决策变量 ##

以下表格中**标红**的便是**决策变量**

<table> 
 <thead> 
 <tr> 
 <th></th> 
 <th> x 1 x_1 x1</th> 
 <th> x 2 x_2 x2</th> 
 <th> x 3 x_3 x3</th> 
 <th> x 4 x_4 x4</th> 
 <th> b b b</th> 
 <th> θ \theta θ</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> x 3 x_3 x3</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 <tr> 
 <td> x 4 x_4 x4</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 <tr> 
 <td> λ j \lambda_j λj</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

## 基变量 ##

下面这个表格中**标蓝**的是**基变量**

## 工艺常数 ##

下面这个矩阵中**标绿**了的地方就是**工艺常数**。

## 右端常数 ##

下面这张表中标记为**冷铜色**的地方就是右端常数

## 空白处 ##

下面表格中使用 Φ \\Phi Φ填充的格子中，**并没有**可以填的数据，所以一般都**空着**。

##  θ \\theta θ ##

下面表格中**标紫**了的地方就是 θ \\theta θ

## 检验数 ##

下面表格中**标蓝**了的地方就是**检验数**

其实这一行是**人工添加**的，就像是**特征工程**里面会人工添加特征让数据更清晰一样。这里原本应当填入的数据是我们的**目标函数**。我们一开始拿到的目标方程是 z m a x = 9 x 1 + 8 x 2 z\_\{max\}=9x\_1+8x\_2 zmax=9x1\+8x2，那么就应当是**填成表格上所显示的那样**。

## 把其中的一些部分组合起来 ##

到这里，表格的每个部分代表什么意思都已经介绍完了。接下来，一些特定部分组合起来也有特殊的意义。

## 约束方程 ##

在这里其实约束方程**并不是一开始题目所给的不等式方程组**，**而是我们人工添加变量后拿到的等式方程组**。

也就是**工艺常数**部分加上**右端常数**部分。

## 典则形式 ##

是**约束方程**部分加上**检验数**部分，也就是**工艺常数**、**右端常数**以及**检验数**。

# 计算步骤 #

好了，全部介绍完了，接下来就是真正的计算了。

类似我们刚刚举例的“**典则形式**”应该是没有什么问题了吧？先完善一个**增广矩阵**，接着再根据**目标函数**把下面的**检验数**补齐。这都没什么问题。问题在下面的**寻找最优**。

## 判断条件（一） ##

什么时候我们拿到了最优解？那就是**检测数没有正数**的时候。我们可以看到现在的典则形式还有 9 9 9和 8 8 8两个正数，所以现在显然不是最优解。

## 出基和进基 ##

既然不是最优解，那么我们就根据**出基**和**入基**的规则进行判断。首先，我们选择**检测数最大**的一个，也就是 9 9 9，即 x 1 x\_1 x1列。接着我们用 x 1 x\_1 x1列的数字**根据行对应**分别除以**右端常数**，bin并将得出来的数字一一根据行对应填在 θ \\theta θ列内，得：

接着我们再**从 θ \\theta θ列中选择一个最小的**（*由于这里都是 2 2 2，所以我选择 x 3 x\_3 x3行*），也就是 x 3 x\_3 x3。于是， x 1 x\_1 x1就**成为**了基变量，叫**进基**； x 3 x\_3 x3就**不再是**基变量，叫**出基**。

于是矩阵稍微改写（将**基变量**部分中的 x 3 x\_3 x3改为 x 1 x\_1 x1）：

## 矩阵变换 ##

线性代数告诉我们：在研究高维度的时候，如果有几个**相互垂直**的单位向量，那么一定会这么写：

<table> 
 <thead> 
 <tr> 
 <th></th> 
 <th> e 1 e_1 e1</th> 
 <th> e 2 e_2 e2</th> 
 <th> ⋯ \cdots ⋯</th> 
 <th> e n e_n en</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> e 1 e_1 e1</td> 
 <td> 1 1 1</td> 
 <td> 0 0 0</td> 
 <td> ⋯ \cdots ⋯</td> 
 <td> 0 0 0</td> 
 </tr> 
 <tr> 
 <td> e 2 e_2 e2</td> 
 <td> 0 0 0</td> 
 <td> 1 1 1</td> 
 <td> ⋯ \cdots ⋯</td> 
 <td> 0 0 0</td> 
 </tr> 
 <tr> 
 <td> ⋮ \vdots ⋮</td> 
 <td> ⋯ \cdots ⋯</td> 
 <td> ⋯ \cdots ⋯</td> 
 <td> ⋯ \cdots ⋯</td> 
 <td> ⋯ \cdots ⋯</td> 
 </tr> 
 <tr> 
 <td> e n e_n en</td> 
 <td> 0 0 0</td> 
 <td> 0 0 0</td> 
 <td> ⋯ \cdots ⋯</td> 
 <td> 1 1 1</td> 
 </tr> 
 </tbody> 
</table>

所以，如果 x 1 x\_1 x1作为基变量，那么我们刚刚确认的 x 1 x\_1 x1列和 x 3 x\_3 x3行交界处应当通过**初等行变换**改成 1 1 1，同时 x 1 x\_1 x1列**其余所有位置**应当改为 0 0 0。别忘了，**初等行变换**是**只能行与行**之间进行加减乘除，**列与列之间的任何变换都是不允许的**。当然，像右下角两个**本来就没有值**的地方不需要变换，因为**没有任何意义**。

这个中间计算步骤我们就省略了，直接看我们第一次执行的结果：

<table> 
 <thead> 
 <tr> 
 <th></th> 
 <th> x 1 x_1 x1</th> 
 <th> x 2 x_2 x2</th> 
 <th> x 3 x_3 x3</th> 
 <th> x 4 x_4 x4</th> 
 <th> b b b</th> 
 <th> θ \theta θ</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> x 1 x_1 x1</td> 
 <td> 1 1 1</td> 
 <td> 6 5 6\over5 56</td> 
 <td> 1 5 1\over5 51</td> 
 <td> 0 0 0</td> 
 <td> 2 2 2</td> 
 <td>需刷新</td> 
 </tr> 
 <tr> 
 <td> x 4 x_4 x4</td> 
 <td> 0 0 0</td> 
 <td> − 28 5 -\frac{28}{5} −528</td> 
 <td> − 3 5 -\frac{3}{5} −53</td> 
 <td> − 1 -1 −1</td> 
 <td> 0 0 0</td> 
 <td>需刷新</td> 
 </tr> 
 <tr> 
 <td> λ j \lambda_j λj</td> 
 <td> 0 0 0</td> 
 <td> − 14 5 -\frac{14}{5} −514</td> 
 <td> − 9 5 -\frac{9}{5} −59</td> 
 <td> 0 0 0</td> 
 <td> Φ \Phi Φ</td> 
 <td> Φ \Phi Φ</td> 
 </tr> 
 </tbody> 
</table>

## 判断条件（二） ##

如何判断计算是否**结束**了？那就是最后的 λ \\lambda λ行是不是**没有正数**了。我们现在看到确实没有正数了，但是这样**直接算**还是太麻烦了。所以，强行继续，再来第二次：

<table> 
 <thead> 
 <tr> 
 <th></th> 
 <th> x 1 x_1 x1</th> 
 <th> x 2 x_2 x2</th> 
 <th> x 3 x_3 x3</th> 
 <th> x 4 x_4 x4</th> 
 <th> b b b</th> 
 <th> θ \theta θ</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> x 1 x_1 x1</td> 
 <td> 1 1 1</td> 
 <td> 0 0 0</td> 
 <td> 1 14 1\over14 141</td> 
 <td> − 3 14 -\frac{3}{14} −143</td> 
 <td> 2 2 2</td> 
 <td> 5 3 5\over3 35</td> 
 </tr> 
 <tr> 
 <td> x 2 x_2 x2</td> 
 <td> 0 0 0</td> 
 <td> 1 1 1</td> 
 <td> 3 28 3\over28 283</td> 
 <td> 5 28 \frac{5}{28} 285</td> 
 <td> 0 0 0</td> 
 <td> 0 0 0</td> 
 </tr> 
 <tr> 
 <td> λ j \lambda_j λj</td> 
 <td> 0 0 0</td> 
 <td> 0 0 0</td> 
 <td> − 3 2 -\frac{3}{2} −23</td> 
 <td> 1 2 1\over2 21</td> 
 <td> Φ \Phi Φ</td> 
 <td> Φ \Phi Φ</td> 
 </tr> 
 </tbody> 
</table>

有些版本中的矩阵会看起来更复杂，实际上有这些就够了。

## 写出结果 ##

我们这个时候基本上就可以**认定**：

\{ x 1 = 2 x 2 = 0 \\left\\\{\\begin\{matrix\} x\_1=2\\\\x\_2=0 \\end\{matrix\}\\right. \{ x1=2x2=0

最终，我们所需要求的最大结果就是：

z m a x = 9 x 1 + 8 x 2 = 18 z\_\{max\}=9x\_1+8x\_2=18 zmax=9x1\+8x2=18

# 总结 #

看出来了吗？最核心的几点就是：

*  首先根据题目所给的条件填入矩阵中；
 *  其次选择**最大的** λ \\lambda λ，根据这一列和**右端常数**计算出 θ \\theta θ，接着选出**最小的** θ \\theta θ（*可以横竖各画一道杠，做个标记*），最后该**行**所代表的基变量**出基**、该**列**所代表的决策变量**进基**；
 *  将做标记的列化成**单位列向量**，要求是**交点**处为 1 1 1而**其他**位置是 0 0 0；
 *   λ \\lambda λ列有正数吗？**有还要继续**，**基变量部分如果还存在人为添加的辅助变量也要继续**，**即没有正数又没人工变量就可以结束了**
 *  最后，把此时的**右端常数**当作结果抄下来。

这就是运筹学的**单纯形法**。是不是有点能理解了呢？

[Link 1]: https://baike.baidu.com/item/%E5%8D%95%E7%BA%AF%E5%BD%A2%E6%B3%95/8580570
[Link 2]: https://blog.csdn.net/ordinary_brony/article/details/108033909
[Link 3]: https://www.bilibili.com/video/BV1u7411y7ex