网络规划(运筹学)

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

2、71。当地居民考虑这样一个问题：能否从某个地点（任意点）出发经过七个桥，且每个桥只经过一次，最后回到出发地点。 图图7-1.7-1.哥尼斯堡七桥问题哥尼斯堡七桥问题欧拉在1736年发表了图论方面的第一篇论文，解决了哥尼斯堡的七桥问题。欧拉将此问题归结为图72所示的一笔画问题。也就是能否从某一点开始，不重复地一笔画出这个图形，最后回到原来出发点。 BACD图图7-2.7-2.一笔画问题一笔画问题欧拉证明了这是不可能完成的。因为图形中的每个点都与奇数个线相关联，不可能将这样的图形不重复地一笔画出来，这是古典的图论中的一个著名问题。 7.2.1图图: 由节点（Node）和边（Edge）组成。节点和边

3、是图中最基本的概念，我们不对其作出定义。图7-3的图中，有4个节点，7条边，每一条边都与2个节点对应。因此，一条边可以用它的两个节点来标记。图7.3中的边，可以记为v1，v2，v1，v3，v2，v3，v3，v2，v2，v4，v3，v4，v4，v1。 v3 v1 v4 v2 e1e2e3e4e5e6图图7-3. 7-3. 无向图无向图定义定义 设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

4、为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的一个支撑子图（生成子图）),.,(11211kkkiiiiiivevvevkiivv 1kiiivvv

7、,.,21121,.,kiiivvv,1ttktiiivve),.,(121kkiiiivvvv前面讨论的图中，边是没有方向的，ek=vi，vj= vj，vi。这样的图称为无向图。但许多实际问题用无向图表示是不够的。例如，涉及交通网络中单行道、一项工程的各工序的前后次序关系等。 v3v1v4v2图7-4.有向图a1a2a3a4a5a6a7定义定义 设V=v1，v2，vm表示节点的集合，A=a1，a2，an表示边的集合，若对任一akA，均有vi，vjV与之对应，则称VA为图图，记为D=(V，A)。称ak为D的弧弧，记为ak=（vi，vj）（vj，vi）。 始点和终点始点和终点: : 对弧a=(u

8、,v), u为a的始点, v为a的终点。基础图基础图: : 对D=(V, A), 去掉图上的箭头的无向图。链链: : 点弧交错序列, 若在其基础图中对应一条链, 则称为 D的一条链。路路：若 是D中的一条链，且 ，t=1,2,k-1,称之为从 到 的一条路。回路回路: : 的路。初等路初等路: : 路中点不相同。初等回路初等回路: : 回路中点不相同。),.,(112211kkkiiiiiiivavavav),(1tttiiivva1ivkivkiivv 1如果给定一个图G=(V，E)或D=(V，A)的任一边（弧）有一个实数 与之相对应，由称这样的图为赋权无向（有向）图。如图7-5。赋权图的应

9、用是很广泛的。例如，在一个交通网络中，边的权数可以是两个点之间的距离，也可以表示两点之间的运输费用、运输时间、运输能力等。在一个设备维修的图中，权数可以表示维修费用，在工程项目计划网络图中可以表示各工序的完成时间等。ijw1354256-2023-44图7-5.赋权图在赋权图中的链（路）上所有边（弧）对应的权之和，称为链（路）链（路）的权的权。一个连通图连同定义在其边集上的实函数一起，称为一个网络网络图形虽然有直观等优点，但随着实际问题的大型化，大多数算法需要在计算机上运算和求解，计算机处理直观图形是比较困难的。以下介绍将图用矩阵表示，将图的几何形状转化为代数矩阵，可以方便计算机对图形的处理与

10、运算。以下举例说明。例例7-17-1将图7-6用矩阵表示。V1V2V3V4V5V6V7V10111000V21011100V31100110V41100101V50111011V60010101V70001110两个端点之间有边记为1，无边相连则记为0，对角线上记为0。这样得到一个对称的矩阵。 V1V2V3V4V5V6V7V10347V230324V343057V472026V5452014V670102V76420两个端点之间有边相连的，记上其权数，无边相连的记为，对称线上仍记为0。赋权无向图的矩阵也是对称矩阵。 第8章 网络分析17基本概念基本概念一、树一、树 树树 一个连通无圈简单图，记

11、为一个连通无圈简单图，记为T ； 林林 一个无圈简单图一个无圈简单图。如：由六个结点构成的树，有以下不同形式：如：由六个结点构成的树，有以下不同形式：7.3 7.3 树树 第8章 网络分析18图的支撑树图的支撑树若图若图G的一个支撑图的一个支撑图T是树，则称是树，则称T为为G的一棵的一棵支撑树支撑树。 图图GT1T2T3T4第8章 网络分析19最小支撑树最小支撑树 树的权数树的权数: 树的各边权数的总和；树的各边权数的总和； W(T) 图的图的最小支撑树最小支撑树: 网络所有支撑树中的权数最小者网络所有支撑树中的权数最小者, ,记为记为T*，简称简称网络最小树网络最小树。图图GT1T2T3T4

12、1 12 22 22 22 21 11 13 34 43 35 54 44 45 55 56 66 65 5W( (T1 1) )= =1111W( (T2 2) )= =1313W( (T3 3) )= =7 7W( (T4 4) )= = 9 9W( (T*) )= = 6 6图的支撑树图的支撑树（Spanning TreeSpanning Tree）: :设图G有p个节点，q条边。由G中p个节点，p-1条边组成的树称为图G的支撑树，也称为图G的生成树。图7-8(a). 图7-6的一个支撑树（1） 图7.8(b). 图7-6的一个支撑树（2） 图7-8就是一个树。树中只与一条边关联的节点称

13、为悬挂点悬挂点。与悬挂节点关联的边称为悬挂边悬挂边。图7-8中节点3和节点5都是悬挂点，1，3和4，5都是悬挂边。树有以下性质：（1）任何树至少有两个悬挂点。图7-8中节点3，节点5。（2）如果树的节点数是p，则边的个数为p-1。图7-8的图有5个节点，有4条边。（3）树中任意两个节点之间只有唯一的一条链。（4）在树中任意两个不相邻的节点之间增加一条边，则会形成圈。 解法一：破圈法解法一：破圈法解法二：避圈法解法二：避圈法 解法三：顶点扩充法解法三：顶点扩充法例例7-27-2设某个小区由六个楼组成，如图7-9，图上的数字为各相邻楼的距离（百米）。现要铺设光纤，试求光纤总长度最短的铺设方案。15

14、3232213v4v2v1v5v64v3图7-9. 例7-2的网络图 用破圈法求解过程如下：一般先找权数最大的边所在的圈 （1）找圈v1，v2 ，v4，v3或v1，v3 ，v4，v2去掉边v3，v1，如图7-1013232213v4v2v1v5v64v3图7-10. 破圈法求解示意图（1） （2）去掉边v4，v5（3）去掉边v3，v6（4）去掉边v3，v1（5）去掉边v2，v5。得图7-12。此时图中已不含圈，剩下的边构成了原网络的最小支撑树，也就是铺设光纤的最优方案。最小树的权为：W(T*)=1+2+2+2+1=812221v2v1v5v6v4v3图7-11. 破圈法求解示意图（2）第8章

15、网络分析24破圈法破圈法破破圈圈法法73247641213456743522142132356352452457567w (T ) = 13任选一个任选一个圈圈，去掉，去掉圈圈中中权数最大权数最大的的边边，直到图中直到图中为止。为止。避圈法与破圈法的思想相反，先将所有边的权按从小到大的次序排列，然后依次检查，如果某个边加到图上不会产生圈，就将其加上，否则就不加到图上。直到所有边都检查完为止。在图7-9中加边的顺序为v1，v2、v4，v6、v2，v4、v3，v4、v5，v6，由于本图为6个点，加上5个边即完成。得到如图7-11的结果，与破圈法得到的结果相同。一般来说，一个图可以有多个不同的最小支

16、撑树，但它们的总权一定相同。 顶点扩充法是先在图中任选一个点，记为S=a1，以该点为出发点，将与其相连的最小权的边加入图中，将相关连的点加入到S中，得到S=a1，a2；再寻找与S中的点相连的边中权数最小的边加入图中，将相关连的点加入到S中，反复进行以上步骤，直到所有的点都加入到S中为止。即可得到最小支撑树。 在例7-3中，以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条，其中权数最小

17、的有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，v1相连的边有3条，其中权数最小的有1条，权数是2，将v3加入，得S=v4，v6，v5，v2，v1，v3。此时所有点都加入到S中，可以得到如图7-12的结果。 153232213v4v2v1v5v64v3第8章 网络分析27重复重复 得得 w (T ) = = 13123S4252617233顶顶点点扩扩充充法法73247641213456743522S = =

18、 1 1， S = =2 2, ,3 3, ,4 4, ,5 5, ,6 6, ,7 7, , 连结连结 S与与 S 的边中，的边中，_S = = 1 1，2 2， S = = 3, 4, 5, 6, 73, 4, 5, 6, 7, , _最短为最短为( 1 1，2 2 ) T 第8章 网络分析287.4. 基本概念基本概念 一、网络流一、网络流：是指在一定的条件下通过一个网络的某种流在：是指在一定的条件下通过一个网络的某种流在各边上各边上的流量的的流量的。 一定条件一定条件指的是：指的是： （1 1）网络有一个网络有一个始点始点 s s 和和终点终点 t t 。 （2 2）流过网络的流量具有

19、一定的流过网络的流量具有一定的方向方向，一般用有向网络，一般用有向网络 N = (V，A)加以描述，各弧的方向就是流量通过的方向。加以描述，各弧的方向就是流量通过的方向。 （3 3）对每一弧对每一弧 ( i, , j ) A，都赋予一个，都赋予一个容量容量 c ( i, , j) = cij，表示容许，表示容许通过该弧的最大流量。通过该弧的最大流量。 在一个网络在一个网络 N = = (V, A) 中，设以中，设以xij= = x( i, , j)表示通过弧表示通过弧( i, , j)A 的的流量，则集合流量，则集合 X = = xij( i , , j)A 称为该网络的一个称为该网络的一个流

20、流。其其流量流量记为记为 f = f (X) 。 第8章 网络分析29 二、可行流二、可行流 满足下面条件的满足下面条件的流流称为一个称为一个可行流可行流： (1) (1) 弧流量限制条件弧流量限制条件 00 xijrrij ( ( i, , j)A (2)(2) 中间点平衡条件中间点平衡条件 xij - - xji = 0 0， i s, t 这意味着每个中间点的这意味着每个中间点的为为 ，即每个中间点的流，即每个中间点的流入量必须等于其流出量，二者必须平衡。入量必须等于其流出量，二者必须平衡。 i j jxjixij xji xij 第8章 网络分析30 可行流恒存在，如可行流恒存在，如X

21、0 0 = xijij= = 0 0( i,i, j j)A 就是一个可行流，称为就是一个可行流，称为零流零流，其流量，其流量 f( (X0 0) )= = 。 又如图所示又如图所示也是一个也是一个可行流。可行流。 三、最大流三、最大流 流量最大的可行流流量最大的可行流称为称为最大流最大流，记为，记为X* * = = xij* * ，其流量其流量记为记为f * * = = f( (X* *).).s2143t(9 , 7)(5, 3)(3, 2)(4, 4)(5, 5)(3, 1)(6, 3)(7, 7)(2 , 1)max f = f ( (X) ) f i = s 0 0 i s, t -

22、f i = t 0 0 xij rrij , ( , ( i,i, j j)As.t jj xij - - xji =最大流问题的最大流问题的 LP 模型模型网络最大流问题可以用线性规划方法求解。例如图7-12的最大流问题，设xij为各弧的流量，f表示可行流的流量。则此最大流问题的线性规划形式为： 23411342f2cijijijcxfxxxxxxxxfxxt sfz040302010. .max34243423132423121312节点节点节点节点第8章 网络分析32六、截集六、截集S SS S则把始点在则把始点在S S中而终点在中而终点在 中的一切弧所构成的集合，称为一个分离中的一切弧

23、所构成的集合，称为一个分离 s s和和 t t的的截集截集，记为，记为(S, )(S, )。七七、截量截量r(r( S, ) S, ) = = r rijij( ( i i, , j j)(S,S)(S,S)S S(S, )(S, )=a1, a3S SSSa1a2a3 s s t t在网络中，将点集分成两个不相交的非空集合在网络中，将点集分成两个不相交的非空集合S S和和 S S23411342f2cij23411342f2cij23411342f2cij23411342f2cij图7-13图7-14图7-15图7-16定理定理7-37-3： 网络任一可行流的流量f必定小于或等于网络中任一截

24、集的容量。即：定理定理7-47-4： 网络中从vs 到vt 的最大流的流量等于分离vs 和vt的最小截集的截量。),(min111kkSkVVCf),(*1*1*VVCf第8章 网络分析35 设设 X = = xij 是一可行流，是一可行流， 是从是从 s 到到 t 的一条链。的一条链。若若 上各弧的流量上各弧的流量满足下述条件：满足下述条件： 设设是网络是网络N中的一条从中的一条从 s s到到 t t的链的链, ,则链则链上与链的方向一致的弧称上与链的方向一致的弧称为为前向弧前向弧，其集合记为，其集合记为 ；链；链 上与链的方向相反的弧称为上与链的方向相反的弧称为后向弧后向弧，其集合，其集合

25、记为记为 - 。 = = ( (s, ,2 2) ), ,( (1 1, ,4 4) ), ,( (3 3, ,t) ) - = = ( (1 1, ,2 2) ), ,( (3 3, ,4 4) )xij 当当( ( i, , j) - 则称则称 为一条为一条关于可行流关于可行流X的的增广链增广链，记为，记为 ( (X) )。四、链的前向弧与后向弧四、链的前向弧与后向弧五五、增广链、增广链非非零流弧零流弧非非饱和弧饱和弧s2143t(9 , 7)(5, 3)(3, 2)(4, 4)(5, 5)(3, 1)(6, 3)(7, 7)(2 , 1)第8章 网络分析36 定理定理4 4： 设设 X*

26、 * = x* *ijij 是网络是网络 N =( (V, ,A) ) 的一个可行流，则的一个可行流，则 X* * 为最大流的为最大流的充要条件是：网络充要条件是：网络 N 中不存在增广链中不存在增广链 ( (X* *) )。 定理定理5 5： 网络中从网络中从 s s到到 t t的最大流的流量等于分离的最大流的流量等于分离 s s和和 t t的最小截集的截量。的最小截集的截量。 令令 1= = minrij - -xij则则 = = 也是也是N 的一个可行流，且有的一个可行流，且有 f ( = f (X) + )再令再令ij =xij + + , , 当当( ( i, , j) xij -

27、- , , 当当( ( i, , j) - - xij , , 当当( ( i, , j) = = min 1 , , 2 - - 2 = = minxij即，若设即，若设X* *为一最大流，（为一最大流，（, ,) )为一最小截集，则有为一最小截集，则有f (X* *) = r(，)第8章 网络分析377.4. 3 求网络最大流的标号法求网络最大流的标号法 （福特福特- -富尔克逊标号法富尔克逊标号法） 一、基本思想一、基本思想 从某一可行流从某一可行流 X（如（如零流零流）出发，按一定规则找出）出发，按一定规则找出一条增广链，并按一条增广链，并按定理定理3 3的方法（的方法（增广链调整法增

28、广链调整法）调整）调整 X, ,得到一个流量增大得到一个流量增大 的新可行流的新可行流 。重复上述做法直到。重复上述做法直到找不出增广链为止找不出增广链为止, ,这时就得到一个最大流，同时还得到这时就得到一个最大流，同时还得到一个最小截集。一个最小截集。 二、基本步骤二、基本步骤 1 给始点给始点 标号标号(0， ) ，则，则 已标号待检查已标号待检查；前源点前源点当前最大可调整量当前最大可调整量第8章 网络分析38 2 取一个已标号待检查的点取一个已标号待检查的点 i，对所有与对所有与 i 相邻而未标号相邻而未标号的点的点 j 依次判依次判断、执行如下断、执行如下手续手续： (1) 若关联若

29、关联 j 与与 i 的弧为的弧为( i, j)，则当该弧上的流量则当该弧上的流量 ij 时时, , 给给 j 标号标号( - - i，b( j)，其中其中 b( j) = = min b( i)，ji 而当而当 xji = = 0 时时, , 不给不给 j 标号；标号； 当所有与当所有与 i 相邻而未标号的点相邻而未标号的点 j 都执行完上述手续后，就给都执行完上述手续后，就给点点 i 打打，表示对它已检查完毕。，表示对它已检查完毕。第8章 网络分析39 3重复重复 2, ,可能出现两种结果：可能出现两种结果： (1)终点终点 得到标号得到标号。则从。则从回溯标号点的第一个回溯标号点的第一个

30、标号，就能找出一条由标号点和相应的弧连接而成的标号，就能找出一条由标号点和相应的弧连接而成的 从从 到到 的增广链的增广链 ( (X) )，转，转 4； (2) 所有标号点均已打所有标号点均已打（检查过）（检查过），而而又未得又未得 标号标号。这说明不存在增广链，而当前的可行流即最大。这说明不存在增广链，而当前的可行流即最大 流，算出其流量，停止。流，算出其流量，停止。 4取调整量取调整量 b( ) (即终点即终点 的第二个标号的第二个标号), ,令令 xij : = xij + ， 对一切对一切 ( i, j) xij : = xij - ， 对一切对一切 ( i, j) - 非增广链上的各

31、弧流量非增广链上的各弧流量 xij 不变。不变。 第8章 网络分析405删除网络中原有一切标号，返回删除网络中原有一切标号，返回 1；例例11s2143t(9 , 7)(5, 3)(3, 2)(4, 4)(5, 5)(3, 1)(6, 3)(7, 7)(2 , 1)()( ， )( ， )()(-)()调整量调整量 = =1s2143t(9 , 7)(5, 3)(3, 2)(4, 4)(5, 5)(3, 1)(6, 3)(7, 7)(2 , 1)()()()()= = 4 + 7 = = 11 = = , ,三、三、举例举例534762(4,4)(10,7)(4,4)(8,1)(1,1)(8,

32、4)(6,3)(7,7)(2, 2)(3,3)(3,3)(10,5)(0,)1(v1,7)(-v4,3)(v4,4)(v6,2)图7-90. 可行流（1） 图7-20. 可行流（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)第8章 网络分析43例例12 求网络的最大流求网络的最大流 与最小截集与最小截集 12st2st32st3t31s1st3st321287 1122 4 2 13 4 3 2 9 5 3 11 = = = = = =8

33、8101012122 21 18 82 23 32 24 42 23 35 52 24 46 611111212s12123 35 52 24 43 38 81313213t第8章 网络分析44f ( X* ) = 20例例13 分配问题分配问题A B C D 甲甲 乙乙 丙丙需求量需求量 10 20 15 10加工件数加工件数 18 19 18 55 ( ( S*, S* ) = (s, 1) , (s, 2) , (s, 3) 第8章 网络分析45 A B C D甲：甲： 18 18 乙：乙： 1919丙：丙： 1818 10 20 15 10 20 15 1010甲甲乙乙丙丙ABCDS

34、St1818，1818，1818，1919，1818，1919，1818，1919，1818，1919，1515，1010，1010，2020，101010100 02020191919191 115158 87 70 018188 80 0 = 10 1 11 11 11 110108 80 09 9101011117 7第8章 网络分析46 概概 念念：在一网络中，给定一个在一网络中，给定一个始点始点s和和终点终点t ，求求s到到t的的 一条路一条路，使路长最短使路长最短(即路的各边权数之和最小即路的各边权数之和最小)。 方方 法法：和和。 8.3.1 狄克斯屈标号法狄克斯屈标号法(适用于

35、适用于不含负权不含负权的网络的网络) 一、基本思想一、基本思想 固定固定标号标号 P( i i) - - 从从始点始点 s s到到 i i的最短路长最短路长 标号标号 () - - 从从始点始点 s s到到的最短路长最短路长上界上界第8章 网络分析47二、基本步骤二、基本步骤 给给始点始点 s s标上标上0，即令，即令 i i= = s s，令令 P( ( i i)=)= 0；给其余各点给其余各点 j j标上标上临时标号临时标号( (省略不写省略不写),),即令即令T( ( j j)= )= 。 在所有在所有临时标号临时标号中，选择中，选择改为改为，并且根据该标号的由来并且根据该标号的由来选择

36、选择。 是则结束，否则返回是则结束，否则返回。 对刚得到对刚得到那点那点 i i一切一切 ，修改修改其其临时标号临时标号：min P( ( i) ) + wi ，T( () ) T( () )关关键键步步骤骤第8章 网络分析48例例6 6（0）（ ）（ ）（ ）3（ ）10133742264423456751271472457118（ ）11（ ）567w = 10第8章 网络分析49 例例7 设备更新问题设备更新问题 各年初购价各年初购价 年年 度度 i 1 2 3 4 5 年初购价年初购价pi 13 14 16 19 24各年维护费各年维护费 使用年数使用年数 k 1 2 3 4 5 第第

37、k年维护费年维护费ck 8 10 13 18 27 解：解：设以 6 6第第5 5年末年末这一这一 ( i , , j)第第i年初购置的一台新设备一直使用到第年初购置的一台新设备一直使用到第j年初年初这一这一方案方案 wij 方案方案( i , , j ) 的的费用费用 i第第i i年初年初这一这一， i = 1 1, ,2 2, , , ,5 5第8章 网络分析50有有 j - - i wij = pi + ck k = 1 累积维护费累积维护费 使用年数使用年数 j j- -i i 1 2 3 4 51 2 3 4 5 第年维护费第年维护费c ck k 8 10 13 18 27 8 10

38、 13 18 27 累积维护费累积维护费 c ck k 76 81831 49第8章 网络分析51123456214489623132342422373227474563（0）2131446289（ ）84（ ）78（ ）（ ）（ ）136第8章 网络分析528.3.2 距离矩阵距离矩阵() 一、一、 网络的距离矩阵网络的距离矩阵 设一网络设一网络N中有中有n个结点，其中任意两点个结点，其中任意两点 i与与 j之间都有之间都有一条边一条边( i, , j), , 其权数其权数wij - -。 若若 i与与 j不相邻不相邻, ,则虚设则虚设一条边一条边( i, , j), , 并令其权数并令其权

39、数 wij = = , , 则则 W = (wij)nn 称为网络称为网络N的的直接距离直接距离矩矩阵阵。 - -（0）12 （ ）狄克斯屈标号法对于狄克斯屈标号法对于有有负权的网络可能失效。负权的网络可能失效。第8章 网络分析53 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 0 W =例例8从至从至 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- -24413

40、613- -13第8章 网络分析54二、二、求各点求各点至某点至某点的最短路的最短路 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。 ：两矩阵两矩阵对应元素对应元素求和求和取小。取小。 两矩阵两矩阵元素对应方式，元素对应方式，矩阵乘法。矩阵乘法。wijd(k- -1)jr第8章 网络分析55* 4 4 1

41、 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 6d2d1d3d4d54 41 19 9-1-13 30 0d(2) = min w1j + d(1) j616=

42、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章 网络分析56* 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

43、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 2 2 5 5 34253- -24413613

44、- -132 - -1 - -2 +1 = 0第8章 网络分析57 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 3 3

45、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最短路问题就是在一个网络图中，给定一个起点vs和一个终点vt，寻找vs到vt的路，使该路为从vs到vt的所有路中权数最小的路。实际问题中最短路问题有广泛的应用。例如

46、管道铺设、线路安排、运输线路选择、工厂布局、设备更新等问题。解法：标号法矩阵法 最短路的标号法是由狄克斯屈（E.W.Dijkstra）于1959年提出的，是目前公认的求解权数为非负的网络最短路问题较好的算法。这种算法能够求出网络中任意一点出发到其它各点的最短路。算法的思想算法的思想如下：对每一个网络中的点vj，均赋予一个标号，永久标号P（vj）或临时标号T（vj）。其含义如下：P（vj）从起点vs到vj最短路的长；T（vj）从起点vs到vj最短路的长的上界。一个点只能有上述两种标号之一，如果有了P标号就不再改变了，如果有T标号则根据情况进行修改。该算法的基本思想就是先给vs点标号为P（vs）=

47、0，其余点标号为T（vj）=；然后检查有P标号的点，对与该点有关联边的vj的T标号进行修改；在所有T标号中找一个最小的，将其T标号修改成P标号。再检查新得到P标号的点，修改其它点的T标号，再在所有T标号中找最小的修改为P标号；如此反复，直到要求的终点（或所有点）得到P标号为止，即可得到网络最短路。因为此算法一次修改一个P标号，所以如果网络中有N个点，最多经过N-1步就能找出要求的最短路。为了寻找到vs各点的最短路线，给每个顶点一个 值，算法终止时，如果 表示在从vs到vj的最短路上vj的前一个点为vm；若 ，则表示vs到vj不存在路；，则表示vj为起点。 ,)(mvjMvj)(（1）给vs标上

48、永久标号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标号、或无法继续修改时，则算法终止；否则转（2）。 0)( )( )(ssjjsjjvvvMvvvvT步骤V1V2V3V4V5V6V7V800 0MM MMMMM151316 1MMMM2514 3M103MM3518464M

49、M48464MM576126M695M7M15347627356422121681用表格的一行表示一个步骤，表格中的左上角表示P（T）标号，其中表示P标号；右下角表示 值到各点的最短路的长就是各点的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 v57V6v

50、1 v3 v4 v6 6V7v1 v3 v4 v6 v5 v79V8无对于无负权的无向图来说，标号法的程序也是相同的。 当一个网络存在负权时，Dijkstra算法会失效。如图7-22 13232-3 图7-22. 负权网络从v到v3的最短路长为-1，而不是2。(1)(,)sjsjdvvw),(min),()1()2(ijisjswvvdvvd),(min),() 1()(ijiskjskwvvdvvd矩阵法的基本思想是利用本章第一节中介绍的网络图的矩阵表示，其中的wsj表示从vs经一步到vj的权，可记为：则从vs经两步到达vj的权为：一般，经K步从vs经两步到达vj的权为Sj1in),()1(

51、iskvvdk-1步 1步 ijw图7-23. 求解存在负权网络步骤 如图7-23； njnskjskjskjskwvvdwvvdwvvdvvd),(),(),(min),()1(22)1(11)1()(即： ),(min)1(ijiskwvvd),(),()1()(jskjskvvdvvdjsvv 到),(),()1()(jskjskvvdvvdjsvv 到由于 的计算就是n 个对应元素的求和取小求和取小，这与矩阵的乘法的计算是相类似的，所以此算法也称矩阵摹乘法矩阵摹乘法。当（j=1,2,n）时，说明从的最短路的权不能再减少，所以（j=1,2,n）即为的最短路的权。 第三节讨论了网络最大流问

52、题，在实际中涉及流的问题时，人们考虑的不只是流量，同时要考虑“费用”的因素。对D=(V,A,C), 给定一个单位流量的费用bij0, 最小费用最最小费用最大流大流即:求一最大流f, 使Avvijijjifbfbfb),()(min*)(最大流的算法是从某个可行流出发，寻找关于可行流的增广链，然后沿着增广链调整可行流的流量，得到一个新的可行流，反复以上过程即可得到最大流。对于增广链, 若调整流量=1, 那么新可行流F的费用比原可行流F的费用增加量为:称为增广链增广链 的费用。的费用。ijijbbFbFb)()(可以证明，若F是流量为f的所有可行流中费用最小的，而是关于F的费用最小的增广链，那么沿

53、着增广链去调整流量，得到的新可行流F，就是流量为f的费用最小的可行流。这样当F为最大流时，也就是所求的最小费用最大流。由于bij0，所以零流的费用总是最小的。所以可以从零流出发去寻找最小费用最大流。这里主要需要解决的问题就是如何寻找关于F的费用最小的增广链。为此，可构造网络图D的相对应的赋权有向图W（F），其节点与原网络图D相同，将D中的每一条弧（，）都变成两方向相反的弧（，）与（，）定义W（F）中弧的权为：权数为的弧表示不能通过，可以在W（F）中省略。这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。0 0 ijijijjiijijijijijijff

54、bwcfcfbw权数为的弧表示不能通过，可以在W（F）中省略。这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。具体算法为：从零流出发，构造其W（F），在W（F）中寻找最短路，在F中对应一个增广链，增广链的调整量由下式确定：沿增广链，对流量进行调整，调整方法同最大流的调整方法。然后对新得到的可行流继续做前述的工作，直到在赋权有向图W（F）中找不到从始点到终点的最短路（也就是在网络图D中不存在增广链）为止，即可得到最小费用最大流。 ),( ),( ),( )(min),(minmin)1()1()1()1()1(jikijjikijjikijkijkijk

55、ijijvvfvvfvvffffc第8章 网络分析70 8.5. 基本概念基本概念一、一、最小费用流最小费用流 (1) 运价运价 设设X是网络是网络N=(V, A)的一个可行流的一个可行流, ,定义实值函数定义实值函数c( i, , j ) = cij 0， ( i, , j ) A表示表示该弧输送该弧输送的的费用费用，简称，简称运价运价； (2) 可行流的费用可行流的费用c(c(X) )= c cijxij ( ( i i, , j j ) ) A (3) 最小费用流最小费用流 在流量为在流量为 f 的一切可行流中，若的一切可行流中，若X费用为最小，则称费用为最小，则称X为为流量为流量为 f 的的最小费用流最小费用流。第8章 网络分析71 二、二、最小费用增广链最小费用增广链 (1) 增广链的费用增广链的费用 设：设： ( (X ) ) 可行流可行流 X 的增广链的增广链 X 沿着沿着 ( (X ) )以以 = 1 去调整去调整 X 而得到的一个而得到的一个 新可行流新可行流则则增广链增广链 ( (X ) )