运筹学资料：8图与网络模型

1、2021/1/25,天道酬勤,1,第八章 图 与 网 络 模 型,在实际的生活中，人们为了反映一些对象之间的关系，常常用点和线画出各种的示意图。在运筹学中有一个分支被称为图论，便是通过研究反映相互关系的点和边(弧)组成的图（网络）来解实际问题,2021/1/25,天道酬勤,2,在哥尼斯堡城中有一条河叫普雷格尔河，河上有七座桥连接两岸及河中的两个岛.当时困扰当地居民的一个问题是：是否存在一种走法，使走过每座桥恰好一次又回到原点。 Euler提出了判断一般图存在这种走法的充要条件，它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2,2021/1/25,天道酬勤,3,第一节 图 和网络的

2、 基 本 概 念,1、图是由点和点间的连线组成的(有箭头的连线，无箭头的连线,2、有箭头的连线称为弧， 无箭头的连线称为边,3、如果一个图是由点和边构成的（无箭头连线），则称之为无向图,4、如果一个图是由点和弧构成的（有箭头连线），则 称之为有向图,5、无向图记为G（V，E）（V代表点的集合，E代表边 的集合,6、有向图记为D（V，A）（V代表点的集合，A代表弧 的集合,2021/1/25,天道酬勤,4,8、边（弧）上的数值称为权，边上的权表示为ij，弧上的权表示为Cij,9、若一个无向图的每条边上均有权值， 则称之为赋权无向图,10、若一个有向图的每个条弧上均有权值， 则称之为赋权有向图,1

3、3、在一个赋权有向图中，若指定了一个发点(VS)和一 个收点（Vt），其余点为中间点，并把弧上的权值 称为对应弧的容量，这样的赋权有向图称为网络,11、无向图中有 “链”、“圈”的概念 12、有向图中还有“路”、“回路”的概念,第一节 图 和网络的 基 本 概 念,2021/1/25,天道酬勤,5,例： 求 右 图 V1 到 V6 最 短 路,1、给起始点V1标号(0,S),表示从起 点到V1的最短距离为0, V1为起点,2、已标号点集IV1 未标号点集JV2,V3,V4,V5,V6,3、计算2中所有弧对应的Sij值；Sij=Li+Cij,S12=L1+C12 0+33,S14=L1+C14

4、0+55,S13=L1+C13 0+22,min(S12 , S13, S14)= S13 =2,则可知：L3 2,给弧(V1,V3)中的未标号点V3标号（2,1,2,1,0,S,第二节 最 短 路 问 题,2021/1/25,天道酬勤,6,重复】已标号点集IV1 , V3; 未标号点集JV2,V4,V5,V6,4、计算集合中所有弧对应的Sij值；Sij=Li+Cij,S12=L1+C12 0+33,S14=L1+C14 0+55,S34=L3+C34 2+13,min(S12 , S13, S34)= S12 = S34=3,则可知： L2 L4 3,给弧(V1,V2) (V3,V4)中的未

5、标号点V2 V4标号,3,1,3,3,2,1,0,S,第二节 最 短 路 问 题,例 求 右 图 V1 到 V6 最 短 路,2021/1/25,天道酬勤,7,5、计算集合中所有弧对应的Sij值；Sij=Li+Cij,S26=L2+C26 3+710,S46=L4+C46 3+58,min(S26,S46)=S46=8,则可知： L6 8,给弧(V4,V6)中的未标号点V6标号,从已标号点到未标号点的所有弧的集合 (V2,V6)(V4,V6,3,1,3,3,2,1,0,S,重复】已标号点集IV1 , V2, V3 , V4; 未标号点集JV5,V6,8,4,第二节 最 短 路 问 题,例 求

6、右 图 V1 到 V6 最 短 路,2021/1/25,天道酬勤,8,即不存在从V1到V5的有向路,从已标号点到未标号点的所有弧的集合 此时为空集,3,1,3,3,2,1,0,S,重复】 V6标号后， 未标号点集JV5,8,4,从最后一个标号点开始从后向前确定最短路径,V6点的标号 (8,4,之前点为V4 ，再从V4开始继续逆推,第二节 最 短 路 问 题,例 求 右 图 V1 到 V6 最 短 路,2021/1/25,天道酬勤,9,一、双标号法：（迪杰斯特拉算法Dijkstra） Cij0 双标号（lj，kj,基本步骤： 1、对起点V1标号为（0，S,3、计算2中所有弧对应的Sij值； Si

7、j=Li+Cij，Li为从起点到Vi点的最短距离， Cij为弧(Vi,Vj)的权,第二节 最 短 路 问 题,赋权有向图，指定两点Vs和Vt，找一条从Vs到Vt的最短路,2021/1/25,天道酬勤,10,4、选出各弧中Sij值最小者，对该弧上未标号点进行标号， 重复，直到2中弧的集合变为空集为止,注意： 1、双标号法适用范围:权值非负的有向图 也适用于权值非负的无向图。 2、在选择Sij最小值时，若出现多个相等最小值且这些弧(边)的终点为同一点，则此点应有多个标号，以便在最终确定具体路径时可以找到多条最短路线。 3、 Sij代表某条路线上从起点到第j点的距离(不一 定是最短距离),而不是从第

8、i点到第j点的距离,第二节 最 短 路 问 题,5、若Vt 已标号，则说明Vs到Vt存在最短路，若Vt 未标号，则说明不存在Vs到Vt最短路,2021/1/25,天道酬勤,11,双标号法也可用来求解赋权无向图： 1、Sij =Li+ij公式中权值表示为ij（边的权） 2、边的集合表示为Vi,Vj 3、边的集合仍是从已标号边的点到未标号的点的边的集合,第二节 最 短 路 问 题,2021/1/25,天道酬勤,12,例：求赋权交通图最短路(无向图,1、给起始点V1标号(0,S),表示从起 点到V1的最短距离为0, V1为起点,2、已标号点集IV1 未标号点集JV2,V3,V4,V5,V6 , V7

9、,3、计算2中所有边对应的Sij值；Sij=Li+ij,S12=L1+12 0+1515,S13=L1+13 0+1010,min(S12 , S13)= S13 =10,则可知： L3 10,给边V1,V3中的未标号点V3标号,0,S,10,1,2021/1/25,天道酬勤,13,重复】已标号点集IV1 , V3; 未标号点集JV2,V4,V5,V6 , V7,4、计算集合中所有边对应的Sij值；Sij=Li+ij,S12=L1+12 0+1515,S32=L3+32 10+313,S35=L3+35 10+414,min(S12 , S32, S35)= S32 =13,则可知： L2 1

10、3,给边V3,V2中的未标号点V2 标号,从已标号点到未标号点的所有边的集合 V1,V2 V3,V2 V3,V5,0,S,10,1,13,3,2021/1/25,天道酬勤,14,5、计算集合中所有边对应的Sij值；Sij=Li+ij,S27=L2+27 13+1730,S24=L2+24 13+619,min(S27,S24 , S35)=S35=14,则可知： L5 14,给边V3,V5中的未标号点V5标号,从已标号点到未标号点的所有边的集合 V2,V7 V2,V4 V3,V5,0,S,重复】已标号点集IV1 , V2, V3 ; 未标号点集JV4 , V5,V6 , V7,10,1,13,

11、3,14,3,2021/1/25,天道酬勤,15,6、计算集合中所有边对应的Sij值；Sij=Li+ij,S27=L2+27 13+1730,S24=L2+24 13+619,min(S27,S24 , S54 , S56)=S56=16,则可知： L6 16,给边V5,V6中的未标号点V6标号,从已标号点到未标号点的所有边的集合 V2,V7 V2,V4 V5,V4 V5,V6,0,S,重复】未标号点集IV4 , V6 , V7; 已标号点集JV1 , V2, V3 , V5,10,1,13,3,14,3,S54=L5+54 14+418,S56=L5+56 14+216,16,5,2021/

12、1/25,天道酬勤,16,7、计算集合中所有边对应的Sij值；Sij=Li+ij,S27=L2+27 13+1730,S24=L2+24 13+619,min(S27,S24 , S54 , S67)=S54=18,则可知： L4 18,给边V5,V4中的未标号点V4标号,从已标号点到未标号点的所有边的集合 V2,V4 V2,V7 V5,V4 V6,V7,0,S,重复】未标号点集IV4, V7; 已标号点集JV1 , V2, V3 , V5 , V6,10,1,13,3,14,3,S54=L5+54 14+418,S67=L6+67 16+622,16,5,18,5,2021/1/25,天道酬

13、勤,17,8、计算集合中所有边对应的Sij值；Sij=Li+ij,S27=L2+27 13+1730,S47=L4+47 18+523,min(S27,S47 ,S67)=S67=22,则可知： L7 22,给边V6,V7中的未标号点V7标号,从已标号点到未标号点的所有边的集合 V2,V7 V4,V7 V6,V7,0,S,重复】未标号点集IV7; 已标号点集JV1 , V2, V3 , V4, V5 , V6,10,1,13,3,14,3,S67=L6+67 16+622,16,5,18,5,22,6,2021/1/25,天道酬勤,18,应用:设备更新问题 某企业需要一台设备，在每年年初，企业

14、领导部门就要决定是购置新的，还是继续使用旧的，若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。如何制定一个几年之内的设备更新计划，使得总的支付费用最少。已知该设备在各年年初的价格和维修费用,2021/1/25,天道酬勤,19,如何制定一个计划使得总的支付费用最少？转化为最短路问题。 用点Vi代表“第i年年初购进一台新设备” 弧（vi，vj）表示在第i年年初购进的设备一直使用到第j年年初（即第j1年底）。 制定一个最优的设备更新计划的问题等价于寻求从v1到v6的最短路的问题,2021/1/25,天道酬勤,20,按求解最短路的计算方法，有两个最优方案。一个方案是在第

15、1年、第3年各购置一台新设备；另一个方案是在第1年、第4年各购置一台新设备。五年的总的支付费均为53,2021/1/25,天道酬勤,21,二、如何求任意两点间最短距离？ Floyed算法,第二节 最 短 路 问 题,2021/1/25,天道酬勤,22,第三节 最小生成树,的生成子图:无向图，保留所有点，删掉部分边. 生成树:若的生成子图是一棵树，称这个生成子图为生成树 树:无圈连通图 最小生成树:对于权数最小的那个生成树，称为G的最小生成树,利用这一性质，可用要求解很多实际问题，如电话线 铺设、输电线铺设、网络线路铺设等,2021/1/25,天道酬勤,23,例5某学校对其所属的7个学院进行联网

16、，7个学院间铺设网线情况如图所示，问如何铺设网线可总长度最短,理论上, V1与V6之间直接传输,速度最快,若经其它点中 转会影响速度,但当这种影响,与铺设一条网线的花费相 比很小时,我们可将这种影响忽略不计,只要保证连通就 可以了,即在保证连通的情况下,使连线最短,2021/1/25,天道酬勤,24,一、用破圈法来确定最小生成树：1975 中国 管梅谷 步骤： 1、在给定的连通图中任找一个圈； 2、去掉该圈中权数量大的边（如果有多条,可任选其一） 3、再重新选定一个圈，重复上述去权数最大的边，直到 连通图中再找不到一个圈为止,1,3,4,3,3,5,2,7,8,10,3,2021/1/25,天

17、道酬勤,25,二算法把图中的最小边先算入集合里边（这是集合里含有2个点）然后考虑所有和集合里的点有连接关系的边 选一个最短的再加入集合一直到图里边所有的点都被算入集合为止,三算法 在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止,2021/1/25,天道酬勤,26,第四节 最 大 流,许多系统中包含了流量问题，例如公路系统中有车辆流，控制系统中有信息流，供水系统中有水流，金融系统中有现金流等等。 1955年T.E. 哈里斯在研究铁路最大通量时首先提出，在一个给定的网络上寻求两点间最大运输量的问题。

18、1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论,2021/1/25,天道酬勤,27,一 基本概念 赋权有向图D=(V,A)满足下列条件： 源点：有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点s便称为源点（发点）。 汇点：有且仅有一个顶点t，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点（收点）。 容量：每一条弧都有非负数的权，容量用cij表示。 网络：赋权有向图为D = (V, A, C) 最大流问题：给定了一个带源、汇点的网络，在不超过每条弧的容量(权)的前提下，求出从源点到汇点的最大流量,第四节 最 大 流 问

19、 题,2021/1/25,天道酬勤,28,D = (V, A, C)是已知的网络流图，设U和W是V的子集，U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合,满足sU，tW。 割切，（U，W）：对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。 割切的容量， C（U，W）：割切（U，W）中所有弧的容量之和 定理：对于已知的网络流图，设任意一可行流为f，任意一割切为(U, W)，必有：V(f) C(U, W)。 即：“最大流小于等于最小割”。这是“流理论”里最基础最重要的定理,第四节 最 大 流 问 题,2021/1/25,天道酬勤,29,可行流 对于网络流图D，每一条

20、弧(vi,vj)都给定一个非负数f，这一组数满足下列三条件时称为这个网络的可行流，用f表示它。 1 每一条弧(vi,vj) 0fCij。 2 除源点s和汇点t以外的所有的点vi，恒有： 流出量=流入量 3 对于源点s和汇点t有： 源点s流出量=汇点t流入量,第四节 最 大 流 问 题,2021/1/25,天道酬勤,30,饱和弧 非饱和弧 零流弧 非零流弧 饱和弧：给定一个可行流fij ,若fij = Cij，称(vi, vj)为饱和弧； 非饱和弧：若fij Cij，称(vi, vj)为非饱和弧。 零流弧：若fij = 0，称(vi, vj)为零流弧； 非零流弧：若 fij 0，称(vi, vj

21、)为非零流弧,第四节 最 大 流 问 题,2021/1/25,天道酬勤,31,弧的分类:定义路的方向是从Vs到Vt，则路上的弧被分为两类:一类与路的方向一致，称为前向弧；另一类和路的方向相反，称为后向弧 增广路P: P是网络中连接源点Vs和汇点Vt的的一条路(不管边的有向性)，这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 若p满足下列条件： (1)在p上的所有前向弧都是非饱和弧，0fijCij (2)在p上的所有后向弧都是非零弧，即0fijCij 则称p为(关于可行流f的)一条可增广路径,第四节 最 大 流 问 题,2021/1/25,天道酬勤,32,改进规则 修正P上各弧的流量

22、来使得总流量变得更大,修正的方法： 不属于P的弧一概不变 对于P上的所有前向弧加上a，后向弧减去a。a是一个可改进量。 a既要尽量大，又要保证变化后0Fij Cij。 a=min(Cijfij),fij)。 最大流定理 当且仅当不存在关于f的增广路径，可行流f为最大流。 最大流的算法可以表示为：不断寻找可改进路P，并修改P，直到找不到P为止,前向弧,后向弧,第四节 最 大 流 问 题,2021/1/25,天道酬勤,33,二、用网络图论解法求解,1、将各弧的流量作如下改进:将容量Cij标在靠近流入点(称为顺流流量),将0标在靠近流出点(称为逆流流量,6,0,6,0,3,0,2,0,2,0,2,0

23、,1,0,2,0,5,0,4,0,3,0,第四节 最 大 流 问 题,2021/1/25,天道酬勤,34,2、选择一条源点到汇点的增广路(包含弧数量最少路)进行第一次迭代:找出该条路中可改进量a，前向弧顺流量减a逆流量加上a，后向弧顺流量加a逆流量减a,a =2,4,0,2,2,第四节 最 大 流 问 题,2021/1/25,天道酬勤,35,3、进行第二次迭代:任选一条增广路 找出该条路中可改进量a，前向弧顺流量减a逆流量加上a，后向弧顺流量加a逆流量减a,a=3,3,0,2,3,3,3,3,0,第四节 最 大 流 问 题,2021/1/25,天道酬勤,36,a =2,4、如果找不到一条增广路

24、，那么迭代线结束， 如果能找到增广路,则要对该线路继续迭代,3,0,1,0,0,2,5,2,2,2,第四节 最 大 流 问 题,2021/1/25,天道酬勤,37,a =2,2,1,0,0,4,2,2,5,第四节 最 大 流 问 题,2021/1/25,天道酬勤,38,a=1,1,0,1,5,1,3,第四节 最 大 流 问 题,2021/1/25,天道酬勤,39,5、将每次迭代时确定的改进量进行累加,当最终迭代完毕后，所有改进量的和便是整个网络允许的最大流量,maxf=1+2+2+3+2,第四节 最 大 流 问 题,2021/1/25,天道酬勤,40,1,0,1,5,1,3,6、在最终迭代完毕

25、后,每条弧的实际输送量,便是该弧逆流流量的值,第四节 最 大 流 问 题,2021/1/25,天道酬勤,41,P 253习题,2021/1/25,天道酬勤,42,第五节 最小费用最大流问题,在最大流问题中，由于每次选择的路线是任意选取的，所以会出现：网络最大流是唯一的，但每条弧实际输送量不唯一的情况，即会有多个方案。 如果给出了每条弧的单位流费用，可以求出每个方案的总费用，在所有方案中，必存在一个费用最小者，该类问题即为最小费用最大流问题,2021/1/25,天道酬勤,43,最小费用最大流问题: 带源点(发点)和汇点(收点) 网络流图D = (V, A, C, B)，每条弧(Vi, Vj)给出

26、容量Cij和单位流量费用bij，若可行流fij满足： (1) maxZ=V(fij)。 (2) 满足(1)的前提下，MinF=Cost(fij) 。 就称f是网络流图D的最小费用最大流,第五节 最小费用最大流问题,2021/1/25,天道酬勤,44,基本思想：每次选择最小费用增广路进行改进，直到不存在最小费用增广路为止。这样得到的最大流必然是费用最小的,第五节 最小费用最大流问题,2021/1/25,天道酬勤,45,一、最小费用最大流求解步骤：与求解最大流问题近似，不同的是,在每次迭代时,不能任意选取路线,而应该依据费用由小到大依次选取路线。 确定费用最小路线的方法：对于一个较简单的网络图可采取“穷取法”。 复杂的网络如何确定费用最小路线,注意：根据费用选定迭代路线后,仍然需要检验该路线是否是增广路,第五节 最小费用最大流问题,2021/1/25,天道酬勤,46,二、最小费用流问题： 指在给定流量的前提下，找到最小费用线。 求解时，仍然用求解最小费用最大流的思路，依次迭代，当某次