《运筹学图与网络分析课件》由会员分享,可在线阅读,更多相关《运筹学图与网络分析课件(130页珍藏版)》请在金锄头文库上搜索。
1、第5章 图论与网络分析,图的基本概念,网络分析,最小支撑树问题 最短路径问题 网络最大流问题,图论起源:哥尼斯堡七桥问题,问题:一个散步者能否从任一块陆地出发,走过七座桥,且每座桥只走过一次,最后回到出发点?,结论:每个结点关联的边数均为偶数,1 图的基本概念,由点和边组成,记作G=(V,E),其中V=(v1,v2,vn)为结点的集合,E=(e1,e2,em) 为边的集合。,点表示研究对象,边表示研究对象之间的特定关系,1. 图,p114,图,无向图,记作G=(V,E),有向图,记作D=(V,A),例1:哥尼斯堡桥问题的图为一个无向图。,有向图的边称为弧。,2、图的分类,例,图1,图2,3、链
2、与路、圈与回路,链,点边交错的序列,路,点弧交错的序列,回路,起点=终点的路,无向图:,有向图:,链与路中的点均不相同,则称为初等链 (路)类似可定义初等圈(回路),4、连通图,G1为不连通图, G2为连通图,例 :,5、支撑子图,图G=(V,E)和G=(V ,E ),若V =V 且E E ,则称G 为G的支撑子图。,G2为G1的支撑子图,例 :,G2 是G1 的子图;,例 :,6、赋权图(网络),图的每条边都有一个表示一定实际含义的权数,称为赋权图。记作D=(V,A,C)。,例 :,2 最小支撑树问题,本节主要内容:,树,支撑树,最小支撑树,树:无圈的连通图,记为T。,一、树的概念与性质,树
3、的性质: (1)树的任2点间有且仅有1链; (2)在树中任去掉1边,则不连通;故树是使图保持 连通且具有最少边数的一种图形 (3)在树中不相邻2点间添1边,恰成1圈; (4)若树T有m个顶点,则T有m-1条边。,若一个图 G =(V , E)的支撑子图 T=(V , E) 构成树,则称 T 为G的支撑树,又称生成树。,二、图的支撑树,例,例 某地新建5处居民点,拟修道路连接5处,经勘测其道路可铺成如图所示。为使5处居民点都有道路相连,问至少要铺几条路?,解:,该问题实为求图的支撑树问题,共需铺4条路。,图的支撑树的应用举例,用破圈法求出下图的一个生成树。,最小支撑树:求网络的支撑树,使其权和最
4、小。,三、最小支撑树问题,算法1(破圈法): 在给定的赋权的连通图上找一个圈; 在所找的圈中去掉一条权数最大的边(若有两条或两条以上的边都是权数最大的边,则任意去掉其中一条): 若所余下的图已不含圈,则计算结束,所余下的图即为最小支撑树,否则,返问。,例 求上例中的最小支撑树,解:,5,5.5,v1,v2,v3,v4,v5,3.5,7.5,4,2,3,算法2(避圈法):从某一点开始,把边按权从小到大依次添入图中,若出现圈,则删去其中最大边,直至填满n-1条边为止(n为结点数) 。,最小生成树举例: 某六个城市之间的道路网如图 所示,要求沿着已知长度的道路联结六个城市的电话线网,使电话线的总长度
5、最短。,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,联系今有煤气站A,将给一居民区供应煤气,居民区各用户所在位置如图所示,铺设各用户点的煤气管道所需的费用(单位:万元)如图边上的数字所示。要求设计一个最经济的煤气管道路线,并求所需的总费用。,练习今有煤气站A,将给一居民区供应煤气,居民区各用户所在位置如图所示,铺设各用户点的煤气管道所需的费用(单位:万元)如图边上的数字所示。要求设计一个最经济的煤气管道路线,并求所需的总费用。,例今有煤气站A,将给一居民区供应煤气,居民区各用户所在位置如图所示,铺设各用户点的煤气管道所需的费用(单位:万元)如图边上的数字所示。要求设计一个最经
6、济的煤气管道路线,并求所需的总费用。,例今有煤气站A,将给一居民区供应煤气,居民区各用户所在位置如图所示,铺设各用户点的煤气管道所需的费用(单位:万元)如图边上的数字所示。要求设计一个最经济的煤气管道路线,并求所需的总费用。,例今有煤气站A,将给一居民区供应煤气,居民区各用户所在位置如图所示,铺设各用户点的煤气管道所需的费用(单位:万元)如图边上的数字所示。要求设计一个最经济的煤气管道路线,并求所需的总费用。,例今有煤气站A,将给一居民区供应煤气,居民区各用户所在位置如图所示,铺设各用户点的煤气管道所需的费用(单位:万元)如图边上的数字所示。要求设计一个最经济的煤气管道路线,并求所需的总费用。
7、,例今有煤气站A,将给一居民区供应煤气,居民区各用户所在位置如图所示,铺设各用户点的煤气管道所需的费用(单位:万元)如图边上的数字所示。要求设计一个最经济的煤气管道路线,并求所需的总费用。,此即为最经济的煤气管道路线,所需的总费用为25万元,3最短路径问题,最短路问题是在一个网络(赋权有向图)中寻找从起点到某个节点之间一条最短的路线。现欲求出1至6距离最短的路径。,基本思想:从起点vs开始,逐步给每个结点vj标号dj ,vi,其中dj为起点vs到vj的最短距离, vi为该最短路线上的前一节点. 若给终点vt标上号dt ,vi, 表示已求出v1至vt的最短路其最短路长为 dt ,最短路径可根据标
8、号 vi 反向追踪而得,最短路问题的Dijstra解法 (狄克拉斯),0, v1,1, v1,(3) 考虑所有这样的边vi , vj,其中viVA, vjVB,挑选其中与起点v1距离最短(mindi+cij)的vj,对vj进行标号,(4) 重复(2)、(3),直至终点vn标上号dn, vi,则dn即为v1 vn的最短距离,反向追踪可求出最短路。,(1)给起点v1标号0, v1,0, v1,1, v1,(3) 考虑所有这样的边vi , vj,其中viVA, vjVB,挑选其中与起点v1距离最短(mindi+cij)的vj,对vj进行标号,(4) 重复(2)、(3),直至终点vn标上号dn, vi
9、,则dn即为v1 vn的最短距离,反向追踪可求出最短路。,(1)给起点v1标号0, v1,3, v1,0, v1,1, v1,3, v1,5, v3,0, v1,1, v1,3, v1,5, v3,6, v2,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,12, v5,此时终点v9已标号12, v5,则12即为v1 vn的最短距离,反向追踪可求出最短路,0, v1,1, v1,3, v1,5, v3
10、,6, v2,9, v5,10, v5,12, v5,v1到v9的最短路为:v1 v3 v2 v5 v9,最短距离为12,p119,练习:用Dijkstra算法求下图中V1至V8的最短路及最短路长。,关键线路: 1.V1-V2-V4-V6-V8 2.V1-V2-V4V7-V8 最短路长:12,课堂练习 无向图情形,求网络中v1至v7的最短路。,课堂练习 无向图情形,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/ v4,7,v3,8,v5,13,v6,课堂练习 无向图情形,答案(2):,v1,v2,v3,v4,v
11、5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/ v4,7,v3,8,v5,13,v6,最短路模型的应用设备更新问题,例 某工厂使用一种设备,这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备,每年需支付购置费用;若继续使用旧设备,需要支付维修与运行费用。计划期(五年)内中每年的购置费、维修费与运行费如表所示,工厂要制定今后五年设备更新计划,问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,最短路模型的应用设备更新问题,分析:,结点:V=v1,v6, vi表示第i年初;,弧:
12、A=(vi,vj) 表示第i年初购买,用至第j年初;i= 1,5; j= 2,6,权cij: i年初 j年初的费用,即cij= i年初购买费+(j-i)年里的维修费,通路:表示一个更新策略。例如v1-v2-v6表示第一年购买用到第二年更新,继续用至第五年末的一个更新策略,最短路模型的应用设备更新问题,0,v1,16,v1,22,v1,30,v1,41,v1,53,v3/v4,16,30,22,41,59,16,22,30,41,17,23,31,17,23,18,建模:,求解:,求得两个最优更新策略: v1-v4-v6,即第一年购买设备,用到第四年更新,再用至第五年年末 V1-v3-v6,即第
13、一年购买设备,用到第三年更新,再用至第五年年末 最优费用为53,计划期(五年)内中每年的购置费、维修费与运行费如表所示,工厂要制定今后五年设备更新计划,问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,练习:设备更新问题,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,算法的基本思路与步骤: 首先设任一点vi到任一点vj都有一条弧。无弧相连的点之间假设存在权为+的弧相连。 从v1到vj的最短路是从v1出发,沿着这条路到某个点vi再沿弧(vi ,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有
14、路中的最短路。 设P1j表示从v1到vj的最短路长,P1i表示从v1到vi的最短路长,则有下列方程:,(二) Ford法(逐次逼近法) (权有负数),开始时,令 即用v1到vj的直接距离做初始解。,从第二步起,使用递推公式:,求 ,当进行到第t步,若出现,即为v1到各点的最短路长。,则停止计算,,例:,从第二步起,使用递推公式,从第二步起,使用递推公式,为了求出从v1到各个点的最短路,一般采用反向追踪的方法:如果已知d(vs ,vj),那么寻求一个点vk ,使得d(vs,vk)+wkj=d(vs ,vj) ,然后记录下(vk ,vj);在看d(vs ,vk) ,寻求一个点vi ,使得d(vs
15、,vi)+wik=d(vs ,vk)依次类推,一直到达为止。这样,从vs到vj的最短路是(vs ,vi ,vk ,vj),d(v1 ,v8)=6, 由于d(v1 ,v6)+w68=(-1)+7记录下v6 由于d(v1 ,v3)+w36=d(v1 ,v6) , 记录下v3 由于d(v1 ,v1)+w13=d(v1 ,v3), 于是,从v1到v8的最短路是(v1 ,v3 ,v6 ,v8)。,4 网络最大流问题,引例:下图为V1到V6的一交通网,权表示相应运输线的最大通过能力,制定一方案,使从V1到V6的运输产品数量最多。,已知网络D=(V,A,C),其中V为顶点集,A为弧集,C=cij为容量集, cij 为弧(vi,vj )上的容量。现D上要通过一个流f=fij,其中fij 为弧(vi,vj )上的流量。 问题:应如何安排流量fij可使D上通过的总流量v最大?,一、一般提法,二、最大流问题的数学模型,max v=v(f),容量约束,平衡约束,P125,满足上述所有约束条件的流成为可行流。,(1)容量条件:对于每一个弧(vi ,vj)A,有0 fij cij 。 (2)平衡条件: 对于发点vs,有 对于收点vt ,有 对于中间点,有 为可行流f 的流量(发点的净输出量或收点的净输