信息技术--网络分析与网络计划.docx

《信息技术--网络分析与网络计划.docx》由会员分享，可在线阅读，更多相关《信息技术--网络分析与网络计划.docx（63页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第六章网络分析与网络计划网络分析是图论的一个应用分支 它主要是应用图论的理论与方法来解决具有网络性质的管理决策问题在现实生活和生产实践中，网络分析方法有很广泛的应用如在企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小；在组织生产中，如何使各工序衔接好，使生产任务完成得既快又好；在交通网络中，如何使调运的物资数量多且费用最小等由于网络分析具有图形直观，方法简便，容易掌握的特点，因此得到迅速的发展，且广泛地应用在各个领域，成为经济活动中许多管理决策的优化问题的重要手段网络计划方法是上世纪 50 年代发展起来的计划控制技术，主要包括计划评审技术(programme evaluatio

2、n and review technique，简称 PERT)和关键路径方法(critical path method 或 critical path analysis，简称 CPM、CPA)网络计划方法特别适用于现代管理中的多因素多环节的复杂计划的优化控制，成为管理运筹学的重要应用分支本章在引入有关图的一些基本概念的基础上，介绍最小生成树、网络最短路、最大流、最小费用最大流等网络分析模型及其解法；并对网络计划图（统筹图）的制作、作业时间参数计算、关键线路方法和计划评审技术等网络计划基本技术和方法进行初步介绍第一节 图的基本概念一、图现实世界中有许多具体事物及关系可以用图形来抽象表示 例如，路

3、线关系、工序安排、区位规划等都可以用图来表达我们先通过几个直观的例子，来认识什么是图例 6-1 歌尼斯堡七桥问题哥尼斯堡(Konigsbergs)城域有一个普雷格尔河系，由新河、旧河及其交汇而成的大河组成，它把该城分成了一岛三岸共四块陆地，陆地之间有七座桥连通，如图 6-1(a)所示当时城内居民在散步时热衷于这样一个问题：从某陆地出发，能否走遍七桥且每桥只过一次而最终回到原出发地图 6-1（a）图 6-1（b）欧拉在 1736 年解决了这一问题他用四个点表示四块陆地，用相应两点间的边表示桥，从而建立了该问题的图的模型，见图 6-1(b)于是问题归结为：在这个连通多重图中，能否找出一条回路，过每

4、边一次且仅仅一次欧拉在求解该问题时，把图 6-1（a）所示的实际问题抽象为图 6-1（b）所示图形例 6-2比赛安排问题5 个球队之间安排赛事其中 a 球队分别与 b，c，d 球队有赛事；b 球队还与 c 球队，d 球队还与 e 球队有赛事综上，这 5 个球队之间的比赛关系可用图 6-2(a)来表示，也可用图 6-2(b)来反映图 6-2（a）图 6-2（b）以上两例都忽略了问题的具体细节，而把问题的关键性质或关系抽象为图的形式 例 6-1 中两岸和岛的形状及桥的曲直都被忽略，但陆地间的关联情况却得到保持例 6-2 中把比赛关系抽象为连接关系简单些说，一个图代表了某些对象集合之间的关系，而图论

5、是主要研究这些对象在上述表示法中的许多可能的性质中的某些性质详细些说，一个图指的是一些点以及连接这些点的一些线的总体 这种连接方式可以具有许多特征，而图论本质上就是研究这种特征的 注意，这里所讲的图并不是解析几何与微积分书中常见的图，在那里，点的位置，线的长度和斜率是它的重要部分而在图论中，这些都是不重要的，而重要的只是哪些点之间有线相连有时，连接的先后次序也是重要的二、几个基本概念1无向图一个图G定义为一个有序二元组（V，E），记为：G（V，E）其中，V 是一个有限非空的集合，其元素称为 G 的结点或顶点，简称点，而V 称为 G 的结点集或顶点集，简称点集，一般表示为：V1v，2v，nv而

6、E 称为 G 的边集，表示为：E1e，2e，ne其中e由V中元素对(iv，jv)所构成如果(iv，jv)是无序对，则G称为无向图E中元素e称为G的无向边，一般表示为e(iv，jv)对于给定的图可以作出其几何图例 6-3无向图G（V，E），其中点集V1v，2v，3v，4v，5v，E1e，2e，3e，4e，5e，6e，7e,8e，边与顶点的关联情况由表 6-1 给出表 6-1边与顶点的关联情况e1e2e3e4e5e6e7e8e(iv，jv)(1v,2v)(1v,5v)(2v,4v)(1v,4v)(4v,3v)(5v,4v)(1v,5v)(2v,3v)根据表 6-1，可作其几何图，如图 6-3 所示

7、在作几何图时，仅要求表示出顶点、边以及它们间的关联关系，而对顶点的位置以及边的曲直、长短都没有任何规定图 6-3基于无向图G的结构特点，我们给出下列一些术语：平行边若两条不同的边e与 e具有相同的端点，则称e与 e为G的平行边图 6-3 中2e与7e是平行边，因为它们的端点均为1v、3v简单图若G无平行边，则称图G为简单图完备图图G中任两个顶点间恰有一条边相关联，G为完备图2有向图设顶点的非空集合V（1v，2v，nv），边的集合A（1a，2a，na）如果A中任一条边ija是V的一个有序元素对(iv，jv)(这里，ivjv)，则称A为有向边集，A中元素ija称为有向边或弧，记为ija(iv，jv

8、)其中iv为ija的起点，jv为ija的终点V和A组成了一个有向图，记作D（V，A）例 6-4给有向图D（V，A），其中V（1v，2v，3v，4v），A（1a，2a，7a），边与顶点的关联情况如表 6-2 所给表 6-2边与顶点的关联情况a1a2a3a4a5a6a7a8a(iv，jv)(2v,1v)(1v,2v)(3v,2v)(3v,2v)(2v,4v)(3v,4v)(2v,4v)(1v,3v)根据表 6-2 也可作出有向图，如图 6-4（a）图 6-4(a)图 6-4(b)图 6-4（c）有向图区别于无向图的关键，在于它的边（或弧）是有方向的，图 6-4（a）中边上的箭头所指即边的方向在有向

9、图中(iv，jv)(jv，iv)类似于无向图，有向图G也有下列术语：平行边不同的弧a与 a(iv，jv)的起点与终点都相同 图 6-4（a）中3a、4a是平行边，而1a、2a却不是，1a(2v,1v)；而2a(1v,2v)简单图无平行边的有向图称为简单图完备图图中任两个顶点iv与jv间，恰有两条有向边(iv，jv)及(jv，iv)，则称该有向图D为完备图基本图把有向图D的每条边除去方向就得到一个相应的无向图G，称G为D的基本图例如图 6-4（b）是图 6-4（a）的基本图3同构对于无向图和有向图，如果图G（V，E）和G(V，E)的顶点集合V和V，以及边集 E 和 E之间在保持关联性质的条件下一

10、 一对应，则图G和G同构例如图 6-2(a)、(b)所示的两个图看似不同，其实是同构图由于同构的图被认为是相同的，这就给我们在网络规划中建立网络模型带来许多方便，当我们用几何图来反映和分析实际问题的内在关系而构建网络模型时，点的位置可以任意布置，边的长短曲直也可任意，故而我们尽量设计那种反映问题清晰、简练的几何图4链、路和连通性给定一个无向图G（V，E），其中的一个点与边的交错序列1 iv，1 ie，2iv，2ie，1ikv，1ike，ikv，如果序列中所有ite都满足ite（itv，1itv），（t1，2，k1），则称交错序列为联结1 iv和ikv的链，记为（1 iv，1 ie，2iv，2i

11、e，1ikv，1ike，ikv）或简记为（1 iv，2iv，1ikv，ikv）和（1 ie，2ie，2ike，1ike）当k0，且1 ivikv，则链的起点等于终点，称为闭链闭链中除起点和终点外没有相同的结点和边，则该闭链称为圈当1 ivikv，时称为开链若开链中所有结点均不相同，称为初等链例如图 6-5 中：图 6-51（1v，2v，4v，3v，2v，1v）是闭链，但不是圈；2（1v，2v，3v，1v）是闭链，同时也是圈；3（1v，2v，4v，3v，2v）是开链；4（1v，2v，4v，3v）是初等链对于有向图D（V，A），可以通过其相应的基本图来定义它的链但由于有向图中弧是有方向的，可能出现

12、链中的弧的方向与链的方向不一致的情况 如果链中所有弧的方向与链的方向一致，则称该链为单向路，简称路显然，在有向图中链和路的概念并不一致，而在无向图中两者没有区别如果路的起点和终点相同，则称为回路对于无向图而言闭链和回路概念一致在图 6-4（a）中：1（1a，3a，8a）是链，但不是路；2（8a，3a，1a）是链，同时也是路和回路在D中任意两个结点vi1和vik，从vi1到vik存在路，则称vi1可达vik 若D中任意两结点间存在链，则称D为连通图若D中任意两结点间相互可达，则称D为强连通图对于无向图而言连通图等价于强连通图例如图 6-4（a）所示的是强连通图，因为1v、2v、3v、4v都是相互

13、可达的 如果我们将图中弧8a删去，如图 6-4（c）所示，则成为一般的连通图 因为这时1v、3v不能相互可达5网络一个图连同定义在其边集上的实函数一起称为一个网络网络一般是连通图定义在边集上的实函数称为边的权数记为ijww(iv，jv)它与边(iv，jv)具有一一对应关系，可以用以表达网络上的各种有关性质，如路长、流量、费用等等网络的图解即在每条边旁标上相应的权数若一网络的每条边都是无向边，则称为无向网络，记为N（G，w）或N(V，E)若一网络的每条边都是有向边，则称为有向网络，记为N（D，w）或N(V，A)若一网络中既有无向边，也有有向边，则称为混合网络所谓网络分析，简单地说，即对网络进行定

14、性和定量分析，以便为实现某种优化目标而寻求最优方案这方面的典型问题有：最小树问题，最短路问题，中心问题，重心问题，最大流问题，最小费用最大流问题，最短回路问题，网络计划问题，等等第二节 最小树问题一、树的基本概念1子图、真子图、生成子图设有图G(V，E)和图G(V，E)，如果VV，E E，则称G为G的子图，并记为GG，而G则为G的原图当子图的边集或点集不同于原图时，即GG时，称子图G为G的真子图，记为GG当子图的点集等于原图的点集时，则称子图G为原图G的生成子图或支撑子图在图 6-6 中，（a），（b），（c），（d）均是（a）的子图；（a），（b），（c）是（a）的真子图；（a），（b），（

15、c）均是（a）的生成子图由于（d）比（a）少一个点，所以（d）不是（a）的生成子图图 6-62树无圈且连通的无向图称为树树一般记为T作为树定义还可以有以下几种表述：(1)T连通且无圈或回路；(2)T无圈且有 n1 条边（如果有 n 个结点）；(3)T连通有 n1 条边；(4)T无回路，但不相邻的两个结点之间联以一边，恰得一个圈；(5)T连通，但去掉 T 的任意一条边，T就不连通了；(6)T的任意两个结点之间恰有一条初等链二、最小生成树及其算法1最小生成树如果T是无向图G的生成子图，同时T又是树，则称T是G的生成树或支撑树例如图 6-7（b），（c）是（a）的生成树图 6-7一个网络图可以有多个

16、生成树记 N 的所有生成树的集合为：TkT|k1，2，L设iT（V，kE）是网络图 N（G，w）的一棵生成树，则边集kE中所有边的权数之和称为树kT的权数，记为w（kT）Ekeew)(若*TT，使w（*T）TTkminw（kT）则称*T为网络N的一棵最小生成树，简称最小树2最小树的求法定理 8-1如果把网络N的点集V分割成两个不相交的非空集合S和_S，则联结S和_S的最小边必包含于 N 的最小树内根据定理 8-1，可以给出求最小树的两种方法，这就是避圈法与破圈法，分述如下：(1)避圈法其计算步骤如下：从网络N中任选一点iv，令Siv，_SViv；从联结S与_S的边中选取最小边，不妨设为(iv，

17、jv)，则它必包含于最小树内；令SjvS，_Sjv_S；若_S，则停止，已选出的诸边即给出最小树；否则返例例 6-56-5试求图 6-8 所示网络的最小树，各边旁边的数字为各边的权图 6-8解解由题意可知这是一个最小树问题先按原图画出 7 个点，令S1，_S2，3，4，5，6，7由于联结S与_S的边共有三条，其中最短边为(1，2)故用线把点 1 和 2 连结起来，令S1，2，_S3，4，5，6，7，如图 6-8(a)所示，重复上述步骤，直到 7 个点全都连通为止具体求解过程如图 6-8（a）到图 6-8（f）所示，其中图 6-8（f）)即给出本例的最小树*T，w(*T)13图 6-8（a）（b

18、）图 6-8（c）（f）(2)破圈法用破圈法求最小树时，先从图中任取一圈，去掉该圈的一条最大边，然后重复这一步骤，直到无圈为止例 6-6图 6-9 所示的一赋权连通图是某一具有 9 个居民点的交通网络图，其中边权表示该段道路的长，现欲沿小区道路架设一联络各个居民点的闭路电视系统，求可使闭路电视系统所架线路总长最短的方案图 6-9解这是一个求网络最小树的问题可利用破圈法求解过程如图 6-9（ai）所示图 6-9（ai）图 6-9（i）所示的是网络最小树*T按图安排闭路电视系统可使所架线路总长最短，w(*T)19第三节 最短路径问题在生产实践，运输管理和工程建设的很多活动中，诸如各种工艺路线的安排

19、、厂区及货场的布局、管道线网的铺设及设备的更新等等问题，都与寻找一个“图的最短路径”问题(shortest-path problem)密切相关，它是网络规划中的一个最基本的问题一、基本概念给定一个赋权有向图D(V，A)，对每一条弧ija(iv，jv)，相应地有权w（ija）ijw，又有两点sv、tvV，设p是D中从sv到tv的一条路，路p的权是p中所有弧的权之和，记为w(p)最短路问题就是求从sv到tv的路中一条权最小的路*p：w(*p)pmin w(p)二、最短路问题的算法1Dijkstra 算法(Dijkstra algorithm)该算法是由 Dijkstra 于 1959 年提出来，用

20、于求解指定两点之间的最短路，或从指定点到其余各点的最短路，目前被认为是求解最短路问题的最好方法 算法的基本思路基于以下原理.定理 6-2若p是从sv到tv的最短路，iv是p中的一个点，那么从sv沿p到iv的路必定是从sv到iv的最短路引理若p是从sv到tv的最短路，iv是p中的一个点，则从sv到iv的最短路必定包含于p之内根据定理 6-2 及引理，我们可以从vs出发试探所有可能到达vt的下一个结点vi，取距离最短的一个弧（sv，iv），则必然包含于从sv到tv的最短路中；从iv开始对没有试探过的结点进行进一步的试探、推进，直至tv，最终可以找出从sv到tv的最短路Dijstra 算法采用（双标

21、号法）T 标号与 P 标号，来实现这一试探、推进过程T 标号为试探性标号；P 为永久性标号给iv点一个 P 标号时，表示从sv到iv点的最短路权，一旦iv点得到 P 标号则意味着从sv到iv点的最短距离已经确定，标号不再改变给iv点一个 T 标号时，表示从sv到iv点的估计最短路权的上界，这是一种临时标号凡没有得到 P 标号的点都有 T 标号算法每一步都把某一点的 T 标号改为 P 标号，当终点tv得到 P 标号时，全部计算结束Dijstra 算法基本步骤：(1)给sv以 P 标号，P(sv)0，其余各点均给 T 号，T(iv)(2)若iv点为刚得到 P 标号的点，考虑jv，(iv，jv)A

22、且jv为 T 标号 对jv的 T 标号进行如下的更改：T(jv)minT(jv)，P(iv)ijw(6-1)(3)比较所有具有 T 标号的点，把最小者iv改为 P 标号，即：P(iv)min T(iv)(6-2)当存在两个以上最小者时，可同时改为 P 标号(4)若全部点均为 P 标号，则停止计算否则用iv代替iv并转至步骤（2）例 6-7用 Dijkstra 算法求图 6-10 中从1v到7v的最短距离，以及相应的路线图 6-10解（1）首先给1v以 P 标号，P（1v）0，给其余所有点 T 标号，T（vi）（i=2，3，7）（2）考察1v，由于（1v，2v），（1v，3v），（1v，4v）A

23、，且2v、3v、4v是 T 标号，所以修改 T 标号为：T（2v）min T（2v），P（1v）12wmin，022T（3v）min T（3v），P（1v）13wmin，055T（4v）min T（4v），P（1v）14wmin，033在所有 T 标号中，T(2v)2 最小，于是令 P(2v)2将结果记在图 6-10（a）上：P 标号以（）形式标在结点旁边，T 标号以不带（）的数字标在结点旁边，图中没有标号的结点均代表 T（iv）(3)考察2v因为（2v，3v），（2v，6v）A，且3v、6v是 T 标号，故3v、6v新的 T 标号为：T（3v）min T（3v），P（2v）23wmin，22

24、4T（6v）min T（6v），P（2v）26wmin，279在所有 T 标号中，T(4v)3 最小，故令 P(4v)3图上标号如图 6-10（b）(4)考察4v，因（4v，5v）A，T（5v）min T（5v），P（4v）45wmin，358在所有 T 标号中，T(3v)4 最小，令 P(3v)4图上标号如图 6-10（c）(5)考察3v，（3v，5v），（3v，6v）A，T（5v）min T（5v），P（3v）35wmin，437T（6v）min T（6v），P（3v）36wmin，459在所有 T 标号中，T(5v)7 最小，令 P(5v)7图上标号如图 6-10（d）(6)考察5v，（

25、5v，6v），（5v，7v）A，T（6v）min T（6v），P（5v）56wmin，718T（7v）min T（7v），P（6v）57wmin，7714在所有 T 标号中，T(6v)8 最小，故令 P(6v)8图上标号如图 6-10（e）(7)考察6v，（6v，7v）A，T（7v）min T（7v），P（6v）67wmin 14，8513令 P(7v)13，图上标号如图 6-10（f）所有点都标上 P 标号，计算结束从1v到7v的最短路径，可从7v开始根据永久性标号数值回溯得到最短路径是：1v2v3v4v5v6v7v，路长 13同时得到1v到其余各点的最短路，即各点的永久性标号 P（vi）D

26、ijkstra 算法只适用于所有ijw0 的情形，当赋权有向图中存在负权时，则算法失效图 6-10（a）（b）（c）（d）（e）（f）2逐次逼近算法为方便起见，不妨设从任一点iv到任一点jv都有一条弧，如果在D中，不存在弧(iv，jv)，则添加虚设弧(iv，jv)，令ijw从起点sv到任意点jv的最短路可以视为一个两阶段过程，如图 6-11 所示：图 6-11(1)从sv出发，沿着一条路走k1 步到某点iv，其最短距离表示为)1(kd(sv，iv)(2)再从iv沿(iv，jv)到jv，其最短距离就是弧(iv，jv)上的权ijw所以，从sv到jv的最短距离必满足如下递推公式：）（1d(sv，jv

27、)sjw（j1，2，n）（6-3）)(kd(sv，jv)imin)1(kd(sv，iv)ijw（6-4）式（6-3）是任意两点间的一步距离，由前面假设可知其存在，这可以作为初始条件式（6-4）是任意两点间的 k 步距离，这是一个递推公式利用初始条件和递推公式通过逐步迭代就可以确定网络D中任意点之间经k步到达的最短距离并得到与之相应的路线下面以实例来说明迭代过程例例 6 6-8-8用逐次逼近算法求例 6-6 图 6-10 中从1v到各点的最短距离解根据初始条件可知）（1d(1v，1v)0）（1d(1v，2v)2）（1d(1v，3v)5）（1d(1v，4v)3）（1d(1v，5v)）（1d(1v，

28、6v)）（1d(1v，7v)；初始条件仅仅表达了1v从出发到jv的一步到达的距离，在有向简单网络中即为从1v到各点的最短距离1v到各点的k步距离由公式（6-4）递推得出为方便、直观可列表计算如表 6-3：表 6-31v到各点的k步距离ijw)(kd(sv，jv)imin)1(kd(sv，iv)ijw1v2v3v4v5v6v7vk=1k=2k=3k=4k=5k=61v02 2530000002v0272 2222223v013554 444444v053333335v01787 77776v0598 8887v014131313jviv表的左半部是一个 nn 的关于结点两两之间的一步距离矩阵，由

29、式（6-3）可知，iv到jv的一步距离就是弧（iv，jv）上的权ijw一步距离矩阵中 0 元素表示原地踏一步，没有填写数字的空格是的省略表右半部是公式（6-4）的计算结果k=h 时，第 h+n 列数据表示1v到各点的 h 步最短距离譬如 k=3为第 列，表示1v经 3 步到达各点的最短距离计算过程如下：（1）当 k=1 时）（1d(1v，jv)jw1这是初始条件，表示从1v出发到各点的一步距离，将其依次列于第 列由此推算）（2d(1v，jv)（2）k=2 时）（2d(1v，jv)imin）（1d(1v，iv)ijw即用表中第 列数字与表左边一步距离矩阵中第j列相应数字相加取小，得到从1v出发到

30、各点的二步距离：（00）（2）（5）（2d(1v，1v)min（3）0（）（）（）（20）（02）（5）（2d(1v，2v)min（3）2（）（）（）同理：）（2d(1v，3v)4）（2d(1v，4v)3）（2d(1v，5v)8）（2d(1v，6v)）（2d(1v，7v)得：024）（2d(1v，jv)38将其填入表 6-3 第 列（3）重复上述步骤得到）（3d(1v，jv)、)4(d(1v，jv)、)5(d(1v，jv)、)6(d(1v，jv)；分别填入表 6-3 第、列（4）当 k=6 时，发现)6(d(1v，jv)5(d(1v，jv)，说明对于整个有向图 D 而言，继续增加步数已不起作用

31、，即已得到从1v到各点的最短距离，即表中 或 列数字：1v 1v0；原地一步1v 2v2；一步到达1v 3v4；二步到达1v 4v3；一步到达1v 5v7；三步到达1v 6v8；四步到达1v 7v13；五步到达从表 6-3 中还可以用回溯方法推知1v到各点最短距离的相应最短路线，以1v到7v为例：由第列7v行可知，1v到7v经 5 步到达，最短距离 13回溯 13 的来源：d（1v，7v）=13因d（1v，7v）列6v行 列6v行 d（1v，6v）67w8513故记下（6v，7v）因d（1v，6v）列5v行 列5v行 d（1v，5v）56w718故记下（5v，6v）.因d（1v，5v）列3v行

32、 列3v行 d（1v，3v）35w437故记下（3v，5v）因d（1v，3v）列2v行 列2v行 d（1v，2v）23w224故记下（2v，3v）因d（1v，2v）12w022，记下（1v，2v）得到最短路径：1v 2v 3v 5v 6v 7v当网络图存在负权时，Dijkstra 算法失效，必须采取逐次逼近算法来求解最短路例 6-9试求网络图 6-12 中1v到各点的距离图 6-12解初始条件：）（1d(1v，1v)0）（1d(1v，2v)1）（1d(1v，3v)）（1d(1v，4v)2）（1d(1v，5v)）（1d(1v，6v)计算结果如表 6-4 所示：表 6-41v到各点的距离ijw)(

33、kd(sv，jv)1v2v3v4v5v6vk=1k=2k=3k=4k=51v012000002v034111-1-13v-205141114v40-3222225v330-1-1-1-16v20求得1v到各点的最短距离：）（1d(1v，1v)0；原地一步)4(d(1v，2v)-1；四步到达1v4v5v3v2v）（3d(1v，3v)1；三步到达1v4v5v3v）（1d(1v，4v)2；一步到达）（2d(1v，3v)-1；二步到达1v4v5v）（kd(1v，6v)；无法到达vjvi逐次逼近算法，因其类似于矩阵乘法，在有些书籍表述为距离矩阵摹乘法，它们的实质一致这种算法在 n 个结点的网络图中，至多

34、经过 n-1 次迭代必然收敛但前提条件是图中不含有总权小于 0 的回路，否则最短路权没有下界第四节最大流问题网络流(network flow)是一类普遍存在的现象例如在交通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流；等等在 20 世纪 50 年代 Ford 和 Fulkerson 建立的“网络流理论”是网络应用的重要组成部分网络最大流问题(max-flow problem)尤为重要这是因为绝大部分网络流研究，旨在寻求在一定条件下使网络流达到最大的方法如图 6-13 是输油管道网，sv为起点，tv是终点，1v，2v，3v，4v为中转站，弧上的数表示该

35、管道的最大输油能力，问应如何安排各管道输油量，才能使从sv到tv的总输油量最大?图 6-13一、基本概念和基本定理1网络流所谓网络流，是指在一定的条件下流过一个网络的某种流在各边上的流量的集合表达为Ff(iv，jv)|(iv，jv)A所谓一定条件，一般是指如下规定：(1)网络有一个始点sv和一个终点tv，始点是流的源，终点是流的汇；(2)流具有一定的方向，流经各弧的流，其方向就是相应弧的方向；(3)对每一弧(iv，jv)A，都赋予一个容量r(iv，jv)0，简记为ijr，表示容许通过该弧的最大流量 并称f(iv，jv)为通过弧(iv，jv)流，简记为ijf凡做出上述规定的网络都可称为容量网络，

36、记为N（V，A，r）图 6-13 所示的就是一个容量网络图中每条弧上的数对为(ijr，ijf)，标明了弧的容量以及流经该弧的流量2可行流和最大流可行流是指满足容量限制条件和平衡条件的流(1)容量限制条件：对于任一弧(iv，jv)A，都有 0ijf ijr，即任何弧上的流量不能超过弧的容量(2)平衡条件：对于任一中间点iv，都有Avjvi),(ijfAvivk),(kif即每个中间点的流出量必须等于流入量，其净流量为 0对于始点和终点，有Avivs),(sifAvtvi),(itf即始点流出量等于终点的流入量，这个流量即是可行流F的流量，记为v（f）所谓最大流问题，就是在可行流恒存在的前提下，满

37、足maxv(f)fiss.t.Avjvi),(ijfAvivk),(kif0is、t0ijf ijr；fit这是一个特殊的线性规划问题，可用单纯形法求解但用图形方法求解更为直观和简单3增广链如果是网络中联结始点和终点的一条链，且链的方向从sv到tv，则与链方向一致的弧称为前向弧，用来表示前向弧集合；与链方向相反的弧称为后向弧，用来表示后向弧集合如图 6-13 中(sv，2v)，(1v，4v)，(3v，tv)(1v，2v)，(3v，4v)设f是一个可行流，是一条从sv到tv的链，若满足下列条件，则是可行流的一条增广链：（1）在弧(iv，jv)上，0ijfijr；（2）在弧(iv，jv)上，0ij

38、f ijr这就意味着在增广链上每一个前向弧的流量都没有达到最大容量（即不饱和前向弧）,而每一个后向弧的流量均不为 0（即非零后向弧）如图 6-13 中链sv2v1v4v3vtv、sv1v4v3vtv、sv1v4vtv都是增广链可以指出，沿增广链调整各弧的流量可以使网络流量v（f）增大，而寻求网络最大流的方法正是以增广链为基础的4截集与截量在一个网络N(V，A)中，若把点集 V 剖分成不相交的两个非空集合S和S，使svS，tvS，且S中各点不须经由S中的点而均连通，S中各点也不须经由S中的点而均连通，则把始点在S中而终点在S中的一切弧所构成的集合，称为一个分离sv和tv的截集，记为(S，S)截集

39、实质上是网络N从sv到tv通路的横截面表达，它反映了网络从sv到tv的必经之路一个网络可以有多个截集，表 6-5 反映了图 6-13 网络的截集集合表 6-5图 6-13 网络的截集集合SivSjv截集(S，S)=(iv，jv)截量r(S，S)s1,2,3,4,t(s,1),(s,2)14s,12,3,4,t(s,2),(1,2),(1,3),(1,4)15s,21,3,4,t(s,1),(2,4)14s,1,23,4,t(1,3),(1,4),(2,4)12s,1,2,32,4,t(s,2),(1,2),(1,4),(3,4),(3,t)19s,2,41,3,t(s,1),(4,t)16s,

40、1,2,34,t(1,4),(2,4),(3,4),(3,t)16s,1,2,43,t(1,3),(4,t)11s,1,2,3,4t(3,t),(4,t)13给定一截集(S，S)，其中所有弧的容量之和称为这个截集的截量，记为r(S，S)ijr|（iv，jv）(S，S)一个网络可以有多个截集和截量，其中截量最小的截集称为最小截集，记为(*S，*S)，其截量称为最小截量(min-cut)，记为r(*S，*S)图 6-13 的最小截量由表 6-5 看出为 11，最小截集为(*S，*S)(1,3),(4,t)二、基本原理为了介绍一种寻求网络最大流的标号法，这里将阐述其原理定理6-3（流量截量定理）在网

41、络N=(V，A，r)中，设f为一可行流，(S，S)是任一截集，则v（f）r(S，S)定理6-3表明，网络的任一可行流的流量恒不超过任一截集的截量因此，网络的最大流量也不会超过最小截量定理 6-4（最大流量最小截量定理）网络中从vs到vt的最大流的流量等于分离vs和vt的最小截集的截量即，v（*f）r(*S，*S)定理 6-4 实际上是定理 6-3 的推论定理 6-5（最大流的充要条件）设*f是网络N(V，A，r)的一个可行流，则*f为最大流的充要条件是：网络N中不存在关于*f的增广链(*f)定理6-6（增广链调整法）设fijf是N(V，A，r)的一个可行流，是关于f 的一条增广链令ijrijf

42、当1min当ijrijf当（6-5）2min当min（1，2）构造一个新的可行流，令ijf当（iv，jv）ijfijf当（iv，jv）（6-6）ijf当（iv，jv）则f(ijf)也是N的一个可行流，其流量为v（ijf）v（ijf）（6-7）定理 6-4 表明：只要网络中还存在关于可行流f的增广链，则f就非最大流，起码其流量还能增大这样就给出了一种沿着增广链上的各弧去调整流量，从而得到一个流量增大的新可行流f的方法，故称之为增广链调整法三、寻求网络最大流的标号法这种标号法由福特(Ford)和富尔克逊(Fulkerson)于 1956 年提出，故称为福特一富尔克逊标号法(Ford-Fulkers

43、on algorithm)1基本算法思想：该法从某一可行流f出发，按一定规则找出一条增广链(f)，并按定理 8-6 的方法调整f，得到一个流量增大的新可行流f 对f重复上述做法直到找不出增广链为止，这时就得到一个最大流，同时还得到一个最小截集2算法步骤（1）给出一个初始可行流f初始可行流可以是零流或非零流；（2）标号、检查过程：给顶点标号，标号用iv，L(jv)表示，其中第一个分量表示该标号是从哪个点得到的，用以反向追踪找出增广链，第二个分量是为确定的调整量用的点sv标号(0，)，则sv已标号待检查；取一个已标号待检查的点iv，所谓检查是对所有与iv相邻而未标号的点jv依次执行下述 a）、b）

44、两种考察：a）若联结iv与jv的弧(iv，jv)为前向弧，则当该弧上的流量小于容量，即ijfijr时给jv标号iv，L(jv)，其中 L(jv)min（L(iv)，ijr一ijf）这里 L(jv)表示弧(iv，jv)上流量的最大可调整量而当弧(iv，jv)上的ijfijr时，弧(iv，jv)是饱和前向弧，则不给jv标号b）若关联iv与jv弧(jv，iv)为后向弧，则当该弧上的流量大于零，即jif0 时给jv标号-iv，L(jv)，其中 L(jv)minL(iv)，jif而当jif0时不给jv标号当所有iv与相邻而未标号的点jv都完成了 a）、b）两种考察后，给iv打，表示对它的检查完毕重复，如

45、果终点tv得到标号，则可以从tv沿标号点回溯到第一个标号，从而找出一条从sv到tv的增广链，转至；如果所有标号点均已打，而vt又未得标号这说明不存在关于当前可行流的增广链，由定理 6-3 可知当前可行流即最大流，算出流量，计算停止取增广链的流量调整量L（tv），对增广链上的流量进行调整，对增广链上的前向弧，令ijfijf对增广链上的后向弧，令jifjif非增广链上的弧流量不变删除原有所有标号，返回例 6-10用 Ford-Fulkerson 标号法求图 6-14 所示网络的最大流图6-14解第一步：图中给出了网络的初始可行流；第二步：首先给vs以标号(0，)，此时待查点是sv，相邻而未标号的点

46、有1v、2v检查sv：弧(sv，1v)，1sf1sr3，为饱和前向弧，所以不对1v标号弧(sv，2v)，2sf2sr，为非饱和前向弧，所以给点2v标号sv，L(2v)其中 L(2v)min L(sv)，2sr2sfmin，51 4.sv检查完成，对其打此时2v有了标号成为待查点，相邻而未标号的点有1v、4v，如图 6-15（a）所示检查点2v：弧(2v，4v)，24f24r，为饱和前向弧，所以不对4v标号.弧(1v，2v)，12f0，为非零流后向弧，所以给1v标号2v，L(1v)，其中 L(1v)min L(2v)，f12min4，1 1.2v检查完成，对其打此时完成检查的点有sv、2v，1v

47、因有了标号成为待查点，相邻而未标号的点有3v、4v如图 6-15（b）所示检查点1v：弧(1v，3v)，13f13r，为不饱和前向弧，所以给3v标号1v，L(3v)，其中 L(3v)min L(1v)，13r13fmin1，43 1.弧(1v，4v)，14f14r，为不饱和后向弧，所以给4v标号-1v，L(4v)，其中 L(4v)min L(1v)，14r14fmin1，21 1.1v检查完成，对其打此时完成检查的点有sv、2v、1v，3v和4v因有了标号成为待查点，相邻而未标号的点有tv如图 6-15（c）所示.检查点3v：弧(3v，tv)，tf4tr4，为不饱和前向弧，所以给tv标号3v，

48、L(tv),其中 L(tv)min L(3v)，tr4tf4min1，53 1.3v检查完成，对其打由于tv已得到标号，已经可以得到一条增广链，不需再检查4v（如果检查4v而不检查3v可以得到另一条增广链，可自行验证）,如图 6-15（d）所示图 6-15（a）、（b）、（c）、（d）第三步：利用各点已标号的第一个分量，从tv反向追踪得增广链sv，2v，1v，3v，tv，如图 6-15（d）中粗箭头线所示其中前向弧(sv，2v)、(1v，3v)、(3v，tv),后向弧(1v，2v).由tv标号的第二个分量知1，于是在已知增广链上进行调整：2sf2sf112（sv，2v）13f13f314（1v

49、，3v）3tftf3314（3v，tv）12f12f110（1v，2v）ijfijf（iv，jv）调整后的可行流如图 6-16 所示 对这个新的可行流重新在图中进行标号，寻找新的增广链图 6-16第四步：再标号给sv以标号(0，)，检查sv：弧(sv，1v)为饱和前向弧，1v不标号弧(sv，2v)为非饱和前向弧，2v标号sv，L(2v)，L(2v)3.检查2v：弧(1v，2v)为零流后向弧，1v不标号弧(2v，4v)为饱和前向弧，4v不标号此时已标号的点均已打，而tv又未得标号，由算法步骤可知网络中不存在增广链，目前的可行流就是最大流第五步：确定最小截集和最大流量此时已标号且打的点构成*S集，

50、而未标号的点构成*S集，最小截集为(S，S)如图 6-16 所示,*Ssv，2v,*S（1v，3v，4v，tv）最小截量r(*S，*S)最大流量*f1sf24f5.第五节 最小费用流问题在实践中，人们考虑网络流问题不仅仅考虑流量，还必须考虑流的费用例如，在运输网络中，从发点sv到收点tv所经过的路程，往往因为交通工具不同或道路本身结构不同而产生各段路程交通费用不同，这时问题就变成了不仅要求sv到tv的一定运输量，而且要求这种运输方案的总费用最小这类问题就属于本节要介绍的最小费用流问题(min-cost-flow)一、最小费用流算法A DN S在给定网络N=(V，A，r)中，对每条弧(iv,jv