Loading...
墨滴

进击的土豆同学

2021/08/30  阅读:40  主题:默认主题

最大流模型

最大流模型

很多的数学模型往往来源于生活问题,本文介绍其中一个问题借此引出最大流模型,让读者能够更好地了解模型的背景以及应用。

现有一管道网络用于运输原油,将原油从油井运输到提炼厂,为了在网络中顺畅地输运原油,需要在中间合适的距离安装增压泵站,每一段管道有一个有限的最大原油流量(容量),每段管道可以是单向,也可以是双向,取决于它的原始设计。那么如何确定从油井到提炼厂原油的最大流量?

下面给定双向弧的相关概念:

给定弧 ,其中 ,用符号 表示两个方向 弧上的容量。为了更清晰地描述,把 放在靠近节点 的一边,把 放在靠近节点 的一边,如下所示。

1 枚举割

割(cut) 是一部分弧的集合,如果将这些弧从网络中删除,就会断开源点和汇点之间所有的流。割的容量等于这个割中所有弧上容量的和。在网络中所有可能的割中,最小容量的割就对应了这个网络的最大流

例子

如下图网络,按照上述表示方法对每一条双向弧都标上了容量。例如,对于弧(3,4),从节点3到节点4的流量限制为10单位,从节点4到节点3为5单位。我直接在图中,标出了该网络的3个割: 在这里插入图片描述

图中3个割的容量如下表:

相应的弧
容量
1
(1,2),(1,3),(1,4)
20+30+10=60
2
(1,3),(1,4),(2,3),(2,5)
30+10+40+30=110
3
(2,3),(3,5),(4,5)
30+20+20=70

从表中可以看出,该网络最大流不超过60个单位。枚举所有割,对于小型网络是可行的,但是对于比较复杂的网络,效率就很低了,所以需要寻找其他算法。

2 最大流算法

2.1 原理

最大流算法的核心思想是:从网络中寻找从源点到汇点具有的流的突破路径

上的初始容量 ,当给定一个流并找到突破路径后,需要对每条弧上的容量进行修改,修改后的容量称为剩余容量 。 如果节点 从节点 接收到一个流,那么给节点 标号为 (节点 的表示)。其中 表示从节点 流到节点 的量, 表示流的来源是节点

2.2 步骤

第1步: 首先将所有弧 的剩余容量设为初始容量,即 .取 ,则源点1标号为 . 令 ,进入第2步。

第2步: 确定集合 ,它是节点 通过剩余容量为正的弧能够直接到达的所有未标号的节点 的集合。如果 ,进入第3步;否则,进入第4步。

第3步: 确定 ,使之满足 . 令 ,并且给节点 标号 .如果 ,此时汇点(终点)得到了标号,也找到了一条突破路径,进入第5步;否则令 ,转回第2步。

第4步(回溯): 如果 ,那么不存在突破路径,进入第6步;否则,令 是紧邻在当前节点 之前得到标号的节点,并将节点 从节点 的相邻节点集合中删除,令 ,转回第2步。

第5步(剩余容量的确定): 是从源点1到汇点 的第 条突破路径,则这条路径上最大流量为:

这条路径上每条弧的剩余容量在顺着流的方向上 是减少的,在逆着流的方向上 是增加的。

例如,对于该路径上的节点 与节点 ,当前剩余容量为 变为:

<\a> 如果流是从节点 流向节点 ,则弧上的剩余容量为 ;

<\b> 如果流是从节点 流向节点 ,则弧上的剩余容量为 ;

恢复第4步删除掉的节点,然后令 ,转回第2步接着寻找新的突破路径。

第6步(最优解)

<\a> 给出已经找到的 条突破路径,那么网络的最大流为:

<\b> 根据每条弧 上的初始的和最终的剩余容量, 按照下面的方法确定该弧上的最优流:令 ,如果 ,那么从节点 流向节点 的最优流是 个单位;如果 ,那么从节点 流向节点 的最优流是 个单位.(注意 不能同时为正数).

3 总结

由于例子过于繁杂,这里就不做具体展示,有兴趣的读者可以参考运筹学相关书籍,这里推荐2本我觉得不错的,分别是:

《运筹学导论》 作者:[美]Hamdy A·Taha 出版社:人民邮电出版社;

《运筹学》 作者:运筹学教程编写组 出版社:清华大学出版社

运筹学导论
运筹学

进击的土豆同学

2021/08/30  阅读:40  主题:默认主题

作者介绍

进击的土豆同学