清华大学出版《运筹学》第三版课件第六章.ppt

单击此处编辑母版标题样式,OR3,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 图与网络分析,A,B,C,D,E,引论,:,哥尼斯堡七桥问题,A,B,C,D,A,B,c,D,OR3,1,铁路交通图,此图是我国北京,上海等十个,城市间的交通图,反映了这,十个城市间的铁路分布情况,.,点表示城市,点间的连线表示,两个城市间的铁路线,.,诸如此类问题还有电话线分,布图或煤气管道分布图等,.,北京,济南,徐州,青岛,南京,上海,连云港,郑州,武汉,天津,OR3,2,球队比赛图,五个球队比赛,比过的两个队之间用连线相连，还没有比赛的队之间没有连线,v,5,v,4,v,3,v,2,v,1,OR3,3,6.1,图的基本概念,图是由点和线构成的。点代表所研究的对象，线表示对象间的关系。,1,、图的分类：无向图，有向图,无向图：由,点,和,边,所组成的图。表示为,G=(V,E).,有向图：由,点,和,弧,所组成的图。表示为,D=(V,A),点的集合用,V,表示，,V=,v,i,2,、图上的基本概念：,（,1,）边：图中不带箭头的连线叫做边,(edge),，,边的集合记为,E=,e,j,，,一条边可以用两点,v,i,v,j,表示,e,j,=,v,i,v,j,.,弧：图中带箭头的连线叫做弧,(arc),弧的集合记为,A,，,A=,a,k,一条弧也是用两点表示，,a,k,=,v,i,v,j,弧有方向：,v,i,为始点，,v,j,为终点,OR3,4,例1.,v,7,v,1,v,2,v,3,v,4,e,1,e,2,e,3,e,4,e,5,e,6,e,7,a,9,v,1,v,2,v,3,v,4,v,5,v,6,a,1,a,2,a,8,a,4,a,3,a,5,a,6,a,7,a,10,环：两端点相同的边。,多重边：若两点之间有多于一条边，则称这些边为多重边。,简单图：无环、无多重边的图。,多重图：无环，但允许有多重边的图。,e,7,OR3,5,（,2,）次：以点,u,为端点的边的条数，叫做点,u,的次。,悬挂点：次为,1,的点叫做悬挂点；,孤立点：次为,0,的点叫做孤立点；,奇点：次为奇数则称奇点；,偶点：次为偶数则称偶点。,基本定理：,1,、图,G=(V,E),中，所有点的次之和是边数的两倍，即,2,、任一图中，奇点的个数为偶数。,OR3,6,（,3,）链：点边交替序列称为链；,圈：首尾相连的链称为圈；,初等链：链中各点均不同的链；,初等圈：圈中各点均不同的圈；,简单链：链中边均不同的链；,简单圈：圈中边均不同的圈。,（,4,）连通图：任意两点之间至少有一条链的图。,连通分图：对不连通的图，每一连通的部分称为一个连通分图。,支撑子图：对,G=(V,E),，若,G,=(V,E,),，使,V,V,，,E,包含于,E,，则,G,是,G,的一个支撑子图。,赋权图：在图中，如果每一条边（弧）都被赋予一个权值,w,ij,，则称图,G,为赋权图。,（,5,）路：在有向图中，如果链上每条弧的箭线方向与链行进方向相同，则称之为路。,回路：首尾相接的路称回路,OR3,7,6.2,树与最小生成树,1,、树的概念与性质,树：,无,圈,的,连通图,称为树。,定理：,定量,3,：设图,G=,（,V,E),是一个树，,p(G,)2,则,G,中至少有两个悬挂点。,定量,4,：图,G=,（,V,E),是一个树的充要条件是,G,不含圈，且恰有,p,1,条边。,定量,5,：图,G=,（,V,E),是一个树的充要条件是,G,是连通图，并且,q(G,)=p(G)-1.,定量,6,：图,G=,（,V,E),是一个树的充要条件是任意两个顶点之间恰好有一条链。,OR3,8,2,、图的支撑树,支撑树：设,T=(V,E,),是图,G=(V,E),的支撑子图，如果,T,是一个树，则称,T,为,G,的支撑树。,定理,7,：图,G,有支撑树的充要条件是图,G,是连通的。,求支撑树的方法：,破圈法：即任取一个圈，从圈中去掉一条边，对余下的图重复这个步骤，直至图中不含圈为止。,避圈法：在图中每次任取一条边，与已经取得的任何一些边不够成圈，重复这个过程，直到不能进行为止。,OR3,9,3,、最小支撑树,最小支撑树：当一个连通图的所有边都被赋权，则取不同边构成的支撑树具有不同的总权数，其中总权数最小的支撑树称为最小支撑树。,求最小支撑树的方法：,破圈法：在连通图中任取一个圈，去掉一条权数最大的边，在余下的图中重复上述步骤，直至无圈为止。,避圈法：将连通图所有边按权数从小到大排序，每次从未选的边中选一条权数最小的边，并使之与已选的边不能构成圈，直至得到最小支撑树。,OR3,10,避圈法的基本步骤,P,259,第一步：令,i,1,，,E,0,空集。,第二步：选一条边,e,i,EE,i-1,使,e,i,是使,（,V,E,i-1,e,）不含圈的所有边,e,（,e EE,i-1,）中权最小的边。令,E,i,E,i-1,e,i,如果这样的边不存在，则,T=(V,E,i-1,),是最小树。,第三步：把,i,换成,i,1,，转入第,2,步。,OR3,11,6.3,最短路问题,引例,:,单行线交通网：,v,1,到,v,8,使总费用最小的旅行路线。,最短路问题的一般描述：,对,D=,（,V,，,A,），,a=,（,v,i,，,v,j,），,w,（,a,）,=,w,ij,，,P,是,v,s,到,v,t,的路，定义路,P,的权是,P,中所有弧的权的和，记为,w,（,P,），,则最短路问题为：,V,2(v,1,6）,路,P,0,的权称为从,v,s,到,v,t,的距离，记为：,d,（,v,s,，,v,t,）,最短路：赋权有向图,D=,（,V,，,A,）中，从始点到终点的,权值最小的路称为最短路。,OR3,12,最短路算法,Dijkstra,算法：有向图，,wij0,一般结论：,Dijkstra,算法基本思想,:,采用标号法,:P,标号和,T,标号,P,标号,：已确定出最短路的节点,(,永久性标号,),。,T,标号,：未确定出最短路的节点，但表示其距离的上限,(,试探性标号,),。,算法的每一步都把某一点的,T,标号改为,P,标号直至改完为止,.,S,i,：,P,标号节点的集合。,OR3,13,Dijkstra,算法的基本步骤：,1:,给,v,s,以,P,标号,P(v,s,)=0,其余各点均给,T,标 号,T(v,i,)=+,2:,若,v,i,点为刚得到,P,标号的点,考虑这样的点,v,j,(,v,i,v,j,)A,且,v,j,为,T,标号,.,3:,对,v,j,的,T,标号进行如下更改,:,4:,比较所有具有,T,标号的点,把最小者改为,P,标号,.,当存在两个以上最小值时,可同时改为,P,标号,.,若全部改为,P,标号,则停止,.,否则转回,(2).,OR3,14,用,Dijkstra,算法求图中,v,1,到,v,8,的最短路,OR3,15,OR3,16,OR3,17,OR3,18,OR3,19,最短路问题的算法：,Bellman,算法,适用范围：有向图，且图中有,wij0,。,假设前提：任意两点,v,i,v,j,之间都有一条弧。（若无，则添加一条虚拟的弧，且其权值为。）,公式来源分析：,OR3,20,基本思路：,用,逐次逼近,来求网络中的最短路：每次求出从始点到网络中其余各点,有限制,的最短路。,若第一次逼近即得最短路，则限制其最短路只有一条弧，其路长记为 ；,若第二次逼近即得最短路，则限制其最短路不超过两条弧，其路长记为 ；,依此类推，第,k,次逼近得最短路，则限制其不超过,k,条弧。,一般的，最多逼近,n-1,次即得到最短路。,OR3,21,为了求得公式的解可以运用以下公式：,令：,OR3,22,基本步骤：,1,、令 ，其中，若,v,1,与,v,j,间没弧，则记,w,1j,=+,。,2,、,当计算到第,k,步时，若有 成立，则停止计算。即为从,v,1,到各点的最短路。,OR3,23,举例：求,v,1,到各点的最短路,OR3,24,计算过程见下表：,0,2,5,-3,0,-2,4,0,6,4,0,0,-3,0,4,7,2,0,3,-1,0,0,2,5,-3,0,2,0,-3,6,11,0,2,0,-3,6,6,15,0,2,0,-3,3,6,14,10,0,2,0,-3,3,6,9,10,0,2,0,-3,3,6,9,10,OR3,25,当计算到第六步时，计算结果与第五步相同，则表中第六列的数字分别表示点,v,1,到其它各点的最短路。,寻找最短路径的方法：反向追踪法。,OR3,26,OR3,27,最短路问题的应用,（使总费用最小的问题）,奎克公司获悉它的一个竞争对手计划将把一种很有销售潜力的新产品投放市场。奎克公司也一直在研制一种类似的产品，并计划在,20,个月后投放市场。但是，研究临近结束，奎克公司的管理者希望迅速推出产品去参与竞争。,现在还有四个没有时间重叠的阶段没有完成，包括正以正常速度进行剩下的研究工作。然而，每个阶段的实施水平可以从正常水平提高为优先水平或应急水平，使之能够加速完成；而且最后三个阶段中都可以考虑提高实施水平。,OR3,28,OR3,29,当网络中实际行进在多于一个节点结束时，在每个这样的节点和虚拟目标地之间插入一条长度为,0,的弧，从而使得网络中仍然只有一个目标地。,OR3,30,6.4,最大流问题,1,、掌握可行流、增广链、截集、截量等基本概念,2,、掌握基本定理,8,及其证明,3,、掌握求最大流的标号法,OR3,31,引例：如下输水网络，南水北调工程，从,v,s,到,v,t,送水，弧旁数字前者为管道容量，后者为现行流量，如何调运输水最多？,v,s,v,t,v,2,v,1,v,4,v,3,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(2,1),(5,3),OR3,32,最大流问题的基本概念,1,、容量网络,如果有向连通网络图,D=(V,A),的每一条弧（,v,i,，,v,j,）上都被赋予一个非负数，以表示通过该弧的最大通行能力，称为弧的容量，则称这样的网络为容量网络，记作,D=(V,A,C),。,OR3,33,2,、流,在,D=(V,A,C),中，如果实际通过每一弧（,v,i,，,v,j,）的流量是,f,ij,，则称集合,f=,f,ij,为网络,D=(V,A,C),上的一个流。,OR3,34,3,、可行流,对给定的,D=(V,A,C),，把满足下列两个条件,1,），,2,）的流称为可行流。,1,）容量限制条件,:,对,D,中的每一条弧（,v,i,，,v,j,），有,0 f,ij,c,ij,;,2,）平衡条件,:,对中间点,v,i,，流入量等于流出量,即,;,对发点,v,s,，有,;,对收点,v,t,，有,.,是可行流的流量，是发点的净输出量，是收点的净入量。,注意：任一,D=(V,A,C),都存在可行流。如零流就是一个可行流。如果,D=(V,A,C),中没有给出弧上的流量,f,ij,，可认为,f,ij,0,。,OR3,35,4,、最大流,使得从网络发点到收点得总流量（,W,）达到最大得可行流,f=,f,ij,称为最大流。,最大流问题就是求一个流,f=,f,ij,使其流量 达到最大，并且满足：,注意：寻求网络中的最大流就相当于求线性规划模型的最优解。,OR3,36,5.,截集、截量、最小截量,截量：截集（，）中所有弧的容量之和称为该截集的截量，记为,c,（，）,.,最小截集：在,D=(V,A,C),的所有截集中，截量最小的截集称为最小截集，记为,(),。,OR3,37,注意：容量网络图,D,的截集不是唯一的，截集个数是有限的。如果在图,D,中把任何一个截集中的弧丢掉，那么从发点就不能通往收点。所以，截集是从发点到收点的必经之道。从而，有任何一个可行流的流量都不会超过任意截集的截量。,OR3,38,6,、增广链,在容量网络,D=(V,A,C),中，若 为网络中从,v,s,到,v,t,的一条链，给链 定方向为从,v,s,到,v,t,，上与 同方向的弧称为前向弧，与 反方向的弧称为后向弧，前向弧和后向弧的集合分别用 和 来表示。设 是一个可行流，如果满足：,则称 为从,v,s,到,v,t,的（关于,f,的）增广链。,OR3,39,增广链的实际意义：,沿着这条链从,v,s,到,v,t,输送的流，还有潜力可挖，只需按照定理证明中的调整方法，就可以把流量提高；调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。这样，就得到了一个寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的增广链时就的得到了最大流。,OR3,40,7,、最大流量最小截量定理,定理,8,：可行流 是最大流的充要条件是不存在从,v,s,到,v,t,的关于 的增广链。,重要结论：,任一容量网络,D=(V,A,C),中，最大流的流量等于最小截集的截量。,可行流,f,是最大流的充分必要条件是不存在从,到,可行流,f,是最大流的充分必要条件是不存在从,到,可行流,f,是最大流的充分必要条件是不存在从,OR3,41,定理,8,可行流 是最大流的充要条件是不存在从,vs,到,vt,的关于 的增广链证明：,先证明：若可行流 是最大流，则 中不存在关于 的增广链。,若 是最大流，设,D,是 的增广链。令,：,由增广链的定义可知 ，令：,不难验证该流是一个可行流，且其最大流量比原流大 。,则，证明原可行流不是最大流，与假设矛盾。,OR3,42,再证明：若,D,中不存在关于 的增广链，则该流是最大流。,利用下面的方法来定义,V,1:,OR3,43,求,最大流的方法：标号法,方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链为止。,如何找增广链？如何调整？,设已有一个可行流,f,（若网络中没有给定,f,，则可以设,f,是零可行流），通过标号过程来找到增广链，通过调整过程来对增广链上的流量进行调整。,第一步 标号过程，通过标号来寻找可增广链；,第二步 调整过程，沿可增广链调整,f,，以增加流量。,OR3,44,标号法的基本方法介绍,1.,标号过程,在这个过程中，网络中的每个标号点的标号由两个标号组成：,第一个标号表明该点的标号是从哪一点得到的，以便找到增广链；,第二个标号是为确定增广链上的调整量用的。,OR3,45,标号过程,1,）给发点以标号（,0,，,+,）。,2,）选择一个已标号的顶点,v,i,，对于,v,i,的所有,未给标号的邻接点,按下列规则处理：,若弧（,v,i,v,j,),上,f,ij,c,ij,，则令,l(v,j,),minl(v,i,),c,ij-,f,ij,，并给,v,j,以标号（,v,i,，,l(v,j,),）。,若弧（,v,j,，,v,i,）上,f,ji,0,，则令,l(v,j,),minl(v,i,),f,ji,并给,v,j,以标号（,v,i,，,l(v,j,),）。,重复第,2,）步，直到收点被标号或不再有顶点可标号时为止。若收点得到标号，说明存在增广链，转调整过程。若收点未获得标号，标号过程已无法进行时，说明,f,已是最大流。,OR3,46,调整过程,1,）按上一步的第一个标号用反向追踪法找出增广链。,2,）令调整量 ,l(v,t,),，且令：,然后去掉所有标号，回到标号过程，对可行流 重新标号。,OR3,47,举例,1,：解水网最大流问题,OR3,48,OR3,49,(0,+),(v,s,4),(v,3,1),(-v,1,1),(v,2,1),(-v,4,1),(5,2),(1,0),(1,0),(2,2),OR3,50,(5,2),(1,0),(1,0),(2,2),OR3,51,最大流应用举例,有四个人，四项任务，甲可以承担,A,C,，乙可以承担,A,丙可以承担,A.C,，丁可以承担,B,C,D,限量每人只能承担一项任务，每项任务也只需要一人承担，问最多能安排几个人工作？如何安排？,OR3,52,令所有弧的容量均为,1,，该问题即求网络最大流及流量问题。,S,丁,丙,乙,甲,D,C,B,A,t,1(1),1(1),1(1),1(1),1(1),1(1),1(1),1(1),1(1),1(0),1(0),1(0),1(0),1(0),1(0),1(0),OR3,53,