引言
图论与网络分析简介
¢图论(Graph Theory)是运筹学的一个分支，是建立和处理离散数学模型的一个重要工具，其起源最早可追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文，现已广泛应用在物理学、化学、控制论、信息论、科学管理、计算机等各个领域中。

¢网络分析（Network Analysis）作为图论的一个重要内容，已成为对各种系统进行分析、研究和管理的重要工具，包括：最小支撑树问题、最短路问题、最大流问题，以及网络计划评审与优化问题等。

¢哥尼斯堡城有一条河叫普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。

一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到出发地。

尽管试验者很多，但是都没有成功。

A B
¢为了寻找答案，1736年欧拉将这个问题抽象成下图所示的一笔画问题。

即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。

¢欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。

¢图论中的图，是反映现实世界中具体事物及其相互关系的一种抽象工具，它比地图、分子结构图、电路图等更抽象。

¢图的定义：简单的说，一个图是由一些点(Vertices)及点间的连线(Edges)所组成的。

点可以作为现实世界中事物的抽象，而点间的连线表示事物间的关系。

例2：有A、B、C、D四支篮球队，进行单循环比赛，比
赛情况如表1所示。

试用一个图表示各队之间的胜负关系。

比赛球队获胜球队
A——B A
A——C A
A——D D
B——C B
B——D D
C——D C
表1
图2
图3
01,,k i i i v v v V
∈ 1,k j j e e E ∈ 1(,)
t t t j i i e v v -=(1,2,,)t k = ，0112,,,,,,k k
i j i j j i v e v e e v μ= 0i v k i v 01k
i i i v v v μ=
0k
i i v v =0k
i i v v =
1475678v v v v v v μ=图4
44768754
v v v v v v v μ=245768v v v v v μ=3456874v v v v v v μ=
图5
图6
22412
v v v v μ=12143
v v v v μ= 图6
1(,)t t t j i i a v v -=(1,2,,)
t k = 0i v k i v 01k
i i i v v v μ= 0i v k
i v 0112,,,,,,k k
i j i j j i v a v a a v μ=
32143
v v v v μ=42412v v v v μ=12413v v v v μ=24134v v v v μ= 图6
(,)
ij i j v v ωω=ij ω,()
i j v v
1.产销平衡问题
¢
当总产量等于总销量，即：
时，称为产销平衡的运输问题，简称平衡问题。

11m n i j
i j a b
===∑∑
表1
运价（元/吨）（c ij）
产量（a i）
B1B2
A112015011
A214513015
A31351409
销量（b j）1421
解：因为 ， ，
所以这是一个产销平衡问题。

1
1115935
m i i a ==++=∑1
142135n j j b ==+=∑11m n i j
i j a b ===∑∑
111221223132111221
223132112131122232min 12015014513013514011159s.t.14
210
(1,2,31,2)ij z x x x x x x x x x x x x x x x x x x x i j =++++++=⎧⎪+=⎪⎪+=⎪⎨++=⎪⎪++=⎪≥==⎪⎩；
z=
*(11,0,0,15,3,6)T
X=*4515
，
¢产销平衡运输问题的一般模型为： 111
1
m in (1,2,)s.t.(1,2,)0(1,2,1,2,)m n ij ij
i j n ij i
j m ij j i ij z c x x a i m x b j n x i m j n =====⎧==⎪⎪⎪==⎨⎪⎪≥==⎪⎩∑∑∑∑ ；
2.产销不平衡问题
当总产量大于总销量
即 时，称为产大于销的运输问题；当总产量小于总销量
即 时，称为产小于销的运输问题。

¢产大于销的运输问题和产小于销的运输问题统称为产销
不平衡问题。

11m n
i j i j a b ==>∑∑11m n
i j i j a b ==<∑∑
表2
运价（元/吨）（c ij）
产量（a i）
B1B2
A112015011
A214513015
A31351409
销量（b j）1320
解: 因为 所以这是一个产大于销的运输问题。

1132033n j j b ==+=∑
1
1115935m i i a ==++=∑11==>∑∑m n i j
i j a b
111221223132
11122122
3132112131122232min 12015014513013514011159s.t.13
200
(1,2,31,2)ij z x x x x x x x x x x x x x x x x x x x i j =++++++≤⎧⎪+≤⎪⎪+≤⎪⎨++=⎪⎪++=⎪≥==⎪⎩；
z=
*(11,0,0,15,2,5)T
X=*4240
¢产大于销运输问题的一般模型为：
m in 11(1,2,)1s.t.(1,2,)1
0(1,2,1,2,)m n z c x ij ij i j n x a i m ij i j m x b j n ij j i x i m j n ij =∑∑==⎧≤=∑⎪=⎪⎪==∑⎨=⎪⎪≥==⎪⎩
；
¢产小于销运输问题的一般模型为：
m in 11(1,2,)1s.t.(1,2,)1
0(1,2,1,2,)；=∑∑==⎧==∑⎪=⎪⎪≤=∑⎨=⎪⎪≥==⎪⎩
m n z c x ij ij i j n x a i m ij i j m x b j n ij j i x i m j n ij
3.转运问题
¢前面介绍的运输问题，都是将物资直接由产地运往销地，但是，实际中很多的运输问题是先将物资由产地运往某个或某些转运站（转运站在现实情况中往往表现为仓库），再由转运站运往销地，这类运输问题不仅要求总运费最少，而且要同时选出最优运输路线，这就是转运问题。

图1
141511
x x+=
242515
x x+=
34359
x x+=
1424344647
x x x x x ++=+1525355657
x x x x x ++=+465614
x x +=475721x x +=
¢综上，建立此例的数学模型为：
14152425343546475657
14152425
343514243446471525355657
4656475714152425343546475min 90 10010592102837267 586411159s.t.1421,,,,,,,,z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x =++++++++++=+=+=++=+++=++=+=657
,0x ⎧⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪≥⎩
¢ 经求解，最优解如下：
*(11,0,0,15,0,9,0,11,14,10)T
X=*5306
z=最优调度方案如下图：
图2
¢归纳出转运问题的一般线性规划模型
m in ()0s.t.()0ij ij ij ij i ij ij ij ij j ij i j z c x x x a x x x x b x =
⎧-=≤⎪⎪-=⎪⎨⎪-≤=⎪⎪≥⎩∑∑∑∑∑∑∑所有弧运出弧运入弧运出弧
运入弧运入弧运出弧
起点节点转运节点销地节点对于所有的和
图1
图1
(0)
14(14)7
819(7)(8)(19)11
(11)。