网络规划与网络分析

1、运 筹 学“运筹学”课题组6.7 习 题本章内容重点 6.1 图与网络6.2 树6.3 最短路问题6.4 网络最大流问题6.5 最小费用最大流6.6 案例：网络的中心与选址问题第六章 网络规划与网络分析概 述图论是目前运用十分广泛的运筹学分支之一；自1736年著名数学家欧拉(Euler)解决了有名的哥尼斯堡七桥问题以来，图论取得了十分迅速的发展； 已广泛应用于计算机、信息论、经济科学等各领域，用以解决各种各样的决策问题。 概 述生活中的许多问题都可以运用图论的理论与方法来解决。例如： 在生产的组织与管理中，为了完成某项生产任务，各工序之间如何衔接，才能使任务完成得既快又好？在城市水、电、煤气供

2、应问题中，管道与供电线路如何铺设，才能做到既满足要求，又使总费用最省？6.1 图与网络自然界和人类社会中许多事物以及事物之间的关系，都可以用点和线连接起来的图形来描述。例如用点表示城市，点间联线表示城市间的道路，就可描述城市间的交通，哥尔斯保七桥问题：哥尔斯保城有一条普雷尔河，该河上有两个小岛，河上有七座桥将这两个小岛及岛与河岸之间连接起来。 概 述 问题是要从A,B,C,D这四块陆地中的任何一块开始，通过所有的桥一次且仅一次，最后回到开始出发的这块陆地。如果联线旁标注城市间的距离网络图中称为权，形成加权图，就称为网络图，就可进一步研究从一个城市到另一个城市的最短路径；或者标上单位运价，就可分

3、析运费最小的运输方案。例6-1图a表示5个球队之间的赛事关系。其中点 a, b, c, d, e, f 分别表示5个球队，两点的连接表示两球队之间的赛事关系。 aedbc从图中可反映出a球队分别与b，c，d 球队有赛事；球队还与c球队，d球队还与e球队有赛事。图a 这5个球队之间的关系也可用图b)来反映。图a)与b)没有本质的差异 可见表示球队间有无赛事关系是两点间的连线，而图中点的相对位置如何、点与点之间联线的长短曲直，对反映对象之间的关系并不重要。eabdc图b例 6-2 图 6-2 是一张管道运输网示意图，代表7个城市间物资运输关系，v1,v2,v3,v4,v5,v6,v7表示7个城市，

4、箭线旁数字表示物流的最大容量。现在要求出从v1地到v7地的运送的最大流方案。图 6-2 是由点及带箭头的连线所组成的图形。为区别起见，把两点间不带箭头的连线称为边，带箭头的连线称为弧。 用图来描述事物间的联系，不仅直观清晰，且网络图的画法简便，不必拘泥于比例和曲直。这里所讲的图是反映对象之间关系的一种工具。电路网络、城市规划、信息传递、物质结构、物资调配等也都可以用点和线连接起来的图进行模拟。 定义6-1 无向图是一个有序二元组（V，E），记为G=（V,E），其中V=(v1， v2，vp)是p个点的集合，简称定点集； E=（e1， e2，eq）是条边的集合，简称边集合，并且是一个无序二元组。记

5、为（1）无向图由点和边组成的图称为无向图，如图 6-1。图 6-3即为无向图，图中：顶点数：点集V中元素的个数称为图G的顶点数，记为 。如图 6-3，边数 ：边集 E中元素的个数，记为如图 6-3，端点：对于边，e为vi , vj的关联边。图 6-3 中， 为 的端点， 为 的关联边。称vi，vj为e的端点。若点vi , vj有边相连，即则称vi ,vj 相邻， vi ,vj 与e关联。如图6.3 中， v3,v5相邻， v3,v5与e7关联。图6.3（2）简单图环（自回路）：一条边的两个端点如果相同，称此边为环。如图6-3中的e1。多重边 ：两个点之间多于一条边的，如图6-3中的e4， e5

6、.不含环和多重边的图称为简单图，含有多重边的图称为多重图。(3) 点的次（度）以点v为端点的边数叫做点v的次，记作d(v)。如图6-3中，d(v1)=4，d(v2)=4。 若，则称称为图G的次序列。 次为 1 的点称为悬挂点，连接悬挂点的边称为悬挂边。次为 0的点称为孤立点。次为奇数的点称为奇点，次为偶数的点称为偶点。定理 6-1 任何图G =（V,E）中，所有点的次数之和等于边数的2倍。即证：由于每条边必有两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数之和等于边数的2倍。定理 6-2 任何图G =（V,E）中，奇点的个数必为偶数。证：设图G中奇点与偶点的集合分别为V1和V2

7、， 由定理 6-1 知由于2q(G)为偶数，而 是若干个偶数之和，也为偶数。所以 必为偶数，即奇点的个数 必为偶数。（4）链链：对于无向图G =（V,E）, 称顶点和边交替的序列 为连接 的一条链，简记为 其中 ,称 为链的两个端点。图6-3 中的都是链。两个端点重合的链，称为圈。在一个图中，如果任何两个顶点之间都有一条链，该图称为连通图。有向图是一个有序二元组（V,A），记为D（V,A），其中 是p个顶点的集合，是q条弧的集合，并且 是一个有序二元组，记为 并称 是以vi为始点， vj为终点的弧，i，j的顺序不能颠倒，图中弧的方向用箭头标识。由点和弧组成的图称为有向图，如图6-4。图中：二、

8、有向图 （1）有向图 （2）简单有向图两个端点重合的弧称环。如图 6-4 中的a1 .图6-4两个端点之间的同向弧数大于等于2，称为多重弧。无环也无多重弧的有向图称为简单有向图。 （3）点的出次和入次以点v为起点的弧数叫做点v的出次，记作以点v为终点的弧数叫做点v的入次，记作称 为点v的次。 （4）路在有向图D=(V,A)中，点和弧交替的序列，若有或，则称P是一条链接的有向路 实际问题中，如果在图中赋予边一定的数量指标，我们常称之为“权”。通常把这种赋权图称为网络。 与无向图和有向图相对应，网络又分为无向网络和有向网络。 三、网络 图的矩阵表示方法：关联矩阵：在图G=(V,E) 中，V=（v1

9、,v2,vp), E=(e1,e2 ,eq)，见图6.5,构造一个矩阵 其中图6.5则称A为G的关联矩阵。关联指顶点与边的关系。图6.5的关联矩阵邻接矩阵：在图G=(V,E) 中，V=（v1,v2,vp), E=(e1,e2 ,eq),见图6.6构造一个矩阵 其中图6.6则称A为G的邻接矩阵。邻接指顶点与顶点的关系。图6.6的邻接矩阵权矩阵 ：在图G=(V,E) 中，V=(v1,v2,vp),E=(e1,e2 ,eq),其边vi,vj有权wij。见图6.7构造一个矩阵 其中图6.7则称A为G的权矩阵。图6.7的权矩阵6.2 树树是图论中结构最简单但又十分重要的图，在自然科学和社会科学的许多领域

10、都有广泛的应用。a）b）实例：已知有 5个城市，要在它们之间架设电话线网，要求任何两个城市都可以彼此通话（允许通过其他城市），并且电话线的条数最少。 用点 分别表示 5个城市。如果在v1与v5，v1与v2，v3与v4之间各架一条电话线，这个方案可用图6.7（a）表示出来。这个方案显然是不满足要求的，因为在这样的电话线网中， v3，v4与v1 ，v2， v5之间就不能通话。图6.7（a）如果按照图 6.7（b）来设计电话网，虽然方案能满足不同城市之间通话的要求，但却不能保证电话线的条数最少。原因是图 中含有一个圈， 如果从这个圈上，任意去掉一条，并不影响电话网的连通性，同时又可节省一条线。因此，

11、满足要求的电话网必须是：连通的；不含圈的。满足这两点要求的图称为“树”。图 6.7（b）6.2.1 树的基本概念与性质定义 ：连通且不含圈的无向图称为树。树中次为1的顶点称为树叶(悬挂点)，次大于 1的顶点称为分枝点。树的性质可用下面定理给出： 设有图G=(V,E) ，n和m分别为图G的顶点数和边数，则下列命题是等价的：（1） G是一个树。（2） G无圈，且m=n-1 。（3） G连通，且m=n-1 。（4） G无圈，但每加一条新边即存在唯一一个圈。（5） G 连通，但每舍去一条边就变成不连通。（6） G中任意两点，有唯一路相连。定义6-7 图G=(V,E)，若E是E的子集，V是V的子集，且E

12、中的边仅与V中的顶点相关联，则称G=(V,E)是G的一个子图。特别的，若V=V，则G称为G的生成子图（或支撑子图）定义6-8 若图G的生成子图是一棵树，则称该树为G的生成树，或简称为图G的树。G中属于生成树的边称为树枝，不在生成树中的边称为弦。定理 6-4 图G=(V,E)有生成树的充分必要条件为 G是连通图 。证明：必要性由定义直接可得。充分性的证明过程如下： 设图G是连通的。若G不含圈，则 G就是其自身的一棵生成树； 若G含有圈，任取一个圈，从圈中任意去掉一条边，得到图G的一个生成子图G1。 如果G1不含圈，那么G1是G的一棵生成树； 如果G1仍含有圈，那么从G1中任取一个圈，从圈中再任意

13、去掉一条边，得到图 G的一个生成子图G2。 重复使用此法使每个圈都受到破坏，最后可以得到G的一个生成子图Gk，它是不含圈的生成子图。 这就是G一棵生成树。 上述充分性的证明给出了求生成树的一种方法。就是任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到不含圈时为止，即得到一棵生成树，称这种方法为“破圈法”。除“破圈法”外，还有另一种方法可称为“ 避圈法”。这种方法是在图 G中，每步选取一条边使它与已选边不构成圈，直到选够n-1条边为止。 6.2.2 最小支撑树及其算法（1）构造支撑树的算法1) 破圈法 破圈法思路：将连通有圈图逐步删除边，变成连通无圈图。破圈法步骤： G=(V,E)为连通

14、图，Gk=(V,Ek)是G的支 撑子图。 步骤1 开始取G0=(V,E)=G，k=0 步骤2 若Gk不含圈，则Gk为支撑树；若Gk含圈，取Gk中的任一圈，去掉圈上任一条边，得Gk+1=(V，Ek+1)， Ek+1=Ekek; 步骤3 若kq(G)-p(G)+1,则重复步骤 2；否则， Gk+1一定是支撑树。 2）避圈法 避圈法思路：将不连通的无圈图通过边的增加，逐步变成连 通无圈图。 避圈法步骤： 为连通图。步骤1 始取 ；步骤 2 若Gk 连通，则Gk为支撑树；若Gk不连通，任选图G边集E中的一边e，使e的两个端点分属两个不同的连通分图，得， ；步骤 3 若 ，则重复步骤 2；否则，Gk一定

15、是支撑树。 支撑树的构造不涉及边的权。将支撑树的构造与边权的选择结合，产生最小树的概念。最小支撑树是网络优化中一个重要的概念，它在交通网、电话网、管道网、电力网等设计中均有广泛的应用。 （2）最小支撑树定义设有一个连通图G=(V,E),每一边e=vi,vj有一个权w(e)=wij，如果是的一个支撑树，称中所有边的权之和为支撑树的权，记为：如果支撑树T*的权W(T*)是G的所有支撑树中权数最小的，则称T*是G的最小支撑树（也称最小树），即（3）寻找最小支撑树的算法 寻找最小支撑树也可以用上面介绍的破圈法和避圈法，但要在舍边和增边时，增加一些边的权数的限制。1）破圈法 步骤：从图G中任取一圈，去掉

16、这个圈中权数最大的一条边，得一支撑子图G1。在G1中再任取一圈，再去掉圈中权数最大的一条边，得G2 。如此继续下去，一直到剩下的子图中不再含圈为止。该子图G1就是的最小支撑树T* 。 2）Kruskal算法（避圈法） Kruskal算法是Kruskal于1956年提出的一个产生最小树的算法 算法的基本思想是：每次将一条权最小的弧加入子图T 中，并保证不形成圈。即按照边长由小到大排序，如果当前弧加入后不形成圈，则加入这条弧。当弧有 时，即为最小树。 步骤0 按照权的大小对边由小到大排序，即 令 步骤1 判断 是否含圈。如含圈，转步骤2；否则，转步骤3. 步骤2 令i=i+1 。若im ，转步骤1

17、；否则，结束，没有支撑树，G 不联通。 步骤3 令 。若j=n-1 ，结束，T是最小树；否则，转步骤1。例6-4 用Kruskal算法求解下图6.8（a)所示网络的最小树，每条边上的数表示该边的权值。图6.8（a)解：按照破圈法的原则，从图中任取一圈，去掉这个圈中权数最大的一条边，得一支撑子图。在支撑子图中再任取一圈，再去掉圈中权数最大的一条边。如此继续下去，一直到剩下的子图中不再含圈为止。该子图就是所求的最小生成树。最小生成树如图6.8（b）所示：图6.8（b）3）Prim算法(边割法)Prim算法又称为边割法，是Prim于1957年提出的求解最小树的算法。 算法的核心思想是不断扩展一个子树

18、，使其逐步包含所有的顶点。具体增边的选择，是在当前子树的顶点集合与补集合所形成的边割中选择最小的边。Prim算法：步骤0 从图中任选一点Vi，让ViS，图中其余点均包含在 中；步骤2 从 之间的连线中找出最小边，这条边一定包含在 最小支撑树内，不妨设最小边为vi, vj，将vi, vj标记成最小支撑树内的边； 步骤3 令 步骤4 重复步骤2、步骤3，一直到图中所有点均包含在S中为止。 例题6-5 用Prim算法求解图6.9（a）中的最小树。图6.9（a）解：求解结果见图6.9（b）图6.9（b）例6- 在一个地区有一个公共服务机构，如飞机场、医院等，图6.10中O所示。三个乡镇（图6.10中的

19、v1,v2,v3所示）需要连接到这个公共服务机构。乡镇与服务机构之间、乡镇与乡镇之间的连接高速公路的造价为边的权。问如何构建这个连接网络并分配建设费用？图6.10解：这显然是一个最小支撑树的构建和建设成本分担问题。 v1,v2,v3分别连接到O的建设成本为C(v1)9，C(v2)10，C(v3 )11； 将 v1,v2 连接到O的最小树的建设成本为C(v1,v2 )17，同样，C(v1,v3)18， C(v2,v3)11；将3个顶点连接到 的最小树O的建设成本C(v1,v2,v3)18 设分别承担的建设费用为x1,x2,x3，则建设费用的分配应该满足：有无限个向量满足上式，每个向量都可以作为一

20、个建设费用的分配方案。6.3 最短路问题 最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、厂区布局等。 在上一章中我们曾介绍了最短路问题的动态规划解法，但某些最短路问题（如道路不能整齐分段者）构造动态规划方程比较困难，而图论方法则比较有效。另外，这个问题相对比较简单，其算法经常做为其他问题的子算法而调用。 最短路问题是求一条v1vj的路 ，使它是从v1到vj的所有路中总权最小的路。即：优化问题6.3.1 基本概念与Bellman方程 最短路问题的一般提法是设N=(V,A,W)为网络图，图中各边(vi , vj)有权wij（wij=表示v

21、i, vj之间没有边）， v1为起始点， vj为图中任意一点。网络中有多条v1vj的路P,每条路的权是其所有构成弧的权之和。 对于网络中的一个圈，其权是其所构成边的权之和。权为正的圈称为正圈；权为负的圈称为负圈；权为0的圈称为零圈。 在一个没有负圈的网络中，求解最短路问题比较简单，目前的大多数算法也是面向这种网络的。 对于存在负圈的网络，其最短路的求解问题很复杂，目前还没有好的有效算法。令uj表示网络中v1vj的最短路的长度。基于动态规划中递归方程的思想，得到求解最短路问题的递归关系如下：定理 6-5 设有向网络G中只含正圈，并且从点v1到其余点 vj都有有限长度的有向路，那么(6.1)有唯一

22、有限解。定理 6-6 设 不含圈，则N的顶点可以重新编号，使Bellman算法的基本思想是： 基于这样的事实：从v1到vj的最短路总是沿着该路先到vj前面的某一点vi ，然后再沿着(vi ,vj)到vj 。于是，若v1到vj为最短路，则v1到vj亦为最短路。例6-7 计算如下网络中 各点的最短路。图6.11解：这是一个有圈网络图，但v1是起始点，故进入v1的弧可以删去。对顶点进行重新标号，得到网络图，图6-11(b)。按照ui，求出最短路网络，图6-11(c)。Bellman方程的计算：6.3.2 Dijkstra算法 1959年,E.W.Dijkstra 提出了求正权网络最短路径的标号法，用

23、给节点记标号来逐步形成起点到各点的最短路径及其距离值，是目前较好的一种算法。 Dijkstra 算法也称为双标号法。也就是对图中的每个点vj 赋予两个参数（通常称为标号） ： 第一个标号uj表示从起点v1到vj的最短路的长度，是距离标号； 第二个标号 称作前趋标号，是记录在v1到vj的最短路上， vj 前面一个邻点的下标，用来标识最短路路径，从而可对终点到始点进行反向追踪，找到v1到vj的最短路。通过不断修改这些标号，进行迭代计算。Dijkstra 算法：步骤0 给起点v1标号(0,s)，表示从v1到v1的距离为0，vs为起 点。 步骤1 如果S=V，则uj即为v1到vj的最短路的长度，最短路

24、可以按照 pred(j )记录的信息，反向追踪即可获得，结束。 否则，转步骤2。步骤2 求出弧集 。若 ，表明从所有已经赋予标号的顶点出发，不再有这样的弧，它的另一顶点尚未标号，则计算结束。对于已有标号的顶点，可求得从到达这个顶点的最短路，对于没有标号的顶点，则不存在从到达这个顶点的路。若弧集，转步骤3。 步骤3 对弧集A中的每一条弧(vi , vj) ，计算 则vi 赋予双标号 其中 。 转步骤 2 经上述一个循环的计算，将求出v1到一个顶点vj的最短路及其长度，从而使一个顶点vj得到双标号。 若图中总共有n个顶点，则最多计算个(n-1)循环，即可得到最后结果。 例6-8 求v1到其余各点的

25、最短路 图6.12解：（1）给起点V1 标号(0,S) ，表示从V1到V1的距离P(V1)=0,V1为起点。 （2）标号点的集合 ，没标号点的集合 ， 弧集 中 ，点V2 对应的是010，点V3对应的是015，点V4对应的是08。点V4最小，故点V4得到双标号（8，1）。8代表从V1到V4的最短路长度，1代表前趋点V1。 （3）标号点的集合 ，没标号点的集合 ，弧集 中点V2对应的是10，点V3 对应的是15。点V2最小，点V2得到双标号（10，1）。10代表最短路长度，1代表前趋点V1。 （4）标号点的集合 ，没标号点的集合 ，弧集点V3对应的是102，点V5对应的是106。故点V3得到双标

26、号（12，2）。（5）标号点的集合 ，没标号点的集合 ，弧集点V5对应的仍然是16，点V5得到双标号（16，2）。（6）标号的点的集合 ，没标号的点的集合 ，弧集点V7对应的是1620，点V7得到双标号（36，5）。（7）标号的点的集合 ，没标号的点的集合 ，弧集 计算结束。 此时， ，即点V6 还未标号，说明点 V1到点V6 没有有向路。 图 6.13至此，自顶点 V1至其余顶点的最短路都已求得。如图 6.13粗线所示。 由上述步骤看出，标号法是一种按标号值从小到大的逐步外探法。只适用于权值为正实数的情况，如果权值有负的，算法失效。 6.3.3 Floyd-Warshall算法基本思路： 先

27、给每个顶点一个标号，这些标号不一定是最短路的长度，一般是一个近似。 然后逐步对顶点的标号进行修正，使标号逐步接近最短路长度。 当算法迭代终止时，所有的定点标号变成最短路长度，临时标号变成永久标号 Floyd-Warshall算法是求网络中任意两点间的最短路的算法，这个算法的基本思想就是标号修正。 为计算方便，令网络的权矩阵为 ， 为 到 的距离。FloyWarshall算法用标号修正算法表示如下： 是第k次迭代得到的vi到vj的临时性标号，是在到的路中边数不超过k条的路中最短路的长度，是最短路长度的近似。 这个算法在迭代n次后，如果各顶点对之间存在最短路， 即是vi到vj的最短路长度，临时性标

28、号变成永久性标号。 如果 还没有收敛，即存在两个顶点vi和vj ，使得 ，这说明网络中存在负圈。 例6-9 求如图6.14所示的网络G中任意两点间的最短路。弧旁的数字表示弧的长度。图6.14解：用 表示各顶点对之间通过不超过k条弧所能够到达的最短路的长度矩阵，则计算结果如下： 首先给出通过不超过1条弧即可到达的长度矩阵到不超过2条弧即可到达的长度 就是D(1)第一行与它第二列对应元素之和的最小值到不超过2条弧即可到达的长度 就是D(1)第一行与它第三列对应元素之和的最小值到不超过2条弧即可到达的长度 ；其他同样计算。就是D(1)第一行与它第四列对应元素之和的最小值 得到各顶点对之间通过不超过2

29、条弧所能够到达的最短路的长度矩阵：各顶点对之间通过不超过k(3,4)条弧所能够到达的最短路的长度矩阵如下：我们看到 则 中的长度就是最短路长度。 6.4 网络最大流问题 最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息流，等等。 20 世纪 50 年代,福特（Ford）、富克逊（Fulkerson）建立的“网络流理论”是网络应用的重要组成部分。 最大流量问题就是： 给一个带收发点的网络（一般收点用 vt 表示，发点用 vs 表示，其余为中间点），其每条弧的权值称之为容量，在不超过每条弧的容量的前提下，要求确定每

30、条弧的流量，使得从发点到收点的流量最大。 6.4.1 基本概念与模型 要把一批货物从起点v1通过铁路网络运到终点v6去，把铁路网上的车站看作顶点，两个车站间的铁路线看作弧，而每条铁路线上运送的货物总量（容量）总是有限的，我们把某线路上的最大可能运送量称为它的容量。考虑：如何安排运输方案，使得从起点v1运到终点v6的总运量达到最大？“流”，是指铁路线（弧）上的实际运输量。 每条弧旁的数字即为该弧的容量cij，弧的方向就是允许流的方向。 把标有弧容量的网络称为容量网络， 记为实际通过各弧的流量，记为 。所有弧上流量的集 称为该网络D的一个流。 弧旁括号中的两个数字 ，第一个数字表示弧容量，第二个数

31、字表示通过该弧的流量，如弧（vs ,v2）上的(5，1)， 图616可行流 满足以下两个约束条件： 1) 各弧最大输送能力约束(容量约束)条件： ，即对每一条弧(vi,vj)的流量要满足流量的可行条件，应小于等于弧的容量 ，并大于等于零。 （2）可行流与最大流 2）节点流量平衡条件：网络中的流量必须满足守恒条件，对收发点来说，发点的总流出量=收点的总流入量； 对中间点v1,v2 ,v3,v4 来说，中间点的总流入量=总流出量。前者是可通过该弧的最大流量为 5，后者是目前通过该弧的流量 1。 最大流： 寻求网络最大流就是找到一个可行流 ，使得网络发点到收点的总流量达到最大。网络最大流问题的线性规

32、划表达式是（3）增广链 设网络D=(V,A,C)中，有一可行流 按每条弧上流量的多少，可将弧分为 4 种类型： 饱和弧 非饱和弧 零流弧 非零流弧 设 是网络D中从vs 到vt 的一条链，沿此方向 上的各弧可分为两类:前向弧：与链的方向一致的弧，前向弧的全体记为 后向弧 : 与链的方向相反的弧，后向弧的全体记为增广链：对于可行流 f， 是一条从 vs 到vt的链，如果 中的每条弧均为非饱和弧，且 中的每条弧均为非零流弧，则称链是关于f 的增广链。 如果 是一条增广链，那么在 上可以增加一定的流量，从而增加可行流的流值。 增广链起的作用有两个：一是目前的可行流是否是最大流？二如果不是最大流，如何

33、通过增广链找到更大的可行流？ 如果将网络D=(V,A,C)的V剖分为两部分 ，使 ，则把从 指向弧 的全体称为分离 的一个截集，记为 ，即 。 （4）截集和截量 截集 中所有弧的容量之和称为该截集的截量，记为 ，有 在 D的所有截集中，称截量最小的截集为最小截集。取 ，则： 截集： 截量： 若取 ， 则： 截集： 截量： 任何一个可行的流量v(f)都不会超过任一截集的截量，即 证明如下：由该结论可知： 在一个容量网络中，最大流的流量小于等于最小截集的截量。 如果存在一可行流 f*和一个截量 使得 则 f* 就是最大流，且 是最小截集。 定理6-7 在网络D=(V,A,C)中，可行流 f * 是

34、最大流的充分必要条件是网络中不存在vs到vt的增广链。最大流最小截集定理：任一容量网络中，最大流的流量等于最小截集的截量。判断一个可行流是否为最大流，有两种途径： 一是能否找出vs到vt的增广链，若能，则说明f不是最大流；否则f就是最大流。 二是看V( f )是否等于最小截量。若等，则f就是最大流，否则就不是最大流。6.4.2 Ford-Fulkerson标号算法 标号法的基本思想是： 从一个可行流 f 出发，由发点vs开始，对网络D中的每个顶点进行标号，如vt得到标号，这时可用反向追踪法在网络中找出一条从vs 到 vt 的由标号点及相应的弧连接而成的增广链。 若无，则 f 为所求的最大流；

35、若有，则在增广链上进行调整，改变流量，得一新的可行流 ，继续寻找相应于该可行流的增广链。 算法的步骤如下： 步骤 1 给出一个初始可行流； 步骤 2 标号、检查过程。 给顶点标号，寻找增广链。凡是标号的点用表示(vi , L(vj)），其中第一个分量表示该标号是从哪个点得到的，以便反向追踪找出增广链 ，第二个分量是为确定的调整量用的。 在标号过程中，每个点属于且仅属于下列集合之一：已标号，但未检查的点集V0；已标号，已检查的点集Vs ；未标号的点集 首先给Vs 标号(0，+ )，因Vs是发点，故括弧中第一个数字记为 0。括弧中第二个数字表示从上一标号点到这个标号点的流量的最大允许调整值。 Vs

36、为发点，不限允许调整量，故为+。 此时 如果V0非空，则反复按以下，进行，否则转第三步。在V0中任选一元素vi ，检查vi 到 中的点vj的弧(vi, vj )，或 中的点vj 到vi 的弧 ，满足以下条件的给vj 标号： （a）对于前向弧(vi, vj ) ，若非饱和，则给点 vj 标以(vi,l(vj) ），其中 同时把 vj 从 中除去，归入V0 。 （b） 对于后向弧(vj,vi) ，若非零流，则给点vj 标以(-vi,l(vj) ） ，其中，同时把 vj 从 中除去，归入V0 。 如果 归入 V0 ，说明已找出f 的增广链 ，则转第三步。 把已标号已检查的点vi归入 Vs 。 若vt

37、得不到标号，说明该网络中不存在增广链，给定的可行流即为最大流。转第四步。 步骤 3 调整过程 则调整之后仍为可行流，流值比原来的可行流流量增大了(0) 。 步骤 4 写出最小截集 ，最大流 的流量 终止计算。 例6-10 试用 FordFulkerson 标号法求图 618所示的网络最大流，括号中，第一个数字是容量，第二个数字是流量。第二步，首先给Vs标以(0，+ )，此时 。 检查点Vs： 弧 ，为饱和弧，所以对V1不标号。弧 ，为非饱和弧，所以给点V2标号， 。其中此时第一步，图中已给出可行流f；检查点V2：弧(V2，V4)， ，为饱和弧，所以对V4不标号。 弧(V1，V2) ， ，为非零

38、流弧，所以给V1标号， ，其中此时检查点V1 ：弧(V1，V3)， ，为非饱和弧，所以对V3 标号。 ，其中弧(V4，V1) ， ，为非零流弧，所以给V4 标号， ，其中此时检查点V3 ：弧(V3，Vt)， ，为非饱和弧，所以对Vt 标号。 ，其中由于Vt已标号，不需再检查 V4 。第三步，利用各点已标号的第一个分量， 从 Vt 反向追踪得增广链 ，如图中粗箭头线所示，其中 ， 由 Vt 标号的第二个分量知 ，于是在 上进行调整： 调整后的可行流如图 6.21所示。对这个新的可行流重新在图中进行标号，寻找新的增广链。图 6.214）再标号 同上述第二步标号，易见，当给V2 标号 后，无法再进行

39、下去，此时， 因此，目前所得到的可行流就是最大流，最小截集为 ，最大流量为 从上例可以看出，最小截集中各弧的容量总和构成最大流问题的瓶颈，在实际问题中，为提高网络中的总流量，必须首先着力改善最小截集中各弧的弧容量。 当沿着可行流 f 的一条的增广链 ，以调整 f ，得到新的可行流 f 时，b( f ) 比 b( f )增加：6.5 最小费用最大流 在上节最大流问题中，每一个可行流在现实生活中，还对应着一定的费用，许多情况下优化目标不但要求流量尽可能的大，还要求费用尽可能的小。 在一个网络中每条弧都有“容量”和“费用”两个限制的条件下，寻求vs到 vt 的最大流，使该最大流在所有最大流中费用达到

40、最小。求解最小费用最大流问题的基本思想是： 在寻求最大流的算法过程中，不但通过增广链使流量逐步增加，还要考虑费用的约束，即每次可行流的调整都使费用增加最小。 1时，费用的增加量是 这个数值反映了增广链的好坏，这个数值越小，这条增广链就越好。 把 称为增广链的费用。 若 f 是流值为v( f )的所有可行流中费用最小者，而 是关于 f 的费用最小的增广链，那么沿去调整可行流 f ，得到可行流 f，新可行流就是流值为v( f ) 的所有可行流中费用最小的可行流。 确定一个最小费用可行流,然后找出最小费用增广链，按照最小费用增广链对可行流进行调整，一直调整下去，直到找不出增广链为止，这样得到的可行流

41、即为最小费用最大流。 为了寻找最小费用增广链，我们以原可行流 f 为基础，构造一个新赋权图D(f )=(V,A(f), W)。D( f )的顶点为原网络D的顶点V ，把D中的每条弧A变为两条方向相反的两条弧，,形成弧集合 A(f)。弧的赋权原则如下：对于弧 ，有对于弧 , 有当然，长度为+的弧可以略去。最小费用最大流的算法：（1）取零流为初始最小费用可行流，记为f(0) 。（2）若第k步得到最小费用可行流f(k) , 则构造一个新赋权图D( f(k) ) ,在D( f(k) )中寻求从vsvt 最短路。 若不存在最短路，则目前的可行流F(k)即为网络D的最小费用最大流；若存在最短路，则在原网络

42、D中得到了相应的最小费用增广链 ，对F(k)进行调整，调整量为（3）调整方法如下： 重复进行上述步骤，直到找不出增广链为止。例6.11 求网络（图6.20）的最小费用最大流，弧旁的数字为图6.20解：（1）取f(0)=0为初始可行流。弧旁的数字为 ,如图6.21所示图6.21 在零流中，每条弧只能做前向弧，因此可得新赋权网络 ,如图6.22所示。图6.22 中最短路见图6-22中的粗线所示，由此找到最小费用增广链，见图6-21中粗线所示。利用最小费用增广链对可行流进行调整，调整后的新流见图6-23。图6.23（2）继续进行可行流的调整： 在图6-23中 是饱和弧，它们只能作后向弧； 既是非0流

43、弧，又非饱和弧，因此它既作前向弧，也作后向弧，其他弧只是0流弧，只能做前向弧。新赋权网络如图6.24所示： 图6.24 图6-24中的最短路见粗线所示，因此找到最小费用增广链，见图6-23中粗线所示。利用最小费用增广链对可行流进行调整，调整后的新流见图6-25。图6.25（3）继续进行可行流的调整： 以图6.25中的可行流为基础，得到新赋权网络，如图6.26。图6.26 图6.26已经找不到 的路，因此图6.25也就没增广链了，即图6-25所示的可行流即为最小费用最大流，流值v(f )5，其费用为31。6.6 网络计划技术网络图的绘制网络图的时间参数计算网络优化 用网络分析的方法编制的计划称为

44、网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及各项工作的相互关系。通过网络分析研究工程费用与工期的相互关系。并找出在编制计划时及计划执行过程中的关键路线。这种方法称为关键路线法（Critical Path Method）简称CPM。1958年，美国海军武器部，在制定研制“北极星”导弹计划时，同样地应用了网络分析方法与网络计划。但它注重于对各项工作安排的评价和审查。这种计划称为计划评审方法（Program Evaluation and

45、 Review Technique）简称为PERT。鉴于这两种方法的差别，他们应用的领域略有差别：CPM主要应用于以往在类似工程中已取得一定经验的承包工程；PERT更多地应用于研究与开发项目。在这两种方法得到应用推广之后，又陆续出现了类似的最低成本和估算计划法、产品分析控制法、人员分配法、物资分配和多种项目计划制定法等等。 虽然方法很多，各自側重的目标有所不同。但它们都应用的是CPM和PERT的基本原理和基本方法。二十世纪六十年代我国开始应用CPM与PERT，并根据其基本原理与计划的表达形式，称它们为网络技术或网络方法，又按照网络计划的主要特点统筹安排，把这些方法称为统筹法。 国内外应用网络计

46、划的实践表明，它具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划。例如：新产品研制开发、大型工程项目、生产技术准备、设备大修等计划。还可以应用在人力、物力、财力等资源的安排，合理组织报表、文件流程等方面。编制网络计划包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节。下面分别讨论这些内容。 为了编制网络计划，首先需绘制网络图。网络图是由节点(点)、弧及权所构成的有向图。即有向的赋权图。 一、网络图的绘制节点表示一个事项（或事件），它是一个或若干个工序的开始或结束，是相邻工序在时间上的分界点。节点用圆圈和里面的数字表示，数字表示节点的编号，如，等。

47、弧表示一个工序，工序是指为了完成工程项目,在工艺技术和组织管理上相对独立的工作或活动。一项工程由若干个工序组成。工序需要一定的人力、物力等资源和时间。弧用箭线“”表示。 权表示为完成某个工序所需要的时间或资源等数据。通常标注在箭线下面或其它合适的位置上。 例1 某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如下表所示。要求编制该项工程的网络计划。 工 序 工序代号 所需时间(天) 紧后工序 产品设计与工艺设计 a60b，c，d，e 外购配套件 b45l 下料、锻件 c10f 工装制造1 d20g，h 木模、铸件 e40h 机械加工1 f18l 工装制造2 g30k 机械加工2 h

48、15l 机械加工3 k25l 装配调试 l35根据上表绘制的网络,如图6.28所示。b12467835a6045 c10d20e40f18g30h15k25l350图6.28在图6.28中，箭线a、b、 l分别代表10个工序。 箭线下面的数字表示为完成该个工序所需的时间（天数）。 结点、分别表示某一或某些工序的开始和结束。 例如，结点表示a 工序的结束和b、c、d、e等工序的开始,即a工序结束后,后四个工序才能开始。 在绘制网络图中，用一条弧和两个结点表示一个确定的工序。例如，表示一个确定的工序b。 工序开始的结点称为箭尾结点,如b工序的； 工序结束的结点称为箭头结点,如b工序的。 称为箭尾事

49、项，称为箭头事项。工序的箭尾事项与箭头事项称为该工序的相关事项。在一张网络图上只能有始点和终点两个结点，分别表示工程的开始和结束，其它结点既表示上一个（或若干个）工序的结束，又表示下一个（或若干个）工序的开始。 为正确反映工程中各个工序的相互关系,在绘制网络图时，应遵循以下规则：(1) 方向、时序与结点编号按照工艺流程的顺序，规定工序从左向右排列。网络图中的各个结点都有一个时间,一般按各个结点的时间顺序编号。为了便于修改编号及调整计划,可以在编号过程中留出一些编号。始点编号可以从1开始，也可以从0开始。网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号(2)紧前工序与

50、紧后工序 例如,在图61中,只有在 a 工序结束以后,b、c、 d、e工序才能开始。a工序是b、c、d、e 等工序的紧前工序,而b、c、d、e等工序则是工序a 的紧后工序。(3)虚工序为了用来表达相邻工序之间的衔接关系，而实际上并不存在而虚设的工序。虚工序不需要人力、物力等资源和时间。只表示某工序必须在另外一个工序结束后才能开始。如图61中，虚工序只表示在 d 工序结束后，h 工序才能开始。(4)相邻两个结点之间只能有一条弧即一个工序用确定的两个相关事项表示，某两个相邻结点只能是一个工序的相关事项。在计算机上计算各个结点和各个工序的时间参数时，相关事项的两个结点只能表示一道工序，否则将造成逻辑

51、上的混乱。 123abc图6.291342abc图6.30如图6.29的画法是错误的图6.30的画法是正确的。(5)网络图中不能有缺口和回路 在网络图中，除始点和终点外，其它各个结点的前后都应有弧相连接，即图中不能有缺口，使网络图从始点经任何路线都可到达终点。否则，将使某些工序失去与其紧后（或紧前）工序应有的联系。1234abcd图6.31 在本章讨论的网络图中不能有回路，即不可能有循环现象。否则，将使组成回路的工序永远不能结束，工程永远不能完工。在如下网络图6.31中出现的情况，显然是错误的。(6) 平行作业为缩短工程的完工时间，在工艺流程和生产组织条件允许的情况下，某些工序可以同时进行，即

52、可采用平行作业的方式。如在图6.28中，工序b、c、d、e 四个工序即可平行作业。在有几个工序平行作业结束后转入下一道工序的情况下，考虑到便于计算网络时间和确定关键路线，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。如在图6.28中,工序d、e 平行作业,这两个工序都结束后,它们的紧后工序h 才可能开始。在工序d、e 中,工序 e 所需的时间(40天)比工序d 所需时间(20天)长，则工序e 直接与工序h 连接，而工序d 则通过虚工序与工序 h 连接。(7) 交叉作业对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许

53、的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。这种方式称为交叉作业。交叉作业可以缩短工程周期。如在图6.28中，将工装制造分为两批，将一个工序分为两个工序d、g，分别与紧后工序h 、k连接。(8) 始点和终点为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个工序平行作业，或在几个工序结束后完工，用一个始点、一个终点表示。若这些工序不能用一个始点或一个终点表示时，可用虚工序把它们与始点或终点连起来。 (9) 网络图的分解与综合根据网络图的不同需要，一个工序所包括的工作内容可以多一些，即工序综合程度较高。也可以在一个工序中所包括的工作内容少一

54、些，即工序综合程度较低。一般情况下，工程总指挥部制定的网络计划是工序综合程度较高的网络图（母网络图）而下一级部门，根据综合程度高的网络图的要求，制定本部门的工序综合程度低的网络图（子网络图）。将母网络分解为若干个子网络，称为网络图的分解。而将若干个子网络综合为一个母网络，则称为网络图的综合。图6.28视为一个母网络。它可以分解为工序a ，工序b、c、d、e、f、g、h、k ，及工序l 三个子网络。工序 a 和工序 l 都可以再分解为综合程度较低的若干个工序。 (10) 网络图的步局在网络图中，尽可能将关键路线布置在中心位置，并尽量将联系紧密的工作布置在相近的位置。为使网络图清楚和便于在图上填写

55、有关的时间数据与其它数据，弧线尽量用水平线或具有一段水平线的折线。网络图也可以附有时间进度；必要时也可以按完成各工序的工作单位布置网络图。 (1)、网络图的绘制步骤确定目标，做好准备工作任务分解和分析绘制网络图二、关键路径与网络图的编制表 6.2 调查项目的任务分解和分析绘制网络图(2) 路线与关键路线在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条通路称为路线。如在图6.28中，共有五条路线，五条路线的组成及所需要的时间如表62所示。 表62路线 路 线 的 组 成 各工序所需的时间之和(天) 1 60+45+35=140 2 60+10+18+35=123 3 60+2

56、0+30+25+35=170 4 60+20+15+35=130 5 60+40+15+35=150 在各条路线上，完成各个工序的时间之和是不完全相等的。其中，完成各个工序需要时间最长的路线称为关键路线，或称为主要矛盾线，在图中用粗线表示。在图6.28中，第三条路线就是条关键路线，组成关键路线的工序称为关键工序。 如果能够缩短关键工序所需的时间，就可以缩短工程的完工时间。而缩短非关键路线上的各个工序所需要的时间，却不能使工程的完工时间提前。即使在一定范围内适当地拖长非关键路线上各个工序所需要的时间，也不至于影响工程的完工时间。编制网络计划的基本思想是： 在一个庞大的网络图中找出关键路线。对关键

57、工序，优先安排资源，挖掘潜力，采取相应措施，尽量压缩时间。而对非关键路线上的各工序，只要在不影响工程完工时间的条件下，抽出适当的人力、物力等资源，用在关键工序上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各关键工序加以有效控制和调度。关键路线是相对的，也是可以变化的。在采取一定的技术组织措施之后，关键路线有可能变为非关键路线。而非关键路线也有可能变为关键路线。网络图的路线以上网络图共有8条路线计算出8条路线的总时间，最长的是16天。关键路线是当某些工作的时间调整后，可能引起关键路线和工期的变化。例如将E的时间缩短为2天，则工期缩短为13天，关键路线将变为13

58、46BEG5651356BFH553（1）作业时间为了编制网络计划和找出关键路线,要计算网络图中各个事项及各个工序的有关时间，称这些有关时间为网络时间。作业时间(Tij )：为完成某一工序所需要的时间称为该工序的作业时间，用Tij表示。三、网络时间参数的计算2) 事项时间： 事项最早时间TE (j) 通常是按箭头事项计算事项最早时间,用TE (j)表示,它等于从始点事项起到本事项最长路线的时间长度。计算事项最早时间是从始点事项开始，自左向右逐个事件向前计算。 假定始点事项的最早时间等于零，即TE (1)= 0。 箭头事项的最早时间等于箭尾事项最早时间加上作业时间。 当同时有两个或若干个箭线指向

59、箭头事项时，选择各工序的箭尾事项最早时间与各自工序作业时间之和的最大值。即： TE (1) = 0 TE (j) = max TE (i) + T(i，j) ( j = 2，n) 式中： TE (j)为箭头事项的最早时间； TE (i) 为箭尾事项的最早时间例如，在网络图6.28中各事项的最早时间为：TE (1) = 0TE (2) = TE (1) + T(1，2) = 0 + 60 = 60TE (3) = TE (2) + T(2，3) = 60 + 10 = 70TE (4) = TE (2) + T(2，4) = 60 + 20 = 80TE (5) = max TE (2) + T

60、(2，5) ，TE (4) + T(4，5) = max 60 + 40 ， 80 + 0 = 100TE (6) = TE (4) + T(4，6) = 80 + 30 = 110 TE (7) = max TE (2) + T(2,7)，TE (3) + T(3,7) ，TE (6) + T(6,7)，TE (5) + T(5,7) = max 60 + 45 ,70 + 18 ,110 + 25 ,100 + 15 = 135TE (8) = TE (7)+T(7，8)=135 + 35 = 170将计算结果计入各事项左下方的方框内，如图6.32所示。 事项最迟时间TL(i) 即箭头事项