运筹学课件--第七章 网络分析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,管理运筹学,-,管理科学方法,李军,桂林电子科技大学商学院,Sub title,OR:SM,第,7,章 图与网络分析,内容提要,2,第一节,第二节,第三节,第四节,第五节,图论的概念,最小树问题,最短路问题,网络最大流,最小费用流,OR:SM,OR:SM,哥尼斯堡，原属,波兰，现属俄罗,斯，名为加里宁,格勒,3,OR:SM,18,世纪，哥尼斯堡城（当时东普鲁士柯尼斯堡，今日俄罗斯加里宁,格勒）中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸,连接起来。,茶余饭后，人们提出了这样的问题：一个散步者能否从某地出发，,走遍七座桥且每座桥恰好经过一次，最后回到原地？,4,OR:SM,第,7,章 网络分析,1736,年瑞士数学家欧拉将两岸和小岛抽象,为四个点，将桥抽象为七条边，此问题归结为,一笔画问题。,陆地,A,A,岛,D,岛,C,D,C,B,陆地,B,欧拉回答的根据是：若图是连通的，且图中奇点,(,和奇数条边相关联的点,),的数目为,0,或,2,时，则图能“一笔画”。奇点的数目为零时，则图中任一点即是,“一笔画”的起点又是终点。奇点的数目为,2,时，则两点中任一点为“一笔画”,的起点，而另一点为终点。前图中奇点数目为,4,，不满足“一笔画”规则，因,此是无解的。,哥尼斯堡七桥问题，用图论的方法得到了简捷的证明，所以欧拉被人们,公认为图论的创始人，人们称他为“图论之父”。,5,OR:SM,OR:SM,第一节,图论的概念,一、图的内涵,1,、图的定义,图论的图与一般几何图形或代数函数图形是完全不同的,图论中的图,:,由一些点和连接点的线所组成的“图形”,点和线的位置是任意的,线的曲直、长短与实际无关，代表的只是点与点之间的相互关系,例：表示,苏州,v,1,、杭州,v,2,、上海,v,3,、南京,v,4,仓储网点之间的物流运输线路关系,v,2,e,4,e,1,e,5,v,1,e,2,v,3,e,3,e,6,v,4,e,2,e,3,v,2,e,4,v,3,e,5,e,6,e,5,e,2,e,1,v,4,e,3,v,1,6,v,1,e,1,v,2,e,4,v,3,e,6,v,4,OR:SM,OR:SM,第一节,图论的概念,一、图的内涵,2,、图的分类,不带箭头的连线,称为“边”，如公路运输线路；,带箭头的连线称为“弧”，如供排水的管道运输线,路,。,1,、无向图,由点和边的集合所构成,2,、有向图,由点和弧的集合所构成,链：无向网络中，前后相继点和边,路径：有向网络图中，前后相继并且,7,的交替序列称为一条链。,圈：闭合的链称为一个圈。,方向一致的点弧序列称为一条路径。,回路：闭合的路径称为一个回路。,OR:SM,OR:SM,8,第一节,图与网络的基本概念,图及其分类,3,、简单图,无环，且任意两点间,不多于一条边,图论的概念,4,、多重图,有环，或有多重边,OR:SM,OR:SM,第一节,图与网络的基本概念,母图、子图、支撑子图,图论的概念,9,母图,子图,支撑子图（生成子图）,OR:SM,OR:SM,第一节,图论的概念,图与网络的基本概念,网络（赋权图）,在实际问题中，只用图来描述所研究的对象间的关系往往是不够的，而常,常还需要考虑与点或边有关的某些数量指标（即“权”），其可以代表诸如距离、,费用、通过能力（容量）等等。,网络,点或边带有某种数量指标的图,2,2,3,4,2,2,3,4,6,1,3,7,6,1,3,7,10,5,5,OR:SM,OR:SM,第一节,图论的概念,图与网络的基本概念,连通图,在众多各类图中有一类在实际应用中占有重要地位的图,连通图,在图中，任意两点间至少存在着一条链。,11,连通图,不连通图,OR:SM,OR:SM,第二节 最小树问题,树及其性质,无圈且连通的无向图称为树。例如，企业的组织结构，文,件的目录管理等都可以用一个树状图来表示。,性质：,树中任两点之间必有且只有一条链；,树中去掉任一条边，则成为不连通图；,树中不相邻两顶点之间添一条边，则得到一个圈；,顶点个数,n,v,与边的个数,n,e,的关系：,n,e,=n,v,1,。,12,OR:SM,v,v,T,i,j,OR:SM,第二节,最小树问题,支撑树：如果图,G,（,V,，,E,）的支撑子图,T=,（,V,，,E/,）是树，则,称,T,为,G,的支撑树。,权数总和为最小的那棵支撑树，称为最小树。,w,(,T,),w,ij,求解方法：,破圈法；避圈法,例：一家企业分别要在,6,间办公室铺设网线接入口，网线的可行走,线方式如下图所示，如何铺设网线才能使网线总长为最短？,8,v,2,4,v,5,6,v,1,3,5,6,v,6,2,6,v,3,8,v,4,最短网线总长度为最小树权之和,2+3+4+6+6=21,13,OR:SM,OR:SM,14,第二节,最小树问题,方法一：破圈法 ：任取一个圈，从圈中去掉一条权最大的边。,在余下的图中，重复这个步骤，一直到一个不含圈的图为止，,这时的图便是最小树。,6,v,3,5,v,5,4,v,1,1,7,3,v,6,5,4,v,2,2,v,4,这就得到了该图的一个最小支撑树。,14,2011-03-25,OR:SM,OR:SM,15,第二节,最小树问题,方法二 ：避圈法：开始选一条权最小的边（也可从一点开,始），以后每一步中，总从未被选取的边中选一条权最小,的边，并使之与已选取的边不构成圈。,6,v,3,5,v,5,4,v,1,1,7,3,v,6,5,4,v,2,2,v,4,这就得到了该图的一个最小支撑树。,15,2011-03-25,OR:SM,OR:SM,第三节,一、最短路问题,最短路问题,Shortest Route(Path)Problems,路权：弧,(v,i,v,j,),的权为,w,ij,；路权是路,p,中各条弧权之和,最短路：在所有从,v,s,到,v,t,的路,p,中，求一条路权最短的路,狄克斯特拉,(Dijkstra),算法,算法说明：,w(P*),minw(P),P,1959,年提出，目前公认的最短路算法,适合于求解所有弧权,w,ij,0,的最短路问题,算法假设：有向图,D,是完备图,图,D,中任意两点,v,i,v,j,之间，恰有两条弧,(v,i,v,j,),和,(v,j,v,i,),若,v,i,v,j,不存在弧,可设想一条从,v,i,v,j,的弧,权,w,ij,=+,；,若,v,i,v,j,有重复的弧，则保留弧权最小的弧,16,OR:SM,OR:SM,17,OR:SM,OR:SM,第三节,一、双标号算法,最短路问题,18,基本思路,:,从始点,v,s,出发，逐步探寻，给每个点标号；,标号分永久标号,P(v,k,),和临时标号,T(v,k,),两种：,永久标号,P(v,k,),是从点,v,s,v,k,的最短路权,临时标号,T(v,k,),是从点,v,s,v,k,最短路权的上界,算法的每一步从临时标号集中选最小者变为永久标号；,经过逐次改变，就可以得到从点,v,s,到各点的最短路。,标号形式：,单标号法是对每一点赋予一个路权标号,双标号法是对每一点赋予两个标号：路标、,路权,OR:SM,OR:SM,第三节,最短路问题,一、双标号算法,例：用双标号法求下图网络最短路,v,1,2,v,5,3,7,4,1,8,v,s,10,9,v,2,4,1,3,v,4,6,7,1,v,t,19,v,3,2,v,6,OR:SM,2,OR:SM,v,s,第三节,一、双标号算法,最短路问题,第一步：,3,(,v,s,3),v,1,7,2,4,v,5,1,(,v,s,),8,(,v,s,0),v,s,9,v,2,(,v,s,9),1,v,4,(,v,s,),7,v,t,(,v,s,),10,4,3,6,1,20,v,3,(,v,s,10),v,6,(,v,s,),OR:SM,2,OR:SM,第三节,一、双标号算法,最短路问题,第二步：,(,v,s,3),(,v,1,5),v,1,2,v,5,3,7,4,1,8,(,v,s,0),v,s,9,v,2,(,v,s,9),1,v,4,(,v,1,7),7,v,t,(,v,s,),10,4,3,6,1,21,v,3,(,v,s,10),v,6,(,v,s,),OR:SM,2,OR:SM,第三节,一、双标号算法,最短路问题,第三步：,(,v,s,3),(,v,1,5),v,1,2,v,5,3,7,4,1,8,(,v,s,0),v,s,9,v,2,(,v,s,9),1,v,4,(,v,5,6),7,v,t,(,v,5,13),10,4,3,6,1,22,v,3,(,v,s,10),v,6,(,v,s,),OR:SM,2,OR:SM,第三节,最短路问题,一、双标号算法,最终：依此类推，重复上述标号过程。得最短路。,(,v,s,3),(,v,1,5),v,1,2,v,5,3,7,4,1,8,(,v,s,0),v,s,9,v,2,(,v,s,9),1,v,4,(,v,5,6),7,v,t,(,v,6,12),10,4,3,6,1,23,v,3,(,v,4,9),v,6,(,v,3,11),OR:SM,OR:SM,即时练习：,某一个配送中心要给一个快餐店送快餐原料，应按,照什么路线送货才能使送货时间最短。,(4,1),(18,3),(25,4),2,16,4,7,6,4,6,1,12,2,8,7,(27,5),18,3,(16,2),6,5,5,(22,3),24,OR:SM,OR:SM,第三节,最短路问题,二、最短路的应用,1,、网络的中心,所谓网络的中心是指一个网络中，选择某一点，使之其,余各点到该中心点的距离之和为最小。,例：如果要在下表中,6,个销售点中选一个作为仓库所在地，应,该建在哪个经销点，使其余各销售点都离它较近？,25,OR:SM,OR:SM,第三节,最短路问题,二、最短路的应用,2,、网络的重心,引进点的权系数，将权系数与最短距离阵各列对应元素加权,求和，再从中选择最小的即为网络重心。,26,OR:SM,OR:SM,27,第三节,最短路问题,3,、设备更新问题,:,制订一设备更新问题，使得总费用最小？,第,1,年,第,2,年,第,3,年,第,4,年,第,5,年,购买费,使用年数,维修费,13,0-1,8,14,1-2,10,16,2-3,13,19,3-4,18,24,4-5,27,解,设以,v,i,(i=1,2,3,4,5),表示“第,i,年初购进一台新设备”这种,状态，以,v,6,表示“第,5,年末”这种状态；以弧,(v,i,v,j,),表示“第,i,年,初购置的一台设备一直使用到第,j,年初”这一方案，以,w,ij,表示这,一方案所需购置费和维护费之和。于是，该问题就可归结为从,图中找出一条从,v,1,到,v,6,的最短路问题。其网络模型如下：,27,2011-03-25,OR:SM,OR:SM,28,设备更新的网络模型,(21),v,2,32,(44)v,4,63,21,44,22,45,27,37,(0)v,1,31,89,62,24,(78),v,6,用,Dijkstra,标,号法，求得最,短路为,:,v,1,v,3,v,6,v,3,(31),47,34,v,5,(62),32,28,2011-03-25,OR:SM,OR:SM,*设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买,新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置,费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置,费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五,年内购置费用和维修费用总的支付费用最小。,表,1,：设备每年年初的价格表,年份,年初价格,1,11,2,11,3,12,4,12,5,13,表,2,：设备维修费如下表,使用年数,每年维修,0-1,5,1-2,6,2-3,8,3-4,11,4-5,18,费用,29,OR:SM