运筹学最大流.ppt

第6页/共36页
(1)为了便于弧标号法的计算，首先需要将最大流 问题（譬如图10.3.1）重新改画成为图10.3.2的形式。
图10.3.2
第7页/共36页
在图10.3.2中，每条弧 上V标ij 有两个数字，其
中，靠近点 i 的是 ，c靠ij 近点 j 的是 。如c①ji
②表示5 从0①到②的最大通过量是5（百辆），从② 到①的最大通过量是0；② ③表示从2②到2③和 从③到②都可以通过2（百辆）；等等。
例如，在图10.3.11中，从①到⑦的最短路是①— ③—⑤—⑦，代价为7，在这条最短非饱和路上取P 3 后，③—⑤变成容量为零，在下一次选择最短路时 应将③—⑤视为断路来选取最短非饱和路。另外， 选取①—③—⑤—⑦路后，③—①，⑤—③，⑦— ⑤的弧成为容量大于零的弧，可分别标上它们的代 价值为-3，-3，-1，是①—③，③—⑤，⑤—⑦的相 反数。
转入步骤④，用原图中各条弧上发点与收点数
值减去修改后的图上各点的数值，将得到正负号
相反的两个数，将这个数标在弧上，并将从正到
负的方向用箭头表示,这样就得到最大流量图。例
如原来弧(3,6) 是③ 7 0 ⑥，现在是③ 2 5 ⑥，
相减为±5，③那边为正，我们就记作③ 5⑥。
这样，就得到图10.3.9，即最大流量图。依这样的
第12页/共36页
通过第1次修改，得到图10.3.3。
图10.3.3
返回步骤①，进行第2次修改。
第13页/共36页
第2次修改： 选定①—②—⑤—⑦，在这条路中，由
于 P c25，所3 以，将 改为2c12， 改为0，c25 改
为5，c5、7 、 改为c213。c5修2 改c后75 的图变为图
10.3.4。

第i年 价格 ai 使用寿命 费用 bi 1 11 0－1 b1 5 2 11 1－2 b2 6 3 12 2－3 b3 8 4 12 3－4 b4 11 5 13 4－5 b5 18
最短路径问题的应用

例 设备更新问题
把求总费用最小问题化为最短路径问题。用点 i (i=1,2,3,4,5)表示第 i 年买进一台新 设备。增设一点 6 表示第五年末。从i点到i+1,……, 6 各画一条弧，弧（i , j）表示在 第 i 年买进的设备一直使用到第 j 年年初（第 j －1年年末）。求1点到6点的最短路径。 路径的权数为购买和维修费用。 弧（i , j）的权数为第i年的购置费ai＋从第i年使用至第j-1年末的维修费之和。 从第i年使用至第j-1年末的维修费：b1+…+bj-i
1 1 2 3 4 5 2 16 3 22 16
（使用寿命为j-i年） 具体权数计算结果如下：
5 41 30 23 17 6 59 41 31 23 18
如：（2－4）权数为：a2+b1+b2=11＋5＋6=22
4 30 22 17
通过一个网络的最短路径

例 设备更新问题 ：
2 16 30 22 41 4 23

最大流问题
两个重要结论： 1、任何一个可行流的流量都不会超过任一截集的容量。 2、若对于一个可行流f *，网络中有一个截集（ V1*，V1*）， 使v（ f *）=C(V1*，V1 *)，则f *必是最大流，而（ V1*， V1 *）必是所有截集中容量最小的一个，即最小截集。
定理：可行流f *是最大流，当且仅当不存在关于f *的增广链。 于是有如下结论：最大流量最小截量定理：任一个网络中，从vs 到vt的最大流量等于分离vs，vt的最小截集的容量。

解决方案：可以通过建立最大流模型，求解出最优的运输路径，从而提高物流运输效率，降低运输 成本。
实际应用效果：在实际应用中，最大流问题可以有效地解决物流运输中的路径规划、车辆调度等问 题，提高物流运输效率，降低运输成本。
网络流量优化中的最大流问题
背景：随着互联网 技术的发展，网络 流量优化成为重要 问题
预流推进法的实现
预流推进法是一种求解最大流问题的算法 基本思想：通过寻找增广路径，逐步增大流值
实现步骤：初始化、寻找增广路径、更新流值、重复以上步骤直到找不到增广路径
优点：效率较高，适用于大规模网络流问题
Dinic算法的实现
初始化：设置源 点s和汇点t，初 始化网络流网络
寻找增广路径： 使用BFS寻找从 s到t的增广路径
汇报人：
EdmondsKarp算法等
扩展问题：最小 费用最大流问题 的扩展问题包括 最小费用最大流 问题、最小费用 最大流问题等。
多终端最大流问题
定义：在一个网络中，有多个源点和多个汇点，每个源点和汇点之间都有一条或多条边相连，每条边上都有一个容 量限制，求从源点到汇点的最大流量。
应用场景：多终端最大流问题在物流、交通、网络等领域有广泛的应用。
电力分配中的最大流问题
电力分配：将电力从发电站分配到各个用户 最大流问题：在电力分配中，需要找到一种最优的分配方案，使得电力分配达到最大 实际应用：在实际电力分配中，可以使用最大流算法来寻找最优的分配方案 应用效果：使用最大流算法可以大大提高电力分配的效率和准确性，降低电力损耗和成本
感谢您的观看
更新流量：沿 着增广路径更 新流量
重复步骤2和3， 直到找不到增 广路径
输出最大流值： 计算从s到t的 最大流值
Ford-Fulkerson算法的实现

S
5
I1 ∞
6 I2 ∞
7
∞ ∞
实验 E1 10
E2 2
t
I3
5
最大净收益：
（10+25）-（5+6+7） =17
2021/6/7
26
1 6 s32
43
12 25 t 39
最大净收益：(2+5+9) – ( 2+3+4 )= 16 – 最大流 9 = 7
做实验 2和3
2021/6/7
27
实验仪器和实验的输出： 构造图时要重新编号
怎样求正向割边和逆向割边？
2021/6/7
18
水流管道的最大流量由最细的管子容量决定的
2021/6/7
19
二、最大流最小割定量的应用
1、太空飞行计划问题
【问题描述：】 W 教授正在为国家航天中心计划一系列的太空飞行。每次太
空飞行可进行一系列商业性实验而获取利润。现已确定了一个 可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验 需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到 的仪器是I的子集Rj 。配置仪器Ik的费用为ck美元。实验Ej的赞 助商已同意为该实验结果支付pj美元。W教授的任务是找出一 个有效算法，确定在一次太空飞行中要进行哪些实验并因此而 配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指 进行实验所获得的全部收入与配置仪器的全部费用的差额。
1 6 s32
43
12 25 t 39
仪器：1-3中b[i]=-1的点。 实验：4-6中b[ j]=-1的点。
2021/6/7
割边：如果存在弧<i,j>， 满足：i∈S,b[i]>=0,