运筹学第五章图与网络分析ppt课件.ppt

第5章图与网络分析,第章图与网络分析,.基本概念.最小支撑树问题.最短路问题.最大流问题,5. 基本概念,1.图、子图与简单图图：由节点和线组成的图形 记为： G = ( V, E ) V=v1,v2,vm节点集,表示研究对象. E=e1,e2,en边集，表示研究对象之间的关系.,图,图,子图：图的一部分，记为,多重边：两节点之间有多于一条边。,环：首尾相接的边,简单图：无环、无多重边的图。,2.有向图与无向图,有向图：有方向的图。无向图：无方向的图。,e1 V2 V1 e2 V3,v1 e v2,3.关联与相邻,关联(边与节点的关系):若e是v1、v2两节点间 的边，记e=v1，v2 ，称v1、v2 与e关联。,相邻（边与边、节点与节点的关系）： 点v1与v2有公共边，称节点v1与v2相邻； 边e1与e2 有公共节点，称边e1与e2相邻。,圈 封闭的链称为圈如：=(1,2),(2,4),(3,4),(1,3,链:由图G中的某些相连的边构成的图形（首尾不能相接），称为图G中的一条链。 如： =(1,2),(3,2),(3,4),4. 链、圈与连通图,4,2,3,1,4,2,3,1,连通图 任意两个节点之间至少有一条链的图称为连通图,4,2,3,1,5.网络图,给图中的节点和边赋以具体的含义和权数（如距离、时间、费用、容量等），则称这样的连通图为网络图。,4,2,3,1,50 70 20 45,典例: 会议日程安排某单位要在今后的三天内召开6个会议,每天上下午各安排一个会议，参加会议的领导如下会议A: 朱、马、牛、姬、江、姚会议B: 朱、杨、张、江会议C: 马、姬、侯、王、姚会议D: 朱、姬、张会议E: 杨、侯、王会议F: 刘、杨、王、江、姚,每位领导每天最多只参加一个会议。会议A要安排在第一天上午,会议F安排在第三天下午，会议B要安排在任何一天的下午。试根据上述要求排出一个会议日程表，使各位领导都能参加相应的会议,A,B,C,D,E,F,会议日程安排如下: 上午 下午第一天 会议A E 第二天 会议C B第三天 会议D F,解: 用节点表示会议，若两个会议能安排在一天， 则用连线连接。,5.2 最小支撑树问题,树：无圈的连通图，记为T。,树的性质,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果树T有m个节点，则边的个数为m-1。,树中任意两个节点间有且只有一条链。,在树中任意去掉一条边，则不连通。,图的支撑树,图G1和G2 的节点相同，但图G1边的集合包含于G2边的集合，且 G1是树图，则 图G1是G2 的支撑树。一个图的支撑树不是唯一的。,图 G1,图 G2,最小支撑树 树枝总长最短的支撑树。特点：各节点都连通且线路总长最短,最小支撑树的求法1 破圈法2 避圈法,5.2.1 求解最小支撑树问题的破圈法,方法：去边破圈的过程。,步骤：1）在给定的赋权的连通图上任找 一 个圈。 2）在所找的圈中去掉一条权数最 大的边。 3）若所余下的图已不含圈，则计 算结束，余下的图即为最小支撑 树，否则返回 1）。,例：用破圈法求右图 的最小支撑树。,总权数=3+4+1=8,5.2.2 求解最小支撑树的避圈法,方法：选边的过程。,步骤：1）从网络中任意选一点vi，找出与vi相关联的权最小的边vi,vj，得第二个顶点vj。,2）把顶点集V分为互补的两部分A,，其中： A：与已选边相关联的点集 ：不与已选边相关联的点集,3) 考虑所有这样的边vi,vj，其中viA,vj,挑选其中权最小的。,4）重复3），直至全部顶点均属于A即可。,例：用避圈法求图的最小 支撑树。,V4,V2,V3,V1,7 4 5 8 1,任选点v1，挑与之相关联的权最小的边（ v1,v4）.,A= v1,v4,=v2,v3 从边（ v1,v2）,（ v1,v3）, （ v4,v2）, （ v4,v3） 中选权最小的边（ v1,v2）。,V4,V2,V3,V1,7 4 5 8 1,A= v1,v2 ,v4,=v3 从边（ v1,v3）, （ v2,v3）, （ v4,v3） 中选权最小的边（ v2,v3）。, A= v1,v2 , v3， v4,网络的生成树和线性规划的关系,网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换,7,破圈法举例,避圈法举例,例 校园局域网问题,某大学准备把所属个学院办公室的计算机联网这个网络的可能联通的途径如图所示边上权数为这条边的长度，单位为百米试设计一个网络联通个学院办公室，并使总长度为最短,v1,v4,v5,v3,v7,v6,v2,5,1,3,7,2,4,8,4,3,10,3,v1,v4,v5,v3,v7,v6,v2,1,3,7,2,3,3,权和,例 电话线网架设问题,某个城市之间的道路网如图所示要求沿着已知长度的道路联结个城市的电话线网，并使电话线的总长度最短,v1,v4,v2,v6,v5,v3,6,1,7,5,2,4,4,5,3,v1,v4,v2,v6,v5,v3,1,2,4,5,3,权和,5.3 最短路问题,问题：求网络中一定点到其它点的最短路。,5.3.1 最短路问题的Dijstra解法,方法：给vi点标号i,vk 其中：i：vi点到起点vs的最短距离 vk: vi的前接点,方法：(1) 给起点vs标号0，vs。,（2）把顶点集v分为互补的两部分A和 其中：A：已标号点集 ：未标号点集,（3）考虑所有这样的边vi, vj, 其中vi A,vj 挑选其中与vs距离最短的点vj标号 mini+cij,vi,(4) 重复（3），直至终点vt标上号t,vk，则 t即为vs至vt的最短距。反向追踪可求得最短路。,例：求v1至v8的最短路。,v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(1) v1:0,v1,计算min 0+2, 0+1, 0+3 = min 2,1,3=1 v4:1.v1,1,v1,0,v1,(2)A=v1,检查边（v1,v2),(v1,v4),(v1,v3),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(3)A=v1,v4,计算 min0+2, 0+3, 1+10, 1+2=min 2,3,11,3 =2 v2:2,v1,0,v1,1,v1,2,v1,考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,（4）A=v1,v2,v4,计算min 0+3, 2+6, 2+5, 1+2 v6:3,v1 =min 3,8,7,3=3,2,v1,1,v1,0,v1,3,v1,考虑边（v1,v6),(v2,v3),(v2,v5),(v4,v7),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(5)A=V1,V2,V4,V6,计算 min 2+6, 2+5, 1+2, 3+4=min 8,7,3,7=3 v7:3,v4,2，V1,1，V1,0，V1,3，V1,3,v4,考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7),V2,V3,V7,V1,V8,V4,V5,V6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(6)A=V1,V2,，V4,V6,V7,计算min 2+6, 2+5, 3+3, 3+8=min 8,7,6,11=6 v5:6,v7,2,v1,1,v1,0,v1,3,v1,3,v4,6,v7,考虑边(v2,v3),(v2,v5),(v7,v5),(v7,v8),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(7)A=V1,V2,V4,V6,V7,计算min 2+6, 6+9, 6+4, 3+8=min 8,15,10,11=8 v3:8,v2,2,V1,1,V1,0,V1,3,V1,3,V4,6,V7,8,v2,考虑边(v2,v3),(v5,v3),(v5,v8),(v7,v8),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(8)A=v1,v2,v3,v4,v6,v7,计算 min 8+6, 6+4, 3+7=min 14,10,11=10 v8:10,v5,2,v1,1,v1,0,v1,3,v1,3,v4,6,v7,8,v2,10,v5,考虑边（v3,v8),(v5,v8),(v7,v8),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(9)A=v1,v2,v3,v4,v6,v7,v8,v1到v10的最短路径为v1v4v7v5v8，最短路长度为10。,2,v1,1,v1,0,v1,3,v1,3,v4,6,v7,8,v2,10,v5,反向追踪：v8-v5-v7-v4-v1,例6 设备更新问题某厂使用一种设备，每年年初设备科需要对该设备的更新与否作出决策。五年内：购买新设备-购置费；13，14，16，19，24；使用老设备-维护费。8，10，13，18，27。问：在5年内如何制定更新计划，以便使新设备购置费和老设备维修费的总费用最小？,34,21,31,32,32,44,62,24,89,22,45,63,47,37,27,v1-v3-v6minL=78,例7火车调度问题某火车货运调车场，主要调运建筑材料中的黄沙、碎石和水泥。该调车场有3个装运点：黄沙装运点、碎石装运点和水泥装运点；另有2个机车挂钩处（挂火车头的地方），即图1中的节点1、2、5和9、10。货运火车的各节车厢在一个装运点装货后，必须由调车场的火车头把装好货的车厢拉走，按调车场的铁路网络的某一路线运行到某一机车挂钩处，由那里的火车头把满载的车厢拉走。网络图中，各条弧代表铁路线，节点代表铁路交叉口，弧旁的数字代,表距离（单位：百米），这里需注意的是，网络图只是描述了各换轨点(即交叉口）、装运点和机车挂钩处之间的关系，并不表示铁路线的实际走向。调车场的调度室需要解决的问题是：各车厢在某一装运点装好货后应把它拉到哪一个机车挂钩处，而且应走哪一条运行路线最短，从而提高调车场作业的效率，减少装载的车厢等候挂钩时间而尽快拉离调车场。,分别求出结点1、2、5到结点9和10的最短路径及最小路径值。,结果分析黄沙装运点、水泥装运点、碎石装运点到两个机车挂钩处的最短路径及最短路径值，如下 30； 35； 27； 32； - 19； - 24,5. 最大流问题,v2,v3,v5,v4,v6,v7,v1,f=0,f=0,6,2,4,7,4,3,7,9,3,1,8,8,问题的一般提法：,有一网络D=(V,A;C) 其中V：点集；A：弧集；C=cij,cij为弧（vi,vj)上的容量。 现D上要安排通过一个流f=fij，其中fij为弧(vi,vj)上的流量。,问题：如何安排流量fij，可使D上通过 的总流量V(f)最大？,5.4.1 网络流的基本概念与基本定理,(1)弧的容量和流量容量cij，流量fij(2)可行流a、每一个节点流量平衡b、0fij cij,1.弧的容量和流量、可行流,2. 饱和弧、不饱和弧、流量的间隙,（i，j）是饱和的,(2)如果fijcij，弧从i到j的方向是不饱和的；,（i，j）是不饱和的间隙为ij=cij-fij=5-3=2,(1)如果fij=cij，弧从i到j的方向是饱和的；,(3)如果fij=0，弧从j到i的方向是饱和的；,（j，i）是饱和的,如果fij0，弧从j到i的方向是不饱和的；,（j，i）是不饱和的间隙为ij=fij=5,3.可增广链（或可扩充链）,网络D中st的链，记为 +：前向弧（与方向一致） -：后向弧（与方向相反）,若链 上的流量满足：所有的前向弧皆未饱和，后向 弧皆非零，则称为D中关于可行流fij的可增广链。,(4,2) (3,1) (5,3) (4,1) (3,2),4.截集与截量,截集：将网络图中的起点与终点分开并使流中断的一组正向弧的集合。,即将顶点V分为二个非空互补集E和，使s E,t ,称弧集（ E，)= (i,j) | i E,j 为D的截集。,截量：截集上的容量之和。记为C(E, ).,5.流量与截量的关系,任何一个可行流的流量V(f)都不会超过任一截量。即V(f) C(E, ),最大流-最小截定理：max V(f) = minC(E, ),判别最大流的条件：可行流f是最大流 D中不存在关于f 的可增广链,5.4.2 最大流问题的标号解法,步骤：先找一个可行流检验调整,算法步骤：1.标号找可增广链,（1）给vs标号,vs,选与vs相关联的流出未饱和弧(vs,vi) ，给vi标号i,vs. 其中i= csi-fsi,（3）考虑所有这样的弧(vi,vj),其中 viE,vj,（2）点集V=E，其中 E：已标号点集 ：未标号点集,若(vi,vj)为流出未饱和弧，则vj:j , vi j=mincij-fij, i若(vi,vj)为流入非0弧，则vj:j , -vi j=min fij, i,(4)直到终点已标号为止,反向追踪便得可增广链. 若未标到终点,但已标不下去，说明网络D中不存在可增广链，便得最大流maxV(f),同时得 到最小截集min(E，).,2.调整流量：选择一条可增广链,调整流量。 fij+ t (vi,vj)+fij= fij- t (vi,vj)- fij 其它调整后得到新的网络图,重复步骤1.,例：用标号法求下面网络的最大流。,vs,v1 v3,V2 v4,vt,(4,3),(3,3) (1,1) (5,3),(1,1) (3,0),(5,1) (2,1),(2,2),1.标号找可增广链(1) vs:,vs v1:4,vs(2) E=vs,v1 v2:1,-v1(3) E=vs,v1,v2 v4:1,v2 v3:1,-v2,vs,v1 v3,v2 v4,vt,(4,3),(3,3) (1,1) (5,3),(1,1) (3,0),(5,1) (2,1),(2,2),vs,4,vs,1,-v1,1,v2,1,-v2,(4)E=vs,v1,v2,v3,v4 vt:1,v4 1,v3可增广链： vt-v4-v2-v1-vs vt-v3-v2-v1-vs,1,v4,1,v3,2.调整流量(选择一条可增广链:vs-v1-v2-v4-vt)调整量 t调整后得到新流量图.再标号找增广链(1) vs:,vs v1:,vs(2)E=vs,v1,但是标号不能进行下去，说明网络图中已不存在可增广链，即当前流为最大流。.maxv(f)=3+2=4+1=5,vs,v1 v3,v2 v4,vt,(4,4),(1,0) (3,0),(2,2),vs,3,vs,(3,3) (1,1) (5,4),(5,2) (2,1),5.min(E,)=(vs,v2)，(v1,v3) minc(E, )=3+2=5,例10：求结点v1至结点v7的最大流，同时写出其最小截集及截量。,v2,v3,v5,v4,v6,v7,v1,f=0,f=0,6,2,4,7,4,3,7,9,3,1,8,8,解：（1）给出一个可行流f=0， 找到一条从v1到v7的可增广链,可增广链为：v7-v6-v3-v1；可调整流量为： =1调整链的流量：xij=xij+ ；f=f+1=1,v2,v3,v5,v4,v6,v7,v1,f=0,f=0,(6,0),(2,0),(4,0),(7,0),(4,0),(3,0),(7,0),(9,0),(3,0),(1,0),(8,0),(8,0),，v1,8,v1,3,v2,1,v3,1,v6,（2）调整流量f=1,继续求出网络的一条可增广链。,v2,v3,v5,v4,v6,v7,v1,f=1,f=1,(6,0),(3,1),(7,0),(9,0),(2,0),(4,0),(4,0),(3,0),(7,0),(8,1),(1,1),(8,1),可增广链为：v7-v5-v2-v3-v1;可调整流量为：=1； 调整链的流量为： xij=xij+1; f=f+1=2,v1,7,v1,2,-v3,2,v2,2,v5,(3)调整流量f=2,继续求出网络的一条可增广链.,v2,v3,v5,v4,v6,v7,v1,f=2,f=2,(6,1),(3,0),(7,1),(9,1),(2,0),(4,0),(4,0),(3,0),(7,0),(8,1),(1,1),(8,1),v1,7,v1,5,v2,5,v5,可增广链为：v7-v5-v2-v1;可调整流量为：=5； 调整链的流量为： xij=xij+5, f=f+5=2+5=7,(4)调整流量f=7,继续求出网络的一条可增广链.,v2,v3,v5,v4,v6,v7,v1,f=7,f=7,(6,6),(3,0),(7,1),(9,6),(2,0),(4,0),(4,0),(3,0),(7,0),(8,1),(1,1),(8,6),v1,3,v5,6,v1,4,v3,4,v4,可增广链为：v7-v5-v4-v3-v1;可调整流量为：=3, 调整链上的流量为： xij=xij+3, f=f+3=7+3=10,(5)调整流量f=10,继续求出网络的一条可增广链.,v2,v3,v5,v4,v6,v7,v1,f=10,f=10,(3,0),(7,4),(9,9),(2,0),(4,3),(4,3),(3,0),(7,0),(8,1),(8,6),v1,3,v6,1,v3,3,v1,3,v4,(6,6),可增广链为：v7-v6-v4-v3-v1;可调整流量为：=1； 调整链上的流量为： xij=xij+1, f=f+1=10+1=11,(1,1),(6)调整流量f=11,继续求出网络的一条可增广链.,v2,v3,v5,v4,v6,v7,v1,f=11,(3,0),(7,5),(9,9),(2,0),(4,4),(4,3),(3,1),(7,0),(8,2),(8,6),v1,3,v1,(6,6),f=11,(1,1),2,v1,网络已不存在可增广链，因此，当前流达到最大流。,(7)已求得最大流 f=11,v2,v3,v5,v4,v6,v7,v1,f=11,(6,6),(2,0),(4,3),(3,0),(7,5),(4,4),(3,1),(1,1),(7,0),(9,9),(8,2),(8,6),f=11,最小截集为(E，)=(v2,v5),(v3,v4),(v3,v5)最小截量为C(E，)=f25+f34+f35=6+4+1=11,例11 有限容量限制的调运问题的分析 某产品从仓库Ai（i=1,2,3）运往市场Bj(j=1,2,3,4)销售。已知各仓库的可供量、各市场的需求量及Ai仓库至Bj市场路径上的容量如表1所示（表中数字0表示两点间无直接通路）。试制定一个调运方案使从各仓库调运产品总量最多。,vs,A1,A2,A3,B4,vt,B3,B2,B1,5,20,100,40,10,30,10,50,20,10,40,20,60,20,20,20,由此图看出，该调运方案并不能完全满足市场要求，B3市场并未完全饱和，可以通过增加A3到B3市场的容量，使B3市场得到完全饱和，增加量最少为10。,例12 发电问题有三个发电站（节点v1,v2,v3），发电能力分别为15、10和40兆瓦，经输电网可把电力送到8号地区（节点v8），电网的能力如图。求三个发电站输到这地区（节点v8）的最大电力。,30,45,15,10,20,15,10,40,15,v1,v8,v7,v6,v5,v4,v3,v2,(30,0),(45,0),(15,0),(10,0),(20,0),(15,0),(10,0),(40,0),(15,0),v1,v8,v7,v6,v5,v4,v3,v2,v0,(15,0),(40,0),(10,0),(30,20),(45,35),(15,15),(10,10),(20,20),(15,15),(10,10),(40,20),(15,15),v1,v7,v6,v5,v4,v3,v2,v0,(15,15),(40,20),(10,10),Maxv(f)=45,最小截集(E，)=（v0,v2),(v6,v5) ,(v6,v7)最小截量C (E，)=10+20+15=45,v8,