网络流与图（四）

针对网络流模型的应用我们继续延申更多的变种，学习更多现实案例的应用。

传送门：网络流与图（一）网络流与图（二）网络流与图（三）

1

最大流与最小割

运输与分配问题是只有源集与汇集的特殊网络流模型，与之延申的还有一类特殊情景——最大流与最小割问题。我们先给定义，

一个给定有向图G(V,A)上的最大流(max flow)问题即找到一个特定源节点s和一个特定汇节点t之间的最大可行流,要求满足其他所有弧上的流守恒条件,以及给定弧容量u的限制。

有向图G(V,A)中的s-t割集(S-T)是删掉后能将图分为两个不重叠部分的弧的集合，其中一部分基于包含源节点s在内的节点S⊂ V，另一部分则基于包含汇节点t在内的T=V\S。而最小割(min cut)问题是在前向弧(i,j)中寻找一个总容量最小的s-t割集,其中i∈S,j∈T

用建筑疏散最大流例子介绍。

下面是一个竞技场的提案。在紧急情况下，竞技场中的人员可以由位于四侧的门离开，门每分钟可以容纳600人。这些门通向一个外部大厅，大厅每个方向，每分钟允许移动350人。出大厅需要通过4个消防楼梯，楼梯每分钟能容纳400人；或通过一个通往停车场的隧道，隧道每分钟能容纳800人。我们要关注的是该设计下可能的最大疏散量。

首先，为竞技场设计图添加节点，表示疏散的方向：

然后，为各个节点添加信息，简化为网络流模型(添加疏散出去后的节点10)：

人员流始于源节点1，最终达到汇节点10。容量限制了各条弧的流量。我们希望在此限制条件下，从1到10的最大流。

为解决此问题，先引入知识：流增广路（flow augmenting path）

增广路实际是对应原始图的链，它在残留有向图是一个路。这一点概念需要明确。然后我们给出算法步骤：

举个例子演示一下算法的过程，下图展示了源节点s到汇节点t中每条弧的容量以及初始可行流,设k=0.

k=1时刻的残留有向图与更新流为:

k=2时刻的残留有向图与更新流为:

k=3时刻迭代停止：

2

多商品与增益-损耗流模型

到目前为止，针对一类特殊的线性规划问题，我们提出了网络流模型来解决。并开发了针对更特殊的网络流（二分图）的匈牙利算法以及延展的最大流-最小割问题。这些流模型均隐含一个假设——模型都只对应着一种单一商品（single commodity）。比如OOI案例的单一商品面包炉，竞技场的单一商品人流，CAM案例的单一商品工作任务等。这些均假设汇节点的需求可以由任意一个供给点来满足。

当通过一个普通网络传递的一些流必须保持分离时，则会产生多商品流问题：

多商品流问题（multicommodity flow model）即寻找一个最小费用流，其中彼此分离的商品通过一个普通网络进行传递。

便于理解，我们用实际案例引入——海港渡船多商品流：

下图给出了一个海港周边社区的交通流。每天早上，三个住宅区的人们会去该区域的两个工业中心和两个商业中心。表格详细统计出了按出发地到目的地次数。例如，每天源于住宅节点4的6000次总出行中有1250次是将工业区节点7作为目的地。

目前由于地理因素限制，每种出行都仅有一条单一的路。图中弧上的数字表示不同点间的距离（单位：千米）。比如从节点1到节点7必须全程绕海港行使，途中经过节点2到6。三个住宅区每天共产生21100次出行，沿这些路线行使的总距离为399250千米/天。

区域规划者考虑采取多种改进办法，通过减少驾车行驶的千米数来减少空气污染。其中一个想法即为图中用虚线（2，6）和（6，2）表示渡船。若引入一艘渡船，则它可以在早高峰时段沿着每个方向携带2000辆车。我们想知道这样做能够节省多少千米的行使距离。

显然，若将出行视为流，这样得到的解没意义。因为对于源节点4和汇节点7来说，满足最小距离的算法自然为其选择节点5满足。在此问题中，每个住宅的出行需求是不可替代的。

我们必须分别从三个源出发的出行构建分离的商品网络，但商品仍然不是独立的，因为所有人共享渡船的2000个出行容量。我们将给出多商品流问题的一般模型：

这显然是个特殊的线性规划问题。事实上，它能够发展出非常高效的算法。我们先看另外一个问题——泰尼克现金流。

现金流管理针对的是现金及诸如短期债券的类似等价物。其目标为，当需要支付债务时有可获得的现金，同时用非立即需要的基金来获取尽可能多的利息。在一些情境下，也有可能借用现金以谋求未来的收入。

下图展示了泰尼克公司的具体实例。节点1至节点5代表一段时间内的现金，每个节点旁边的数字b表示各月的现金净需求（单位：千美元）。节点6和7表示从初始持有的200000美元开始，投资于短期债券的基金。

我们假设投资的现金每月回报0.5%，债券每月回报0.9%，这使得显示在图中弧上方框内的增益乘子a能够跑在时间前面。例如弧（3，4）的乘子a=1.005，因为在月利率0.5%下，第3个月投资的每一美元在一个月后都会变成1.005美元。通过对现金借用进行建模，可以用沿途中现金部分的后向弧来表示损耗弧。假设公司至多可以获得100000美元现金，且每月利息为1%。因此，为满足当前需求所借的下个月的每一美元都对应现在的1/1.01=0.9901美元。同样的，也用类似的损耗来连接现金和债券节点，例如弧（2，7）代表第2周投资到债券的现金，损耗乘子a=0.998对应着0.2%的投资税。弧（7，2）上相似的损失则表明，将债券换为现金也需要按相同的税率付税。

管理问题的目标即在计划周期末持有尽可能多的钱。因此，目标函数中唯一的非零系数出现在节点5的流出流入。

为了将诸如现金管理问题的增益/损耗流应用简化为标准的网络流形式，我们需要将乘子纳入最小费用网络流形式。

很显然，这类问题也是线性规划问题。我们很容易求解得到泰尼克公司案例的最优解。

3

最小/最大生成树

最小/最大生成树问题（min/max spanning tree）是求解一类特殊线性规划的简单解法。为了更好展示该算法的内容，仍从一个案例开始——荒地能源（WE）

荒地能源是一家天然气钻井公司，钻井位置位于其控制的一块荒地，公司目前想要修建去往/源于钻戒位置，及钻井位置之间的道路。下图展示了相应的区域，以及由航空和卫星分析选出的7个钻戒位置。图中也给出了已经确认的、两个位置间可能的道路线形，包括构建它们的预期费用（千美元）。只有位置1能够将其他位置与外界相连。WE希望选择一个总费用最小的道路集合，以生成一个每对位置间都存在一条路的网络。该问题的最优解由红色粗线表示，其总费用为80000美元。

最优解是一个生成树，它是一个连通子图。最小/最大生成树即分别为总权重最小和最大的生成树。荒地能源案例即在寻找所示道路网络的一个最小生成树。

面对这类问题，使用贪心算法（greedy algorithm）非常简单高效：

下表展示了能源荒地用贪心算法的搜索过程：

4

知识补充

最后我们补充一下关于网络流模型的一些细节。我们知道，如果决策变量中存在离散变量，则该优化模型为整数规划（integer program,IP），如果整数规划的目标函数方程和约束方程都是线性的，则该整数规划称为整数线性规划（integer linear program,ILP）。而ILP问题通常情况下比LP问题难处理，但对于一个整数规划问题若能表示为网络形式，那么用最小费用网络流模型的算法可以轻松得到整数解。这就是我们说的最小费用网络流模型“开始于整数并保持整数”属性：当所有约束数据均为整数时，网络流最优解即为整数。该性质被称为全幺模性（totally unimodular）

至于为什么会这样，我们这里不展示细说。这里还要说个例外，对于多商品流和增益/损耗流模型，即使所有约束均为整数，最优解也不一定是整数。