D=（V，A，C，Vs，Vt）。
2、流量、可行流、流出量、流入量 ： （1）流量：是指定义在网络 D上的每一条弧上的一个
? ? 函数 f (a ) ? f (vi , v j ) ? { f i j } 其中f(vi ,vj) =fij 叫做弧(vi，
vj)上的流量。
（2 ）可行流 ：称满足下列条件的流为可行流：
14.00000
Variable
Value Reduced Cost
FLOW 14.00000
0.000000
C( S, 1) 8.000000
0.000000
C( S, 2) 7.000000
0.000000
C( 1, 2) 5.000000
0.000000
C( 1, 3) 9.000000
0.000000
v4
9 (3)
v3
5 (0)
4 (2) 4 (1)
v6
9 (5)
vt
10 (1)
图中 (v3 , v6 ) 为零流弧，其余为非饱和弧、非零流弧。
流量v(f ) =8
最大流
? 网络上的流量最大的可行流称作的最大流 ?所谓最大流问题就是求给定网络的最大流
（二）最大流的算法
1、由图编写程序
2、由lingo8.0 软件求最大流
C( 2, 4) 9.000000
0.000000
C( 3, 2) 2.000000
0.000000
C( 3, T) 5.000000
0.000000
C( 4, 3) 6.000000
0.000000
C( 4, T) 10.00000
0.000000
F( S, 1) 7.000000
0.000000
图与网络分析
(Graph Theory and Network Analysis)
赵芳玲
图论是运筹学的一个重要分支，它是建立 和处理离散类数学模型的一个重要工具。用图 论的方法往往能帮助人们解决一些用其它方法 难于解决的问题。图论的发展可以追溯到 1736 年欧拉所发表的一篇关于解决著名的“哥尼斯 堡七桥问题”的论文。由于这种数学模型和方 法直观形象，富有启发性和趣味性， 深受人们 的青睐。到目前为止，已被广泛地应用于系统 工程、通讯工程、计算机科学及经济领域。传 统的物理、化学、生命科学也越来越广泛地使 用了图论模型方法。
1）容量约束：对于每一个弧（ vi ,vj）∈A有 0 ? fij ? cij 。
2）守恒条件：对于所用的中间点 v ? V ? {vs , vt )
有
?
? f i j ?
f ji
(vi , v j )? E
(v j , vi )? E
顶点vi 的流
顶点vi的流
入量
出量
则称f 为D上的可行流。其流量 v(f )为
图与网络分析
(Graph Theory and Network Analysis)
图的基本知识 树及最小生成树 最短路问题 最大流问题 最小费用最大流问题
四、 最大流问题
（一）、 基本概念
1、网络：设一个 赋权有向图 D=（V, A）,在V中指定一
个发点 vs和一个收点 vt ,其它的点叫做中间点。对于 D中的 每一个弧（ vi , vj）∈A ,都有一个非负数 cij,叫做弧的容量 。我们把这样的图 D叫做一个容量网络，简称网络，记做
s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/:c,f; endsets
s.t
? f ij ?
?
f ji
?
?? ?
v ?
f, vf
,
i? s i?t
j? V (i,j)? A
j? V ( j,i )? A
??0,
i ? s,t
data: c= 8 7 5 9 9 2 5 6 10;
F( 4, 3) 0.000000
1.000000
F( S, 2) 7.000000
0.000000
F( 1, 2) 2.000000
0.000000
F( 1, 3) 5.000000
0.000000
F( 2, 4) 9.000000
-1.000000
F( 3, 2) 0.000000
0.000000
F( 3, T) 5.000000
-1.000000
例8 现需要将城市 s 的石油通过管道运送到城市 t, 中间有4个中转站v1,v2,v3 和v4，城市与中转站的连 接以及管道的容量如下图所示，求从城市 s 到城市t
的最大流
v1
9
v3
8
5
2
s
5
6
t
7
v2
9
10 v4
v1
9
v3
8
5
s
5
2
6
t
7
v2
9
10 v4
附程序
max v f
MODEL: sets: nodes/s,1,2,3,4,t/; arcs(nodes,nodes)/
v( f ) ? ?
? f s j ?
f js
(vs , v j )? E
(v j , vs )? E
v( f ) ? ? f j t ? ? f t j(v j , v Nhomakorabea )? E
(vt , v j )? E
(发点vs )
(收点vt )
（3）饱和弧：可行流中 fij＝cij 的弧叫做饱和弧。
（4）非饱和弧： 可行流中fij＜cij的弧叫做非饱和弧。 （5）零流弧： fij＝0 的弧叫做零流弧。 （6）非零流弧 ： fij＞0 的弧为非零流弧。
0 ? f ij ? cij , (i,j) ? A
enddata
max = flow; @for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes):
程序结构
@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0); @sum(arcs(i,j)|i #eq# 1:f(i,j)) = flow;
1、集合定义部分（sets 到endsets)
@for(arcs:@bnd(0,f,c)); END
2、数据输入部分（data 到enddata) 3、其他部分（优化目标和约束）
Global optimal solution found at iteration: 6
Objective value:
例6 下图给出一个可行流 （容量约束、守恒条件）
5 (3)
v2
v5
13 (5)
6(3) 5 (2)
vs
4 (1) 5 (2)
v4
9 (3)
v3
5 (0)
4 (2) 4 (1)
v6
9 (5)
vt
10 (1)
例7 下图给出一个可行流
5 (3)
v2
v5
13 (5)
6(3)
5 (2)
vs
4 (1) 5 (2)