管理运筹学07-网络规划1

1、第七章网络规划,第七章网络规划,第一节：现实中的网络规划问题 第二节：图的基本概念 第三节：树 第四节：最大流问题 第五节：最短路径问题 第六节：最小费用最大流问题 第七节：网络计划技术 第八节：网络规划的应用,7.1现实中的网络规划问题,许多工程和管理的问题都可以用图与网络来描述，图与网络优化问题是一类应用十分广泛的问题。图与网络优化是线性规划等理论和算法在具有图结构的问题中的应用。由于图与网络问题具有特殊的结构，相应的优化算法也不同于一般的单纯形算法，具有其独特的直观和简捷的特点。,哥尼斯堡七桥问题,哥尼斯堡城有条河流，河中有两个小岛，河上共有七个桥，当地居民考虑这样一个问题：能否从某个地

2、点（任意点）出发经过七个桥，且每个桥只经过一次，最后回到出发地点。,哥尼斯堡七桥问题,欧拉在1736年发表了图论方面的第一篇论文，解决了哥尼斯堡的七桥问题。欧拉将此问题归结为下图所示的一笔画问题。也就是能否从某一点开始，不重复地一笔画出这个图形，最后回到原来出发点。,欧拉证明了这是不可能完成的。因为图形中的每个点都与奇数个线相关联，不可能将这样的图形不重复地一笔画出来，这是古典的图论中的一个著名问题。,7.2图的基本概念,7.2.1图: 由节点（Node）和边（Edge）组成。 节点和边是图中最基本的概念，我们不对其作出定义。下图中，有4个节点，7条边，每一条边都与2个节点对应。因此，一条边可

3、以用它的两个节点来标记。图7.3中的边，可以记为v1，v2，v1，v3，v2，v3，v3，v2，v2，v4，v3，v4，v4，v1。,图的定义,定义 设V=v1，v2，vm表示节点的集合，E=e1，e2，en表示边的集合，若对任一ekE，均有vi，vjV与之对应，则称VE为图，记为G=(V，E)。 称vi为G的顶点，ek为G的边，记为ek=vi，vj= vj，vi。称vi，vj为ek的端点，ek为vi，vj的关联边。称vi，vj为邻接点。 将图7.3用数学定义表示如下： G=(V，E) V=v1，v2，v3，v4 E=e1，e2，e3，e4，e5，e6， e1，e2，e3，e4，e5，e6，e

4、7=v1，v2，v1，v3，v2，v3，v3，v2，v2，v4，v3，v4，v4，v1 ,相关定义,如果图中一个边的两个端点为同一个点，称这样的边为环。如果两个点之间存在两个以上的边，称为多重边。一个没有环、也没有多重边的图，称为简单图。无环,允许有多重边的图称为多重图。本章讨论的图主要是指简单图。 图中的边是对节点的关系描述，所以我们讨论的图如果关系表示的相同，不论图的形状如何，我们认为这样的图都是相同的。 次: 以点v为端点的边的个数称为v的次， 表示为: d(v)。 悬挂点: 次为1的点。 悬挂边: 悬挂点的关联边。 孤立点: 次为0的点。 奇点: 次为奇数的点。 偶点: 次为偶数的点。

5、,两个定理,定理7-1: 图G=(V,E)中,所有点的次之和是边数的两倍, 即: 证明:计算各端点的次时，每个边都用了两次，所以次数的总和必然为边数的两倍。 定理7-2: 任意一图中, 奇点的个数为偶数。 证明:设 V1表示奇点的集合， V2表示偶点的集合。由有： 因为偶点的次之和为偶数，总数为偶数，所以奇点的次之和必须是偶数，只有偶数个奇数之和才能是偶数。所以奇点的个数必然为偶数个。,相关定义,链：点边交错系列， 记为： 如果满足 ，一般简记为： 圈： 的链。 初等链：点 均不相同。 初等圈：点 均不相同。 简单链：链中边均不相同。 简单圈：圈中边均不相同。 连通图：任意两点之间至少有一条链

6、。否则称为不连通图 连通分图：对不连通图，每一连通的部分称为一个连通分图。 支撑子图： 对G=（V，E），若G=(V,E), 使V=V, E E, 则G是G的一个支撑子图（生成子图）,7.2.2有向图,前面讨论的图中，边是没有方向的，ek=vi，vj= vj，vi。这样的图称为无向图。但许多实际问题用无向图表示是不够的。例如，涉及交通网络中单行道、一项工程的各工序的前后次序关系等。,定义 设V=v1，v2，vm表示节点的集合，A=a1，a2，an表示边的集合，若对任一akA，均有vi，vjV与之对应，则称VA为图，记为D=(V，A)。 称ak为D的弧，记为ak=（vi，vj）（vj，vi）。,

7、相关定义,始点和终点: 对弧a=(u,v), u为a的始点, v为a的终点。 基础图: 对D=(V, A), 去掉图上的箭头的无向图。 链: 点弧交错序列, 若在其基础图中对应一条链, 则称为 D的一条链。 路：若 是D中的一条链，且 ，t=1,2,k-1,称之为从 到 的一条路。 回路: 的路。 初等路: 路中点不相同。 初等回路: 回路中点不相同。,7.2.3 赋权图,如果给定一个图G=(V，E)或D=(V，A)的任一边（弧）有一个实数 与之相对应，由称这样的图为赋权无向（有向）图。 赋权图的应用是很广泛的。例如，在一个交通网络中，边的权数可以是两个点之间的距离，也可以表示两点之间的运输费

8、用、运输时间、运输能力等。在一个设备维修的图中，权数可以表示维修费用，在工程项目计划网络图中可以表示各工序的完成时间等。,在赋权图中的链（路）上所有边（弧）对应的权之和，称为链（路）的权。 一个连通图连同定义在其边集上的实函数一起，称为一个网络,7.2.4图的矩阵表示,图形虽然有直观等优点，但随着实际问题的大型化，大多数算法需要在计算机上运算和求解，计算机处理直观图形是比较困难的。以下介绍将图用矩阵表示，将图的几何形状转化为代数矩阵，可以方便计算机对图形的处理与运算。以下举例说明。 例7-1将下7-5用矩阵表示。,不考虑权时的矩阵表示如下 ：,两个端点之间有边记为1，无边相连则记为0，对角线上

9、记为0。这样得到一个对称的矩阵。,考虑权数时的矩阵表示为：,两个端点之间有边相连的，记上其权数，无边相连的记为，对称线上仍记为0。赋权无向图的矩阵也是对称矩阵。,例7-2将下7-6用矩阵表示。,考虑权数时的矩阵表示为：,赋权有向图的矩阵往往不是对称矩阵,7.3 树,树是一类特殊的图。例如连接五个乡镇的光纤网，可表示下图,树（Tree）：无圈的连通图称为树,图的支撑树,图的支撑树（Spanning Tree）:设图G有p个节点，q条边。由G中p个节点，p-1条边组成的树称为图G的支撑树，也称为图G的生成树。,图7-8 图7-5的一个支撑树,图7-9 图7-5的一个支撑树,树中只与一条边关联的节点

10、称为悬挂点。与悬挂节点关联的边称为悬挂边。图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中的所有边的权之和称为支撑树的权, 记为w(T): 例如图7-8的总的权为28，图7-9的总的权为13。 最小支撑树：图的权最小的支撑树，

11、即： 比如，在一个小区铺设光缆通讯网，只要各个楼都连通即可，希望用的光纤越少越好。,以下介绍三种求最小支撑树的方法,解法一：破圈法 解法二：避圈法 解法三：顶点扩充法,解法一：破圈法,例7-3设某个小区由六个楼组成，如图7-10，图上的数字为各相邻楼的距离（百米）。现要铺设光纤，试求光纤总长度最短的铺设方案。,用破圈法求解过程如下：,用破圈法求解过程如下：一般先找权数最大的边所在的圈,（1）找圈v1，v2 ，v4，v1或v1，v3 ，v4，v1去掉边v4，v1，,图7-11. 破圈法求解示意图（1）,（2）去掉边v4，v5 （3）去掉边v3，v6 （4）去掉边v3，v1,（5）去掉边v2，v5

12、。得图7-12。此时图中已不含圈，剩下的边构成了原网络的最小支撑树，也就是铺设光纤的最优方案。 最小树的权为： W(T*)=1+2+2+2+1=8,图7-12. 破圈法求解示意图（2）,解法二: 避圈法,避圈法与破圈法的思想相反，先将所有边的权按从小到大的次序排列，然后依次检查，如果某个边加到图上不会产生圈，就将其加上，否则就不加到图上。直到所有边都检查完为止。 在图7-9中加边的顺序为v1，v2、v4，v6、v2，v4、v3，v4、v5，v6，由于本图为6个点，加上5个边即完成。得到如图7-11的结果，与破圈法得到的结果相同。 一般来说，一个图可以有多个不同的最小支撑树，但它们的总权一定相同

13、。,解法三：顶点扩充法,顶点扩充法是先在图中任选一个点，记为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条，权数都

14、是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，v1相连的边有3条，其中权数最小的有1条，权数是2，将v3加入，得S=v4，v6，v5，v2，v1，v3。此时所有点都加入到S中，可以得到如图7-12的结果。,7.4最大流问题,在网络图中指定一个源节点和一个汇节点，源节点的供应量为f，汇节点的需求量为f，图中其他节点均为中转节点。图中各边（i，j）流量的下界Lij=0，上界cij 0（图7-13）。对于一个给定的图，各节点

15、流入、流出的流量保持平衡，各边上的流量为非负且不超过相应边的流量上界，求通过图的最大流量f的问题就是网络最大流问题。,现实中的许多系统都存在各种各样的流，如公路系统中的车辆流、水利系统中的水流、电力系统中的电流、生产系统中的产品流、金融系统中的货币流、服务系统中的顾客流、信息系统中的信息流等。,图7-13. 最大流示意图,7.4.1基本概念和基本定理,（一）网络与流 定义:有向图D=(V,A)，其中vs 表示始点，vt 表示终点，其余点为中间点，对每个弧对应一个权c(vi,vj)，称为弧(vi,vj)的容量，简写为cij 。称这样的赋权有向图为一个网络，记为D=(V,A,C) 。 一个网络图要

16、求只有一个始点、一个终点。,（二）可行流与最大流,对于网络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达到最大的可行流称为最大流。,网络最大流问题可以用线性规划方法求解,网络最大流问题可以用线性规划方法

17、求解。例如图7-13的最大流问题，设xij为各弧的流量，f表示可行流的流量。则此最大流问题的线性规划形式为：,（三）截集与截量,在网络D=(V,A,C)中，将点集V分成不相交的两个非空集合V1与 ，始点vs在V1中，终点vt在 中，则把起点在V1中且终点在中的弧构成的集合称为分离vs 和vt的截集，记为（V1， ） 将截集中所有弧的容量之和，称为截集的容量，简称为截量。记为：,截集截量的例子,图7-14,图7-15,图7-16,图7-17,截集的节点集合，所包含的弧以及截集容量,（V1，,C(V1，,截集是一种特殊的集合，如图7.16中（2，3）不包含在截集中。如果将任意一个截集中的所有弧去掉

18、，将不存在从网络始点到终点的路了，但可能存在从网络始点到终点的链。将截集容量最小的截集称为最小截集。如（1，2）（3，4），其截量为3。,相关定理,定理7-3： 网络任一可行流的流量f必定小于或等于网络中任一截集的容量。即： 定理7-4： 网络中从vs 到vt 的最大流的流量等于分离vs 和vt的最小截集的截量。 即:若 是一个最小截集，F*是最大流，最大流量为f*，则有图7-17.截集示意图,图7-18.截集示意图,（四）增广链,设是网络D中的一条从vs到vt的链，定义链的方向为从vs指向vt，则链上与链的方向一致的弧称为前向弧，其集合记为；链上与链的方向相反的弧称为后向弧，其集合记为- 。

19、,如图中，弧上的数字表示为（cij，fij），该流是一个可行流。其中的一条链=v1，v4，v5，v6，v7各弧分为如下两类： = ( v1，v4)，( v4，v5)，( v6，v7) - = ( v6，v5),增广链定义,对于一个可行流F，是从vs 到vt 的一条链，如果上的各条弧的流量满足以下条件： fij 0 当( vi，vj)- （后向弧不为零） 则称为关于可行流F的一个增广链。,调整策略,如果一个可行流存在增广链，就可以将可行流进行调整。 令 1 =min cij -fij | ( vi，vj) 2 =min fij | ( vi，vj)- = min1，2 再令 fij+ ( vi，

20、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的增广链。,最大流问题的标号法,此方法是福特和富尔克逊于1956年提出的，所以称为福特富尔克逊标号法。 （一）基本思想 从某一可行流 F（如零流）出发，按一定规则找出一条增广链，并按照前述的沿增广链进行流

21、量调整的方法去调整F，得到一个流量增大 的新可行流 F。重复上述做法直到找不出增广链为止，这时就得到一个最大流，同时还可以得到一个最小截集。,最大流问题的标号法,（二）基本步骤 1. 给始点 vs 标号（0，），则 vs 已标号待检查； 2. 取一个已标号待检查的点 vi对所有与 vi 相邻而未标号的点 vj 依次判断、执行如下手续： （1）若关联 vj 与 vi 的弧为(vi, vj)，则当该弧上的流量 fij 0 时, 给 vj 标号( -vi，b(vj)，其中 b(vj) = min b(vi)，fji 表示 (vi, vj) 弧上的流量的最大可减少量；而当 fji = 0 时, 不给

22、vj 标号；,最大流问题的标号法,当所有与 vi 相邻而未标号的点 vj 都执行完上述手续后，就说明点 vi 已检查完毕。vj为已标号未检查的点。 3. 重复 2的手续，可能出现两种结果： （1）终点 vt 得到标号。则从vt回溯标号点第一个标号，就能找出一条由标号点和相应的弧连接而成的从 vs 到 vt 的一条增广链 (F)，转 4； （2）所有标号点均已检查过，而vt又未得到标号。这说明不存在增广链，而当前的可行流即为最大流，计算出其流量，算法终止。 4. 取调整量 = b(vt) （即终点 vt 的第二个标号）,令 fij = fij + ， 对一切 (vi, vj) fij = fij

23、 - ， 对一切 (vi, vj) - 非增广链上的各弧流量 fij 不变。 5. 删除网络中原有一切标号，返回 1。 注：标号中的第一个标号表示给该点标号的点，第二个标号表示调整量。,例子,图7-20. 可行流（1）,(v1,3),(-v5,2),例子,上例中说明了标号法的基本思想，在解最大流问题时一般可以从零流出发，在图上直接给出标号，找到从vs到vt的一个增广链和相应的调整量，并进行流量的调整，重复以上步骤直到找不到增广链为止。即可得到最大流和最小截集。 最大流不一定是唯一的，但最大流的流量一定是唯一的；最小截集也不一定是唯一的，最小截量一定是唯一的，而且与最大流的流量是相同的。,7.5

24、最短路径问题,最短路问题就是在一个网络图中，给定一个起点vs和一个终点vt，寻找vs到vt的路，使该路为从vs到vt的所有路中权数最小的路。 实际问题中最短路问题有广泛的应用。例如管道铺设、线路安排、运输线路选择、工厂布局、设备更新等问题。 解法： 标号法 矩阵法,标号法,最短路的标号法是由狄克斯屈（E.W.Dijkstra）于1959年提出的，是目前公认的求解权数为非负的网络最短路问题较好的算法。这种算法能够求出网络中任意一点出发到其它各点的最短路。 算法的思想如下： 对每一个网络中的点vj，均赋予一个标号，永久标号P（vj）或临时标号T（vj）。其含义如下： P（vj）从起点vs到vj最短

25、路的长； T（vj）从起点vs到vj最短路的长的上界。 一个点只能有上述两种标号之一，如果有了P标号就不再改变了，如果有T标号则根据情况进行修改。,该算法的基本思想就是 先给vs点标号为P（vs）=0，其余点标号为T（vj）=；然后检查有P标号的点，对与该点有关联边的vj的T标号进行修改；在所有T标号中找一个最小的，将其T标号修改成P标号。再检查新得到P标号的点，修改其它点的T标号，再在所有T标号中找最小的修改为P标号；如此反复，直到要求的终点（或所有点）得到P标号为止，即可得到网络最短路。因为此算法一次修改一个P标号，所以如果网络中有N个点，最多经过N-1步就能找出要求的最短路。 为了寻找到

26、vs各点的最短路线，给每个顶点一个 值，算法终止时，如果 表示在从vs到vj的最短路上vj的前一个点为vm；若 ，则表示vs到vj不存在路则表示vj为起点。,Dijkstra方法的具体步骤为:,（1）给vs标上永久标号P(vs)=0，其余节点标上临时标号T(vj)=，同时给各点vj赋值如下： （2）若节点vi是刚得到P标号的点。把与vi有弧（边）直接相连而且有T标号的节点，对其T标号和 进行如下修改： 若T(vj)P（vi）+wij，则T(vj)=P（vi）+wij ； （3）把T标号中值最小的节点vj0的临时标号T(vj0)改为P(vj0)，如果所有点均有P标号、或要求的终点有P标号、或无法

27、继续修改时，则算法终止；否则转（2）。,例7-4 用标号法求v1到其它各点的最短路。,用表格的一行表示一个步骤，表格中的左上角表示P（T）标号，其中表示P标号；右下角表示 值,例7-4,到各点的最短路的长就是各点的P标号之值。到各点的最短路线可从该点的最后的值出发，逆序寻找其前一点的值，直到起点为止，即可得到从起点到该点的最短路线。 例如：P(v7)=9，说明从v1到v7的最短路长为9 （v7）=5 （v5）=6 （v6）=4 （v4）=3 （v3）=1 v7 v5 v6 v4 v3 v1,对于无负权的无向图来说，标号法的程序也是相同的。,矩阵法,当一个网络存在负权时，Dijkstra算法会失

28、效。如图7-23,图7-23. 负权网络,从v到v3的最短路长为-1，而不是2。,矩阵法的基本思想是利用本章第一节中介绍的网络图的矩阵表示，其中的wsj表示从vs经一步到vj的权，可记为：,则从vs经K步到达vj的权为：,一般，经K步从vs经两步到达vj的权为,矩阵法,k-1步,1步,由于 的计算就是n 个对应元素的求和取小，这与矩阵的乘法的计算是相类似的，所以此算法也称矩阵摹乘法。,当（j=1,2,n）时，说明从的最短路的权不能再减少，所以（j=1,2,n）即为的最短路的权。,第8章 网络分析,52,最短路问题,0 3 2 4 0 4 4 1 0 -1 6 3 -2 0 1 5 0 3 3

29、3 0,W =,例,从至,1 2 3 4 5 6,1 2 3 4 5 6,第8章 网络分析,53,最短路问题,二、求各点至某点的最短路,dk=,负回路,dk=w* dk-1 ， k=2，3, ,n -1,dk= dk-1 则也结束,若不含负回路， 至多算到 dn-1。,* 运算：两矩阵对应元素求和取小。 两矩阵元素对应方式，同矩阵乘法。,wij,第8章 网络分析,54,最短路问题,*,从至,1 2 3 4 5 6,1 2 3 4 5 6,d2,d1,d3,d4,d5,4,1,9,-1,3,0,= min 0+4, 3+1, 2+, +, +3, 4+0,0 3 2 4,4 1 3 0,= 4,

30、 0 4 4 1, 0 -1 6 ,3 -2 0 1 ,5 0 3, 3 3 0,第8章 网络分析,55,最短路问题,2,1,-1,-2,0,3,4,2,6,2,6,6,最 短 路,按W阵中画圈元素的从至关系,0 1 -2 -1 3 0,最短路长,0,2,-1,-2,+1,= 0,第8章 网络分析,56,最短路问题,3,1,3,4,1,1,0 -1 2 1 2 0,最 短 路,最短路长,l2T=,l1T * W =,( 0 3 2 4 ),*,( 0 3 2 1 7 4 ),( 0 -1 2 1 2 4 ),( 0 -1 2 1 2 0 ),( 0 -1 2 1 2 0 ),l3T=,l4T=

31、,l5T=,3,1,-1,1,1,三、 求某点至各点的最短路,2,最短路径问题的线性规划形式,设一个图G中wij为节点i到节点j的距离，求节点1到节点m的最短路径。这就是图最短路径问题。 设节点1为供应节点，供应量b1=1，节点m为需求节点，需求量bm=-1，其他节点i均为转运节点，bi=0。,7.6最小费用最大流问题,第三节讨论了网络最大流问题，在实际中涉及流的问题时，人们考虑的不只是流量，同时要考虑“费用”的因素。 对D=(V,A,C), 给定一个单位流量的费用bij0, 最小费用最大流即:求一最大流f, 使,增广链的费用,最大流的算法是从某个可行流出发，寻找关于可行流的增广链，然后沿着增

32、广链调整可行流的流量，得到一个新的可行流，反复以上过程即可得到最大流。 对于增广链, 若调整流量=1, 那么新可行流F的费用比原可行流F的费用增加量为: 称为增广链的费用。,可以证明，若F是流量为f的所有可行流中费用最小的，而是关于F的费用最小的增广链，那么沿着增广链去调整流量，得到的新可行流F，就是流量为f的费用最小的可行流。这样当F为最大流时，也就是所求的最小费用最大流。,基本思想,由于bij0，所以零流的费用总是最小的。所以可以从零流出发去寻找最小费用最大流。 这里主要需要解决的问题就是如何寻找关于F的费用最小的增广链。为此，可构造网络图D的相对应的赋权有向图W（F），其节点与原网络图D相同，将D中的每一条弧（，）都变成两方向相反的弧（，）与（，）定义W（F）中弧的权为： 权数为的弧表示不能通过，可以在W（F）中省略。 这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。,权数为的弧表示不能通过，可以在W（F）中省略。,具体算法,这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。 具体算法为：从零流出发，构造其W（F），在W（F