《(交通运输)某市交通大学管理科学运筹学讲义》由会员分享，可在线阅读，更多相关《(交通运输)某市交通大学管理科学运筹学讲义（28页珍藏版）》请在金锄头文库上搜索。
1、第5章 图与网络分析5.1 图论的基本概念5.1.1 引言瑞士数学欧拉（Euler）在1736年发表了图论方面的第一篇论文，题为“依据几何位置的解题方法”，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河，该河上有两个岛，河上有七座桥，如图5-1（a）所示。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。欧拉用A、B、C、D四点表示河的两岸和小岛，用两点间的联线表示桥，如图5-1（b），该问题可归结为：能否从任一点出发，通过每条边一次且仅一次，再回到该点？即一笔画问题。欧拉证明了这是不可能的，因为图中每点都只与奇数条线相连。这是古典图
2、论中的一个著名问题。运筹学中的“中国邮递员问题”：一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个总是就与欧拉回路有密切的关系。图论的第一本专著是匈牙利数学家O.Konig著的“有限图与无限图的理论”，发表于1936年。随着科学技术的发展及电子计算机的出现和广泛应用，图论得到进一步发展，广泛应用于管理科学、计算机科学、心理学及工程技术管理中，并取得了丰硕的成果。5.1.2 基本概念自然界和人类社会中，大量的事物以及事物之间的关系，常可以用图形来表示。如为了反映城市之间有没有航班，我们可用图5-2来示意。甲城与乙城，乙城与丙城有飞机到达，而甲、
3、丙两城没有直飞航班。再如工作分配问题，我们可以用点表示每人与需要完成的工作，点间连线表示每个人可以胜任哪些工作如图5-3所示。在上面的例子中，我们关心图中有多少个点，点与点之间有无连线。这种图是反映对象之间关系的一种工具。图可分为无向图和有向图。两点之间不带箭头的联线为边，两点之间带箭头的联线为弧。由点、边构成的图是无向图，记由点、弧构成的图是有向图，记图5-4是一个无向图，其中，图5-5是一个有向图，其中，给定一个图，一个点、边的交错序列，如果满足，则称为一条联结和的链，记为。对于有向图，从中去掉所有弧上的箭头，应得到一个无向图，称为的基础图，记为。设是中的一个点弧交错序列，如果这个序列在基
4、础图中所对应的点边序列是一条链，则称这个点弧交错序列是的一条链。在实际问题中，往往只用图来描述的所研究对象之间的关系还是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，称为“权”，权可以代表如距离、费用、通过能力（容量）等等。这种点或边带有某种数量指标的图称为网络（即赋权图）。5.1.3 图的矩阵表示用矩阵表示图对研究图的性质及应用常是比较方便的，图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵等，这里只介绍其中两种常用矩阵。定义1网络，其边是有权，构造矩阵其中，称矩阵为网络的权矩阵。图5-6表示图的权矩阵为定义2对于图，构造一个矩阵，其中，则称矩阵为图的邻接矩阵。图5-7
5、所示图的邻接矩阵为当为无向图时，邻接矩阵为对称矩阵。5.2 最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、厂区布局等。问题表述：给定一个赋权有向图，对每一弧，相应地有权，又有两点，设是中到的一条路，路的权是中所有弧的权之和，记为。最短路问题就是求从到的路中一条权最小的路，。5.2.1 Dijkstra算法该算法是由Dijkstra于1959年提出来，用于求解指定两点、之间的最短路，或从指定点到其余各点的最短路，目前被认为是求情形下最短路问题的最好方法。算法的基本思路基于以下原理：若是从到的最短路，是中的一个点，那么从沿到的路
6、是从到的最短路。采用标号法：标号与标号。标号为试探性标号，为永久性标号。给点一个标号时，表示从到点的最短路权，点的标号不再改变。给点一个标号时，表示从到点的估计最短路权的上界，是一种临时标号。凡没有得到标号的点都有标号。算法每一步都把某一点的标号改为标号，当终点得到标号时，全部计算结束。Dijkstra算法基本步骤：给以标号，其余各点均给标号，。若点为刚得到标号的点，考虑，且为标号。对的标号进行如下的更改： 比较所有具有标号的点，把最小者改为标号，即当存在两个以上最小者时，可同时改为标号。若全部点均为标号则停止。否则用代替转回。例5.1 用Dijkstra算法求图5-8中从的最短路解：首先给以
7、标号，给其余所有点标号，由于，且是标号点，所以修改标号为：在所有标号中，最小，于是令。是刚得到标号的点，故考察。因为，且是标号，故新的标号为：在所有标号中，最小，故令。考察，因，在所有标号中，最小，令。考察，在所有标号中，最小，令。考察，在所有标号中，最小，故令。考察，令，所有点都标上标号，计算结束。从之最短路是：，路长13，同时得到到其余各点的最短路。5.2.2 逐次逼近算法Dijkstra算法只适用于所有的情形，当赋权有向图中存在负权时，则算法失效。例如在图5-9所示的赋权有向图中，用Dijkstra算法得到到最短路的权是5，但这里显然不对；因为到的最短路是，权为3。在存在负权时，我们采取
8、逐次逼近算法来求解最短路。为方便起见，不妨设从任一点到任一点都有一条弧，如果在中，则添加弧，令。显然，从到的最短路总是从出发，沿着一条路到某点，再沿到的，所以，从到的这条路必定是从到的最短路。故有，的距离必满足如下方程：为了求解这个方程的解，为的点数，令，为迭代步数。若第步，对所有，有则为到任一点的最短路权。例5-2 求图5-10所示赋权有向图中从到各点的最短路。解：迭代初始条件为：有，。用表5-1表示全部计算过程。表5-1 （表中空格为）ji wijD(t)(v1,vj)V1V2V3V4V5V6V7V8V10-1-230000V2602-1-5-5-5V3-30-51-2-2-2-2V480
9、23-7-7-7V5-101-3-3V61017-1-1-1V7-105-5-5V8-3-5066 当时，发现，表明已得到到各点的最短路的权，即表中最后一列数。如果需要知道点到各点的最短路径，可以采用“反向追踪”的办法。如已知，因故记下。因，记下，从而从到的最短路径是。递推公式中实际意义为从到点，至多含有个中间点的最短路权。所以在含有个点的图中，如果不含有总权小于零的回路，求从到任一点的最短路权，用上述算法最多经过-1次迭代必定收敛。显然，如果图中含有总权小于零的回路，最短路权没有下界。应用举例例5-3设备更新问题。某企业使用一台设备，在每年年初，都要决定是否更新。若购置新设备，要付购买费；若
10、继续使用旧设备，则支付维修费用。试制定一个5年更新计划，使总支出最少。若已知设备在各年的购买费及不同机器役龄时的残值和维修费，如表5-2所示。表5-2第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210解：把这个问题化为最短路问题用表示第年初购进一台新设备，虚设一个点，表示第5年底；用弧表示第初购的设备一直使用到第年年底；弧上的数字表示第年初购进设备，一直使用到第年底所需支付的购买、维修的全部费用。例如，弧上的28是第1年初购买费11加上3年的维修费5，6，8，减去了3年役龄机器的残值2；弧上的20是第2年初购买费12
11、减去机器残值3与使用2年维修费5，6之和，见图5-11。这样设备更新问题就变为：求从到的最短路，计算结果表明为最短路，路长为49。即在第1年、第3年初各购买一台新设备为最优决策，这时5年的总费用为49。5.3最大流问题最大流问题是一类应用极为广泛的问题。例如在交通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流；等等。20世纪50年代Ford ，Fulkerson建立的“网络流理论”是网络应用的重要组成部分。图5-12是输油管道网，为起点，是终点，为中转站，弧上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从到的总输油量最大？5.3.1
12、基本概念与基本定理网络与流定义给一个有向图，在中指定一点为发点，另一点为收点，其余的点叫中间点。对于每一个弧，对应有一个（简写为），称为弧的容量。这样的叫做网络，记作。所谓网络上的流，是指定义在弧集合上的一个函数，并称为弧上的流量，简记作。可行流与最大流容量限制条件：每一弧平衡条件：对于中间点，有对于发点，收点，有称为这个可行流的流量。可行流总是存在的，如零流，。所谓最大流问题，就是求一个流，使其流量达到最大，并且满足以上容量限制条件和平衡条件。其实最大流问题是一个特殊的线性规划问题，但是利用它与图的紧密关系求解，更为直观简便。增广链若是网络中联结发点和收点的一条链，且链的方向是从到，则与链的
13、方向一致的弧叫前向弧，表示前向弧的集合；与链的方向相反的弧叫后向弧，表示后向弧的集合。定义设是一个可行流，是从到的一条链，若满足下列条件，是可行流的一条增广链。 弧上，即中每一弧是非饱和弧。 弧上，即中每一弧是非零流弧。截集与截量设，我们把始点在，终点在中的所有弧构成的集合，记为。定义给网络，若点集被剖分为两个非空集合和， ，使，则把弧集称为分离，的截集。从定义可知截集是从到的必经之道。定义给一截集，把截集中所有弧的容量之和称为这个截集的容量，记作不难证明，任何一个可行流的流量都不会超过任一截量的容量，即。显然，若对于一个可行流，网络中有一个截集，则必是最大流，而必定是的所有截集中容量最小的一
14、个，即最小截量。最大流量最小截量定理：任一个网络中，从到的最大流的流量等于分离，的最小截集的容量。定理1可行流是最大流，当且仅当不存在关于的增广链。证明若是最大流，设中存在关于的增广链，令由增广链的定义，可知，令不难验证是一个可行流，且，这与是最大流假设矛盾。现在设中不存在关于的增广链，证明是最大流。令，若，且，则令；若，且，则令。因为不存在关于的增广链，故。记，于是得到一个截集，显然必有所以，。于是必是最大流，定理得证。定理1为我们提供了寻求网络最大流的一个方法。若可行流中存在增广链，说明还有潜力可挖，只须沿增广链调整流量，得到一个流量增大的新的可行流；否则是最大流。而判别是否存在增广链，可以根据是否属于来进行。5.3.2 寻求最大流的标号法（Ford，Fulkerson）设已有一个可行流，标号算法分2步：第1步是标号过程，通过标号来寻找增广链；第2步是调整过程，沿增广链调整以增加流量。标号过程每个标号点的标号包含两部分：第1个标号明它
