文档介绍：网络优化
Network Optimization
http://
办公室：理科楼2206# （电话：62787812）
Email:******@
/~jxie
第6章最大流问题 (Maximum Flow Problem) 第1讲
1
许多实际问题都可以转化为最大流问题
S
T
最大流问题的例子
公路交通网络：车流流量
2
在有向图G=(V，A)上定义如下的权函数：
（1）L：AR为弧上的权函数，弧(i,j) 对应的权 L (i,j) 记为lij，称为弧 (i,j)的容量下界（lower bound）;
（2）U：A R为弧上的权函数，弧(i,j)对应的权U(i,j)记为uij ，称为弧(i,j) 的容量上界，或直接称为容量（capacity）;
（3）D：V R为顶点上的权函数，节点i对应的权D(i)记为di ，称为顶点i的供需量（supply/demand）;
此时网络可称为流网络(Flow Network,一般仍简称为网络),记为 N=(V,A,L,U,D).

di >0:供应点(supply node)或源(source)、起始点或发货点
di <0:需求点(demand node)或汇(sink) 、终止点或吸收点
di ＝0:转运点(transshipment node)或平衡点、中间点
3
对于流网络N=（V，A，L，U，D），其上的一个流(flow) x是指从N的弧集A到实数集合R的一个函数x：A R, 即对每条弧(i,j) 赋予一个实数 (称为弧(i,j)上的流).
如果流x满足
存在可行流的必要条件
则称x为可行流(feasible flow).
至少存在一个可行流的流网络称为可行网络(feasible network).
如果流x只满足容量约束(), 但不一定满足流量守恒条件(), 则称x为伪流(pseudoflow)，或容量可行流.
流量守恒/平衡条件
容量约束/可行条件
网络中的流
一般可以把L 0的流网络转化为L=0的流网络进行研究(思考？)
除非特别说明, 以后我们总是假设L=0,网络简记为N=(V,A,U,D).
4
运输网络的特点是只有源或汇，没有中间转运点.
显然，此问题有解的一个必要条件是
网络中的流
例 - 运输网络和运输计划
有一批货物从货源地运往目的地，假设货源集合为S，目的地集合为T. 货源i可提供的货物数量为ai个单位，目的地j对货物的需求量为bj个单位.
以（S，T）为节点集作完全二部图，以 ai ，- bj 为节点上的供需量。通过每条弧的运输量没有限制（非负即可）。
一个运输计划就相当于该网络中的一个流。
S
T
5
网络中的流
有向网络中，令所有弧上的容量下界为0，容量（上界）为1，并令节点s的供需量为1，节点t的供需量为-1。
从s到t的一条有向路正好对应于网络中的一个可行流x
（当xij =1时，表示弧(i，j)位于s-t路上，
当xij=0时，表示弧(i，j)不在s-t路上）.
思考：网络中的任意一个可行流是否一定对应于一条有向路？
P
s
t
6
网络中的流
在流网络N=(V,A,U,D)中，对于流x, 如果某条弧(i,j)上的流量等于其容量（　　　　），则称该弧为饱和弧（saturated arc）；如果某条弧（i，j）上的流量为0(　　　)，则称该弧为空弧（void arc）.
如果所有弧均为空弧，即

则称x为零流，否则为非零流.
S 1
5 t
2
3
4
1,1
1,1
1,1
1,0
1,1
2,2
3,0
3,2
7
网络中的流
对于给定流网络N=(V,A,U,D)中的流 x：A R ，如果N中存在一条有向路P，使得
，
则称x为路流（Path flow），v称为该路流的流值（流量）. v=0时，称该路流为零路流，否则称为非零路流.
如果N中存在一个有向圈W，使得
，
则称x为圈流（Cycle flow），v 称为该圈流的流值（流量）. v=0时，称该圈流为零圈流，否则称为非零圈流.
5
6
P
6
5
5
5
6
W
8
在网络N=(V,A,U,D)中，任何一个可行流可以表示为若干个路流和若干个圈流之和，且这些路流和圈流满足下列性质：
（1）非零路流对应的有向路从一个源点指向