文档介绍：第3节最大流与最小费用流
最大流问题及其求解方法
最小费用流及其求解方法
网络分析方法
一、最大流问题及其求解方法
（一）最大流问题
最大流问题
设有向网络N（V，A），在发点Vs 有一批货，要通过网络上的弧运输到收点Vt 去，受运输条件限制，每条弧aij在单位时间内通过的车辆数不能超过cij 辆，分析：如何组织运输才能使从Vs到Vt 在单位时间内通过的车辆达到最多？
上面描述的这类问题，称为最大流问题。
最大流问题广泛地应用在交通运输、供水、油管供油、邮电通讯，也可以用在生产安排，管理优化等实际问题上。
网络分析方法
例：，有一批物资需要用汽车尽快从发点①运到收点⑦，弧（i，j）上所标的数字表示该条道路在单位时间内最多能通过的车辆数（单位：百辆），问如何调运，才能使单位时间里有最多的车辆从①调到⑦。

网络分析方法
┍┑线性规划方法┕┙
点①出发的车辆数应该与点⑦到达的车辆数相同，除①和⑦以外的各中间点，进的车辆数应该与离去的车辆数应该相同。
xij 是通过弧(i，j)的车辆数。
（）
（）
（）
（）
（）
（）
网络分析方法
对所有弧（i，j），应满足约束
满足（）～（）的解称为从①到⑦的一个可行流。
我们的目的：在所有可行流中求出一个方案，使得这个可行流得到的 f 最大。
若从收点到发点连接一条假想弧(7，1)，设它的容量c71=∞，那么
对点①：
对点⑦：

最大流问题的目标为
┍┑线性规划方法┕┙
（）
（）
（）
（）
网络分析方法
所以，对于发点为Vs，收点为Vt的网络N（V，U），当增加一条约束为cts=∞的假想弧（t，s）后，最大流问题就成为：
容量约束

平衡条件

目标函数
┍┑线性规划方法┕┙
（）
（）
（）
网络分析方法
（二）求最大流的方法：弧标号法
尽管最大流问题可以用线性规划模型描述，但是我们一般并不用求解线性规划的方法求最大流，而是用一种更为简便明了的图上作业法——弧标号法，求解上述最大流问题。
网络分析方法
(1)为了便于弧标号法的计算，首先需要将最大流问题（）。

网络分析方法
，每条弧上标有两个数字，其中，靠近点 i 的是，靠近点 j 的是。如① ②表示从①到②的最大通过量是5（百辆），从②到①的最大通过量是0；② ③表示从②到③和从③到②都可以通过2（百辆）；等等。

网络分析方法
(2)求最大流的基本步骤：标号法求最大流的过程，，其计算步骤如下：
步骤1. 从发点s到收点t选定一条路，使这条路通过的所有弧Vij的前面约束量cij都大于0，如果找不到这样的路，说明已经求得最大流，转步骤4。
步骤2. 在选定的路上，找到最小的容许量cij定为P。
网络分析方法