文章目录
导读
运筹学第一课会给你讲
线性规划
，也就是从初中以来我们拿多元一次方程组做的“
旅游叫车问题
”、“
投资问题
”等等。相信在这个时候，每个人的第一印象是：
我感觉我行了
。然后老师就开始讲
单纯形法
。从那时候起，
理智直接归零
，再也没恢复，于是便
带着满脑子问号开始了除了上课以外的其他任何事情
。
这里就简单梳理一下单纯形法的
概念
和
步骤
。
单纯形法简介
单纯形法是求解线性规划问题最常用、最有效的算法之一。单纯形法最早由 George Dantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止 。
——摘自
百度百科【单纯形法】
简单地说，单纯形法就是
解决线性规划的另一种选择
。毕竟，我们既然在大学的线性代数里面学习了
多元一次方程
和
增广矩阵
，那么单纯形法就单纯的是
用大学生的方法解决初中生的问题
。那这个锅老师就不该背了，
感觉难实际上是工具难用
。
单纯形法的步骤简介
题目一开始会给定约束方程，比如说：
{
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.
⎩
⎨
⎧
5
x
1
3
x
1
x
1
+
−
,
6
x
2
2
x
2
x
2
≤
≥
≥
1
0
6
0
然后就让你求目标函数的最优解，就假设是：
z
m
a
x
=
9
x
1
+
8
x
2
z_{max}=9x_1+8x_2
z
m
a
x
=
9
x
1
+
8
x
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.
⎩
⎨
⎧
5
x
1
3
x
1
x
1
,
+
6
x
2
−
2
x
2
x
2
,
+
x
3
x
3
,
−
x
4
x
4
=
=
≥
1
0
6
0
虽然第三个式子依然是不等式，但是这个
没什么影响
。我们可以
不考虑第三个不等式
然后
求出所有的解
，最后根据第三个不等式
筛选出全都是正数的解
就好了。
于是，整个方程组就剩下：
{
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.
{
5
x
1
3
x
1
+
6
x
2
−
2
x
2
+
x
3
−
x
4
=
=
1
0
6
我们做出增广矩阵
[
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]
[
5
3
6
−
2
1
0
0
−
1
1
0
6
]
但是我们的目标是
找出最优
，而不是
求出解
。所以再加上一些行列：
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
||||||
|
x 4 x_4 x 4 |
||||||
|
λ j \lambda_j λ j |
突然蒙圈了？没有关系，看看下面的说明
单纯形法的一些说明
简介不需要明白太多，毕竟几十年前的东西了。这里就直接开始说明矩阵的构成。
由于市面上不同的书有着不同的版本，我这里就选择
西安邮电大学史新峰老师的教学视频
里使用的矩阵格式进行说明，因为
这个矩阵是我认为最简洁最好懂的
。
另外说明一点：我会把需要说明的部分
高亮
标记，但是这
并不代表文字对应的意义
，而应当
是表格的该位置对应的意义
。
决策变量
以下表格中
标红
的便是
决策变量
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
||||||
|
x 4 x_4 x 4 |
||||||
|
λ j \lambda_j λ j |
基变量
下面这个表格中
标蓝
的是
基变量
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
||||||
|
x 4 x_4 x 4 |
||||||
|
λ j \lambda_j λ j |
工艺常数
下面这个矩阵中
标绿
了的地方就是
工艺常数
。
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
5 5 5 |
6 6 6 |
1 1 1 |
0 0 0 |
||
|
x 4 x_4 x 4 |
3 3 3 |
− 2 -2 − 2 |
0 0 0 |
− 1 -1 − 1 |
||
|
λ j \lambda_j λ j |
右端常数
下面这张表中标记为
冷铜色
的地方就是右端常数
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
10 10 1 0 |
|||||
|
x 4 x_4 x 4 |
6 6 6 |
|||||
|
λ j \lambda_j λ j |
空白处
下面表格中使用
Φ
\Phi
Φ
填充的格子中，
并没有
可以填的数据，所以一般都
空着
。
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
||||||
|
x 4 x_4 x 4 |
||||||
|
λ j \lambda_j λ j |
Φ \Phi Φ |
Φ \Phi Φ |
θ
\theta
θ
下面表格中
标紫
了的地方就是
θ
\theta
θ
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
2 2 2 |
|||||
|
x 4 x_4 x 4 |
2 2 2 |
|||||
|
λ j \lambda_j λ j |
检验数
下面表格中
标蓝
了的地方就是
检验数
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
||||||
|
x 4 x_4 x 4 |
||||||
|
λ j \lambda_j λ j |
9 9 9 |
8 8 8 |
0 0 0 |
0 0 0 |
其实这一行是
人工添加
的，就像是
特征工程
里面会人工添加特征让数据更清晰一样。这里原本应当填入的数据是我们的
目标函数
。我们一开始拿到的目标方程是
z
m
a
x
=
9
x
1
+
8
x
2
z_{max}=9x_1+8x_2
z
m
a
x
=
9
x
1
+
8
x
2
，那么就应当是
填成表格上所显示的那样
。
把其中的一些部分组合起来
到这里，表格的每个部分代表什么意思都已经介绍完了。接下来，一些特定部分组合起来也有特殊的意义。
约束方程
在这里其实约束方程
并不是一开始题目所给的不等式方程组
，
而是我们人工添加变量后拿到的等式方程组
。
也就是
工艺常数
部分加上
右端常数
部分。
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
5 5 5 |
6 6 6 |
1 1 1 |
0 0 0 |
10 10 1 0 |
|
|
x 4 x_4 x 4 |
3 3 3 |
− 2 -2 − 2 |
0 0 0 |
− 1 -1 − 1 |
6 6 6 |
|
|
λ j \lambda_j λ j |
典则形式
是
约束方程
部分加上
检验数
部分，也就是
工艺常数
、
右端常数
以及
检验数
。
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
5 5 5 |
6 6 6 |
1 1 1 |
0 0 0 |
10 10 1 0 |
|
|
x 4 x_4 x 4 |
3 3 3 |
− 2 -2 − 2 |
0 0 0 |
− 1 -1 − 1 |
6 6 6 |
|
|
λ j \lambda_j λ j |
9 9 9 |
8 8 8 |
0 0 0 |
0 0 0 |
计算步骤
好了，全部介绍完了，接下来就是真正的计算了。
类似我们刚刚举例的“
典则形式
”应该是没有什么问题了吧？先完善一个
增广矩阵
，接着再根据
目标函数
把下面的
检验数
补齐。这都没什么问题。问题在下面的
寻找最优
。
判断条件（一）
什么时候我们拿到了最优解？那就是
检测数没有正数
的时候。我们可以看到现在的典则形式还有
9
9
9
和
8
8
8
两个正数，所以现在显然不是最优解。
出基和进基
既然不是最优解，那么我们就根据
出基
和
入基
的规则进行判断。首先，我们选择
检测数最大
的一个，也就是
9
9
9
，即
x
1
x_1
x
1
列。接着我们用
x
1
x_1
x
1
列的数字
根据行对应
分别除以
右端常数
，bin并将得出来的数字一一根据行对应填在
θ
\theta
θ
列内，得：
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 3 x_3 x 3 |
5 5 5 |
6 6 6 |
1 1 1 |
0 0 0 |
10 10 1 0 |
2 2 2 |
|
x 4 x_4 x 4 |
3 3 3 |
− 2 -2 − 2 |
0 0 0 |
− 1 -1 − 1 |
6 6 6 |
2 2 2 |
|
λ j \lambda_j λ j |
9 9 9 |
8 8 8 |
0 0 0 |
0 0 0 |
Φ \Phi Φ |
Φ \Phi Φ |
接着我们再
从
θ
\theta
θ
列中选择一个最小的
（
由于这里都是
2
2
2
，所以我选择
x
3
x_3
x
3
行
），也就是
x
3
x_3
x
3
。于是，
x
1
x_1
x
1
就
成为
了基变量，叫
进基
；
x
3
x_3
x
3
就
不再是
基变量，叫
出基
。
于是矩阵稍微改写（将
基变量
部分中的
x
3
x_3
x
3
改为
x
1
x_1
x
1
）：
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 1 x_1 x 1 |
5 5 5 |
6 6 6 |
1 1 1 |
0 0 0 |
10 10 1 0 |
2 2 2 |
|
x 4 x_4 x 4 |
3 3 3 |
− 2 -2 − 2 |
0 0 0 |
− 1 -1 − 1 |
6 6 6 |
2 2 2 |
|
λ j \lambda_j λ j |
9 9 9 |
8 8 8 |
0 0 0 |
0 0 0 |
Φ \Phi Φ |
Φ \Phi Φ |
矩阵变换
线性代数告诉我们：在研究高维度的时候，如果有几个
相互垂直
的单位向量，那么一定会这么写：
|
e 1 e_1 e 1 |
e 2 e_2 e 2 |
⋯ \cdots ⋯ |
e n e_n e n |
|
|---|---|---|---|---|
|
e 1 e_1 e 1 |
1 1 1 |
0 0 0 |
⋯ \cdots ⋯ |
0 0 0 |
|
e 2 e_2 e 2 |
0 0 0 |
1 1 1 |
⋯ \cdots ⋯ |
0 0 0 |
|
⋮ \vdots ⋮ |
⋯ \cdots ⋯ |
⋯ \cdots ⋯ |
⋯ \cdots ⋯ |
⋯ \cdots ⋯ |
|
e n e_n e n |
0 0 0 |
0 0 0 |
⋯ \cdots ⋯ |
1 1 1 |
所以，如果
x
1
x_1
x
1
作为基变量，那么我们刚刚确认的
x
1
x_1
x
1
列和
x
3
x_3
x
3
行交界处应当通过
初等行变换
改成
1
1
1
，同时
x
1
x_1
x
1
列
其余所有位置
应当改为
0
0
0
。别忘了，
初等行变换
是
只能行与行
之间进行加减乘除，
列与列之间的任何变换都是不允许的
。当然，像右下角两个
本来就没有值
的地方不需要变换，因为
没有任何意义
。
这个中间计算步骤我们就省略了，直接看我们第一次执行的结果：
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 1 x_1 x 1 |
1 1 1 |
6 5 6\over5 5 6 |
1 5 1\over5 5 1 |
0 0 0 |
2 2 2 |
需刷新 |
|
x 4 x_4 x 4 |
0 0 0 |
− 28 5 -\frac{28}{5} − 5 2 8 |
− 3 5 -\frac{3}{5} − 5 3 |
− 1 -1 − 1 |
0 0 0 |
需刷新 |
|
λ j \lambda_j λ j |
0 0 0 |
− 14 5 -\frac{14}{5} − 5 1 4 |
− 9 5 -\frac{9}{5} − 5 9 |
0 0 0 |
Φ \Phi Φ |
Φ \Phi Φ |
判断条件（二）
如何判断计算是否
结束
了？那就是最后的
λ
\lambda
λ
行是不是
没有正数
了。我们现在看到确实没有正数了，但是这样
直接算
还是太麻烦了。所以，强行继续，再来第二次：
|
x 1 x_1 x 1 |
x 2 x_2 x 2 |
x 3 x_3 x 3 |
x 4 x_4 x 4 |
b b b |
θ \theta θ |
|
|---|---|---|---|---|---|---|
|
x 1 x_1 x 1 |
1 1 1 |
0 0 0 |
1 14 1\over14 1 4 1 |
− 3 14 -\frac{3}{14} − 1 4 3 |
2 2 2 |
5 3 5\over3 3 5 |
|
x 2 x_2 x 2 |
0 0 0 |
1 1 1 |
3 28 3\over28 2 8 3 |
5 28 \frac{5}{28} 2 8 5 |
0 0 0 |
0 0 0 |
|
λ j \lambda_j λ j |
0 0 0 |
0 0 0 |
− 3 2 -\frac{3}{2} − 2 3 |
1 2 1\over2 2 1 |
Φ \Phi Φ |
Φ \Phi Φ |
有些版本中的矩阵会看起来更复杂，实际上有这些就够了。
写出结果
我们这个时候基本上就可以
认定
：
{
x
1
=
2
x
2
=
0
\left\{\begin{matrix} x_1=2\\x_2=0 \end{matrix}\right.
{
x
1
=
2
x
2
=
0
最终，我们所需要求的最大结果就是：
z
m
a
x
=
9
x
1
+
8
x
2
=
18
z_{max}=9x_1+8x_2=18
z
m
a
x
=
9
x
1
+
8
x
2
=
1
8
总结
看出来了吗？最核心的几点就是：
- 首先根据题目所给的条件填入矩阵中；
-
其次选择
最大的
λ\lambda
λ
，根据这一列和
右端常数
计算出
θ\theta
θ
，接着选出
最小的
θ\theta
θ
（
可以横竖各画一道杠，做个标记
），最后该
行
所代表的基变量
出基
、该
列
所代表的决策变量
进基
； -
将做标记的列化成
单位列向量
，要求是
交点
处为
11
1
而
其他
位置是
00
0
； -
λ\lambda
λ
列有正数吗？
有还要继续
，
基变量部分如果还存在人为添加的辅助变量也要继续
，
即没有正数又没人工变量就可以结束了
-
最后，把此时的
右端常数
当作结果抄下来。
这就是运筹学的
单纯形法
。是不是有点能理解了呢？