管理运筹学07网络规划1ppt课件

《管理运筹学07网络规划1ppt课件》由会员分享，可在线阅读，更多相关《管理运筹学07网络规划1ppt课件（67页珍藏版）》请在金锄头文库上搜索。

1、第七章网第七章网络规划划第七章网络规划第七章网络规划第一节：现实中的网络规划问题第一节：现实中的网络规划问题第二节：图的根本概念第二节：图的根本概念 第三节：树第三节：树 第四节：最大流问题第四节：最大流问题 第五节：最短途径问题第五节：最短途径问题 第六节：最小费用最大流问题第六节：最小费用最大流问题第七节：网络方案技术第七节：网络方案技术第八节：网络规划的运用第八节：网络规划的运用7.17.1现实中的网络规划问题现实中的网络规划问题许多工程和管理的问题都可以用图与网络来描画，图与网络优化问题是一类运用非常广泛的问题。图与网络优化是线性规划等实际和算法在具有图构造的问题中的运用。由于图与网络

2、问题具有特殊的构造，相应的优化算法也不同于普通的单纯形算法，具有其独特的直观和简捷的特点。哥尼斯堡七桥问题哥尼斯堡七桥问题 哥尼斯堡城有条河流，河中有两个小岛，河上共有七个桥，当地居民思索这样一个问题：能否从某个地点恣意点出发经过七个桥，且每个桥只经过一次，最后回到出发地点。 哥尼斯堡七桥问题哥尼斯堡七桥问题欧拉在1736年发表了图论方面的第一篇论文，处理了哥尼斯堡的七桥问题。欧拉将此问题归结为以下图所示的一笔画问题。也就是能否从某一点开场，不反复地一笔画出这个图形，最后回到原来出发点。 BACD欧拉证明了这是不能够完成的。由于图形中的每个点都与奇数个线相关联，不能够将这样的图形不反复地一笔画

3、出来，这是古典的图论中的一个著名问题。 7.27.2图的根本概念图的根本概念 7.2.1图: 由节点Node和边Edge组成。节点和边是图中最根本的概念，我们不对其作出定义。以下图中，有4个节点，7条边，每一条边都与2个节点对应。因此，一条边可以用它的两个节点来标志。图7.3中的边，可以记为v1，v2，v1，v3，v2，v3，v3，v2，v2，v4，v3，v4，v4，v1。 v3 v1 v4 v2 e1e2e3e4e5e6图的定义图的定义定义定义 设设V=V=v1v1，v2v2，vmvm表示节点的集合，表示节点的集合，E=E=e1e1，e2e2，enen表示边的集合，假设对任一表示边的集合，假

4、设对任一ekEekE，均有，均有vivi，vjVvjV与之对应，那么称与之对应，那么称VEVE为图，记为为图，记为G=(VG=(V，E)E)。称称vivi为为G G的顶点，的顶点，ekek为为G G的边，记为的边，记为ek=viek=vi，vj= vjvj= vj，vivi。称称vivi，vjvj为为ekek的端点，的端点，ekek为为vivi，vjvj的关联边。称的关联边。称vivi，vjvj为邻接为邻接点。点。将图将图7.37.3用数学定义表示如下：用数学定义表示如下：G=(VG=(V，E)E)V=V=v1v1，v2v2，v3v3，v4v4E=E=e1e1，e2e2，e3e3，e4e4，e

5、5e5，e6e6，e1e1，e2e2，e3e3，e4e4，e5e5，e6e6，e7=v1e7=v1，v2v2，v1v1，v3v3，v2v2，v3v3，v3v3，v2v2，v2v2，v4v4，v3v3，v4v4，v4v4，v1 v1 相关定义相关定义假设图中一个边的两个端点为同一个点，称这样的边为环。假设两个点之间存在两个以上的边，称为多重边。一个没有环、也没有多重边的图，称为简单图。无环,允许有多重边的图称为多重图。本章讨论的图主要是指简单图。图中的边是对节点的关系描画，所以我们讨论的图假设关系表示的一样，不论图的外形如何，我们以为这样的图都是一样的。次: 以点v为端点的边的个数称为v的次，

6、表示为: d(v)。悬挂点: 次为1的点。悬挂边: 悬挂点的关联边。孤立点: 次为0的点。奇点: 次为奇数的点。偶点: 次为偶数的点。两个定理两个定理定理定理7-1: 7-1: 图图G=(V,E)G=(V,E)中中, ,一切点的次之和是边数的两倍一切点的次之和是边数的两倍, , 即即: :证明证明: :计算各端点的次时，每个边都用了两次，所以次数的计算各端点的次时，每个边都用了两次，所以次数的总和必然为边数的两倍。总和必然为边数的两倍。定理定理7-2: 7-2: 恣意一图中恣意一图中, , 奇点的个数为偶数。奇点的个数为偶数。证明证明: :设设 V1 V1表示奇点的集合，表示奇点的集合， V2

7、 V2表示偶点的集合。由有：表示偶点的集合。由有： 由于偶点的次之和为偶数，总数为偶数，所以奇点的次之由于偶点的次之和为偶数，总数为偶数，所以奇点的次之和必需是偶数，只需偶数个奇数之和才干是偶数。所以奇和必需是偶数，只需偶数个奇数之和才干是偶数。所以奇点的个数必然为偶数个。点的个数必然为偶数个。相关定义相关定义链：点边交错系列，链：点边交错系列， 记为：记为： 假设满足假设满足 ，普通简记为：，普通简记为：圈：圈： 的链。的链。 初等链：点初等链：点 均不一样。均不一样。初等圈：点初等圈：点 均不一样。均不一样。简单链：链中边均不一样。简单链：链中边均不一样。简单圈：圈中边均不一样。简单圈：圈

8、中边均不一样。连通图：恣意两点之间至少有一条链。否那么称为不连通连通图：恣意两点之间至少有一条链。否那么称为不连通图图连通分图：对不连通图，每一连通的部分称为一个连通分连通分图：对不连通图，每一连通的部分称为一个连通分图。图。支撑子图：支撑子图： 对对G=G=V V，E E，假设，假设G=(V,E), G=(V,E), 使使V=V, V=V, EE E, E, 那么那么GG是是G G的一个支撑子图生成子图的一个支撑子图生成子图7.2.27.2.2有向图有向图前面讨论的图中，边是没有方向的，ek=vi，vj= vj，vi。这样的图称为无向图。但许多实践问题用无向图表示是不够的。例如，涉及交通网络

9、中单行道、一项工程的各工序的前后次序关系等。 v3v1v4v2a1a2a3a4a5a6a7定定义 设V=v1，v2，vm表示表示节点的集合，点的集合，A=a1，a2，an表表示示边的集合，假的集合，假设对任一任一akA，均有，均有vi，vjV与之与之对应，那么称，那么称VA为图，记为D=(V，A)。称称ak为D的弧，的弧，记为ak=vi，vjvj，vi。 相关定义相关定义始点和终点始点和终点: : 对弧对弧a=(u,v), ua=(u,v), u为为a a的始点的始点, v, v为为a a的终点。的终点。根底图根底图: : 对对D=(V, A), D=(V, A), 去掉图上的箭头的无向图。去

10、掉图上的箭头的无向图。链链: : 点弧交错序列点弧交错序列, , 假设在其根底图中对应一条链假设在其根底图中对应一条链, , 那么称那么称为为 D D的一条链。的一条链。路：假设路：假设 是是D D中的一条链，中的一条链，且且 ，t=1,2,k-1,t=1,2,k-1,称之为从称之为从 到到 的一条路。的一条路。回路回路: : 的路。的路。初等路初等路: : 路中点不一样。路中点不一样。初等回路初等回路: : 回路中点不一样。回路中点不一样。7.2.3 7.2.3 赋权图赋权图 假设给定一个图G=(V，E)或D=(V，A)的任一边弧有一个实数 与之相对应，由称这样的图为赋权无向有向图。赋权图的

11、运用是很广泛的。例如，在一个交通网络中，边的权数可以是两个点之间的间隔，也可以表示两点之间的运输费用、运输时间、运输才干等。在一个设备维修的图中，权数可以表示维修费用，在工程工程方案网络图中可以表示各工序的完成时间等。1354256-2023-44在赋权图中的链路上一切边弧对应的权之和，称为链路的权。一个连通图连同定义在其边集上的实函数一同，称为一个网络7.2.47.2.4图的矩阵表示图的矩阵表示 图形虽然有直观等优点，但随着实践问题的大型化，大多数算法需求在计算机上运算和求解，计算机处置直观图形是比较困难的。以下引见将图用矩阵表示，将图的几何外形转化为代数矩阵，可以方便计算机对图形的处置与运

12、算。以下举例阐明。例7-1将下7-5用矩阵表示。不思索权时的矩阵表示如下不思索权时的矩阵表示如下 ： V1V2V3V4V5V6V7V10111000V21011100V31100110V41100101V50111011V60010101V70001110两个端点之间有边记为1，无边相连那么记为0，对角线上记为0。这样得到一个对称的矩阵。 思索权数时的矩阵表示为：思索权数时的矩阵表示为：V1V2V3V4V5V6V7V10347V230324V343057V472026V5452014V670102V76420两个端点之间有边相连的，记上其权数，无边相连的记为，对称线上仍记为0。赋权无向图的矩阵

13、也是对称矩阵。 例例7-27-2将下将下7-67-6用矩阵表示。用矩阵表示。312453564357思索权数时的矩阵表示为：思索权数时的矩阵表示为：赋权有向图的矩阵往往不是对称矩阵V1V2V3V4V5V1053V2054V3607V40V5307.3 7.3 树树 树是一类特殊的图。例如衔接五个乡镇的光纤网，可表示以下图31245树Tree：无圈的：无圈的连通通图称称为树图的支撑树图的支撑树 图的支撑树图的支撑树Spanning TreeSpanning Tree: :设图设图G G有有p p个节点，个节点，q q条边。条边。由由G G中中p p个节点，个节点，p-1p-1条边组成的树称为图条

14、边组成的树称为图G G的支撑树，也称为的支撑树，也称为图图G G的生成树。的生成树。图7-8 图7-5的一个支撑树图7-9 图7-5的一个支撑树树中只与一条边关联的节点称为悬挂点。与悬挂节点关联的边称为悬挂边。图7-8中节点3和节点7都是悬挂点，6，3和4，7都是悬挂边。树有以下性质：1任何树至少有两个悬挂点。图7-8中节点3，节点7。2假设树的节点数是p，那么边的个数为p-1。图7-8的图有5个节点，有4条边。3树中恣意两个节点之间只需独一的一条链。4在树中恣意两个不相邻的节点之间添加一条边，那么会构成圈。 相关定义相关定义一个连通图可以有多个支撑树。支撑树的权:假设T=(V,E) 是G的一

15、个支撑树, E中的一切边的权之和称为支撑树的权, 记为w(T):例如图7-8的总的权为28，图7-9的总的权为13。最小支撑树：图的权最小的支撑树，即：比如，在一个小区铺设光缆通讯网，只需各个楼都连通即可，希望用的光纤越少越好。以下引见三种求最小支撑树的方法以下引见三种求最小支撑树的方法解法一：破圈法解法一：破圈法解法二：避圈法解法二：避圈法 解法三：顶点扩展法解法三：顶点扩展法解法一：破圈法例例7-37-3设某个小区由六个楼组成，如图设某个小区由六个楼组成，如图7-107-10，图上的数字为，图上的数字为各相邻楼的间隔百米。现要铺设光纤，试求光纤总长度各相邻楼的间隔百米。现要铺设光纤，试求光

16、纤总长度最短的铺设方案。最短的铺设方案。153232213v4v2v1v5v64v3用破圈法求解过程如下：用破圈法求解过程如下：用破圈法求解过程如下：普通先找权数最大的边所在的圈 1找圈找圈v1，v2 ，v4，v1或或v1，v3 ，v4，v1去掉去掉边v4，v1，13232213v4v2v1v5v64v3图7-11. 破圈法求解表示图1 2去掉去掉边v4，v53去掉去掉边v3，v64去掉去掉边v3，v15去掉去掉边v2，v5。得得图7-12。此。此时图中已不含圈，中已不含圈，剩下的剩下的边构成了原网构成了原网络的最小的最小支撑支撑树，也就是，也就是铺设光光纤的最的最优方案。方案。最小最小树的的

17、权为：W(T*)=1+2+2+2+1=812221v2v1v5v6v4v3图7-12. 破圈法求解表示图2解法二解法二: : 避圈法避圈法避圈法与破圈法的思想相反，先将一切边的权按从小到大的次序陈列，然后依次检查，假设某个边加到图上不会产生圈，就将其加上，否那么就不加到图上。直到一切边都检查完为止。在图7-9中加边的顺序为v1，v2、v4，v6、v2，v4、v3，v4、v5，v6，由于本图为6个点，加上5个边即完成。得到如图7-11的结果，与破圈法得到的结果一样。普通来说，一个图可以有多个不同的最小支撑树，但它们的总权一定一样。 解法三：顶点扩展法解法三：顶点扩展法顶点扩展法是先在图中任选一个

18、点，记为S=a1，以该点为出发点，将与其相连的最小权的边参与图中，将相关连的点参与到S中，得到S=a1，a2；再寻觅与S中的点相连的边中权数最小的边参与图中，将相关连的点参与到S中，反复进展以上步骤，直到一切的点都参与到S中为止。即可得到最小支撑树。 以v4做为出发点，S=v4，与v4相连的边有5条，权数最小的为v4，v6，将v6参与S中，S=v4，v6；与S=v4，v6相连的边有7条，其中权数最小的有3条，权数都是2，此时可任选一条。如将v5参与，得S=v4，v6，v5；与S=v4，v6，v5相连的边有5条，其中权数最小的有2条，权数都是2，此时可任选一条。如将v2参与，得S=v4，v6，v

19、5，v2；与S=v4，v6，v5，v2相连的边有4条，其中权数最小的有1条，权数是1，将v1参与，得S=v4，v6，v5，v2，v1；与S=v4，v6，v5，v2，v1相连的边有3条，其中权数最小的有1条，权数是2，将v3参与，得S=v4，v6，v5，v2，v1，v3。此时一切点都参与到S中，可以得到如图7-12的结果。 153232213v4v2v1v5v64v37.47.4最大流问题最大流问题 在网络图中指定一个源节点和一个汇节点，源节点的供应量为f，汇节点的需求量为f，图中其他节点均为中转节点。图中各边i，j流量的下界Lij=0，上界cij 0图7-13。对于一个给定的图，各节点流入、流

20、出的流量坚持平衡，各边上的流量为非负且不超越相应边的流量上界，求经过图的最大流量f的问题就是网络最大流问题。现实现实现实中的中的中的许许许多系多系多系统统统都存在各种都存在各种都存在各种各各各样样样的流，如公路系的流，如公路系的流，如公路系统统统中的中的中的车车车辆辆辆流、水利系流、水利系流、水利系统统统中的水流、中的水流、中的水流、电电电力系力系力系统统统中的中的中的电电电流、消流、消流、消费费费系系系统统统中中中的的的产产产品流、金融系品流、金融系品流、金融系统统统中的中的中的货币货币货币流、效力系流、效力系流、效力系统统统中的中的中的顾顾顾客流、信客流、信客流、信息系息系息系统统统中的信

21、息流等。中的信息流等。中的信息流等。 23411342f2cij图7-13. 最大流表示图7.4.17.4.1根本概念和根本定理根本概念和根本定理 一网络与流一网络与流定义定义: :有向图有向图D=(V,A)D=(V,A)，其中，其中vs vs 表示始点，表示始点，vt vt 表示表示终点，其他点为中间点，对每个弧对应一个权终点，其他点为中间点，对每个弧对应一个权c(vi,vj)c(vi,vj)，称为弧，称为弧(vi,vj)(vi,vj)的容量，简写为的容量，简写为cij cij 。称这样的赋权有向图为一个网络，记为称这样的赋权有向图为一个网络，记为D=(V,A,C) D=(V,A,C) 。

22、一个网络图要求只需一个始点、一个终点。一个网络图要求只需一个始点、一个终点。 二可行流与最大流二可行流与最大流对于网络D=(V,A,C)中的每个弧(vi,vj)定义一个实数fij ，称为弧(vi，vj)上的流量。那么集合 F=fij(vi,vj)A称为此网络的一个流满足以下条件的F=fij(vi,vj)A称为一个可行流：也就是说，一个可行流的每个弧上的流量不超越该弧的容量、中间点流入量与流出量相等、始点的净流出量与终点的净流入量一样。可行流总是存在的，例如一切的fij=0的流F=fij=0(vi,vj)A即是一个可行流，称为零流。在一个网络中，使f到达最大的可行流称为最大流。网络最大流问题可以

23、用线性规划方法求解网络最大流问题可以用线性规划方法求解 网络最大流问题可以用线性规划方法求解。例如图7-13的最大流问题，设xij为各弧的流量，f表示可行流的流量。那么此最大流问题的线性规划方式为： 23411342f2cij=+-=+-=+-=-+=ijijcxfxxxxxxxxfxxt sfz040302010. .max34243423132423121312节点节点节点节点三截集与截量三截集与截量 在网络D=(V,A,C)中，将点集V分成不相交的两个非空集合V1与 ，始点vs在V1中，终点vt在 中，那么把起点在V1中且终点在中的弧构成的集合称为分别vs 和vt的截集，记为V1， 将截

24、集中一切弧的容量之和，称为截集的容量，简称为截量。记为：截集截量的例子截集截量的例子23411342f2cij23411342f2cij23411342f2cij23411342f2cij图7-14图7-15图7-16图7-17截集的节点集合，所包含的弧以及截集容量截集的节点集合，所包含的弧以及截集容量 V1，C(V1，V1（V1，）C(V1， ) 图7-141，23，4（1，3）（2，3）（2，4）c13+c23+c24=4+2+3=9图7-1512，3，4（1，2）（1，3）c12+c13=1+4=5图7-161，32，4（1，2）（3，4）c12+c34=1+2=3图7-171，2，34

25、（2，4）（3，4）c24+c34=3+2=5截集是一种特殊的集合，如图7.16中2，3不包含在截集中。假设将恣意一个截集中的一切弧去掉，将不存在从网络始点到终点的路了，但能够存在从网络始点到终点的链。将截集容量最小的截集称为最小截集。如1，23，4，其截量为3。 相关定理相关定理定理定理7-37-3： 网络任一可行流的流量网络任一可行流的流量f f必定小于或等于网络中必定小于或等于网络中任一截集的容量。即：任一截集的容量。即：定理定理7-47-4： 网络中从网络中从vs vs 到到vt vt 的最大流的流量等于分别的最大流的流量等于分别vs vs 和和vtvt的最小截集的截量。的最小截集的截

26、量。即即: :假设假设 是一个最小截集，是一个最小截集，F*F*是最大流，最大流量是最大流，最大流量为为f*f*，那么有图，那么有图7-17.7-17.截集表示图截集表示图fsiejmkV1f图7-18.截集表示图四增广链四增广链设是网络D中的一条从vs到vt的链，定义链的方向为从vs指向vt，那么链上与链的方向一致的弧称为前向弧，其集合记为；链上与链的方向相反的弧称为后向弧，其集合记为- 。 1534762(4,4)(10,7)(4,4)(8,1)(1,1)(8,4)(6,3)(7,7)(2, 2)(3,3)(3,3)(10,5)如图中，弧上的数字表示为cij，fij，该流是一个可行流。其中

27、的一条链=v1，v4，v5，v6，v7各弧分为如下两类： = ( v1，v4)，( v4，v5)，( v6，v7)- = ( v6，v5)增广链定义增广链定义对于一个可行流对于一个可行流F F，是从是从vs vs 到到vt vt 的一条链，假设的一条链，假设上的上的各条弧的流量满足以下条件：各条弧的流量满足以下条件： fij cij fij 0 fij 0 当当( vi( vi，vj)vj)- - 后向后向弧不为零弧不为零那么称那么称为关于可行流为关于可行流F F的一个增广链。的一个增广链。调整战略调整战略假设一个可行流存在增广链，就可以将可行流进展调整。令 1 =min cij -fij |

28、 ( vi，vj) 2 =min fij | ( vi，vj)- = min1，2 再令 fij+ ( vi，vj)fij = fij- ( vi，vj)- fij ( vi，vj) 那么可得到一个新的可行流F，使得 f=f+由于0，所以新的可行流的流量一定可以得到添加。因此，当一个可行流F存在增广链时，F就不是最大流。这个思想同时也给出了一种沿增广链调整流量，从而得到最大流的方法 定理定理7-4：设F=fij(vi,vj)A是是D=V，A，C的一个的一个可行流，那么可行流，那么F*为最最大流的充要条件是网大流的充要条件是网络中不存在关于中不存在关于F的的增广增广链。 最大流问题的标号法最大流

29、问题的标号法 此方法是福特和富尔克逊于1956年提出的，所以称为福特富尔克逊标号法。一根本思想 从某一可行流 F如零流出发，按一定规那么找出一条增广链，并按照前述的沿增广链进展流量调整的方法去调整F，得到一个流量增大 的新可行流 F。反复上述做法直到找不出增广链为止，这时就得到一个最大流，同时还可以得到一个最小截集。 最大流问题的标号法最大流问题的标号法二根本步骤1. 给始点 vs 标号0，那么 vs 已标号待检查； 2. 取一个已标号待检查的点 vi对一切与 vi 相邻而未标号的点 vj 依次判别、执行如下手续： 1假设关联 vj 与 vi 的弧为(vi, vj)，那么当该弧上的流量 fij

30、 0 时, 给 vj 标号( -vi，b(vj)，其中 b(vj) = min b(vi)，fji 表示 (vi, vj) 弧上的流量的最大可减少量；而当 fji = 0 时, 不给 vj 标号； 最大流问题的标号法最大流问题的标号法当一切与 vi 相邻而未标号的点 vj 都执行完上述手续后，就阐明点 vi 已检查终了。vj为已标号未检查的点。3. 反复 2的手续，能够出现两种结果：1终点 vt 得到标号。那么从vt回溯标号点第一个标号，就能找出一条由标号点和相应的弧衔接而成的从 vs 到 vt 的一条增广链 (F)，转 4；2一切标号点均已检查过，而vt又未得到标号。这阐明不存在增广链，而当

31、前的可行流即为最大流，计算出其流量，算法终止。4. 取调整量 = b(vt) 即终点 vt 的第二个标号,令 fij = fij + ， 对一切 (vi, vj) fij = fij - ， 对一切 (vi, vj) - 非增广链上的各弧流量 fij 不变。5. 删除网络中原有一切标号，前往 1。注：标号中的第一个标号表示给该点标号的点，第二个标号表示调整量。例子例子534762(4,4)(10,7)(4,4)(8,1)(1,1)(8,4)(6,3)(7,7)(2, 2)(3,3)(3,3)(10,5)(0,)1(v1,7)(-v4,3)(v4,4)(v6,2)图7-20. 可行流1(v1,3

32、)(-v5,2)例子例子 图7-21. 可行流2534762(4,4)(10,7)(4,4)(8,3)(1,1)(8,6)(6,3)(7,7)(2, 0)(3,3)(3,3)(10,7)(0,)1(v1,5)(v1,3)(-v4,3)(v4,2)上例中阐明了标号法的根本思想，在解最大流问题时普通可以从零流出发，在图上直接给出标号，找到从vs到vt的一个增广链和相应的调整量，并进展流量的调整，反复以上步骤直到找不到增广链为止。即可得到最大流和最小截集。最大流不一定是独一的，但最大流的流量一定是独一的；最小截集也不一定是独一的，最小截量一定是独一的，而且与最大流的流量是一样的。7.57.5最短途径

33、问题最短途径问题 最短路问题就是在一个网络图中，给定一个起点vs和一个终点vt，寻觅vs到vt的路，使该路为从vs到vt的一切路中权数最小的路。实践问题中最短路问题有广泛的运用。例如管道铺设、线路安排、运输线路选择、工厂规划、设备更新等问题。解法：标号法矩阵法 标号法标号法最短路的标号法是由狄克斯屈E.W.Dijkstra于1959年提出的，是目前公认的求解权数为非负的网络最短路问题较好的算法。这种算法可以求出网络中恣意一点出发到其它各点的最短路。算法的思想如下：对每一个网络中的点vj，均赋予一个标号，永久标号Pvj或暂时标号Tvj。其含义如下：Pvj从起点vs到vj最短路的长；Tvj从起点v

34、s到vj最短路的长的上界。一个点只能有上述两种标号之一，假设有了P标号就不再改动了，假设有T标号那么根据情况进展修正。该算法的根本思想就是先给vs点标号为Pvs=0，其他点标号为Tvj=；然后检查有P标号的点，对与该点有关联边的vj的T标号进展修正；在一切T标号中找一个最小的，将其T标号修正成P标号。再检查新得到P标号的点，修正其它点的T标号，再在一切T标号中找最小的修正为P标号；如此反复，直到要求的终点或一切点得到P标号为止，即可得到网络最短路。由于此算法一次修正一个P标号，所以假设网络中有N个点，最多经过N-1步就能找出要求的最短路。为了寻觅到vs各点的最短道路，给每个顶点一个 值，算法终

35、止时，假设 表示在从vs到vj的最短路上vj的前一个点为vm；假设 ，那么表示vs到vj不存在路那么表示vj为起点。 DijkstraDijkstra方法的详细步骤为方法的详细步骤为: :1给vs标上永久标号P(vs)=0，其他节点标上暂时标号T(vj)=，同时给各点vj赋值如下：2假设节点vi是刚得到P标号的点。把与vi有弧边直接相连而且有T标号的节点，对其T标号和 进展如下修正： 假设T(vj)Pvi+wij，那么T(vj)=Pvi+wij ；3把T标号中值最小的节点vj0的暂时标号T(vj0)改为P(vj0)，假设一切点均有P标号、或要求的终点有P标号、或无法继续修正时，那么算法终止；否

36、那么转2。 例例7-4 7-4 用标号法求用标号法求v1v1到其它各点的最短路。到其它各点的最短路。步骤V1V2V3V4V5V6V7V800 0MM MMMMM151316 1MMMM2514 3M103MM3518464MM48464MM576126M695M7M15347627356422121681用表格的一行表示一个步骤，表格中的左上角表示PT标号，其中表示P标号；右下角表示 值例例7-47-4到各点的最短路的长就是各点的P标号之值。到各点的最短道路可从该点的最后的值出发，逆序寻觅其前一点的值，直到起点为止，即可得到从起点到该点的最短道路。例如：P(v7)=9，阐明从v1到v7的最短路

37、长为9 v7=5 v5=6 v6=4 v4=3 v3=1 v7 v5 v6 v4 v3 v1点最短路最短路的权V1起点0V2v1 v25V3v1 v33V4v1 v3 v4 4V5v1 v3 v4 v6 v57V6v1 v3 v4 v6 6V7v1 v3 v4 v6 v5 v79V8无对于无负权的无向图来说，标号法的程序也是一样的。 矩阵法矩阵法 当一个网络存在负权时，Dijkstra算法会失效。如图7-23 13232-3 图7-23. 负权网络从v到v3的最短路长为-1，而不是2。矩阵法的根本思想是利用本章第一节中引见的网络图的矩阵表示，其中的wsj表示从vs经一步到vj的权，可记为：那么

38、从vs经K步到达vj的权为：普通，经K步从vs经两步到达vj的权为矩阵法矩阵法Sj1ink-1步 1步 由于 的计算就是n 个对应元素的求和取小，这与矩阵的乘法的计算是相类似的，所以此算法也称矩阵摹乘法。当j=1,2,n时，阐明从的最短路的权不能再减少，所以j=1,2,n即为的最短路的权。 最短路问题最短路问题 0 3 2 4 0 3 2 4 0 4 4 1 0 4 4 1 0 -1 6 0 -1 6 3 -2 0 1 3 -2 0 1 5 0 3 5 0 3 3 3 0 3 3 0 W =例例从至从至 1 1 2 2 3 3 4 4 5 5 6 6 1 1 2 2 3 3 4 4 5 5 6

39、 6 1 1 3 3 4 4 6 6 2 2 5 5 34253-2-24413613-1-13最短路问题最短路问题二、求各点至某点的最短路二、求各点至某点的最短路 1 1 n n r r j j i i i i 1步步k-1步步dk=d(k)1r.d(k)ir.d(k)nr 1 1 2 2 3 3 1 12 2-5-5-5-5负回路回路d(k) = min wij + d(k-1) 1j n irjr dk=w* dk-1 ， k=2，3, ,n -1dk= dk-1 那么也那么也终终了了假假设不含不含负回路，回路，至多算到至多算到 dn-1。* * 运算：两矩运算：两矩运算：两矩运算：两矩

40、阵对应阵对应阵对应阵对应元素求和取小。元素求和取小。元素求和取小。元素求和取小。 两矩两矩两矩两矩阵阵阵阵元素元素元素元素对应对应对应对应方式，同矩方式，同矩方式，同矩方式，同矩阵阵阵阵乘法。乘法。乘法。乘法。wijd(k-1)jr最短路问题最短路问题* 4 4 1 1 3 3 0 0W * d1 =0 3 2 0 3 2 4 4 0 4 4 1 0 4 4 1 0 -1 6 0 -1 6 3 -2 0 1 3 -2 0 1 5 5 0 30 3 3 3 0 3 3 04 4 1 1 -2 -2 -1 -1 3 3 0 0 0 0 1 1 -2 -2 -1 -1 3 3 0 0 0 0 1 1

41、 -2 -2 -1 -1 3 3 0 0从从 至至 1 1 2 2 3 3 4 4 5 5 6 6 1 1 2 2 3 3 4 4 5 5 6 6d2d1d3d4d54 41 19 9-1-13 30 0d(2) = min w1j + d(1) j616= min 0+4, 3+1, 2+, +, +3, 4+0 0 3 2 4 4 4 4 4 1 1 1 1 3 3 3 3 0 0 0 0= 4d(k) = min wij + d(k-1) 1j n irjr 0 4 4 1 0 -1 6 3 -2 0 1 5 0 3 3 3 0最短路问题最短路问题* 4 4 1 1 3 3 0 0W *

42、 d1 =0 3 2 0 3 2 4 4 0 4 4 1 0 4 4 1 0 -1 6 0 -1 6 3 -2 0 1 3 -2 0 1 5 5 0 30 3 3 3 0 3 3 04 4 1 1 -2 -2 -1 -1 3 3 0 0 0 0 1 1 -2 -2 -1 -1 3 3 0 0 0 0 1 1 -2 -2 -1 -1 3 3 0 0从从 至至 1 1 2 2 3 3 4 4 5 5 6 6 1 1 2 2 3 3 4 4 5 5 6 6d2d1d3d4d54 41 19 9-1-13 30 021-1-1-2-203 4 4 2 2 6 6 2 2 6 6 6 6最最 短短 路路

43、 1 1 2 2 3 3 4 4 5 5 6 6 3 3 6 6 4 4 2 2 6 6 6 6 按按W W阵中画圈元素的从中画圈元素的从 至关系至关系0 0 1 1 -2 -2 -1 -1 3 3 0 0最短路最短路长 1 1 3 3 4 4 6 6 2 2 5 5 34253-2-24413613-1-130 02 -1-1 -2-2 +1 = 0最短路问题最短路问题 3 3 1 1 3 3 4 4 1 1 1 10 0 -1 -1 2 2 1 1 2 2 0 0最最 短短 路路最短路最短路长 1 1 2 2 3 3 4 4 5 5 6 6 1 1 4 4 1 1 3 3 4 4 2 2

44、l2T=l1T * W = 1 1 2 2 3 3 4 4 5 5 6 6至至 从从 1 1 2 2 3 3 4 4 5 5 6 6 0 3 2 0 3 2 4 4 0 4 4 0 4 4 1 1 0 -1 6 3 -2 0 1 5 0 5 0 3 3 3 3 0 3 3 0( 0 3 2 ( 0 3 2 4 )4 )* *( 0 3 2 1 7 ( 0 3 2 1 7 4 )4 )( 0 -1 2 1 2 ( 0 -1 2 1 2 4 )4 )( 0 -1 2 1 2 ( 0 -1 2 1 2 0 )0 )( 0 -1 2 1 2 ( 0 -1 2 1 2 0 )0 )l3T=l4T=l5T

45、= 3 3 1 1-1-11 11 1三、三、 求某点至各点的最短路求某点至各点的最短路2 2最短途径问题的线性规划方式最短途径问题的线性规划方式设一个图G中wij为节点i到节点j的间隔，求节点1到节点m的最短途径。这就是图最短途径问题。设节点1为供应节点，供应量b1=1，节点m为需求节点，需求量bm=-1，其他节点i均为转运节点，bi=0。7.67.6最小费用最大流问题最小费用最大流问题 第三节讨论了网络最大流问题，在实践中涉及流的问题时，人们思索的不只是流量，同时要思索“费用的要素。对D=(V,A,C), 给定一个单位流量的费用bij0, 最小费用最大流即:求一最大流f, 使增广链增广链

46、的费用的费用 最大流的算法是从某个可行流出发，寻觅关于可行流的增广链，然后沿着增广链调整可行流的流量，得到一个新的可行流，反复以上过程即可得到最大流。对于增广链, 假设调整流量=1, 那么新可行流F的费用比原可行流F的费用添加量为:称为增广链的费用。可以证明，假设F是流量为f的一切可行流中费用最小的，而是关于F的费用最小的增广链，那么沿着增广链去调整流量，得到的新可行流F，就是流量为f的费用最小的可行流。这样当F为最大流时，也就是所求的最小费用最大流。根本思想根本思想由于bij0，所以零流的费用总是最小的。所以可以从零流出发去寻觅最小费用最大流。这里主要需求处理的问题就是如何寻觅关于F的费用最

47、小的增广链。为此，可构造网络图D的相对应的赋权有向图WF，其节点与原网络图D一样，将D中的每一条弧，都变成两方向相反的弧，与，定义WF中弧的权为：权数为的弧表示不能经过，可以在WF中省略。这样寻觅关于F的费用最小增广链的问题就等价于在WF中寻觅从网络始点到终点的最短路问题。权数为的弧表示不能经过，可以在WF中省略。详细算法详细算法 这样寻觅关于F的费用最小增广链的问题就等价于在WF中寻觅从网络始点到终点的最短路问题。详细算法为：从零流出发，构造其WF，在WF中寻觅最短路，在F中对应一个增广链，增广链的调整量由下式确定：沿增广链，对流量进展调整，调整方法同最大流的调整方法。然后对新得到的可行流继

48、续做前述的任务，直到在赋权有向图WF中找不到从始点到终点的最短路也就是在网络图D中不存在增广链为止，即可得到最小费用最大流。 最小费用最大流问题最小费用最大流问题例例 在右在右图中，求最小中，求最小费用最大流。用最大流。 弧旁数字弧旁数字为： bij，cij3, 75, 62, 81, 4s12t1, 6解解 取零流取零流 F0为初始流。初始流。3, 7, 05, 6, 02, 8, 0 1, 4, 0s12t1, 6, 0(a) F03521s12t1(b) W( F0 = 4 = 4 = 4 = 4 8.5 8.5 最小最小费费用最大流用最大流问题问题 = = = = 4 4 4 43,

49、7, 05, 6, 02, 8, 41, 4, 4s12t1, 6, 4(a) F1352-1-1s12t1(b) W( F1-1-1-23, 7, 45, 6, 02, 8, 8 1, 4, 4s12t1, 6, 4(a) F235-3-1-1s12t1(b) W( F2-1-1-2-2 = = = = 3 3 3 3最小费用最大流问题最小费用最大流问题 X* = F3 ， f * = 11 ，b(X*) = 2(8)+5(3)+1(1) + 3(7)+1(4) = 57 3, 7, 75, 6, 32, 8, 8 1, 4, 4s12t1, 6, 1(a) F33, 7, 75, 6, 4

50、2, 8, 7 1, 4, 4s12t1, 6, 0(a) FF 亦最大流，亦最大流， f (F) = 11但但b(F ) = 59 57 = c(X*)故不是最小故不是最小费费用最大流。用最大流。-3-35-5-5-1-1s12t1(b) W( F3-1-1-2-27.87.8网络规划的运用网络规划的运用 某公司有一个管道网络如图7-29所示，运用这个网络可以把石油从v1运到v7。由于输油管道长短不一，每段管道除了有不同的流量限制cij外，还有不同的单位流量的费用bij。图中每边上的数值表示cij ，bij。假设运用这个网络运送石油，怎样运送才干运送最多的石油，并使运送的费用最小？v1v3v

51、4v6v5v2v7(6,6)(6,3)(2,5)(3,2)(2,4)(2,3)(1,3)(2,8)(4,4)(5,7)图7-24. 运用问题图示 线性规划法求解线性规划法求解 第一步：先求出网络的最大流令vi，vj上的流量fij，那么最大流的数学模型为：Max F=f12+f14s.t. (f23+f25)- f12=0 (f35+f36)- (f23+f43)=0 (f43+f46+f47)- f14=0 f57 -(f25+f35) =0 f67- (f36+f46)=0 fij cij fij0图7-25. 运用问题电子表格求解图示1 用电子表格求解，可得最大流量为10，如图7-25所示

52、。线性规划法求解线性规划法求解第二步：在最大流量的一切解中，找出一个最小费用的解。数学模型为：Min z=6f12+3f14+4f25 +5f23+4f35 +3f36+2f43 +3f46+8f47 +7f57+4f67 s.t. f12+f14=10 (f23+f25)- f12=0 (f35+f36)- (f23+f43)=0 (f43+f46+f47)- f14=0 f57 -(f25+f35) =0 f67- (f36+f46)=0 0-(f47+f57+f67)=-10 fij cij fij0图7-26. 运用问题电子表格求解图示2用电子表格求解，可得最大流量为10，总费用为145。如图7-26所示