运筹学第六章图与网络分析优秀PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,*,第六章,图与网络分析,6.1,图的基本概念与数学模型,6.2,树图和图的最小部分树,6.3,最短路问题,6.4,中国邮路问题,6.5,网络最大流问题,6.6,网络模型的实际应用,1,2025/1/5 周日,第六章 图与网络分析,图是一种模型，如公路、铁路交通图，通讯网络图等。,图是对现实的抽象，以点和线段的连接组合表示。,2,2025/1/5 周日,6.1,图的基本概念和模型,一、概念,（,1,）图：点,V,和边,E,的集合，用以表示对某种现实事物的抽象。记作,G=,V,E,V=,v,1,v,2,v,n,E=,e,1,e,2,e,m,点：表示所研究的事物对象；边：表示事物之间的联系。,v,1,v,2,v,3,v,4,v,0,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,0,（,2,）若边,e,的两个端点重合，则称,e,为环。,（,3,）多重边：若某两端点之间多于一条边，则称为多重边。,3,2025/1/5 周日,（,4,）简单图：无环、无多重边的图称为简单图。,（,5,）链：点和边的交替序列，其中点可重复，但边不能重复。,（,6,）路：点和边的交替序列，但点和边均不能重复。,（,7,）圈：始点和终点重合的链。,（,8,）回路：始点和终点重合的路。,（,9,）连通图：若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。,（,10,）子图，部分图：设图,G1=,V1,E1,G2=,V2,E2,如果有,V1,V2,，,E1,E2,，则称,G1,是,G2,的一个子图；若,V1=V2,，,E1,E2,，则称,G1,是,G2,的一个部分图。,（,11,）次：某点的关联边的个数称为该点的次，以,d(v,i,),表示。,4,2025/1/5 周日,二、图的模型,例：有甲、乙、丙、丁、戊、己六名运动员报名参加,A,、,B,、,C,、,D,、,E,、,F,六个项目的比赛。如表中所示，打“”的项目是各运动员报名参加比赛的项目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？,甲 乙 丙 丁 戊 己,项目,人,ABCDEF,5,2025/1/5 周日,建立模型：,解：项目作为研究对象，排序。,设 点：表示运动项目。,边：若两个项目之间无同一名运动员参加。,A,B,C,D,E,F,ACDEFB,AFEDCB,ACBFED,AFBCDE,顺序：,6,2025/1/5 周日,6.2,树图和图的最小部分树,（,1,）树：无圈的连通图称为树图，简称为树。,一、树图的概念,7,2025/1/5 周日,（,2,）树的特性,：,树是边数最多的,无圈,连通图。在树中任加一条边，就会形成圈。,树是边数最少的连通图。在树中任减一条边，则不连通。,（,3,）图的最小部分树：,定义：若,G1,是,G2,的一个部分图，且为树图，则称,G1,是,G2,的一个部分树。,G2,：,A,B,C,D,5,4,7,3,6,5,5,7,6,G1,：,A,C,B,D,8,2025/1/5 周日,定义：树枝总长为最短的部分树称为图的最小部分树。,二、最小部分树的求法,例：要在下图所示的各个位置之间建立起通信网络，,试确定使总距离最佳的方案。,树枝：树图中的边称为树枝。,9,2025/1/5 周日,S,A,B,C,D,E,T,2,5,2,4,1,4,3,1,7,5,5,7,最小部分树长,L,min,=14,1.,避圈法,10,2025/1/5 周日,1.,避圈法：将图中所有的点分,V,为,V,两部分，,V,最小部分树内点的集合,V,非最小部分树内点的集合,任取一点,v,i,加粗，令,v,i,V,，,取,V,中与,V,相连的边中一条最短的边,(v,i,v,j,),，加粗,(v,i,v,j,),，令,v,j,V,重复，至所有的点均在,V,之内。,2.,破圈法：,任取一圈，去掉其中一条最长的边，重复，至图中不存在任何的圈为止。,11,2025/1/5 周日,S,A,B,C,D,E,T,2,5,2,4,1,4,3,1,7,5,5,7,最小部分树长,L,min,=14,2.,破圈法,12,2025/1/5 周日,6.3,最短路问题,在图示的网络图中，从给定的点,S,出发，要到达目的地,T,。问：选择怎样的行走路线，可使总行程最短？,方法：,Dijkstra,（,D,氏）标号法,按离出发点的距离由近至远逐渐标出最短距离和最佳行进路线。,S,1,求某两点间最短距离的,D,（,Dijkstra,）氏标号法,2,4,7,13,2025/1/5 周日,S,A,B,C,D,E,T,2,5,2,4,1,4,3,1,7,5,5,7,0,2,4,4,7,8,9,14,13,5,9,4,最短路线：,S,A,B,E,D,T,最短距离：,L,min,=13,14,2025/1/5 周日,2,求任意两点间最短距离的矩阵算法,构造任意两点间直接到达的最短距离矩阵,D,（,0,）,=,d,ij,（,0,）,S A B C D E T S 0 2 5 4,A 2 0 2 7 B 5 2 0 1 5 3 C 4 1 0 4 D 7 5 0 1 5 E 3 4 1 0 7 T 5 7 0,D,（,0,）,=,构造任意两点间直接到达、或者最多经过,1,个中间点到达的最短距离矩阵,D,（,1,）,=,d,ij,（,1,）,15,2025/1/5 周日,其中,d,ij,（,1,）,=min,d,ir,（,0,）,+d,rj,（,0,）,，,S A B C D E T S 0 2 4 4,9 8 A 2 0 2 3 7 5 12 B 4 2 0 1 4 3 10 C 4 3 1 0 5 4 11 D 9 7 4 5 0 1 5 E 8 5 3 4 1 0 6 T 12 10 11 5 7 0,D,（,1,）,=,i,r,j,d,ir,（,0,）,d,rj,（,0,）,r,d,SE,（,1,）,=min,d,SS,（,0,）,+d,SE,（,0,）,d,SA,（,0,）,+d,AE,（,0,）,d,SB,（,0,）,+d,BE,（,0,）,d,SC,（,0,）,+d,CE,（,0,）,d,SD,（,0,）,+d,DE,（,0,）,d,SE,（,0,）,+d,EE,（,0,）,d,ST,（,0,）,+d,TE,（,0,）,=8,例如,16,2025/1/5 周日,其中,d,ij,（,2,）,=min,d,ir,（,1,）,+d,rj,（,1,）,S A B C D E T S 0 2 4 4 8,7 14 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 14 11 9 10 5 6 0,D,（,2,）,=,i,r,j,d,ir,（,1,）,d,rj,（,1,）,r,构造任意两点间最多可经过,3,个中间点到达的最短距离矩阵,D,（,2,）,=,d,ij,（,2,）,17,2025/1/5 周日,其中,d,ij,（,3,）,=min,d,ir,（,2,）,+d,rj,（,2,）,S A B C D E T S 0 2 4 4 8,7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0,D,（,3,）,=,i,r,j,d,ir,（,2,）,d,rj,（,2,）,r,构造任意两点间最多可经过,7,个中间点到达的最短距离矩阵,D,（,3,）,=,d,ij,（,3,）,18,2025/1/5 周日,说明：,一般，对于,D,（,k,）,=,d,ij,（,k,）,，其中,d,ij,（,k,）,=min,d,ir,（,k-1,）,+d,rj,（,k-1,）,，,k=0,，,1,，,2,，,3,，,最多可经过,2,k,-1,个中间点：其数列为,0,，,1,，,3,，,7,，,15,，,31,，,，,2,k,-1,，,收敛条件：,当,D,（,k+1,）,=D,（,k,）,时，计算结束；,设网络中有,p,个点，即有,p-2,个中间点，,则,2,k-1,-1 p-2,2,k,-1,k-1log,2,(p-1),k,Klog,2,(p-1)+1,，,计算到,k=lg(p-1)/lg2+1,时，收敛，计算结束。,19,2025/1/5 周日,例：有,7,个村镇要联合建立一所小学，已知各村镇小学生的人数大致为,S30,人，,A40,人，,B20,人，,C15,人，,D35,人，,E25,人，,T50,人。问：学校应建在那一个地点，可使学生总行程最少？,S A B C D E T S 0 2 4 4 8,7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0,L=,30 40 20 15 35 25 50,人数,=1325 1030 880 1035 910 865 1485,T,解：,20,2025/1/5 周日,6.4,中国邮路问题,问题：一名邮递员从邮局出发，试选择一条最短的投递路线？,v,1,v,2,v,3,v,4,v,5,v,6,v,8,v,7,v,9,v,10,v,11,v,12,v,13,邮局,4,4,4,5,5,1,2,4,1,2,5,4,4,7,4,2,2,21,2025/1/5 周日,22,2025/1/5 周日,奇点：图中次为奇数的点称为奇点。,偶点：图中次为偶数的点称为偶点。,结论：,最短投递路线应具有下述特征：,若图中所有的点均为偶点，则可不重复走遍所有街道；,重复走的路线长度应不超过所在回路总长度的一半。,23,2025/1/5 周日,步骤：,两两连接所有的奇点，使之均成为偶点；,2.,检查重复走的路线长度，是否不超过其所在回路总长的一半，若超过，则调整连线，改走另一半。,24,2025/1/5 周日,v,1,v,2,v,3,v,4,v,5,v,6,v,8,v,7,v,9,v,10,v,11,v,12,v,13,邮局,4,4,4,5,5,1,2,4,1,2,5,4,4,7,4,2,2,投递距离：,L=60+18=78,25,2025/1/5 周日,6.5,网络最大流问题,一、网络最大流中有关概念,有向图：含有以箭头指示方向的边的网络图。,弧：有向图上的边称为弧。用（,v,i,v,j,）表示。,弧的容量：弧上通过负载的最大能力，简称容量。以,c,ij,表示。,流：加在网络每条弧上的一组负载量，以,f,ij,表示。,可行流：能够通过网络的负载量，通常应满足两个条件：容量限制条件：对所有的弧，,0,f,ij,c,ij,中间点平衡条件：对任何一个中间点，流入量,=,流出量,发点、收点、中间点：流的起源点称发点，终到点称收点，其余的点称中间点。,最大流；能够通过网络的最大流量。,割集：一组弧的集合，割断这些弧，能使流中断。简称割。,26,2025/1/5 周日,8(8),v,1,v,s,v,2,v,3,v,4,v,t,7(5),9(4),9(9),2(0),6(1),5(5),10(8),(0,+,),(v,s,2),(v,2,2),(v,1,2),(v,3,1),(v,4,1),5(4),c,ij,f,ij,27,2025/1/5 周日,割的容量：割集中各弧的容量之和。,最小割：所有割集中容量之和为最小的一个割集。,前向弧,+,：一条发点到收点链中，由发点指向收点的弧，又称正向弧。,后向弧,-,：一条发点到收点链中，由收点指向发点的弧，又称逆向弧。,增广链：由发点到收点之间的一条链，如果在前向弧上满足流量小于容量，即,f,ij,0,，则称这样的链为增广链。,。,二、两个定理,定理：网络的最大流量等于它的最小割集的容量。,定理：当网络中不存在任何增广链时，则网络达到最大流状态。,28,2025/1/5 周日,s,t,6(4),5(3),4(4),8(7),设有如下增广链：,f=1,该网络没有达到最大流状态。,29,2025/1/5 周日,三、网络最大流的标号算法,(Ford-Fulkerson,标号算法,),基本思想：寻找增广链，改善流量分布；再重复，直到不 存在任何增广链为止。,步骤：,给始点标号：（,0,，,+,）,从已标号点,i,出发，看与其相关联的未标号点,j,上的弧，对,+,，若有,0,f,ij,c,ij,，则可对,j,点标号，记（,i,(j),），,其中,(j)=min(i),，,c,ij,-f,ij,对,-,，若有,0 f,ji,c,ij,，也可对,j,点标号，记（,i,(j),），,其中,(j)=min(i),，,f,ji,（注：若有多个可标号点，可任选其中之一。）,若标号中断，则得到最大流状态，否则，重复，继续标号，至收点得到标号，转。,30,2025/1/5 周日,当收点得到标号，则沿标号得到的增广链进行流量调整：,对,+,，,f,ij,=f,ij,+(t),对,-,，,f,ij,=f,ij,-(t),其余弧上的流量不变。,重复上述过程。,最小割集：已标号点集合与未标号点集合相连接的弧中，流量,=,容量的弧。,31,2025/1/5 周日,8(8),v,1,v,s,v,2,v,3,v,4,v,t,7(6),9(5),9(9),2(0),6(0),5(5),10(9),5(3),(0,+,),(v,s,1),(v,2,1),(v,1,1),最大流量：,f,max,=14,最小割集：,(v,3,v,t,),(v,2,v,4,),32,2025/1/5 周日,6.6,网络模型的实际应用,例,1,：,王经理花费,12000,元购买了一台微型车，以后年度的维护费用取决于年初时汽车的役龄，如表示。为避免使用旧车带来较高的维护费用，王经理可选择卖掉旧车，购买新车使用的方案，旧车的预计收入如表示。为简化计算，假定任何时刻购买新车都需花费,12000,元，王经理的目标是使净费用最小（购置费,+,维护费,-,卖旧车收入）。,役龄,(,年,),年维护费,预计收入,单位：元,012345,200040005000900012000,700060002000 1000 0,33,2025/1/5 周日,解：,用网络图模型描述，归结为最短路问题,。,7,7,7,7,7,1,2,3,4,5,6,12,12,12,12,21,21,21,31,31,44,1,年初,5,年末,34,2025/1/5 周日,例,2,：,图示岛屿与河岸有数座桥相联，问至少需要炸毁几座桥，可中断两岸的交通？,A,B,C,D,E,F,35,2025/1/5 周日,A,B,C,F,E,D,2,2,2,1,3,1,1,1,1,36,2025/1/5 周日,例,3,：有,3,根相同的轴,A1,、,A2,、,A3,，另有三根相同的齿轮,B1,、,B2,、,B3,。因为精度不高，不能做到任意的互相配合，其中,A1,能与,B1,、,B2,配合，,A2,能与,B2,、,B3,配合，,A3,能与,B1,、,B3,配合。要求确定合适的配合方案，以得到最多的配合数，将此问题归为网络最大流问题。,A1,A2,A3,B1,B2,B3,1,1,1,1,1,1,S,T,1,1,1,1,1,1,37,2025/1/5 周日,