算法导论随笔(十五)：线性规划与单纯形算法（上篇：基本概念）
线性规划（Linear Programming）问题指的是在给定有限资源的前提下，最大化或最小化某个目标的问题。这里我将分上下两篇来谈谈线性规划和单纯形算法。
前言
线性规划问题有很多例子，比如在算法导论随笔(六)：贪心算法Greedy algorithm与分数背包问题中，我曾经提到过一个分数背包问题。当时是使用贪心策略来解决。其实，这个问题也可以使用线性规划来解决。
先来回顾一下分数背包问题：如下图，图中有5瓶液体，分别标号为1，2，3，4，5。编号为1的液体有4毫升，每毫升价值3美元。所以该液体的总价值为12美元。类似地，编号2，3，4和5的液体，分别有8毫升，2毫升，6毫升和1毫升，而每毫升的价值分别为4，20，5，50美元，它们的总价值分别为32，40，30，50美元。
现在我们有一个10毫升的杯子，想从5个瓶子里取出共10毫升的液体，使得该10毫升液体的总价值最高。回顾本篇文章最开始时候对线性规划问题的描述：在给定有限资源的前提下，最大化或最小化某个目标的问题。
这里我们可以看出来，对于分数背包问题，“给定有限资源的前提”就是：我们只能从每瓶液体中取出大于0而且小于该液体容积的液体，并且最后的总容积为10毫升。“最大化某个目标”也就是指我们要使得该10毫升的液体总价值最高。假定我们把这5个瓶子中所拿出的液体体积分别设置为x1，x2，x3，x4和x5，那么如果我们把这些前提和目标用数学的方式写下来，就是下面的这种形式。
最大化
x
1
×
3
+
x
2
×
4
+
x
3
×
20
+
x
4
×
5
+
x
5
×
50
x_1 \times 3 + x_2 \times 4 + x_3 \times 20 + x_4 \times 5 + x_5 \times 50
x1×3+x2×4+x3×20+x4×5+x5×50
，其中x1，x2，x3，x4和x5满足下列条件：
x
1
≥
0
x
1
≤
4
x
2
≥
0
x
2
≤
8
x
3
≥
0
x
3
≤
2
x
4
≥
0
x
4
≤
6
x
5
≥
0
x
5
≤
1
x
1
+
x
2
+
x
3
+
x
4
+
x
5
=
10
x_1 \ge 0 \newline x_1 \le 4 \newline x_2 \ge 0 \newline x_2 \le 8 \newline x_3 \ge 0 \newline x_3 \le 2 \newline x_4 \ge 0 \newline x_4 \le 6 \newline x_5 \ge 0 \newline x_5 \le 1 \newline x_1 + x_2 + x_3 + x_4 + x_5 = 10
x1≥0x1≤4x2≥0x2≤8x3≥0x3≤2x4≥0x4≤6x5≥0x5≤1x1+x2+x3+x4+x5=10
形如上面的这种格式的问题就是线性规划问题。上面例子中我们需要最大化的式子可以表示为函数形式，即
比如上面的例子中的
x
1
×
3
+
x
2
×
4
+
x
3
×
20
+
x
4
×
5
+
x
5
×
50
x_1 \times 3 + x_2 \times 4 + x_3 \times 20 + x_4 \times 5 + x_5 \times 50
x1×3+x2×4+x3×20+x4×5+x5×50
就可以表示为
f
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
)
=
a
1
x
1
+
a
2
x
2
+
a
3
x
3
+
a
4
x
4
+
a
5
x
5
其
中
a
1
=
3
，
a
2
=
4
，
a
3
=
20
，
a
4
=
5
，
a
5
=
50
f(x_1, x_2, x_3, x_4, x_5) = a_1x_1+ a_2x_2 + a_3x_3 + a_4x_4 + a_5x_5 \newline 其中 a_1 = 3，a_2 = 4， a_3 = 20， a_4 = 5， a_5 = 50
f(x1,x2,x3,x4,x5)=a1x1+a2x2+a3x3+a4x4+a5x5其中a1=3，a2=4，a3=20，a4=5，a5=50
这里的f(x1，x2，x3，x4, x5)被称作一个线性函数。例子中需要满足的所有的条件都被称为约束。若一条约束表达的是一个变量需要大于或等于0，则该约束称为非负约束（比如上面例子中的x1 >= 0， x2 >= 0等等）
标准型和松弛型
标准型(Standard form)和松弛型(Slack form)是线性规划问题的两种形式。先说标准型。一个标准型的线性规划问题，必须具有如下格式：
换句话说，一个线性规划问题只有满足以下条件，才能称为标准型：
- 该线性规划问题的目标是求一个目标函数的最大值，而不是最小值
- 每一个变量都必须有非负约束
- 所有的约束都必须是不等式
- 除了非负约束之外，其他约束必须是 <= 而不是>=
我们可以看出，上面的例子并不是标准型，因为它有一个不等式约束，即
x
1
+
x
2
+
x
3
+
x
4
+
x
5
=
10
x_1 + x_2 + x_3 + x_4 + x_5 = 10
x1+x2+x3+x4+x5=10
因此违背了第3个条件。
下面的例子就是一个标准型线性规划问题。
可以看出，它符合上述四个条件。
下面来说松弛型。对于一个线性规划问题，只要它满足如下条件，则它是松弛型：
除了非负约束之外，所有约束都是等式。
下面的例子就是一个松弛型的线性规划问题。
在等式约束中，等式左边的变量称为基本变量，等式右边的变量称为非基本变量（也称*变量）。上面的例子中，基本变量为x3，x4和x5，而非基本变量为x1和x2。如果我们用数组来表示基本变量和非基本变量的下标，则基本变量的下标为[3, 4, 5]，而非基本变量的下标为[1, 2]。
标准型转化为松弛型
标准型转化为松弛型的过程非常简单，下面直接用一个例子来说明。假设我们有如下一个标准型。
首先把三个非负约束中，小于等于号左侧的变量都移到右边去，即
0
≤
3
+
3
x
1
−
2
x
2
0
≤
2
−
x
1
−
x
2
0
≤
1
−
x
1
+
x
2
0 \le 3 + 3x_1 - 2x_2 \newline 0 \le 2 - x_1 - x_2 \newline 0 \le 1 - x_1 +x_2
0≤3+3x1−2x20≤2−x1−x20≤1−x1+x2
然后我们令
x
3
=
3
+
3
x
1
−
2
x
2
x
4
=
2
−
x
1
−
x
2
x
5
=
1
−
x
1
+
x
2
x_3 = 3 + 3x_1 - 2x_2 \newline x_4 = 2 - x_1 - x_2 \newline x_5 = 1 - x_1 +x_2
x3=3+3x1−2x2x4=2−x1−x2x5=1−x1+x2
那么上面三个不等式就转化成关于x3，x4和x5的非负约束。即x3 >= 0，x4 >= 0和x5 >= 0。 整理后如下图
于是我们就把标准型转化成了松弛型。这里面新添加的x3，x4和x5被称为松弛变量。
基本解和基本可行解
对于一个松弛型，将松弛型的非基本变量均设置为0，得到的解就是该松弛型的基本解。注意基本解并不一定是最优解。例如，上图中我们带入x1=0和x2=0，得到x3=3，x4=5，x5=1，因此[0, 0, 3, 5, 1]就是这个松弛型的基本解（数组中每一个数字代表对应变量的值，即x1=0, x2=0，x3=3，x4=5，x5=1）。
如果基本解的各变量均满足所有约束，则称该基本解为基本可行解。[0, 0, 3, 5, 1]就是该松弛型的基本可行解。
浅谈单纯形算法
上面所有概念的介绍都是为了引出单纯形算法，因为单纯形算法要依靠于上述概念。这里简单对单纯形算法进行一个介绍。对于该算法的具体细节和代码实现，我将在下一篇文章中详细介绍。单纯形算法以一个标准型的线性规划作为输入，并输出它的目标函数（即线性函数）的最大值以及导致目标函数最大值的各变量的值。
首先，让我们来想一想，目标函数应该是一个什么样的格式时，才能明确的知道它的最大值呢？由于每个变量都需要有一个非负约束，因此，当目标函数所有变量的系数都为负数的时候就行了。比如：
最大化 z = 20 - 3x5 - x4
由于x5和x4都需要大于或等于0，因此这个函数只有当它们都等于0的时候才有最大值20，若它们中任意一个有一个正数值，那么函数值就是20减去一个正数，也就是一定会小于20。
要达到这个效果，就需要把标准型的目标函数转化成上述格式，因此需要把标准型的线性规划转换为松弛型，并且保证转化成的松弛型的解也是原始的标准型的解。这就是算法的第一步。转化成松弛型的另一个目的是，松弛型中除了非负约束之外都是等式约束，因此我们可以对等式进行带入求解。
举个例子，我们最终的目的是要把算法的输入转化成一个类似于下面图中的松弛型：
从图中我们可以看出，非基本变量x4和x5为0时，z最大，此时将x4和x5带入四个等式约束中，即可求出x1=4，x2=4，x3=2，x6=2。再加上x4=0和x5=0，这一组变量的值就是这个问题的解。
并不是所有的线性规划问题都有解。比如当我们把上面的约束x3 = 2 + x4 - x5 改成x3 = -2 + x4 - x5，那么最终得出x3 = -2并不满足x3的非负约束。此时该问题就没有解。
因此，线性规划的单纯形算法主要分为以下几个阶段：
- 将输入的标准型转化为松弛型
- 确定该松弛型有解（否则算法结束）
- 将松弛型通过一些变换，最终转化成上面图中的松弛型，并求出该松弛型的解
由于松弛型是由标准型通过一系列变换形成的，因此该松弛型的解也是标准型的解。
关于单纯形算法的更多细节，我将在下一篇文章中介绍。