第11章图与网络模型ppt课件.ppt

《第11章图与网络模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《第11章图与网络模型ppt课件.ppt（73页珍藏版）》请在三一办公上搜索。

1、运 筹 学 Operations Research,Chapter 11 网络模型Network Modeling,11.1基本概念11.2 最小(支撑)树问题11.3 最短路问题 11.4 最大流问题11.5最小费用最大流11.6 中国邮路问题,11/13/2022,欧拉早年解决著名的哥尼斯堡七桥问题，哥尼斯堡城市中有一条河，河中有两个岛，河的两岸和河中的两个小岛有7座桥。当地居民提出：一个步行者能否通过每座桥一次且仅一次就能返回原出发地。,D,C,A岸,B岸,11/13/2022,欧拉将此问题归为一笔画问题，即能否从某点开始一笔画出这个图形，最后回到出发点，而不重复。,C,D,A,B,欧拉

2、证明了这是不可能的。,11/13/2022,在这一时期，还有许多游戏问题，诸如环球旅行、迷宫问题、博奕问题等难题，吸引了许多学者，这些问题看起来似乎是一些无足轻重的游戏，但常常 是由于这些游戏引出了许多实用意义的新问题，开辟了新学科。图论在现实生活中很多，如各种通信网络的合理架设，交通网络的合理分布，邮递员送信，怎么走完他负责投递的全部街道，完成任务回到邮局，使走的路线最短，电子商务物流配送中的最佳运送路线的选择等，都属于图论问题。,11/13/2022,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图111,运筹学中研究的图具有下列特征：（1）用点表示研究对象，

3、用边（有方向或无方向）表示对象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。（4）建立一个网络模型，求最大值或最小值。,11/13/2022,11.1 图的基本概念,11/13/2022,例1：五个队比赛的图,v1,v3,v4,v1,v3,v4,v2,v1,v1,v5,11/13/2022,图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，图论中的图与

4、几何图、工程图是不一样的。,11/13/2022,从以上图可看出图：（1）图是由一些点和一些点之间的连线（带箭头或不带箭头）所组成的。（2）具有“对称性”和“不对称性”概念：边：两点之间的不带箭头的连线。弧：两点之间的带箭头的连线。无向图：由点和边组成。记为（，）,点的集合,边的集合,11/13/2022,e3,一条连结vi,vjV的边,记为vi,vj或vj,vi上图中：v1,v2,v3,v4 E e1,e2,.e7 e1=v1,v2, e2=v2,v1e7=v4,v4,v4,v1,v2,v3,e6,e5,e4,e2,e1,e7,e3,11/13/2022,v9,a2,有向图：由点和弧组成。记

5、为D=(V,A)一条方向从vivj的弧,记为：（vi,vj)V=v1,.,v7 A=a1,.,a11a1=(v1,v2) a2=(v1,v3) .,弧的集合,v1,a4,a5,a6,a7,a10,a11,v3,v2,v5,v4,v6,v7,a8,a1,a3,11/13/2022,点数记为：p(G), p(D)边数记为：q(G) 弧数记为：q(D)下面介绍一些名词，先考虑无向图：e=u,v,称u、v是e的端点，也称u、v是相邻的。称e是u(v)的关联边。多重边：两点之间有多于一条的边。简单图：无环，无多重边的图。多重图：无环，但允许有多重边的图。,11/13/2022,次：以点v为端点的边的个数

6、，记为d(v).悬挂点：次为1的点。悬挂边：悬挂点的关联边孤立点：次为0的点。定理1：在G=(V,E)中，所有点的次之和是边数的两倍。,11/13/2022,奇点：次为奇数的点。偶点：次为偶数的点。定理2：任一个图中，奇点的个数为偶数。（因为奇点的边数为奇数，所以个数为偶数）,为偶数,11/13/2022,链：G=(V,E)，一个点、边交错序列（vi1,ei1,vi2,ei2,.,v(ik-1),e(ik-1),vik)。如满足eit=vit,v(it+1),称为一条连结vi1,vi2,.,v(ik-1),vik的链。记为（vi1,vi2,.,v(ik-1),vik）圈：链（vi1,vi2,.

7、,v(ik-1),vik）中，若vi1=vik,称为圈。记为（vi1,vi2,.,v(ik-1),vi1）。初等链：链中各点都不同。初等圈：圈中除头尾外，中间点都不同。,11/13/2022,e7,e4,简单链（圈）：链（圈）中含的边都不相同。 （点可以相同）以后提到的链（圈），除非特别交代，都指初等链（圈）。,v1,e1,e2,e3,e6,e8,e9,v2,v4,v3,v6,v5,v7,e10,v9,v8,e5,11/13/2022,(v1,v2,v3,v4,v5,v3,v6,v7)是简单链。(v1,v2,v3,v6,v7)是初等链。连通图：G中，若任何两点之间，至少有一条链，否则，称为不连

8、通图。连通分图：若 不连通，它的每个连通，部分称为连通分图。支撑子图：G=(V,E)，如果G=(V,E),使V=V及E E,则G为G的一个支撑子图.,11/13/2022,有向图中:路:如有（vi1,ai1,vi2,ai2,.,v(ik-1),a(ik-1),vik)是D中一条链，且有ait=(vit,v(it+1),称从vi1vik的一条路。回路：若路中第一点和最后一点相同，则称为回路。,支撑子图,11.2 最小(支撑)树问题 Minimal (Spanning)Tree Problem,11/13/2022,11.2.1树的概念,一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机

9、构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图 。,可以证明：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。,在一个连通图G中，取部分边连接G的所有点组成的树称为G的部分树或支撑树(Spanning Tree )。图112是图111的部分树。,11.2 最小树问题 Minimal tree problem,11/13/2022,11.2.2 最小部分树,将网络图G边上的权看作两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C(T)。 G的所有部分树中长度最小

10、的部分树称为最小部分树，或简称为最小树。,最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。破圈法：任取一圈，去掉圈中最长边，直到无圈。,11.2 最小树问题 Minimal tree problem,11/13/2022,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图111,【例11.1】用破圈法求图111的最小树。,图114,图114就是图111的最小部分树，最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同,11.2 最小树问题 Min

11、imal tree problem,11/13/2022,加边法：取图G的n个孤立点v1，v2， vn作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）,v1,v2,v3,v4,v5,v6,图115,在图115中，如果添加边v1, v2就形成圈v1, v2, v4，这时就应避开添加边v1, v2，添加下一条最短边v3, v6。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等,Min C(T)=15,11.2 最小树问题 Minimal tree problem,11/13/2022,下一节：最短路问题,1.树、支撑树、最小支撑树的概念2.掌握求最小树的方法：

12、（1）破圈法 （2）加边法,11.2 最小树问题 Minimal tree problem,11.3 最短路问题 Shortest Path Problem,11/13/2022,最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题,求最短路有两种算法： 一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法 另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。,最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路,11.3.1最短路问题的网络模型,11.3 最短路问题 Sh

13、ortest Path Problem,11/13/2022,6,10,12,3,2,14,6,7,5,8,11,16,5,图116,9,【例11.2】图116中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。,11.3 最短路问题 Shortest Path Problem,11/13/2022,11.3.2有向图的狄克斯屈拉(Dijkstra)标号算法,点标号：b(j) 起点vs到点vj的最短路长；,边标号：k(i，j)=b(i)+cij，,步骤：(1)令起点的标号；b(s)0。,先求有向图的最短路

14、，设网络图的起点是vs ,终点是vt ,以vi为起点vj为终点的弧记为（i，j）,距离为cij,(2)找出所有vi已标号vj未标号的弧集合 B=(i，j)，如果这样的弧不存在或vt已标号则计算结束；,(3)计算集合B中弧k(i，j)=b(i)+cij的标号,(4)选一个点标号 返回到第(2)步。,11.3 最短路问题 Shortest Path Problem,11/13/2022,6,10,12,3,2,14,6,7,5,8,11,16,5,图116,9,0,6,10,12,9,20,9,18,6,16,12,17,16,24,32,18,29,29,【例11.3】用Dijkstra算法求图

15、116 所示v1到v7的最短路及最短路长,v1 到v7的最短路为：p17=v1, v2, v3, v5, v7，最短路长为L17=29,11.3 最短路问题 Shortest Path Problem,14,S=T= min0+c12, 0+c13, 0+c14,S= T= min 0+c13, 0+c14, 6+c23, 6+c25,S= T= min 0+c14, 6+c25, 9+c35, 9+c36,9+c34 ,11/13/2022,从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明v

16、s不可达vj 。,11.3.3 无向图最短路的求法,无向图最短路的求法只将上述步骤（2）改动一下即可。,点标号：b(i) 起点vs到点vj的最短路长；,边标号：k(i，j)=b(i)+cij，,步骤：(1)令起点的标号；b(s)0。,(3)计算集合B中边标号：ki，j=b(i)+cij,(4)选一个点标号: 返回到第(2)步。,(2)找出所有一端vi已标号另一端vj未标号的边集合 B=i，j如果这样的边不存在或vt已标号则计算结束；,11.3 最短路问题 Shortest Path Problem,11/13/2022,【例11.4】求图11-10所示v1到各点的最短路及最短距离,0,4,5,

17、2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。,图11-10,11.3 最短路问题 Shortest Path Problem,11/13/2022,下一节：最大流问题,11.3 最短路问题 Shortest Path Problem,1.最短路的概念及应用。2.有向图、无向图一点到各点最短路的Dijkstra算法,11.4 最大流问题Maximal Flow Problem,11/13/2022,11.4 最大流问题Maximal Flow Problem,11.4.1

18、 基本概念,8,14,5,6,3,3,8,10,7,6,3,图1118,4,图1118所示的网络图中定义了一个发点v1，称为源(source，supply node），定义了一个收点v7，称为汇（sink，demand node），其余点v2，v3，v6为中间点，称为转运点(transshipment nodes)。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的容量(capacity)。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。,11/13/2022,设cij为弧（i，j）的容量

19、，fij为弧（i，j）的流量。容量是弧（i，j）单位时间内的最大通过能力，流量是弧（i，j）单位时间内的实际通过量，流量的集合f=fij称为网络的流。发点到收点的总流量记为v=val(f)，v也是网络的流量。,图1118最大流问题的线性规划数学模型为1,11.4 最大流问题Maximal Flow Problem,11/13/2022,满足下例3个条件的流fij 的集合 f = fij 称为可行流,发点vs流出的总流量等于流入收点vt的总流量,11.4 最大流问题Maximal Flow Problem,11/13/2022,链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收

20、点的方向规定为链的方向。,前向弧：与链的方向相同的弧称为前向弧。,后向弧：与链的方向相反的弧称为后向弧。,增广链: 设 f 是一个可行流，如果存在一条从vs到vt的链，满足：,1.所有前向弧上fijCij,2.所有后向弧上fij0,则该链称为增广链,容量,流量,11.4 最大流问题Maximal Flow Problem,11/13/2022,步骤如下：,第二步：对点进行标号找一条增广链。（1）发点标号（）（2）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查： A如果弧的方向向前（前向弧）并且有fij0，则vj标号: jfji当收点已得到标号时，说明已找到增广链，依据vi 的标

21、号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。,第一步： 找出第一个可行流，例如所有弧的流量fij =0,11.4.2 Ford-Fulkerson标号算法,11.4 最大流问题Maximal Flow Problem,例,11/13/2022,第三步：调整流量（1）求增广链上点vi 的标号的最小值，得到调整量,（2）调整流量,得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止,【定理11.1】 可行流f是最大流的充分必要条件是不存在发点到收点的增广链,11.4 最大流问题Maximal Flow Problem,11/1

22、3/2022,8,14,5,6,3,3,8,10,7,6,3,图1119,(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),【例11.10】求图1118发点v1到收点v7的最大流及最大流量,【解】给定初始可行流，见图11-19,11.4 最大流问题Maximal Flow Problem,11/13/2022,8,14,5,6,3,3,8,10,7,6,3,图1120(b),(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),2,3,3,7,第一轮标号：,c12f12,v2标号2,增广链(1,

23、2)，(3,2)，(3,4)，(4,7) ,+=(1,2)，(3,4)，(4,7),=(3，2)，调整量为增广链上点标号的最小值min，2，3，3，72,11.4 最大流问题Maximal Flow Problem,step,11/13/2022,8,14,5,6,3,3,8,10,7,6,3,图1121,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),调整后的可行流：,11.4最大流问题Maximal Flow Problem,11/13/2022,8,14,5,6,3,3,8,10,7,6,3,图1122,(10),(8),(1),(6

24、),(3),(7),(2),(6),(1),4,(5),(1),(7),4,4,1,5,第二轮标号：,增广链(1,3)，(3,4)，(4,7) ，调整量为 min，4，1，51,11.4 最大流问题Maximal Flow Problem,11/13/2022,8,14,5,6,3,3,8,10,7,6,3,图1123,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),调整后得到可行流：,11.4 最大流问题Maximal Flow Problem,11/13/2022,8,14,5,6,3,3,8,10,7,6,3,图1122,(11),(

25、8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),3,1,4,第三轮标号：,增广链(1,3)，(3,6)，(6,4)，(4,7) ，调整量为 min，3，1，2，41,2,11.4 最大流问题Maximal Flow Problem,11/13/2022,8,14,5,6,3,3,8,10,7,6,3,图1125,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),调整后得到可行流：,114 最大流问题Maximal Flow Problem,11/13/2022,8,14,5,6,3,3,8,10,7,

26、6,3,图1122,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),2,第四轮标号：,v7得不到标号，不存在v1到 v7的增广链，图6-22所示的可行流是最大流，最大流量为 vf12+f138+12=20,4,11.4 最大流问题Maximal Flow Problem,11/13/2022,无向图最大流标号算法,无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另一端vj未标号的边只要满足 Cijfij0 则vj就可标号（Cijfij）,【例11.11】求下图v1到则v7标的最大流,7,(10),(6),(10),(8),(

27、2),(3),(7),(6),(5),(13),(0),(13),2,3,9,9,3,11.4 最大流问题Maximal Flow Problem,11/13/2022,3,7,7,1,V=29,10,5,6,6,11.4最大流问题Maximal Flow Problem,1,11/13/2022,【例11.12】某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少

28、加仑石油？,v5,最大流另一解法只给出最大流时,11/13/2022,最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)和(b)、(c)和(d)的意义相同。 用以上方法对例11.12的图的容量标号作改进，得下图,vi,vj,vi,vj,cij,0,（a）,（b）,cij,cij,vi,vj,（cji）,（c）,vi,vj,cij,cji,（d）,最大流另一解法,11/13/2022,求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流的容量p

29、f，通过这条路增加网络的流量pf。（3）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流容量pf，返回步骤（1）。 用此方法对例11.12求解： 第一次迭代：选择路为v1 v4 v7 。弧（ v4 , v7 ）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：,最大流另一解法,11/13/2022,第二次迭代：选择路为v1 v2 v5 v7 。弧（ v2 , v5 ）的顺流容量为3，决定了pf=3，改进的网络流量图如下图： 第三次迭代：选择路为v1 v4 v6 v7 。弧（ v4 , v6 ）的顺流容量为1，决定了pf=1，改进的网络流量图如下图：,最大流另一解法,11/1

30、3/2022,第四次迭代：选择路为v1 v4 v3 v6 v7 。弧（ v3 , v6 ）的顺流容量为2，决定了pf=2，改进的网络流量图如下图： 第五次迭代：选择路为v1 v2 v3 v5 v7 。弧（ v2 , v3 ）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：,最大流另一解法,11/13/2022,经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。 最大流量图如下图：,“管理运筹学软件”中还有专门的子程序用于解决最大流问题。,最大流另一解法,11/13/2022,11.4.4最大流应用举例,1.二分图的最大匹

31、配问题,【例11.13】某公司需要招聘5个专业的毕业生各一个，通过本人报名和筛选，公司最后认为有6人都达到录取条件。这6人所学专业见表11-10,表中打“”表示该生所学专业。公司应招聘哪几位毕业生，如何分配他们的工作,表11-10,11.4 最大流问题Maximal Flow Problem,11/13/2022,A,B,C,D,E,s,t,(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),图1132,【解】画出一个二分图，虚设一个发点和一收点，每条弧上的容量等于1，问题为求发点到收点的最大流，求解结果之一见图1132。公司

32、录取第26号毕业生，安排的工作依次为管理信息、企业管理、市场营销、工程管理和计算机。,11.4 最大流问题Maximal Flow Problem,11/13/2022,1.最大流的概念：容量、流量、可行流、最大流、前向弧、后向弧、增广链。2.有向图、无向图最大流的Ford-Fulkerson标号算法3. 本节介绍了应用：最大匹配问题,11.4最大流问题Maximal Flow Problem,11/13/2022,11.5最小费用最大流问题,11.6 中国邮路问题 China Carrier Problem,11/13/2022,一、一笔画问题；,11.1中国邮路问题(China carri

33、er problem),11/13/2022,欧拉链：给定一个连通多重图，若存在一条链，过每边一次，且仅一次，称这条链为欧拉链。欧拉圈：若存在一个简单圈，过每边一次，称为欧拉图：一个图若有欧拉圈，称显然，一个图若能一笔画出，则这个图必是欧拉图或含欧拉链。,11/13/2022,定理：连通多重图是欧拉图中无奇点。推论：连通多重图有欧拉链恰 有两个奇点。二、奇偶点图上作业法,11/13/2022,例：,v1,v2,v3,v4,v5,v6,v7,v9,5,5,6,9,4,4,4,2,4,3,3,4,v8,11/13/2022,概念： 使新图中不含奇点而增加重复边，称为可行方案。 使总权最小的可行方案

34、，称为最优方案。1.第一个可行方案的确定 使原图中不含有奇点而增加重复边 奇点的个数是偶数，图中有奇点必是成对出现 在两个奇点之间增加一条链,11/13/2022,消除奇点 调整,v1,v2,v3,v4,v6,v7,v8,v9,5,5,6,9,4,4,4,2,4,3,3,4,(a),v5,11/13/2022,2.最优方案判断的标准 一个方案是最优的 在最优方案中，图的每一边上最多有一条重复边； 在最优方案中，图中每个圈上的重复边的总权不大于该圈总权的一半；,11/13/2022,在(a)图中，圈(v2,v3,v4,v9,v2)中，圈总长24，但圈上重复边权之和1424的一半；见图调整如下图(

35、b)所示。,11/13/2022,调整 后的图,v1,v2,v3,v4,v6,v7,v8,v9,5,5,6,9,4,4,4,2,4,3,3,4,(b),v5,11/13/2022,在图(b)中，圈(v1,v2,v9,v6,v7,v8,v1)中重复边权之和为13圈的权为24的一半；调整为图( c),11/13/2022,v1,v2,v3,v4,v5,v6,v7,v9,5,5,6,9,4,4,4,2,4,3,3,4,(c),v8,11/13/2022,图( c)满足最优方案条件。图中任何一个欧拉圈就是邮递员的最优投递路线注：“日”字型图有三个圈 “田”字型图有13个圈。,11/13/2022,作业第第，题（不用抄题）,