线性规划

线性规划问题

线性规划问题指的是：给定若干个变量，这些变量满足一系列线性等式关系或线性不等式关系，要在满足这些关系的前提下求出某个这些变量的线性函数的最大值或最小值。

我们可以用“归约”的思想把线性规划问题的描述统一为标准的形式，称为“标准型”：首先我们可以把问题归约为所有自变量都是正数的情况，如果存在一个自变量\(x\)可以取负数，那么我们就定义两个新的变量\(x^+\)和\(x^{-}\)，并永远用\(x^{+}-x^-\)来替换\(x\)。这样就保证了所有变量的取值范围都\(\geq 0\)。任何一个线性规划给出的约束的不等关系\(a_1x_1+a_2x_2+\cdots+a_nx_n \geq 0\)可以写作\(a_1x_1+\cdots+a_nx_n-s_n=0\)且\(s_n \geq 0\)，这样就在所有自变量都\(\geq 0\)的基础上，把所有的不等式约束都转化为了“等式约束”。对于要求的目标函数，如果是求最小值，我们就给它取个负号，最后再取回来，这样就转化为了求最大值。因此，一切线性规划问题都可以转化为标准型——变量非负，等式约束，求最大值。

我们可以通过作图来求解线性规划问题：如果变量的数量为2，那么等式关系就对应着平面上的一条直线。令目标函数等于某个量，这个量的变化可以看作确定斜率的直线的平移。所以我们的点在直线围成的多边形的边上运动，同时经过该点做该斜率的直线，直线能达到使目标函数最小的地方就是我们的最优解。变量个数为3的情况同理，此时可行域是空间中的多面体，平移的直线变成了平移的平面， 其它情况都类似。

如果变量的个数达到\(n\)个，我们难以用“作图”来描述。但我们注意到这样一个事实：在二维中我们的答案一定对应着目标函数的极值点，假设可行域是一个凸多边形，我们的答案总是在其某个顶点上取到，并且在最终的顶点上，它相对于我们的平移直线一定是最高的点；三维情形也是类似的，我们最终答案的顶点一定是在目标函数意义下最高的。

我们用“单纯形法”来描述这一事实，并由此在\(n\)维的线性规划中也得出了一个可行的算法：我们把所有“空间多面体的顶点”想象为“节点”，“空间多面体的棱”想象为“边”。从任意某个节点出发，如果它周围有一个节点，在那上面目标函数的取值更大，就走到那个节点，直到无法走到任何节点，即此时到达了一个极值点。那么可以证明这个极值点就是最优解。

值得注意的是，线性规划的正确性是由“实数”这一定义域保证的，对于很多的应用性问题，尽管给出的约束都是整数，但最优解不一定在整数处取到。如果要加上“解必须是整数”这一限制，问题就会变得非常复杂——它已经不再是“线性规划”问题而是“整数规划”问题了。

网络流

在一张只有一个源点和一个汇点的有向图上，边权代表“最大容量”。想象单位时间内有水流从源点流向汇点，每个节点没有储存水流的能力，因此流进的流量必须等于流出的流量，并且每条边上的流量不能超过最大容量，问单位时间最多能流过多大的水流？

这就是最大流问题。我们发现它其实就是一个线性规划的问题：有\(|E|\)个变量，代表每条边的流量，每条边的流量不能超过最大容量是线性不等式约束，每个节点流进等于流出是线性等式约束，要求的目标函数是从源点出发的流量综合（或流入汇点的流量综合）是线性函数。因此我们只需要在这些约束的基础上执行“单纯形法”就可以求出最大流了。

我们想更仔细地看一看，“单纯形法”对应到“网络最大流”这个具体的问题上是如何工作的。在单纯形法中，我们每次要走到一个某个使得目标函数更大的节点上。在这里，“目标函数更大”就对应着“流过了更多的水流”。如果把最终的“最大流的解”拆分成若干从源点到汇点的单一路径，那么这种“目标函数变得更大”就对应着在原先的水流分布上找到了一条新的从源点到汇点的路径可以流通。因此，我们可以记下每条边还最多可以通过多少流量，然后以这个流量为边权找一条从源点到汇点的边权始终为正的路径（用BFS就可以完成），取路上经过的最小边权作为流量，这就是一条通路了。不停执行这个过程，就是在执行“单纯形法”，因此直到我们找不到任何通路，我们就一定到达了最大流。这就是网络最大流的“增广路算法”。

但是，单单在“残量网络”上寻找增广路这种转化和数学上的“单纯形法”还是存在出入的，很容易举出反例以上算法中一条路径有可能堵住了别的路径，导致最终无法成功找出最大流。原因在于我们在线性规划问题中“叠加两个解”的时候是在实数上操作的，而在增广路上一旦我们选定了某个流量，就不能再添加反向的流量了。我们在“增加流量”这一操作上抹去了原本应该存在的其它选择——一条容量为5的边，假设我们已经正向给了它大小为3的流量， 那么接下来它可以选择继续正项增加2的流量，也可以选择反向增加3的流量——残量网络应当是包括两个方向的！这样我们就得到了一个完整的残量网络来执行我们的单纯形算法。

最大流最小割定理

对于一个网络流，我们把点划分成集合\(L,R\)，其中源点在\(L\)中，汇点在\(R\)中。有若干边是横跨\(L,R\)的，有从\(L\)到\(R\)的也有从\(R\)到\(L\)的，这些边就称为一个“割”。我们定义割的大小是所有从\(L\)到\(R\)的边的容量之和。

显然，任意一个流的大小都不可能超过任意一个割的大小。因为割的大小本身就限制了最大的流的大小。因此我们证明了最大流小于等于最小割。

现在我们要证明，存在一个割的大小等于最大流。考虑执行完了增广路算法的残量网络，在这张图上一定不再存在从源点到汇点的路径了（如果存在就又找到了一条增广路），即在此时的残量网络上源点到汇点是不连通的。那么我们令集合\(P\)中存放所有从源点出发可达的节点，余下的节点存放在集合\(Q\)中。我们证明\(P,Q\)形成的割的大小就等于最大流——对于原图中从\(P\)到\(Q\)的所有边，它们在残量网络中一定被设为了0，不然就找到了一条到达\(Q\)中某个点的路径，与\(P,Q\)的定义矛盾，因此在原图中从\(P\)到\(Q\)的边都被流满了；原图中从\(Q\)到\(P\)的边必须流量为0，否则就会出现从\(P\)到\(Q\)的残量边，再次矛盾。因此这个割的大小就恰好等于\(P\)到\(Q\)的流量——最大流。 满足这个取等条件的割根据性质一定就是最小割。