1、第七章网络规划第七章网络规划第一节：现实中的网络规划问题第一节：现实中的网络规划问题第二节：图的基本概念第二节：图的基本概念 第三节：树第三节：树 第四节：最大流问题第四节：最大流问题 第五节：最短路径问题第五节：最短路径问题 第六节：最小费用最大流问题第六节：最小费用最大流问题第七节：网络计划技术第七节：网络计划技术第八节：网络规划的应用第八节：网络规划的应用7.17.1现实中的网络规划问题许多工程和管理的问题都可以用图与网络来描述，图与网络优化问题是一类应用十分广泛的问题。图与网络优化是线性规划等理论和算法在具有图结构的问题中的应用。由于图与网络问题具有特殊的结构，相应的优化算法也不同于一
2、般的单纯形算法，具有其独特的直观和简捷的特点。哥尼斯堡七桥问题哥尼斯堡七桥问题 哥尼斯堡城有条河流，河中有两个小岛，河上共有七个桥，当地居民考虑这样一个问题：能否从某个地点（任意点）出发经过七个桥，且每个桥只经过一次，最后回到出发地点。哥尼斯堡七桥问题哥尼斯堡七桥问题欧拉在1736年发表了图论方面的第一篇论文，解决了哥尼斯堡的七桥问题。欧拉将此问题归结为下图所示的一笔画问题。也就是能否从某一点开始，不重复地一笔画出这个图形，最后回到原来出发点。BACD欧拉证明了这是不可能完成的。因为图形中的每个点都与奇数个线相关联，不可能将这样的图形不重复地一笔画出来，这是古典的图论中的一个著名问题。7.27
3、.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=v1，v2，vm表示节点的集合，E=e1，e2，en表示边的集合，若对任一ekE，均有vi，vjV与之对应，则称VE为图，记为G=(V，E)。称vi为G的顶点顶点，ek为G的边边，记为e
4、k=vi，vj=vj，vi。称vi，vj为ek的端点端点，ek为vi，vj的关联边关联边。称vi，vj为邻接点邻接点。将图7.3用数学定义表示如下：G=(V，E)V=v1，v2，v3，v4E=e1，e2，e3，e4，e5，e6，e1，e2，e3，e4，e5，e6，e7=v1，v2，v1，v3，v2，v3，v3，v2，v2，v4，v3，v4，v4，v1 相关定义相关定义如果图中一个边的两个端点为同一个点，称这样的边为环环。如果两个点之间存在两个以上的边，称为多重边多重边。一个没有环、也没有多重边的图，称为简单图简单图。无环,允许有多重边的图称为多重图多重图。本章讨论的图主要是指简单图。图中的边是
5、对节点的关系描述，所以我们讨论的图如果关系表示的相同，不论图的形状如何，我们认为这样的图都是相同的。次次:以点v为端点的边的个数称为v的次，表示为:d(v)。悬挂点悬挂点:次为1的点。悬挂边悬挂边:悬挂点的关联边。孤立点孤立点:次为0的点。奇点奇点:次为奇数的点。偶点偶点:次为偶数的点。两个定理两个定理定理定理7-1:7-1:图G=(V,E)中,所有点的次之和是边数的两倍,即:证明:计算各端点的次时，每个边都用了两次，所以次数的总和必然为边数的两倍。定理定理7-2:7-2:任意一图中,奇点的个数为偶数。证明:设 V1表示奇点的集合，V2表示偶点的集合。由有：因为偶点的次之和为偶数，总数为偶数，
6、所以奇点的次之和必须是偶数，只有偶数个奇数之和才能是偶数。所以奇点的个数必然为偶数个。qvdVv2)(qvdvdvdVvVvVv2)()()(21相关定义相关定义链链：点边交错系列，记为：如果满足 ，一般简记为：圈圈：的链。的链。初等链初等链：点 均不相同。初等圈初等圈：点 均不相同。简单链简单链：链中边均不相同。简单圈简单圈：圈中边均不相同。连通图连通图：任意两点之间至少有一条链。否则称为不连通图不连通图连通分图连通分图：对不连通图，每一连通的部分称为一个连通分图。支撑子图支撑子图：对G=（V，E），若G=(V,E),使V=V,E E,则G是G的一个支撑子图（生成子图）),.,(11211k
7、kkiiiiiivevvevkiivv 1kiiivvv,.,21121,.,kiiivvv,1ttktiiivve),.,(121kkiiiivvvv7.2.27.2.2有向图有向图前面讨论的图中，边是没有方向的，ek=vi，vj=vj，vi。这样的图称为无向图。但许多实际问题用无向图表示是不够的。例如，涉及交通网络中单行道、一项工程的各工序的前后次序关系等。v3v1v4v2a1a2a3a4a5a6a7定义定义 设V=v1，v2，vm表示节点的集合，A=a1，a2，an表示边的集合，若对任一akA，均有vi，vjV与之对应，则称VA为图图，记为D=(V，A)。称ak为D的弧弧，记为ak=（v
8、i，vj）（vj，vi）。相关定义相关定义始点和终点始点和终点:对弧a=(u,v),u为a的始点,v为a的终点。基础图基础图:对D=(V,A),去掉图上的箭头的无向图。链链:点弧交错序列,若在其基础图中对应一条链,则称为 D的一条链。路路：若 是D中的一条链，且 ，t=1,2,k-1,称之为从 到 的一条路。回路回路:的路。初等路初等路:路中点不相同。初等回路初等回路:回路中点不相同。),.,(112211kkkiiiiiiivavavav),(1tttiiivva1ivkivkiivv 17.2.3 7.2.3 赋权图赋权图 如果给定一个图G=(V，E)或D=(V，A)的任一边（弧）有一个实
9、数 与之相对应，由称这样的图为赋权无向（有向）图。赋权图的应用是很广泛的。例如，在一个交通网络中，边的权数可以是两个点之间的距离，也可以表示两点之间的运输费用、运输时间、运输能力等。在一个设备维修的图中，权数可以表示维修费用，在工程项目计划网络图中可以表示各工序的完成时间等。ijw1354256-2023-44在赋权图中的链（路）上所有边（弧）对应的权之和，称为链（路）的权链（路）的权。一个连通图连同定义在其边集上的实函数一起，称为一个网络网络7.2.47.2.4图的矩阵表示图的矩阵表示 图形虽然有直观等优点，但随着实际问题的大型化，大多数算法需要在计算机上运算和求解，计算机处理直观图形是比较
10、困难的。以下介绍将图用矩阵表示，将图的几何形状转化为代数矩阵，可以方便计算机对图形的处理与运算。以下举例说明。例例7-17-1将下7-5用矩阵表示。不考虑权时的矩阵表示如下不考虑权时的矩阵表示如下 ：V1V2V3V4V5V6V7V10111000V21011100V31100110V41100101V50111011V60010101V70001110两个端点之间有边记为1，无边相连则记为0，对角线上记为0。这样得到一个对称的矩阵。考虑权数时的矩阵表示为：考虑权数时的矩阵表示为：V1V2V3V4V5V6V7V10347V230324V343057V472026V5452014V670102V7
11、6420两个端点之间有边相连的，记上其权数，无边相连的记为，对称线上仍记为0。赋权无向图的矩阵也是对称矩阵。例例7-27-2将下7-6用矩阵表示。312453564357考虑权数时的矩阵表示为：考虑权数时的矩阵表示为：赋权有向图的矩阵往往不是对称矩阵V1V2V3V4V5V1053V2054V3607V40V5307.3 7.3 树树 树是一类特殊的图。例如连接五个乡镇的光纤网，可表示下图31245树（树（Tree）：无圈的连通图称为树图的支撑树图的支撑树 图的支撑树图的支撑树（Spanning TreeSpanning Tree）:设图G有p个节点，q条边。由G中p个节点，p-1条边组成的树称
12、为图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的一个支撑树,E中的所有
13、边的权之和称为支撑树的权,记为w(T):例如图7-8的总的权为28，图7-9的总的权为13。最小支撑树：最小支撑树：图的权最小的支撑树，即：比如，在一个小区铺设光缆通讯网，只要各个楼都连通即可，希望用的光纤越少越好。TvvijjiwTw,)()()(min*TwTwT以下介绍三种求最小支撑树的方法以下介绍三种求最小支撑树的方法解法一：破圈法解法一：破圈法解法二：避圈法解法二：避圈法 解法三：顶点扩充法解法三：顶点扩充法解法一：破圈法例例7-37-3设某个小区由六个楼组成，如图7-10，图上的数字为各相邻楼的距离（百米）。现要铺设光纤，试求光纤总长度最短的铺设方案。153232213v4v2v1
14、v5v64v3用破圈法求解过程如下：用破圈法求解过程如下：用破圈法求解过程如下：一般先找权数最大的边所在的圈（1）找圈v1，v2，v4，v1或v1，v3，v4，v1去掉边v4，v1，13232213v4v2v1v5v64v3图7-11.破圈法求解示意图（1）（2）去掉边v4，v5（3）去掉边v3，v6（4）去掉边v3，v1（5）去掉边v2，v5。得图7-12。此时图中已不含圈，剩下的边构成了原网络的最小支撑树，也就是铺设光纤的最优方案。最小树的权为：W(T*)=1+2+2+2+1=812221v2v1v5v6v4v3图7-12.破圈法求解示意图（2）解法二解法二:避圈法避圈法避圈法与破圈法的思
15、想相反，先将所有边的权按从小到大的次序排列，然后依次检查，如果某个边加到图上不会产生圈，就将其加上，否则就不加到图上。直到所有边都检查完为止。在图7-9中加边的顺序为v1，v2、v4，v6、v2，v4、v3，v4、v5，v6，由于本图为6个点，加上5个边即完成。得到如图7-11的结果，与破圈法得到的结果相同。一般来说，一个图可以有多个不同的最小支撑树，但它们的总权一定相同。解法三：顶点扩充法解法三：顶点扩充法顶点扩充法是先在图中任选一个点，记为S=a1，以该点为出发点，将与其相连的最小权的边加入图中，将相关连的点加入到S中，得到S=a1，a2；再寻找与S中的点相连的边中权数最小的边加入图中，将
16、相关连的点加入到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，v5，v2；与S=v4，v6，v5，v2相连的边有4条，其中权数最小的有1条，权数是1，将v1加入，得S=v4，v6，v5，v2，v1；与S=v4，v6，v5，v2
17、，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）。对于一个给定的图，各节点流入、流出的流量保持平衡，各边上的流量为非负且不超过相应边的流量上界，求通过图的最大流量f的问题就是网络最大流问题。现实中的许多系统都存在各种各样的流，如公路系统中
18、的车辆流、水利系统中的水流、电力系统中的电流、生产系统中的产品流、金融系统中的货币流、服务系统中的顾客流、信息系统中的信息流等。23411342f2cij图7-13.最大流示意图7.4.17.4.1基本概念和基本定理基本概念和基本定理 （一）网络与流（一）网络与流定义:有向图D=(V,A)，其中vs 表示始点始点，vt 表示终点终点，其余点为中间点，对每个弧对应一个权c(vi,vj)，称为弧(vi,vj)的容容量量，简写为cij。称这样的赋权有向图为一个网络网络，记为D=(V,A,C)。一个网络图要求只有一个始点、一个终点。（二）可行流与最大流（二）可行流与最大流对于网络D=(V,A,C)中的
19、每个弧(vi,vj)定义一个实数fij，称为弧(vi，vj)上的流量。流量。则集合 F=fij(vi,vj)A称为此网络的一个流流满足以下条件的F=fij(vi,vj)A称为一个可行流可行流：称为可行流的流量有对有对有对平衡条件（对容量限制条件ffffvfffvfftsivcfAvvAvvjtAvvtjtAvvjsAvvsjsAvvjiAvvijiijijjitjjtsjjsijji),(),(),(),(),(),(:0:,:)20 ),:)1也就是说，一个可行流的每个弧上的流量不超过该弧的容量、中间点流入量与流出量相等、始点的净流出量与终点的净流入量相同。可行流总是存在的，例如所有的fij
20、=0的流F=fij=0(vi,vj)A即是一个可行流，称为零流零流。在一个网络中，使f达到最大的可行流称为最大流最大流。网络最大流问题可以用线性规划方法求解网络最大流问题可以用线性规划方法求解 网络最大流问题可以用线性规划方法求解。例如图7-13的最大流问题，设xij为各弧的流量，f表示可行流的流量。则此最大流问题的线性规划形式为：23411342f2cijijijcxfxxxxxxxxfxxt sfz040302010.max34243423132423121312节点节点节点节点（三）截集与截量（三）截集与截量 在网络D=(V,A,C)中，将点集V分成不相交的两个非空集合V1与 ，始点vs
21、在V1中，终点vt在 中，则把起点在V1中且终点在中的弧构成的集合称为分离vs 和vt的截集截集，记为（V1，）将截集中所有弧的容量之和，称为截集的容量截集的容量，简称为截量截量。记为：),(),(1111),(VVjiijcVVC1V1V1V1V截集截量的例子截集截量的例子23411342f2cij23411342f2cij23411342f2cij23411342f2cij图7-14图7-15图7-16图7-17截集的节点集合，所包含的弧以及截集容量截集的节点集合，所包含的弧以及截集容量 1V1V1V（V1，C(V1，V1（V1，）C(V1，)图7-141，23，4（1，3）（2，3）（2
22、，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（2，4）（3，4）c24+c34=3+2=51V1V1V截集是一种特殊的集合，如图7.16中（2，3）不包含在截集中。如果将任意一个截集中的所有弧去掉，将不存在从网络始点到终点的路了，但可能存在从网络始点到终点的链。将截集容量最小的截集称为最小截集最小截集。如（1，2）（3，4），其截量为3。相关定理相关定理定理定理7-37-3：网络任一可行流的流量f必定小于或等于网络中任一截集的容量。即：定
23、理定理7-47-4：网络中从vs 到vt 的最大流的流量等于分离vs 和vt的最小截集的截量。即:若 是一个最小截集，F*是最大流，最大流量为f*，则有图图7-17.7-17.截集示意图截集示意图),(min111kkSkVVCf),(*1*1VV),(*1*1*VVCffsiejmkV1f图7-18.截集示意图1V（四）增广链（四）增广链设是网络D中的一条从vs到vt的链，定义链的方向为从vs指向vt，则链上与链的方向一致的弧称为前向弧前向弧，其集合记为；链上与链的方向相反的弧称为后向弧后向弧，其集合记为-。1534762(4,4)(10,7)(4,4)(8,1)(1,1)(8,4)(6,3
24、)(7,7)(2,2)(3,3)(3,3)(10,5)如图中，弧上的数字表示为（cij，fij），该流是一个可行流。其中的一条链=v1，v4，v5，v6，v7各弧分为如下两类：=(v1，v4)，(v4，v5)，(v6，v7)-=(v6，v5)增广链定义增广链定义对于一个可行流对于一个可行流F F，是从是从v vs s 到到v vt t 的一条链，如果的一条链，如果 上的各条上的各条弧的流量满足以下条件：弧的流量满足以下条件：f fij ij c 0 0 当当(v(vi i，v vj j)-（后向弧不为零）（后向弧不为零）则称则称 为关于可行流为关于可行流F F的一个的一个增广链增广链。调整策略
25、调整策略如果一个可行流存在增广链，就可以将可行流进行调整。令 1=min cij-fij|(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的增广链。最大流问题的标号法最大流问题的
26、标号法 此方法是福特和富尔克逊于1956年提出的，所以称为福特富尔克逊标号法。（一）（一）基本思想 从某一可行流 F（如零流）出发，按一定规则找出一条增广链，并按照前述的沿增广链进行流量调整的方法去调整F，得到一个流量增大 的新可行流 F。重复上述做法直到找不出增广链为止，这时就得到一个最大流，同时还可以得到一个最小截集。最大流问题的标号法最大流问题的标号法（二）基本步骤1.给始点 vs 标号（0，），则 vs 已标号待检查；2.取一个已标号待检查的点 vi对所有与 vi 相邻而未标号的点 vj 依次判断、执行如下手续：（1 1）若关联）若关联 v vj j 与与 v vi i 的弧为的弧为(
27、v(vi i,v,vj j)，则当该弧上的流量，则当该弧上的流量 f fij ij c 0 0 时时,给给 v vj j 标号标号(-v(-vi i，b(vb(vj j)，其中，其中 b(vb(vj j)=min b(v)=min b(vi i)，f fji ji 表示(vi,vj)弧上的流量的最大可减少量；而当 fji=0 时,不给 vj 标号；最大流问题的标号法最大流问题的标号法当所有与 vi 相邻而未标号的点 vj 都执行完上述手续后，就说明点 vi 已检查完毕。vj为已标号未检查的点。3.重复 2的手续，可能出现两种结果：（1）终点 vt 得到标号。则从vt回溯标号点第一个标号，就能找
28、出一条由标号点和相应的弧连接而成的从 vs 到 vt 的一条增广链(F)，转 4；（2）所有标号点均已检查过，而vt又未得到标号。这说明不存在增广链，而当前的可行流即为最大流，计算出其流量，算法终止。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)
29、(3,3)(10,5)(0,)1(v1,7)(-v4,3)(v4,4)(v6,2)图7-20.可行流（1）(v1,3)(-v5,2)例子例子 图7-21.可行流（2）534762(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的一个增广链和相应的调整量，并进行流量的调整，重复以上步骤直到找不到增广链为止。即可得到最大流和最小截集。最大流不一定是唯一的，但最大流
30、的流量一定是唯一的；最小截集也不一定是唯一的，最小截量一定是唯一的，而且与最大流的流量是相同的。7.57.5最短路径问题最短路径问题 最短路问题就是在一个网络图中，给定一个起点vs和一个终点vt，寻找vs到vt的路，使该路为从vs到vt的所有路中权数最小的路。实际问题中最短路问题有广泛的应用。例如管道铺设、线路安排、运输线路选择、工厂布局、设备更新等问题。解法：标号法矩阵法 标号法标号法最短路的标号法是由狄克斯屈（E.W.Dijkstra）于1959年提出的，是目前公认的求解权数为非负的网络最短路问题较好的算法。这种算法能够求出网络中任意一点出发到其它各点的最短路。算法的思想算法的思想如下：对
31、每一个网络中的点vj，均赋予一个标号，永久标号P（vj）或临时标号T（vj）。其含义如下：P（vj）从起点vs到vj最短路的长；T（vj）从起点vs到vj最短路的长的上界。一个点只能有上述两种标号之一，如果有了P标号就不再改变了，如果有T标号则根据情况进行修改。该算法的基本思想就是先给vs点标号为P（vs）=0，其余点标号为T（vj）=；然后检查有P标号的点，对与该点有关联边的vj的T标号进行修改；在所有T标号中找一个最小的，将其T标号修改成P标号。再检查新得到P标号的点，修改其它点的T标号，再在所有T标号中找最小的修改为P标号；如此反复，直到要求的终点（或所有点）得到P标号为止，即可得到网络
32、最短路。因为此算法一次修改一个P标号，所以如果网络中有N个点，最多经过N-1步就能找出要求的最短路。为了寻找到vs各点的最短路线，给每个顶点一个 值，算法终止时，如果 表示在从vs到vj的最短路上vj的前一个点为vm；若 ，则表示vs到vj不存在路则表示vj为起点。,)(mvjMvj)(DijkstraDijkstra方法的具体步骤为方法的具体步骤为:（1）给vs标上永久标号P(vs)=0，其余节点标上临时标号T(vj)=，同时给各点vj赋值如下：（2）若节点vi是刚得到P标号的点。把与vi有弧（边）直接相连而且有T标号的节点，对其T标号和 进行如下修改：若T(vj)P（vi）+wij，则T(
33、vj)=P（vi）+wij；（3）把T标号中值最小的节点vj0的临时标号T(vj0)改为P(vj0)，如果所有点均有P标号、或要求的终点有P标号、或无法继续修改时，则算法终止；否则转（2）。0)()()(ssjjsjjvvvMvvvvTivj)(例例7-4 7-4 用标号法求用标号法求v1v1到其它各点的最短路。到其它各点的最短路。步骤V1V2V3V4V5V6V7V800 0MM MMMMM151316 1MMMM2514 3M103MM3518464MM48464MM576126M695M7M15347627356422121681用表格的一行表示一个步骤，表格中的左上角表示P（T）标号，其
34、中表示P标号；右下角表示 值例例7-47-4到各点的最短路的长就是各点的P标号之值。到各点的最短路线可从该点的最后的值出发，逆序寻找其前一点的值，直到起点为止，即可得到从起点到该点的最短路线。例如：P(v7)=9，说明从v1到v7的最短路长为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无对于无负权的无向图来说，标号法的程序也是相同的。矩阵法矩
35、阵法 当一个网络存在负权时，Dijkstra算法会失效。如图7-23 13232-3 图7-23.负权网络从v到v3的最短路长为-1，而不是2。(1)(,)sjsjdvvw),(min),()1()2(ijisjswvvdvvd),(min),()1()(ijiskjskwvvdvvd矩阵法的基本思想是利用本章第一节中介绍的网络图的矩阵表示，其中的wsj表示从vs经一步到vj的权，可记为：则从vs经K步到达vj的权为：一般，经K步从vs经两步到达vj的权为矩阵法矩阵法Sj1in),()1(iskvvdk-1步 1步 ijwnjnskjskjskjskwvvdwvvdwvvdvvd),(),()
36、,(min),()1(22)1(11)1()(),(min)1(ijiskwvvd),(),()1()(jskjskvvdvvdjsvv 到),(),()1()(jskjskvvdvvdjsvv 到由于 的计算就是n 个对应元素的求和取小求和取小，这与矩阵的乘法的计算是相类似的，所以此算法也称矩阵摹乘法矩阵摹乘法。当（j=1,2,n）时，说明从的最短路的权不能再减少，所以（j=1,2,n）即为的最短路的权。第8章 网络分析52 0 3 2 0 3 2 4 4 0 4 0 4 4 4 1 1 0 0 -1 -1 6 6 3 -2 3 -2 0 1 0 1 5 5 0 30 3 3 3 3 3 0
37、 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 6 1 1 3 3 4 4 6 6 2 2 5 5 34253-24413613-13第8章 网络分析53二、二、求各点求各点至某点至某点的最短路的最短路 1 n r j 1步步k-1步步dk=d(k)1r.d(k)ir.d(k)nr 1 1 2 2 3 3 负回路负回路d(k)=min wij+d(k-1)1j n irjr dk=w dk-1 ，k=2，3,dk=dk-1 则也则也结束结束若不含若不含负回路负回路，至多算到至多算到 dn-1。：两矩阵两矩阵对应元素对应元素求和
38、求和取小。取小。两矩阵两矩阵元素对应方式，元素对应方式，矩阵乘法。矩阵乘法。wijd(k-1)jr第8章 网络分析54*4 4 1 1 3 3 0 0W *d d1 1 =0 0 3 3 2 2 4 4 0 0 4 4 4 4 1 1 0 -1 6 0 -1 6 3 3 -2 -2 0 0 1 1 5 5 0 0 3 3 3 3 3 3 0 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
39、 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=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第8章 网络分析55*4 4 1 1 3 3 0 0W *d d1 1 =0 0 3 3 2 2 4 4 0 0 4 4 4 4 1 1 0 -1 6 0 -1 6 3 3 -2 -2 0 0 1 1 5 5 0 0 3 3 3 3 3 3 0 04 4 1 1 -2-2 -1 -1 3 3 0 0
40、 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-203 4 4 2 2 6 6 2 2 6 6 6 6最最 短短 路路 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阵中画圈元素的阵中画圈元素的从从 至至关系关系0 0 1 1 -2-2 -1 -1 3 3 0 0最短路长最短路长 1 1 3 3 4 4 6 6
41、2 2 5 5 34253-24413613-132-1-2+1=0第8章 网络分析56 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 l2T=l1 1T T*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 0 3 3 2 2 4 4 0 0 4 4 4 4 1 1 0 0 -1 -1 6 6 3 3 -2 2 0 0 1 1 5 5 0 30 3
42、3 3 3 3 0 0(0 0 3 3 2 2 4 4)*(0 0 3 3 2 2 1 7 4)1 7 4)(0 0 -1 1 2 2 1 2 4)1 2 4)(0 0 -1-1 2 2 1 2 01 2 0)(0 0 -1-1 2 2 1 2 01 2 0)l3T=l4T=l5T=3 3 1 1-1 11 11 1三、三、求求某点至某点至各点的最短路各点的最短路2 2最短路径问题的线性规划形式最短路径问题的线性规划形式设一个图G中wij为节点i到节点j的距离，求节点1到节点m的最短路径。这就是图最短路径问题。设节点1为供应节点，供应量b1=1，节点m为需求节点，需求量bm=-1，其他节点i均
43、为转运节点，bi=0。1,0,11101.min),(),(),(ijGikkiGjiijGjiijijxmimiixxtsxwz7.67.6最小费用最大流问题最小费用最大流问题 第三节讨论了网络最大流问题，在实际中涉及流的问题时，人们考虑的不只是流量，同时要考虑“费用”的因素。对D=(V,A,C),给定一个单位流量的费用bij0,最小费用最最小费用最大流大流即:求一最大流f,使Avvijijjifbfbfb),()(min*)(增广链增广链 的费用的费用 最大流的算法是从某个可行流出发，寻找关于可行流的增广链，然后沿着增广链调整可行流的流量，得到一个新的可行流，反复以上过程即可得到最大流。对
44、于增广链,若调整流量=1,那么新可行流F的费用比原可行流F的费用增加量为:称为增广链增广链 的费用。的费用。ijijbbFbFb)()(可以证明，若F是流量为f的所有可行流中费用最小的，而是关于F的费用最小的增广链，那么沿着增广链去调整流量，得到的新可行流F，就是流量为f的费用最小的可行流。这样当F为最大流时，也就是所求的最小费用最大流。基本思想基本思想由于bij0，所以零流的费用总是最小的。所以可以从零流出发去寻找最小费用最大流。这里主要需要解决的问题就是如何寻找关于F的费用最小的增广链。为此，可构造网络图D的相对应的赋权有向图W（F），其节点与原网络图D相同，将D中的每一条弧（，）都变成两
45、方向相反的弧（，）与（，）定义W（F）中弧的权为：权数为的弧表示不能通过，可以在W（F）中省略。这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。0 0 ijijijjiijijijijijijffbwcfcfbw权数为的弧表示不能通过，可以在W（F）中省略。具体算法具体算法 这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。具体算法为：从零流出发，构造其W（F），在W（F）中寻找最短路，在F中对应一个增广链，增广链的调整量由下式确定：沿增广链，对流量进行调整，调整方法同最大流的调整方法。然后对新得到的可行流继续做
46、前述的工作，直到在赋权有向图W（F）中找不到从始点到终点的最短路（也就是在网络图D中不存在增广链）为止，即可得到最小费用最大流。),(),(),()(min),(minmin)1()1()1()1()1(jikijjikijjikijkijkijkijijvvfvvfvvffffc第8章 网络分析62例例 在右图中，求最小费用最大流。在右图中，求最小费用最大流。弧旁数字为：弧旁数字为：b bij，c cij3,75,62,81,4s12t1,6解解 取取零流零流 F0为初始流。为初始流。3,7,05,6,02,8,0 1,4,0s12t1,6,0(a)F03521s12t1(b)W(F0）第8
47、章 网络分析633,7,05,6,02,8,41,4,4s12t1,6,4(a)F1352-1s12t1(b)W(F1）-1-23,7,45,6,02,8,8 1,4,4s12t1,6,4(a)F235-3-1s12t1(b)W(F2）-1-2第8章 网络分析64 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,5,6,2,8,1,4,s12t1,6,(a)F 亦亦最大流，最大流，f(F)=11但但b(F)=59 57=c(X*)故不是故不是最小费用最小费用最大流最大流。-
48、35-5-1s12t1(b)W(F3）-1-27.87.8网络规划的应用网络规划的应用 某公司有一个管道网络如图7-29所示，使用这个网络可以把石油从v1运到v7。由于输油管道长短不一，每段管道除了有不同的流量限制cij外，还有不同的单位流量的费用bij。图中每边上的数值表示（cij，bij）。如果使用这个网络运送石油，怎样运送才能运送最多的石油，并使运送的费用最小？v1v3v4v6v5v2v7(6,6)(6,3)(2,5)(3,2)(2,4)(2,3)(1,3)(2,8)(4,4)(5,7)图7-24.应用问题图示 线性规划法求解线性规划法求解 第一步：先求出网络的最大流令（vi，vj）上的
49、流量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所示。线性规划法求解线性规划法求解第二步：在最大流量的所有解中，找出一个最小费用的解。数学模型为：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所示
