文档介绍：第6章网络模型
1
网络模型的应用范围和定义
大量的运筹学问题都可以应用网络建模来求解:
在墨西哥海湾上需要设计一个海面上的天然气管道网络,将各个井口链接到岸边的运输点,模型目标是最小化管道建设费用。
在已经存在的道路网络中,求起讫点之间的最短路径.
求山西煤矿到北京的发电厂的煤浆管道网络的最大运输量
给一个工程项目中的各项活动确定时间表
2
网络模型的定义
网络是由节点(node)和弧(arc)集合组成,用符号(N,A)表示,其中N表示节点的集合,A表示弧的集合。
1
4
2
3
5
N={1,2,3,4,5}
A={(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}
如果一条弧上的其中一个方向的流量是正数,相反方向就是为零,该弧是有向的(directed),如果所有弧上的容量都是有向的,则网络是有向网络。将两点之间链接起来,并经过其他的一些节点的这一些列弧,称之为路径(path),如果经过路径又能回到自身,则这些路径称之为圈(Loop),如果网络中没有圈,网络就是树(tree),如果该树包括了图上所有的节点,则是生成树。
3
欧拉(Euler) 在1736 年发表图论方面的第一篇论文,解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河,该河中有两个小岛,河上有七座桥,参见图 (a) 。
当时那里的居民热衷于这样的问题:一个散步者能否走过七座桥,且每座桥只走过一次,最后回到出发点。
B
A
C
D
B
A
C
D
4
例1
是北京、上海等十个城市间的铁路交通图。与此类似的还有电话线分布图、煤气管道图、航空路线图等。
北京
天津
济南
青岛
武汉
南京
上海
郑州
连云港
徐州
5
例2
分别用点v1,v2,v3,v4,v5分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛过,就在相应的点之间联一条线,且这条线不过其他点。如下图所示:
v1
v2
v3
v4
v5
可知各队之间的比赛情况如下:
甲——乙、丙、丁、戊
乙——甲、丙
丙——甲、乙、丁
丁——甲、丙、戊
戊——甲、丁
6
例3 “染色问题”
储存8种化学药品,其中某些药品不能存放在同一个库房里。用v1,v2,…,v8分别代表这8种药品。规定若两种药品不能存放在一起,则其相应的点之间联一条线。如下图所示:
v1
v2
v3
v4
v5
v6
v7
v8
可知需要4个库房,其中一个答案是:
{ v1 }
{ v2, v4, v7 }
{ v3, v5 }
{ v6, v8 }
还有其他的答案。
7
从以上几个例子可见
可以用由点及点与点的联线所构成的网络,去反映实际生活中,某些对象之间的某个特定的关系,通常用点代表研究的对象(如城市、球队、药品等等),用点与点的联线表示这两个对象之间有特定的关系(如两个城市间有铁路线、两个球队比赛过、两种药品不能存放在同一个库房里等)。
网络是反映对象之间关系的一种工具
因此,可以说,在一般情况下,网络中点的相对位置如何,点与点之间联线的长短曲直,对于反映对象之间的关系,并不是重要的,例如哥尼斯堡七桥问题。
如例2,也可以用网络去反映五个球队的比赛情况,这与例3没有本质的区别。所以,图论中的图与几何图、工程图等是不同的。
8
最小生成树算法
最小生成树算法是以来链接一个网络所有的节点,使得树上边的总长度最小。例如,在几个城镇之间修路,使得任意两个城镇之间都有路相连,之间可以穿过其他城镇那么最经济的道路网络设计方案就是道路里程最小。
令N={1,2,…,n}是网络中节点的集合,定义:
9
最小生成树算法步骤:
第0步令
第1步从中的任意一个节点i开始,令C1={i}, 那么
,设定 k=2.
一般的第k步在还没有连接的节点集合中选择一个节点 j*,使得j*到Ck-1中某个节点之间的弧长最小,然后将 j* 放在Ck-1,从中删除 j*,即
10