文档介绍：2017/11/11
管理运筹学课程组 ftp://
1
第四节网络最大流问题
例连接某产品产地vs和销地vt的交通网如下:
v1
v4
1
1
5
v2
vs
v3
vt
3
2
5
2
2
4
弧(vi,vj):从vi到vj的运输线,
弧旁数字:这条运输线的最大通过能力,
制定一个运输方案,使从vs到vt的产品数量最多。
2017/11/11
管理运筹学课程组 ftp://
2
弧旁数字:
运输能力。
问题:这个运输网络中,从vs到vt的最大输送量是多少?
v1
v4
1
1
5
v2
vs
v3
vt
3
2
5
2
2
4
2017/11/11
管理运筹学课程组 ftp://
3
一、基本概念与定理
1. 网络流
定义1 对于网络G=(V,A,C) ,定义在弧集合
A上的一个函数f = {f(vi ,vj)} 称为网络流,
f(vi , vj) (简称fij)为弧aij ∈A上的流。
2017/11/11
管理运筹学课程组 ftp://
4
弧旁数字:
容量
(a)图是一个网络
v2
v5
3
4
8
v3
v1
v4
v6
5
10
6
11
17
3
5
v2
v5
3
1
3
v3
v1
v4
v6
1
5
3
6
2
2
2
弧旁数字:
流量
2017/11/11
管理运筹学课程组 ftp://
5
cij fij
vi
vj
v2
v5
3 1
4 0
8 3
v3
v1
v4
v6
5 0
10 5
6 3
11 6
17 4
3 2
5 3
2017/11/11
管理运筹学课程组 ftp://
6
2. 可行流
定义2 满足下述条件的流 f 称为可行流:
1)容量限制条件: 对每一弧(vi , vj )∈A
0≤fij ≤cij
2)平衡条件: 对中间点vi (i≠s,t ),有
V( f ) 称为可行流 f 的流量,即发点的净输出量。
如所有fij=0,
零流。
可行流总是存在的
2017/11/11
管理运筹学课程组 ftp://
7
3. 最大流
若为网络可行流,且满足:
V(f *)=max{V(f )∣f }为网络D中的任意
一个可行流,则称f *为网络的最大流。
设μ=(x,…,u,v,…A)是网络G中的一条初
等链并且定义链的方向是从x到A。若D中有弧
(u,v),与μ方向一致,则称(u,v)为链μ
的前向弧,若D中有弧(u,v),则称
(v, u),为链μ的后向弧。
2017/11/11
管理运筹学课程组 ftp://
8
5. 增广链
对可行流 f ={ fij }:
非饱和弧:fij < cij
饱和弧:fij =cij
非零流弧:fij >0
零流弧:fij =0
链的方向:若µ是联结vs和vt的一条链,定义链的方向是从vs到vt 。
v2
v5
v3
v1
v4
v6
2017/11/11
管理运筹学课程组 ftp://
9
µ = (v1,v2,v3,v4,v5,v6 )
µ+={(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6)}
µ - ={(v5,v4)}
v2
v5
v3
v1
v4
v6
2017/11/11
管理运筹学课程组 ftp://
10
定义3 设 f 是一个可行流, µ 是从vs 到vt 的一条链,若µ满足下列条件,称之为(关于可行流 f 的)一条增广链。
(vi , vj ) ∈µ- 0 < fij ≤ cij 后向弧是非零流弧,
(vi , vj ) ∈µ+ 0≤ fij <cij 前向弧是非饱和弧,
v1
v2
v3
v4
v5
v6
8 4
6 0
6 5
3 3
5 4