六运筹学图与网络优化.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第六章 图与网络优化,第六章 图与网络优化,第,1,节 图的基本概念,第,2,节 树,第,3,节 最短路问题,第,4,节 网络最大流问题,第,1,节 图的基本概念,例,1,：我国北京、上海等十个城市间的铁路交通图如下图所示：,北京,徐州,青岛,天津,济南,武汉,南京,上海,连云港,郑州,第,1,节 图的基本概念,例,2,：有甲、乙、丙、丁、戊五个球队，他们之间的比赛情况如下图所示：,v,甲,v,乙,v,丙,v,丁,v,戊,第,1,节 图的基本概念,一、图的基本概念,图：由一些点及一些点之间的连线组成。,边：两点之间不带箭头的连线。,弧：两点之间带箭头的连线。,无向图：由点及边组成。,有向图：由点及弧组成。,第,1,节 图的基本概念,图例：,v,2,v,1,e,3,e,2,e,1,v,2,a,1,a,2,a,3,v,3,v,1,第,1,节 图的基本概念,二、无向图的基本概念,端点：两个点,v,i,，,v,j,属于,V,，边,v,i,，,v,j,属于,E,，称,v,i,，,v,j,是边的端点。,关连边：边,v,i,，,v,j,是点,v,i,及点,v,j,的关连边。,环：边的两个端点相同。,多重边：两个点之间多于一条的边。,简单图：不含环和多重边的无向图。,多重图：不含环，但含有多重边的无向图。,第,1,节 图的基本概念,次：以点,v,i,为端点的边的个数。,悬挂点：次为,1,的点。,悬挂边：连结悬挂点的边。,奇点：次为奇数的点。,偶点：次为偶数的点。,孤立点：次为零的点。,第,1,节 图的基本概念,图例：,v,2,e,1,v,4,v,3,v,1,e,2,v,2,v,1,e,3,e,2,e,1,不连通图,第,1,节 图的基本概念,三、无向图的基本性质,任何无向图中，顶点次数的总和等于边数的,2,倍。,任何无向图中，次为奇数的顶点必为偶数个。,第,1,节 图的基本概念,四、有向图的基本概念,基础图：去掉有向图中所有弧上的箭头得到的无向图。,始点、终点：弧,(v,i,，,v,j,),中，称v,i,为弧的始点，,v,j,为弧的终点。,第,1,节 图的基本概念,五、图的综合概念,（一）无向图,链：,圈：,第,1,节 图的基本概念,初等链：链中没有重复的点。,初等圈：圈中没有重复的点。,简单链：链中没有重复的边。,简单圈：圈中没有重复的边。,第,1,节 图的基本概念,图例：,问：（,v,1,，,v,2,，,v,3,，,v,4,，,v,5,，,v,3,，,v,6,，,v,7,）？,（,v,1,，,v,2,，,v,3,，,v,6,，,v,7,）？（,v,1,，,v,2,，,v,3,，,v,4,，,v,1,）？,（,v,4,，,v,1,，,v,2,，,v,3,，,v,5,，,v,7,，,v,6,，,v,3,，,v,4,）？,（,v,1,，,v,2,，,v,3,，,v,5,，,v,4,，,v,3,，,v,4,，,v,1,）？,v,2,e,1,v,4,v,3,v,1,e,2,v,5,v,6,v,7,e,3,e,4,e,5,e,6,e,7,e,8,e,9,第,1,节 图的基本概念,（二）有向图,链：,路：,第,1,节 图的基本概念,回路：,初等路：路中没有重复的点。,初等回路：回路中没有重复的点。,第,1,节 图的基本概念,图例：,问：,（,v,3,，,a,3,，,v,2,，,a,5,，,v,4,，,a,6,，,v,5,，,a,8,，,v,3,）？,（,v,1,，,a,2,，,v,3,，,a,4,，,v,4,，,a,7,，,v,6,）？,（,v,1,，,a,2,，,v,3,，,a,8,，,v,5,，,a,10,，,v,6,）？,（,v,1,，,a,2,，,v,3,，,a,4,，,v,4,，,a,6,，,v,5,，,a,8,，,v,3,）？,v,2,a,1,v,4,v,3,v,1,a,2,v,5,v,6,v,7,a,6,a,5,a,4,a,3,a,10,a,9,a,8,a,7,a,11,第,2,节 树,一、树的概念,连通图：无向图中任意两点间至少有一条链相连。（,不连通图,）,连通分图：不连通图中每个连通的部分。,树：连通且不含圈的无向图。,第,2,节 树,二、树的性质,任何树中必然存在次为,1,的点。,（,1,）树中次为,1,的点称为树叶,（,2,）树中次大于,1,的点称为分枝点,树的点有,n,个，则该树的边必有（,n-1,）条。,任何具有,n,个点、（,n-1,）条边的连通图必是树。,树中任意两点之间有且只有唯一一条链。,从一个树中去掉任一条边，则余下的图必是不连通图。,在树中不相邻的两个点之间添上一条边，则必得到一个圈；反之再从该圈中任意去掉一条边，则必得到一个树。,第,2,节 树,图例：,v,2,v,4,v,1,v,3,v,5,第,2,节 树,三、支撑树,支撑子图,：,支撑树：如果图,G,的支撑子图是一个树,T,，则称树,T,是图,G,的一个支撑树。,支撑树的性质：图,G,有支撑树的充分必要条件是图,G,是连通图。,第,2,节 树,图例：,v,2,v,4,v,1,v,3,v,5,v,2,v,4,v,1,v,3,v,5,支撑子图,第,2,节 树,四、最小支撑树,赋权图：,最小支撑树：,第,2,节 树,最小支撑树的求解方法,方法一：避圈法,基本做法：首先选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈（每一步中，如果有两条或两条以上最小权的边，则任选一条）。,第,2,节 树,例,3,：某工厂内联结六个车间的道路网如下图所示。已知每条道路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。v,3,v,2,v,4,v,1,v,5,v,6,6,1,5,5,7,2,3,4,4,第,2,节 树,方法二：破圈法,基本做法：任取一个圈，从圈中去掉一条权最大的边，（如果有两条或两条以上最大权的边，则任去一条），在余下图中重复这个步骤，一直到得到一个不含圈的图为止。,破圈法求解例,3,习题,6-1,习题,6-1,：分别用避圈法和破圈法求下述图的最小支撑树。,1,、,2,、,2,3,1,4,9,7,4,3,6,3,2,3,1,4,5,7,4,3,5,7,4,1,第,3,节 最短路问题,一、最短路的含义,第,3,节 最短路问题,例,4,：某单行线交通网如下图所示，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从,v,1,出发，通过这个交通网到,v,8,去，求使总费用最小的旅行路线。,v,4,1,v,6,v,2,v,1,6,v,5,v,7,4,10,6,v,3,3,10,1,2,4,v,8,v,9,3,2,2,2,6,3,第,3,节 最短路问题,二、最短路问题的求解方法,（一）,Dijkstra,方法,适用条件：无负权（,ij,0,）的最短路问题,基本思路：,THANK YOU,SUCCESS,2025/5/23 周五,31,可编辑,第,3,节 最短路问题,基本解法：标号,采用两种标号：,T(Temporary),标号和,P(Permanent),标号，,T,标号为临时标号，,P,标号为固定标号。给,v,i,点一个,P,标号时，表示从,v,s,到,v,i,的最短路权，,v,i,点的标号不再改变；给,v,i,点一个,T,标号时，表示从,v,s,到,v,i,的最短路权的上界，凡没有得到,P,标号的点都有,T,标号。方法的每一步就是把某一点的,T,标号改为,P,标号，当终点,v,t,点得到,P,标号时，计算结束。,第,3,节 最短路问题,具体步骤：,第一，给,v,s,标上,P,标号,P(v,s,)=0,，其余各点为,T,标号，,T(v,j,)=+,。,第二，若,v,i,是刚标上,P,标号的点，选取所有与,v,i,有关联的弧,(,v,i,，,v,j,),中的,v,j,点，且v,j,点为,T,标号，去修改,v,j,点的,T,标号：,。,第三，比较所有具有,T,标号的点，把最小的,T,标号值所对应的点改为,P,标号，即 （如果存在两个或两个以上的最小,T,标号，则同时改为,P,标号），若所有点都获得,P,标号，停止计算（除去从,v,s,到,v,j,之间无路可走，即,T(v,j,)=+=P(v,j,),）；否则转入第二。,Dijkstra,方法求解例,4,第,3,节 最短路问题,例,5,：用,Dijkstra,方法求解下图中从,v,1,到,v,8,的最短路。,v,4,v,6,v,2,v,1,v,5,v,7,v,3,v,8,4,6,7,7,9,5,6,4,4,4,1,5,5,习题,6-2,习题,6-2,：用,Dijkstra,方法求解下列各图从,v,1,到,v,7,的最短路。,1,、,v,3,v,4,5,v,6,v,2,v,1,4,v,5,v,7,1,4,8,7,5,6,1,2,4,6,习题,6-2,2,、,v,3,v,4,v,6,v,2,v,1,v,5,v,7,5,9,1,1,8,7,5,1,2,2,5,6,12,第,3,节 最短路问题,（二）赋权无向图的最短,路,问题的求解方法,赋权无向图,G=(V,，,E),，边,v,i,，,v,j,表示既可以从,v,i,到达,v,j,，也可以从,v,j,到达,v,i,，所以边,v,i,，,v,j,可以看作是两条弧,v,i,，,v,j,),和,(v,j,，,v,i,),，且它们具有相同的权,ij,。,第,3,节 最短路问题,例,6,：计算下图所示赋权无向图中,v,1,到,v,7,的最短,路,。,v,3,v,4,5,v,6,v,2,v,1,4,v,5,v,7,1,4,8,7,5,6,1,2,5,6,第,3,节 最短路问题,小结,对于赋权无向图,G=(V,，,E),，从始点,v,s,到各个点的最短,路,，即为最短链,Dijkstra,方法不仅适用于赋权有向图,D,，也适用于赋权无向图,G,Dijkstra,方法直接给出某点（设为,v,s,）到其他所有点的最短路；不能直接给出赋权图上任意两点间的最短路,Dijkstra,方法只适用于全部权为非负情况，如果某权为,负,，则算法失效。,第,3,节 最短路问题,例,7,：求下图中从,v,s,到,v,1,的最短路。,v,s,v,1,v,2,8,5,-5,权为负数,习题,6-3,习题,6-3,：用,Dijkstra,方法求解下图从,v,1,到,v,9,的最短,路,。,v,1,v,3,v,4,v,7,v,2,v,5,v,8,v,9,3,4,2,4,11,6,5,6,2,7,8,4,v,6,5,3,第,3,节 最短路问题,三、最短路问题的应用,设备更新问题,第,3,节 最短路问题,例,10,：某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个,5,年的更新计划，使总支出最少。已知设备在各年的购买费，及不同机器役龄时的维修费如下表所示：,项目,第,1,年 第,2,年 第,3,年 第,4,年 第,5,年,购买费,11 11 12 12 13,机器役龄,0-1 1-2 2-3 3-4 4-5,维修费,5 6 8 11 18,第,3,节 最短路问题,例,10,：,解：转化为最短路问题,点,v,i,表示第,i,年年初购进一台新设备,弧（,v,i,，,v,j,）表示第,i,年年初购进的设备一直使用到第,j,年年初,权,ij,表示第,i,年年初购进设备，一直使用到第,j,年年初所需支付的购买、维修的全部费用,第,3,节 最短路问题,最短路问题图示：,16,41,30,22,18,17,16,17,41,30,22,59,23,31,v,1,v,2,v,3,v,4,v,5,v,6,23,第,4,节 网络最大流问题,例,11,：已知联结某产品产地,v,1,和销地,v,6,的交通网，如下图所示。每一弧,(v,i,，,v,j,),代表从,v,i,到,v,j,的运输线，产品经过这条弧由,v,i,输送到,v,j,，弧旁的数字表示这条运输线的最大通过能力。产品经过交通网从,v,1,输送到,v,6,。要求制定一个运输方案，使从,v,1,运输到,v,6,的产品数量最多。,v,3,8,v,5,v,2,v,110,v,4,v,6,3,6,5,4,11,3,5,17,网络,流量最大,习题,6-4,第,4,节 网络最大流问题,一、基本概念和性质,发点、收点、中间点、容量、网络：,有向图,D=(V,，,A),，,D,的每条弧,(v,i,，,v,j,),上有非负数,c,ij,称为弧的容量，在,V,中指定一点称为发点（记为,v,s,），另一点称为收点（记为,v,t,），其余点称为中间点，这样的,D,称为一个,网络,，记作,D=(V,，,A,，,C),。,流、流量：定义在网络,D,中的弧集合,A,上的一个函数,f=f,ij,称为流，称,f,ij,为弧,(v,i,，,v,j,),上的流量。,流的性质：,每个弧上的流量不超过该弧的容量。,中间点的净输出量为零。,第,4,节 网络最大流问题,可行流,：满足下述条件的流,f,称为可行流，记作,v(f),。,（,1,）容量限制条件：对网络,D,中每条弧,(v,i,，,v,j,),，有,0f,ij,c,ij,（,2,）平衡条件：,中间点每条弧,v,i,：流出量与流入量相等,发点,v,s,、收点,v,t,：从点,v,s,流出的量等于点,v,t,流入的量,可行流的性质：可行流总是存在的。,零流：网络,D,中所有弧的流量,f,ij,=0,的可行流。,第,4,节 网络最大流问题,v,3,8,v,5,v,2,v,1,10,v,4,v,6,3,6,5,4,11,3,5,17,v,3,v,5,v,2,v,1,v,4,v,6,可行流,第,4,节 网络最大流问题,最大流问题：在网络,D,中，求,流量最大,的可行流，记作,v(,f,),。,饱和弧、非饱和弧、零流弧、非零流弧：,（,1,）饱和弧：网络,D,中,f,ij,=c,ij,的弧,（,2,）非饱和弧：网络,D,中,f,ij,c,ij,的弧,（,3,）零流弧：网络,D,中,f,ij,=0,的弧,（,4,）非零流弧：网络,D,中,f,ij,0,的弧,第,4,节 网络最大流问题,链,：网络,D,中联结发点,v,s,和收点,v,t,的一条链,，定义链的方向是从,v,s,到,v,t,。,（,1,）前向弧,+,：弧的方向与链的方向一致,（,2,）后向弧,-,：弧的方向与链的方向相反,增广链,：,f,是一个可行流，,是从,v,s,到,v,t,的一条链，若满足,则称,为从,v,s,到,v,t,关于,f,的增广链。,增广链的实际意义：沿着链,从,v,s,到,v,t,输送的流还有潜力可挖，即可以把流量提高。,定理：可行流,f,是最大流的充分必要条件是不存在从,v,s,到,v,t,关于,f,的增广链。,第,4,节 网络最大流问题,根据,例,11,所描述的问题：,找出链,（,v,1,，,v,2,，,v,3,，,v,4,，,v,5,，,v,6,）,的前向弧和后向弧。,v,3,8,v,5,v,2,v,1,10,v,4,v,6,3,6,5,4,11,3,5,17,链,第,4,节 网络最大流问题,根据例,11,所描述的问题：给出一个运输方案，如下图所示。,试说明链,（,v,1,，,v,2,，,v,3,，,v,4,，,v,5,，,v,6,）,是否为增广链？,v,3,v,5,v,2,v,1,v,4,v,6,10,5,4,3,17,增广链,第,4,节 网络最大流问题,二、求解方法,标号法,解题过程：从一个可行流,f,出发，,（,1,）标号过程：通过标号寻找增广链,（,2,）调整过程：沿增广链调整,f,以增加流量,基本解法：,标号点：用,v,j,（，）表示,表示,v,j,点标号是从哪一点得到的，用,v,i,表示,表示,v,j,点与之间的关系，用,+,或,-,表示,第,4,节 网络最大流问题,具体步骤,（一）标号过程,第一，给,v,s,标上（,0,，,+,），则,v,s,是标号未检查点，其余各点都是未标号点。,第二，取标号未检查点,v,i,，对所有未标号点,v,j,有：,1,）若在弧（,v,i,，,v,j,）上，,f,ij,c,ij,，则给,v,j,标上（,v,i,，,+,）；,2,）若在弧（,v,k,，,v,i,）上，,f,ki,0,，则给,v,k,标上（,v,i,，,-,）。,则,v,j,（,v,k,）成为标号未检查点，而,v,i,成为标号已检查点，在,v,i,标号下面划一横线,重复,1,）,2,），直至,v,t被标上号，则得到一条从,v,s,到,v,t,的增广链,，转入调整过程。,第三，若所有标号都已检查过，而标号过程进行不下去时，则停止计算，此时获得的可行流为最大流,f,。,第,4,节 网络最大流问题,（二）调整过程,第一，按照,v,t,及其它各点标号的第一个部分反向追踪，找出增广链,。,第二，,则获得新的可行流，重复标号过程调整过程，直至得出最大流,f,，其流量,v(f,)=,发点,v,s,的流出量收点,v,t,的流入量。,第,4,节 网络最大流问题,例,12,：求下图所示网络中的最大流，弧旁的数字是（,c,ij,，,f,ij,）。,v,1,(5,1),v,3,v,2,v,s,(3,3),v,4,v,t,(1,1),(2,2),(1,1),(5,3),(3,0),(4,3),(2,1),第,4,节 网络最大流问题,例,13,：求下图所示网络从,v,s,到,v,t,的最大流，弧旁的数字是（,c,ij,，,f,ij,）。,(10,10),v,t,v,3,v,6,v,2,v,s,(14,10),v,5,(5,5),(6,4),(3,1),(9,9),(6,6),(10,7),(5,5),(5,3),(4,3),(4,4),v,4,第,4,节 网络最大流问题,小结,在计算过程中，应注意采用,“,先标号的先检查,”,的原则，从而保证以尽可能少的调整次数求得网络最大流。,习题,6-4,习题,6-4,：用标号法求下图所示网络从,v,1,到,v,6,的最大流，弧旁的数字是（,c,ij,，,f,ij,）。,v,3,(8,3),v,5,v,2,v,1,(10,5),v,4,v,6,(3,2),(6,3),(5,1),(4,1),(11,6),(3,3),(5,2),(17,2),THANK YOU,SUCCESS,2025/5/23 周五,61,可编辑,