网络分析与网络计划的概念

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

2、nd 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无向图一个图定义为一个有序二元组（，），记为：（，）其中，V是一个有限非空的集合，其元素称为G的结点或顶点，简称点，而V称为G的结点集或顶点集，简称点集，一般表示为：，而E称为G的边集，表示为：，其中由中元素对(，)所构成如果(，)是无序对，则称为无向图中元素称为的无向边，一般表示为(，)对于

6、给定的图可以作出其几何图例6-3 无向图（，），其中点集，,，边与顶点的关联情况由表6-1给出表6-1 边与顶点的关联情况(，)(,)(,)(,)(,)(,)(,)(,)(,)根据表6-1，可作其几何图，如图6-3所示在作几何图时，仅要求表示出顶点、边以及它们间的关联关系，而对顶点的位置以及边的曲直、长短都没有任何规定图6-3基于无向图的结构特点，我们给出下列一些术语：平行边若两条不同的边与具有相同的端点，则称与为的平行边图6-3中与是平行边，因为它们的端点均为、简单图若无平行边，则称图为简单图完备图图中任两个顶点间恰有一条边相关联，为完备图2有向图设顶点的非空集合（，），边的集合（，）如果中

7、任一条边是的一个有序元素对(，)(这里，)，则称为有向边集，中元素称为有向边或弧，记为(，)其中为的起点，为的终点和组成了一个有向图，记作（，）例6-4 给有向图（，），其中（，），（，），边与顶点的关联情况如表6-2所给表6-2 边与顶点的关联情况(，)(,)(,)(,)(,)(,)(,)(,)(,)根据表6-2也可作出有向图，如图6-4（a）图6-4(a)图6-4(b)图6-4（c）有向图区别于无向图的关键，在于它的边（或弧）是有方向的，图6-4（a）中边上的箭头所指即边的方向在有向图中(，)(，)类似于无向图，有向图也有下列术语：平行边不同的弧与(，)的起点与终点都相同图6-4（a）中、

8、是平行边，而、却不是，(,)；而(,)简单图无平行边的有向图称为简单图完备图图中任两个顶点与间，恰有两条有向边(，)及(，)，则称该有向图为完备图基本图把有向图的每条边除去方向就得到一个相应的无向图，称为的基本图例如图6-4（b）是图6-4（a）的基本图3同构对于无向图和有向图，如果图（，）和(，)的顶点集合和，以及边集E和E之间在保持关联性质的条件下一 一对应，则图和同构例如图6-2(a)、(b)所示的两个图看似不同，其实是同构图由于同构的图被认为是相同的，这就给我们在网络规划中建立网络模型带来许多方便，当我们用几何图来反映和分析实际问题的内在关系而构建网络模型时，点的位置可以任意布置，边的

9、长短曲直也可任意，故而我们尽量设计那种反映问题清晰、简练的几何图4链、路和连通性给定一个无向图（，），其中的一个点与边的交错序列，如果序列中所有都满足（，），（1，2，1），则称交错序列为联结和的链，记为（，）或简记为（，）和（，）当0，且，则链的起点等于终点，称为闭链闭链中除起点和终点外没有相同的结点和边，则该闭链称为圈当，时称为开链若开链中所有结点均不相同，称为初等链例如图6-5中：图6-51（，）是闭链，但不是圈；2（，）是闭链，同时也是圈； 3（，）是开链；4（，）是初等链对于有向图（，），可以通过其相应的基本图来定义它的链但由于有向图中弧是有方向的，可能出现链中的弧的方向与链的方向不

10、一致的情况如果链中所有弧的方向与链的方向一致，则称该链为单向路，简称路显然，在有向图中链和路的概念并不一致，而在无向图中两者没有区别如果路的起点和终点相同，则称为回路对于无向图而言闭链和回路概念一致在图6-4（a）中：1（，）是链，但不是路；2（，）是链，同时也是路和回路在中任意两个结点i1和ik，从i1到ik存在路，则称i1可达ik若中任意两结点间存在链，则称为连通图若中任意两结点间相互可达，则称为强连通图对于无向图而言连通图等价于强连通图例如图6-4（a）所示的是强连通图，因为、都是相互可达的如果我们将图中弧删去，如图6-4（c）所示，则成为一般的连通图因为这时、不能相互可达5网络一个图连

11、同定义在其边集上的实函数一起称为一个网络网络一般是连通图定义在边集上的实函数称为边的权数记为(，)它与边(，)具有一一对应关系，可以用以表达网络上的各种有关性质，如路长、流量、费用等等网络的图解即在每条边旁标上相应的权数若一网络的每条边都是无向边，则称为无向网络，记为（，）或(，)若一网络的每条边都是有向边，则称为有向网络，记为（，）或(，)若一网络中既有无向边，也有有向边，则称为混合网络所谓网络分析，简单地说，即对网络进行定性和定量分析，以便为实现某种优化目标而寻求最优方案这方面的典型问题有：最小树问题，最短路问题，中心问题，重心问题，最大流问题，最小费用最大流问题，最短回路问题，网络计划问

12、题，等等第二节 最小树问题一、树的基本概念1子图、真子图、生成子图设有图(，)和图(，)，如果，则称为的子图，并记为，而则为的原图当子图的边集或点集不同于原图时，即时，称子图为的真子图，记为当子图的点集等于原图的点集时，则称子图为原图的生成子图或支撑子图在图6-6中，（a），（b），（c），（d）均是（a）的子图；（a），（b），（c）是（a）的真子图；（a），（b），（c）均是（a）的生成子图由于（d）比（a）少一个点，所以（d）不是（a）的生成子图图6-62树无圈且连通的无向图称为树树一般记为作为树定义还可以有以下几种表述：(1)连通且无圈或回路；(2)无圈且有n1条边（如果有n个结点）；

13、(3)连通有n1条边；(4)无回路，但不相邻的两个结点之间联以一边，恰得一个圈；(5)连通，但去掉T的任意一条边，就不连通了；(6)的任意两个结点之间恰有一条初等链二、最小生成树及其算法1最小生成树如果是无向图的生成子图，同时又是树，则称是的生成树或支撑树例如图6-7（b），（c）是（a）的生成树图6-7一个网络图可以有多个生成树记N的所有生成树的集合为： | 1，2，L 设（，）是网络图N（，）的一棵生成树，则边集中所有边的权数之和称为树的权数，记为（）若，使（）（）则称为网络的一棵最小生成树，简称最小树2最小树的求法定理8-1如果把网络的点集分割成两个不相交的非空集合和，则联结和的最小边必

14、包含于N的最小树内根据定理8-1，可以给出求最小树的两种方法，这就是避圈法与破圈法，分述如下：(1)避圈法其计算步骤如下：从网络中任选一点，令，；从联结与的边中选取最小边，不妨设为(，)，则它必包含于最小树内；令Þ，Þ；若，则停止，已选出的诸边即给出最小树；否则返例6-5试求图6-8所示网络的最小树，各边旁边的数字为各边的权图6-8解由题意可知这是一个最小树问题先按原图画出7个点，令1，2，3，4，5，6，7由于联结与的边共有三条，其中最短边为(1，2)故用线把点1和2连结起来，令1，2，3，4，5，6，7，如图6-8(a)所示，重复上述步骤，直到7个点全都连通为止具体求解

15、过程如图6-8（a）到图6-8（f）所示，其中图6-8（f）)即给出本例的最小树，()13图6-8（a）（b）图6-8（c）（f）(2)破圈法用破圈法求最小树时，先从图中任取一圈，去掉该圈的一条最大边，然后重复这一步骤，直到无圈为止例6-6 图6-9所示的一赋权连通图是某一具有9个居民点的交通网络图，其中边权表示该段道路的长，现欲沿小区道路架设一联络各个居民点的闭路电视系统，求可使闭路电视系统所架线路总长最短的方案图6-9解 这是一个求网络最小树的问题可利用破圈法求解过程如图6-9（ai）所示图6-9（ai）图6-9（i）所示的是网络最小树按图安排闭路电视系统可使所架线路总长最短，()19第三

16、节 最短路径问题在生产实践，运输管理和工程建设的很多活动中，诸如各种工艺路线的安排、厂区及货场的布局、管道线网的铺设及设备的更新等等问题，都与寻找一个“图的最短路径”问题(shortest-path problem )密切相关，它是网络规划中的一个最基本的问题一、基本概念给定一个赋权有向图(，)，对每一条弧(，)，相应地有权（），又有两点、V，设是中从到的一条路，路的权是中所有弧的权之和，记为()最短路问题就是求从到的路中一条权最小的路：()()二、最短路问题的算法1Dijkstra算法(Dijkstra algorithm)该算法是由Dijkstra于1959年提出来，用于求解指定两点之间的

17、最短路，或从指定点到其余各点的最短路，目前被认为是求解最短路问题的最好方法算法的基本思路基于以下原理.定理6-2若是从到的最短路，是中的一个点，那么从沿到的路必定是从到的最短路引理若是从到的最短路，是中的一个点，则从到的最短路必定包含于之内根据定理6-2及引理，我们可以从s出发试探所有可能到达t的下一个结点i，取距离最短的一个弧（，），则必然包含于从到的最短路中；从开始对没有试探过的结点进行进一步的试探、推进，直至，最终可以找出从到的最短路Dijstra算法采用（双标号法）T标号与P标号，来实现这一试探、推进过程T标号为试探性标号；P为永久性标号给点一个P标号时，表示从到点的最短路权，一旦点得

18、到P标号则意味着从到点的最短距离已经确定，标号不再改变给点一个T标号时，表示从到点的估计最短路权的上界，这是一种临时标号凡没有得到P标号的点都有T标号算法每一步都把某一点的T标号改为P标号，当终点得到P标号时，全部计算结束Dijstra算法基本步骤：(1)给以P标号，P()0，其余各点均给T号，T()(2)若点为刚得到P标号的点，考虑，(，)A且为T标号对的T标号进行如下的更改：T()minT()，P() (6-1)(3)比较所有具有T标号的点，把最小者改为P标号，即：P()min T() (6-2)当存在两个以上最小者时，可同时改为P标号(4)若全部点均为P标号，则停止计算否则用代替并转至步

19、骤（2）例6-7用Dijkstra算法求图6-10中从到的最短距离，以及相应的路线图6-10解（1）首先给以P标号，P（ ） 0，给其余所有点T标号，T（i）（i = 2，3， 7）（2）考察，由于（，），（，），（，）A，且、是T标号，所以修改T标号为：T（）min T（），P（） min ，022T（）min T（），P（）min ，055T（）min T（），P（）min ，033在所有T标号中，T()2最小，于是令P()2将结果记在图6-10（a）上：P标号以（）形式标在结点旁边，T标号以不带（）的数字标在结点旁边，图中没有标号的结点均代表T（）(3)考察因为（，），（，）A，且、是T

20、标号，故、新的T标号为：T（）min T（），P（）min ，224T（）min T（），P（）min ，279在所有T标号中，T()3最小，故令P()3图上标号如图6-10（b）(4)考察，因（，）A，T（）min T（），P（）min ，358在所有T标号中，T()4最小，令P()4图上标号如图6-10（c）(5)考察，（，），（，）A，T（）min T（），P（）min ，437T（）min T（），P（）min ，459在所有T标号中，T()7最小，令P()7图上标号如图6-10（d）(6)考察，（，），（，）A，T（）min T（），P（）min ，718T（）min T（），P（）

21、min ，7714在所有T标号中，T()8最小，故令P()8图上标号如图6-10（e）(7)考察，（，）A，T（）min T（），P（） min 14，8513令P()13，图上标号如图6-10（f）所有点都标上P标号，计算结束从到的最短路径，可从开始根据永久性标号数值回溯得到最短路径是：，路长13同时得到到其余各点的最短路，即各点的永久性标号P（i）Dijkstra算法只适用于所有0的情形，当赋权有向图中存在负权时，则算法失效图6-10（a）（b）（c）（d）（e）（f）2逐次逼近算法为方便起见，不妨设从任一点到任一点都有一条弧，如果在中，不存在弧(，)，则添加虚设弧(，)，令从起点到任意点

22、的最短路可以视为一个两阶段过程，如图6-11所示：图6-11(1)从出发，沿着一条路走1步到某点，其最短距离表示为(，)(2)再从沿(，)到，其最短距离就是弧(，)上的权 所以，从到的最短距离必满足如下递推公式：(，)（1，2，n） （6-3）(，)(，) （6-4）式（6-3）是任意两点间的一步距离，由前面假设可知其存在，这可以作为初始条件式（6-4）是任意两点间的k步距离，这是一个递推公式利用初始条件和递推公式通过逐步迭代就可以确定网络中任意点之间经步到达的最短距离并得到与之相应的路线下面以实例来说明迭代过程例6-8用逐次逼近算法求例6-6图6-10中从到各点的最短距离解根据初始条件可知(

23、，)0(，)2(，)5(，)3(，)(，)(，)；初始条件仅仅表达了从出发到的一步到达的距离，在有向简单网络中即为从到各点的最短距离到各点的步距离由公式（6-4）递推得出为方便、直观可列表计算如表6-3：表6-3到各点的步距离jvii(，)(，)k=1k=2k=3k=4k=5k=60253000000027222222013554444405333333017877770598880141313表的左半部是一个n×n的关于结点两两之间的一步距离矩阵，由式（6-3）可知，到的一步距离就是弧（，）上的权一步距离矩阵中0元素表示原地踏一步，没有填写数字的空格是的省略表右半部是公式（6-4）

24、的计算结果k=h时，第h+n列数据表示到各点的h步最短距离譬如k=3为第 列，表示经3步到达各点的最短距离计算过程如下：（1）当k=1时(，)这是初始条件，表示从出发到各点的一步距离，将其依次列于第 列由此推算(，)（2）k=2时(，)(，)即用表中第 列数字与表左边一步距离矩阵中第列相应数字相加取小，得到从出发到各点的二步距离：（0 0）（ 2）（ 5）(，)min （ 3） 0（ ）（ ）（ ）（2 0）（0 2）（ 5）(，)min （ 3） 2（ ）（ ）（ ）同理： (，)4(，)3(，)8(，)(，)得：024(，) 38将其填入表6-3第 列（3）重复上述步骤得到(，)、(，)、

25、(，)、(，)；分别填入表6-3第 、 列（4）当k=6时，发现(，)(，)，说明对于整个有向图D而言，继续增加步数已不起作用，即已得到从到各点的最短距离，即表中 或 列数字：0；原地一步2；一步到达4；二步到达3；一步到达7；三步到达 8；四步到达 13；五步到达从表6-3中还可以用回溯方法推知到各点最短距离的相应最短路线，以到为例：由第列行可知，到经5步到达，最短距离13回溯13的来源：（，）=13因（，） 列行 列行 （，）8513故记下（，）因（，） 列行 列行 （，）718故记下（，）.因（，） 列行 列行 （，）437故记下（，）因（，） 列行 列行 （，）224故记下（，）因（，

26、）022，记下（，） 得到最短路径：当网络图存在负权时，Dijkstra算法失效，必须采取逐次逼近算法来求解最短路例6-9试求网络图6-12中到各点的距离图6-12解初始条件：(，)0(，)1(，)(，)2(，)(，)计算结果如表6-4所示：表6-4到各点的距离vjvi(，)=1=2=3=4=501200000034111-1-1-2051411140-322222330-1-1-1-120求得到各点的最短距离：(，)0；原地一步(，)-1；四步到达(，)1；三步到达(，)2；一步到达(，)-1；二步到达(，)；无法到达逐次逼近算法，因其类似于矩阵乘法，在有些书籍表述为距离矩阵摹乘法，它们的实

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

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

29、流和最大流可行流是指满足容量限制条件和平衡条件的流(1)容量限制条件：对于任一弧(，)，都有0，即任何弧上的流量不能超过弧的容量(2)平衡条件：对于任一中间点，都有即每个中间点的流出量必须等于流入量，其净流量为0对于始点和终点，有即始点流出量等于终点的流入量，这个流量即是可行流的流量，记为（）所谓最大流问题，就是在可行流恒存在的前提下，满足max () . 0 、0； 这是一个特殊的线性规划问题，可用单纯形法求解但用图形方法求解更为直观和简单3增广链如果是网络中联结始点和终点的一条链，且链的方向从到，则与链方向一致的弧称为前向弧，用来表示前向弧集合；与链方向相反的弧称为后向弧，用来表示后向弧集

30、合如图6-13中(，)，(，)，(，)(，)，(，)设是一个可行流，是一条从到的链，若满足下列条件，则是可行流的一条增广链：（1）在弧(，)上， 0；（2）在弧(，)上， 0这就意味着在增广链上每一个前向弧的流量都没有达到最大容量（即不饱和前向弧）,而每一个后向弧的流量均不为0（即非零后向弧）如图6-13中链、 、 都是增广链可以指出，沿增广链调整各弧的流量可以使网络流量（）增大，而寻求网络最大流的方法正是以增广链为基础的4截集与截量在一个网络(，)中，若把点集V剖分成不相交的两个非空集合和，使，且中各点不须经由中的点而均连通，中各点也不须经由中的点而均连通，则把始点在中而终点在中的一切弧所构

31、成的集合，称为一个分离和的截集，记为(，)截集实质上是网络从到通路的横截面表达，它反映了网络从到的必经之路一个网络可以有多个截集，表6-5反映了图6-13网络的截集集合表6-5图6-13网络的截集集合S截集(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)1

32、6s,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给定一截集(，)，其中所有弧的容量之和称为这个截集的截量，记为(，)|（，）(，)一个网络可以有多个截集和截量，其中截量最小的截集称为最小截集，记为(，)，其截量称为最小截量(min-cut)，记为(，)图6-13的最小截量由表6-5看出为11，最小截集为(，)(1,3), (4,t)二、基本原理为了介绍一种寻求网络最大流的标号法，这里将阐述其原理定理6-3（流量截量定理）在网络=(，)中，设为一可行流，(，)是任一截集，

33、则（）(，)定理6-3表明，网络的任一可行流的流量恒不超过任一截集的截量因此，网络的最大流量也不会超过最小截量定理6-4（最大流量最小截量定理）网络中从s到t的最大流的流量等于分离s和t的最小截集的截量即，（）(，)定理6-4实际上是定理6-3的推论定理6-5（最大流的充要条件）设是网络(，)的一个可行流，则为最大流的充要条件是：网络中不存在关于的增广链()定理6-6（增广链调整法）设是(V，A，)的一个可行流，是关于f 的一条增广链令 当 当 当 （6-5） 当min（，）构造一个新的可行流，令 当（，） 当（，） （6-6） 当（，）则()也是的一个可行流，其流量为（）（） （6-7）定理

34、6-4表明：只要网络中还存在关于可行流的增广链，则就非最大流，起码其流量还能增大这样就给出了一种沿着增广链上的各弧去调整流量，从而得到一个流量增大的新可行流的方法，故称之为增广链调整法三、寻求网络最大流的标号法这种标号法由福特(Ford)和富尔克逊(Fulkerson)于1956年提出，故称为福特一富尔克逊标号法(Ford- Fulkerson algorithm)1基本算法思想：该法从某一可行流出发，按一定规则找出一条增广链()，并按定理8-6的方法调整，得到一个流量增大的新可行流对重复上述做法直到找不出增广链为止，这时就得到一个最大流，同时还得到一个最小截集2算法步骤（1）给出一个初始可行

35、流初始可行流可以是零流或非零流；（2）标号、检查过程：给顶点标号，标号用，L()表示，其中第一个分量表示该标号是从哪个点得到的，用以反向追踪找出增广链，第二个分量是为确定的调整量用的点标号(0，)，则已标号待检查；取一个已标号待检查的点，所谓检查是对所有与相邻而未标号的点依次执行下述a）、b）两种考察：a）若联结与的弧(，)为前向弧，则当该弧上的流量小于容量，即时给标号，L()，其中L()min（L()，一）这里L()表示弧(，)上流量的最大可调整量而当弧(，)上的时，弧(，)是饱和前向弧，则不给标号b）若关联与弧(，)为后向弧，则当该弧上的流量大于零，即0 时给标号-，L()，其中L()mi

36、nL()，而当0时不给标号当所有与相邻而未标号的点都完成了a）、b）两种考察后，给打，表示对它的检查完毕重复，如果终点得到标号，则可以从沿标号点回溯到第一个标号，从而找出一条从到的增广链，转至；如果所有标号点均已打，而t又未得标号这说明不存在关于当前可行流的增广链，由定理6-3可知当前可行流即最大流，算出流量，计算停止取增广链的流量调整量L（），对增广链上的流量进行调整，对增广链上的前向弧，令对增广链上的后向弧，令非增广链上的弧流量不变删除原有所有标号，返回例6-10用Ford-Fulkerson标号法求图6-14所示网络的最大流图6-14解 第一步：图中给出了网络的初始可行流；第二步：首先给

37、s以标号(0，)，此时待查点是，相邻而未标号的点有、检查：弧(，)，3，为饱和前向弧，所以不对标号弧(，)，为非饱和前向弧，所以给点标号，L()其中L()min L()，min，51 4.检查完成，对其打此时有了标号成为待查点，相邻而未标号的点有、，如图6-15（a）所示检查点：弧(，)，为饱和前向弧，所以不对标号.弧(，)，0，为非零流后向弧，所以给标号，L()，其中L()min L()，12min4，1 1.检查完成，对其打此时完成检查的点有、，因有了标号成为待查点，相邻而未标号的点有、如图6-15（b）所示检查点：弧(，)，为不饱和前向弧，所以给标号，L()，其中L()min L()，m

38、in1，43 1.弧(，)，为不饱和后向弧，所以给标号-，L()，其中L()min L()，min1，21 1.检查完成，对其打此时完成检查的点有、，和因有了标号成为待查点，相邻而未标号的点有如图6-15（c）所示.检查点：弧(，)，为不饱和前向弧，所以给标号，L(),其中L()min L()，min1，53 1.检查完成，对其打由于已得到标号，已经可以得到一条增广链，不需再检查（如果检查而不检查可以得到另一条增广链，可自行验证）,如图6-15（d）所示图6-15（a）、（b）、（c）、（d）第三步：利用各点已标号的第一个分量，从反向追踪得增广链，如图6-15（d）中粗箭头线所示其中前向弧(，

39、)、(，)、(，),后向弧(，).由标号的第二个分量知1，于是在已知增广链上进行调整： 112 （，） 314 （，） 314 （，） 110 （，） （，）调整后的可行流如图6-16所示对这个新的可行流重新在图中进行标号，寻找新的增广链图6-16第四步：再标号给以标号(0，)，检查：弧(，)为饱和前向弧，不标号弧(，)为非饱和前向弧，标号，L()，L()3.检查：弧(，)为零流后向弧，不标号弧(，)为饱和前向弧，不标号此时已标号的点均已打，而又未得标号，由算法步骤可知网络中不存在增广链，目前的可行流就是最大流第五步：确定最小截集和最大流量此时已标号且打的点构成集，而未标号的点构成集，最小截集

40、为(，)如图6-16所示,，,（，）最小截量(，)最大流量5.第五节 最小费用流问题在实践中，人们考虑网络流问题不仅仅考虑流量，还必须考虑流的费用例如，在运输网络中，从发点到收点所经过的路程，往往因为交通工具不同或道路本身结构不同而产生各段路程交通费用不同，这时问题就变成了不仅要求到的一定运输量，而且要求这种运输方案的总费用最小这类问题就属于本节要介绍的最小费用流问题(min-cost-flow)一、最小费用流算法在给定网络=(，)中，对每条弧(, )，除已给出弧容量外，还给出单位流量的费用0设=是中的可行流，其流量总费用为（）=最小费用流问题是考虑在给定可行流量条件下，使得总费用（）最低因此

41、其数学模型为：()=min在最小费用流问题中，有很大一部分是寻求使（）为最小且流量为最大流的流量方案这是最小费用流的特例问题，称为最小费用最大流问题1求最小费用流的基本思想是：从零流（）=0的费用有向图（）开始，先用一定方法寻找关于的从到的最小费用增广链，并对按FordFulkerson标号法进行流量的调整，得到一个新的可行流，新的可行流必是最小费用可行流如果()达到流量目标要求，则计算终止否则，重新构造关于的费用有向图N（），继续在（）上求出由到的最小费用增广链，并在上进行流量的调整，如此下去，直到求出目标流量为的可行流为止如果是最大流的流量，则此最小费用流就是最小费用最大流由此可见，求最小

42、费用流的方法就是求最小费用增广链和求最大流方法的综合所谓最小费用增广链，即诸多增广链中费用权之和最小的一条增广链其求算方法要借助于网络N的辅助赋权有向网络2辅助赋权有向网络构造方法是原图的辅助图，构造的目的是为了在中寻找关于最小费用可行流的从到的最小费用增广链构造时，总体上是要将N中所有可能的弧流量变动特性集中表现于中，并同时为它们的弧重新赋权，具体方法如下：设L（）(，)，其中的，分别是网络的点集，弧集、弧容量和费用集，它与（，）的关系如下：(1)顶点集：（L）（），即的顶点即原有的网络N的顶点(2)弧集及方向和赋权方法：A集中的零流弧：这类弧流量的变动只能增加弧流量，这一流变动特性，在原图

43、中已充分体现，因此在集中，弧的方向与原中的相同，赋权不变； 集中的饱和弧：这类弧流量的变动只能减少流量，因此在集中，弧的方向与原中的相反，赋权：；集中的非饱和、非零流弧：这类弧的流量变动，既可增流又可减流因此在集中，点,之间，应该有正反两个方向的弧同时存在，其中方向与原中相同的弧(, )上 ，方向与原中相反的弧(,)上，例6-11已知原图（图6-17所示），其弧权的含义为（，），求其辅助赋权网络图6-17解（1）N中零流弧只有一条，在L中该弧的方向、赋权均不变（2）中饱和流弧也只有一条，在L中该弧的方向相反，赋权改变：2，4（3）N中非饱非零弧有三条、，这些弧在L中分别有相应的正、反向两条弧存

44、在，赋权情况： 523； 2： 2；2： 422； 2： 2；2： 321； 4： 2；4综上，构造原图N的辅助图，如图6-18所示弧旁数字为（，）图6-18在中找关于的从到的最小费用增广链，就等价于在赋权有向网络中，找从到的最小费用链这样，就把在N中寻找最小费用增广链问题转化为在中寻找最小费用链问题，而这在形式上等同于在中寻找最短路3最小费用流算法步骤第1步：从一流量为（）的初始最小费用可行流开始，(也可以是零流，=0)，在第1步得到最小费用可行流记为 第2步：构造辅助赋权有向网络L（），并在L（）中求到的最小费用链，若不存在最小费用链，则此时的即为最小费用最大流(转第4步)；若存在最小费用

45、链，则在中得到相应的最小费用增广链 (转第3，流调整)第3步：在最小费用增广链上按照定理6-6作调整，得到新的最小费用可行流k，若k已经达到目标流量转第4步，否则转第2步，重复第4步：停止运算，并输出当前最小费用可行流，作为中的最小费用最大流；或输出当前最小费用可行流流量作为中流量（）的最小费用流二、实例例6-12试求图6-19网络（）7的最小费用流和最小费用最大流（弧旁的数字为（，），其中表示弧容量，表示单位物质运费）图6-19解（一）求流量为7的最小费用流（1）因为原图流量0，故先利用Dijkstra标号法对图6-19的网络求最小费用链，显然这时的最小费用链即是最小费用增广链：，如图6-2

46、0（a），调整量min（）， =7，5，5，7，5=5，按照定理6-6对上的各弧进行流量调整，调整后上各弧流量：，同时（）055如图6-20（b）（2）在图6-20（b）中寻找从到的最小费用增广链为此对图6-20（b）作辅助赋权有向网络L（）：A集中：， 均为零流弧；A集中相应的弧不变A集中：，均为饱和前向弧；A集中相应的弧方向反转，赋权A集中：，均为不饱和前向弧；A集中相应的弧不变，添加反方向的弧并赋权得到图6-20（c）图6-20（c）是图6-20（b）的辅助赋权有向网络，其构造目的是寻找图6-20（b）中有关的从到的最小费用增广链，我们知道等价于图6-20（c）中的从到的最小费用链（或最

47、短路）求图6-20（c）的最短路：由于图6-20（c）含有负权，不能使用Dijkstra标号法，可以用逐次逼近法求得图6-20（c）网络的最小费用链：，如图6-20（c）中粗线所示；也是图6-20（b）中关于的从到的最小费用增广链回到图6-20（b），对进行调整：min（），ij （）min（75），（70），（150）2调整后上各弧的流量为：，同时（）（）527，如图6-20（d）所示（3）作图6-20（d）的辅助赋权有向网络（如图6-20（e）所示），其中不存在负回路，证明图6-20（d）所示的网络流是=7的最小费用可行流(这里不加证明地引入为中流量为的最小费用流的判别条件：为中流量为的最

48、小费用流的充要条件是，相应的中没有负回路即中的任意回路C，有0)（二）求图6-19的最小费用最大流承接以上结果对图6-20（e）所示网络，求其最小费用链得为 ，5，（）12调整后上各弧的流量为：，如图6-20（f）所示对图6-20（f）所示网络作辅助赋权有向网络如图6-20（g），求其最小费用链得为 ，5，（）17调整后上各弧的流量为：，得到图6-20（h）所示网络对图6-20（h）所示网络作辅助赋权有向网络图，其中不存在从到的通路，说明图6-20（h）所示网络流为最小费用最大流图6-20（a）（b）（c）（d）（e）（f）（g）（h）第六节网络计划（统筹方法）网络计划（Network Pla

49、nning）是一种计划管理的科学方法，它是编制大型工程进度计划的有效工具对于计划人员清楚地掌握整个工程进度，预见可能发生的问题，协调和控制各项活动，达到合理组织，统筹安排，使工程任务能顺利地按期或提前完成，起到了重要的作用已故著名数学家华罗庚先生将这些方法总结概括为统筹方法一、统筹图的基本概念和基本规则统筹图（project diagram）也可称为工序流程图，它可以直观地反映组成管理的各项活动及其相互间的内在关系正确、完备、详尽的统筹图是网络计划工作必不可少的前提和工具(一)工程的分解及工序间的关系工序：根据工艺技术和组织管理上的需要，将工程划分为按一定顺序执行而又相对独立的若干项活动，这些活动称为工序在统筹图上，工序k用箭线 “”表示工序也可以用（，）表