天津大学管理运筹学课件第二章_图论.ppt

《天津大学管理运筹学课件第二章_图论.ppt》由会员分享，可在线阅读，更多相关《天津大学管理运筹学课件第二章_图论.ppt（110页珍藏版）》请在三一文库上搜索。

1、2019/2/25,管理运筹学,第二章 图论与网络分析,图的基本概念,网络分析,最小支撑树问题 最短路径问题 网络最大流问题 网络计划问题,2019/2/25,管理运筹学,图论起源哥尼斯堡七桥问题,结论：每个结点关联的边数均为偶数。,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？,2019/2/25,管理运筹学,1 图的基本概念,由点和边组成，记作G=(V，E)，其中V=v1，v2，vn为结点的集合，E=e1，e2，em 为边的集合。,点表示研究对象,边表示表示研究对象之间的特定关系,1. 图,2019/2/25,管理运筹学,图,无向图，记作G=(V，E

2、),有向图，记作D=(V，A),例1：哥尼斯堡桥问题的图为一个无向图。,有向图的边称为弧。,2、图的分类,2019/2/25,管理运筹学,3、链与路、圈与回路,链,点边交错的序列,路,点弧交错的序列,回路,起点=终点的路,无向图：,有向图：,2019/2/25,管理运筹学,4、连通图,G1为不连通图， G2为连通图,例 ：,2019/2/25,管理运筹学,5、支撑子图,图G=(V，E)和G=(V ，E )，若V =V 且E E ，则称G 为G的支撑子图。,G2为G1的支撑子图,例 ：,2019/2/25,管理运筹学,6、赋权图（网络）,图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作

3、D=(V，A，C)。,例 ：,2019/2/25,管理运筹学,2 最小支撑树问题,本节主要内容：,树,支撑树,最小支撑树,2019/2/25,管理运筹学,1、树中任两点中有且仅有一条链； 2、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。 3、边数 = 顶点数 1。,树,无圈连通图,树的性质：,例 判断下面图形哪个是树：,一、树的概念与性质,2019/2/25,管理运筹学,若一个图 G =（V , E）的支撑子图 T=（V , E） 构成树，则称 T 为G的支撑树，又称生成树、部分树。,二、图的支撑树,例,2019/2/25,管理运筹学,例 某地新建5处居民点，拟修道路连接

4、5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？,解：,该问题实为求图的支撑树问题，共需铺4条路。,图的支撑树的应用举例,2019/2/25,管理运筹学,问题：求网络的支撑树，使其权和最小。,三、最小支撑树问题,算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数） 。,例 求上例中的最小支撑树,解：,4,2019/2/25,管理运筹学,算法2（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。,2019/2/25,管理运筹学,算法2（破圈法）： 在图中找圈，并删除其中最大边。如此

5、进行下去，直至图中不存在圈。,5,5.5,v1,v2,v3,v4,v5,3.5,4,2,3,2019/2/25,管理运筹学,算法2（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。,5,v1,v2,v3,v4,v5,3.5,4,2,3,2019/2/25,管理运筹学,算法2（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。,5,v1,v2,v3,v4,v5,3.5,2,3,2019/2/25,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设

6、计一个最经济的煤气管道路线，并求所需的总费用。,2019/2/25,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2019/2/25,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2019/2/25,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点

7、的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2019/2/25,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2019/2/25,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2019/2/25,管理运筹学,例今有煤气站A，将给

8、一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,此即为最经济的煤气管道路线，所需的总费用为25万元,2019/2/25,管理运筹学,案例分析：默登公司的联网问题,默登（Modern）公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图1中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。 问：需要铺设哪些光缆使得总成本最低？,2019/2/25,管理运筹学,案例分析：默登公司的联网问题,2019/2

9、/25,管理运筹学,3 最短路问题,问题：求网络中起点到其它点之间的一条最短路线。,2019/2/25,管理运筹学,算法：Dijkstra（狄克斯拉）标号法,基本思想：从起点vs开始，逐步给每个结点vj标号dj，vi，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点。,0, v1,1, v1,(1) 给起点v1标号0, v1,(3) 考虑所有这样的边vi , vj，其中viVA， vjVB，挑选其中与起点v1距离最短（mindi+cij）的vj，对vj进行标号,(4) 重复(2)、(3)，直至终点vn标上号dn, vi，则dn即为v1 vn的最短距离，反向追踪可求出最短路。,步

10、骤：,2019/2/25,管理运筹学,0, v1,1, v1,3, v1,2019/2/25,管理运筹学,0, v1,1, v1,3, v1,5, v3,2019/2/25,管理运筹学,0, v1,1, v1,3, v1,5, v3,6, v2,2019/2/25,管理运筹学,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,2019/2/25,管理运筹学,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,2019/2/25,管理运筹学,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,12, v5,

11、此时终点v9已标号12, v5，则12即为v1 vn的最短距离，反向追踪可求出最短路,2019/2/25,管理运筹学,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,12, v5,v1到v9的最短路为：v1 v3 v2 v5 v9，最短距离为12,2019/2/25,管理运筹学,课堂练习 P129 习题5.3,0, v1,4, v1,3, v1,5, v2,6, v2,9, v7,7, v4/ v6,8.5, v6,6, v2,2019/2/25,管理运筹学,课堂练习 无向图情形,求网络中v1至v7的最短路。,2019/2/25,管理运筹学,课堂练习 无向

12、图情形,答案（1）：,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,2019/2/25,管理运筹学,课堂练习 无向图情形,答案（2）：,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,最短路模型的应用设备更新问题（P119 例 5.3）,16,分析：,结点：V=v1，v6， vi表示第i年初；,边： E=(vi，vj) 表示第i年初购买，用至第j年初；

13、i= 1,5; j= 2,6,权cij： i年初 j年初的费用，即cij= i年初购买费+（j-i）年里的维修费,30,22,41,59,16,22,30,41,17,23,31,17,23,18,2019/2/25,管理运筹学,4 网络最大流问题,引例：下图为V1到V6的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从V1到V6的产品数量最多。,2019/2/25,管理运筹学,设有网络D=(V, A, C)，其中C=cij， cij为弧(vi,vj)上的容量，现在D上要通过一个流f=fij， fij为弧(vi,vj)上的流量。 问题：如何安排fij，可使网络D上的总流量V最大？,一

14、、一般提法：,2019/2/25,管理运筹学,二、最大流问题的模型,max v=v（f）,容量约束,平衡约束,注：满足约束条件的流f称为可行流,2019/2/25,管理运筹学,三、基本概念与定理,2019/2/25,管理运筹学,2. 增广链,f为一可行流，u为vs至vt的链，令u+=正向弧， u-=反向弧。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。,2019/2/25,管理运筹学,2. 增广链,f为一可行流，u为vs至vt的链，令u+=正向弧， u-=反向弧。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。,2019/2/25,管理运筹学,2. 增广链,f

15、为一可行流，u为vs至vt的链，令u+=正向弧， u-=反向弧。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。,2019/2/25,管理运筹学,2. 增广链,f为一可行流，u为vs至vt的链，令u+=正向弧， u-=反向弧。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。,2019/2/25,管理运筹学,3. 截集与截量,把V分成两部分：V1和V2(V1 V2= , V1 V2= V)且vs V1、 vt V2，则弧集(V1,V2)称为D的截集。 截集上的容量和称为截量，记为C(V1,V2) 。,(vs,v2), (v1,vt)； 截量为： C(V1,V2)

16、=4+3=7,截集为：,2019/2/25,管理运筹学,4. 流量与截量的关系,任一可行流的流量都不会超过任一截集的截量 （ v(f)=f (V1,V2) - f (V2,V1) f (V1,V2) C (V1,V2) ）,最大流最小截定理：网络的最大流量等于最小截量。,2019/2/25,管理运筹学,例. 如图所示的网络中，弧旁数字为(cij ,fij),（1）确定所有的截集； （2）求最小截集的容量； （3）证明图中的流为最大流；,2019/2/25,管理运筹学,（1）所有的截集：, V1=vs，,截集为(vs,v1), (vs,v2)，截量为：6,2019/2/25,管理运筹学,v1,v

17、s,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，截集为(vs,v1), (vs,v2)，截量为：6 V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7,2019/2/25,管理运筹学,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，截集为(vs,v1), (vs,v2)，截量为：6 V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7 V1=vs ,v2，截集为，截量

18、为：7,2019/2/25,管理运筹学,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，截集为(vs,v1), (vs,v2)，截量为：6 V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7 V1=vs ,v2，截集为，截量为：7 V1=vs ,v3，截集为，截量为：12,2019/2/25,管理运筹学,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，截集为(vs,v1), (

19、vs,v2)，截量为：6 V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7 V1=vs ,v2，截集为，截量为：7 V1=vs ,v3，截集为，截量为：12 V1=vs ,v1,v2，截集为，截量为：5,2019/2/25,管理运筹学,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，截集为(vs,v1), (vs,v2)，截量为：6 V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7 V1=vs ,v2，截集为，截量为：7 V1=vs ,v3，截集为，截

20、量为：12 V1=vs ,v1,v2，截集为，截量为：5,2019/2/25,管理运筹学,（2）最小截量min C (V1,V2)= 5； （3）v(f*)=5= min C (V1,V2) f*是最大流。,2019/2/25,管理运筹学,四、求最大流方法标号法,理论依据：,思路：从始点开始标号，寻找是否存在增广链。给vj标号为j,vi，其中j为调整量， vi为前一节点。,2019/2/25,管理运筹学,步骤： (1)给vs标号为,vs，,流出未饱和弧(vs , vj) ,给vj标号j,vs,其中j=csj- fsj,例. 图中网络弧旁数字为(cij ,fij)，用标号法求最大流。,vs,4,

21、vs,选与vs关联的,2019/2/25,管理运筹学,2019/2/25,管理运筹学,考虑所有VA VB的弧，若该弧为,流出未饱弧,则给vj标号j,vi,其中j= cij- fij,流入非零弧,则给vj标号j,-vi ,其中j= fij,(3),1,-v1,2019/2/25,管理运筹学,(4),重复（2）,（3），依次进行的结局可能为,vt已标号，得到一条增广链u(反向追踪)，转（5）；,vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。,（3,0）,2019/2/25,管理运筹学,1, v2,（3,0）,2019/2/25,管理运筹学,2, v4,2019/2/25,管理运筹

22、学,2019/2/25,管理运筹学,2019/2/25,管理运筹学,v2,Vs,v1,v4,v3,Vt,（3,3）,（5,2）,（1,0）,（2,2）,（1,1）,（5,4）,（2,1）,（4,4）,（3,0）,调整,2019/2/25,管理运筹学,vs,3,vs,2019/2/25,管理运筹学,此时标号无法进行，当前流为最大流，最大流量为5；,最小截为(vs,v2), (v1,v3)，截量为：5,2019/2/25,管理运筹学,例 有三个发电站v1,v2,v3，发电能力分别为15、10和40兆瓦，经输电网可把电力送到8号地区，电网能力如图所示。求三个发电站输到该地区的最大电力。,v0,10,

23、20,15,15,15,10,20,10,20,20,15,35,2019/2/25,管理运筹学,例、图中A、B、C、D、E、F分别表示陆地和岛屿，表示桥梁及其编号。河两岸分别互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。,2019/2/25,管理运筹学,分析：转化为一个网络图，弧的容量为两点间的桥梁数。,则问题为求最小截。,2019/2/25,管理运筹学,分析：转化为一个网络图，弧的容量为两点间的桥梁数。,则问题为求最小截。,答案：最小截为AE、CD、CF,2019/2/25,管理运筹学,例、有一批人从我国A城赴俄罗斯B城，

24、可能的旅行路线如图：,边防队拟建立足够数量检查站以便使每辆汽车至少必经过一个检查站，建立检查站的费用根据各路段条件有所不同（如图数字所示），求最小费用解。,（分析：最小截问题）,2019/2/25,管理运筹学,例、过纽约ALBANY的北-南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆/小时。求（1）该路网能承受的北-南向最大流量；（2）若要扩充通过能力，应在那一组路段上扩充，说明原因。,2019/2/25,管理运筹学,案例：垃圾处理问题 某地区有3个城镇，各城镇每天产生的垃圾要运往该地区的4个垃圾处理场处理，现考虑各城镇到各处理场的道路对各城镇垃圾外运的影响。假设各城镇每日产生的垃

25、圾量、各处理场的日处理能力及各条道路（可供运垃圾部分）的容量（其中容量为0表示无此直接道路）如右表所示，试用网络流方法分析目前的道路状况能否使所有垃圾都运到处理场得到处理，如果不能，应首先拓宽哪条道路。,2019/2/25,管理运筹学,5 工程网络计划,引例：沏茶,2019/2/25,管理运筹学,一、 问题描述,一项工程，已知各工序完成时间t及其先后关系 求：工程完工期及关键工序,关键工序：主矛盾工序，不能延期完工 路线： 从始点到终点的一条路 关键路线：由关键工序组成的路线，是所有路线中时间最长的路线。,相关概念：,2019/2/25,管理运筹学,二、 求解方法关键路径法（CPM）,分为三步

26、： 绘制工程网络图 标号法求工期 T 标号法求关键路线,2019/2/25,管理运筹学,将整个工程分解为若干工序 确定各工序的前后顺序（紧前、紧后） 确定工序完成时间,三点估计法：最乐观时间a、最可能时间m、最悲观时间b,一点估计法,准备工作,2019/2/25,管理运筹学,1、绘制工程网络图,（1）顺序：按工序的先后从左至右,（2）图的结构,弧：,结点：,相邻工序的时间分界点，称为事项,权：,工序的完成时间,相邻弧：,工序的前后衔接关系，称为紧前或紧后工序,（3）绘图要求,图中不能出现缺口、回路和多重边,多重边的处理：,虚工序,2019/2/25,管理运筹学,例 某工厂进行技术改造，需要拆掉

27、旧厂房、建造新厂房和安排设备。这项改建工程可以分解为7道工序，其相关资料如下表：,2019/2/25,管理运筹学,1,2,3,4,5,A（2）,B (3),C (2.5),D (6),E (20),F (4),6,G (2),解：,2019/2/25,管理运筹学,例：绘制工程网络图,续左表,解：,1,A (2),D (3),C (2),2,E (4),3,F(7),B (0),G(6),4,5,E(0),6,I (10),7,J(3),H (4),8,B (3),2019/2/25,管理运筹学,两种情况需要引入虚工序：,2019/2/25,管理运筹学,课堂练习 P150习题6.1,2019/2

28、/25,管理运筹学,2、用标号法求工期 T,步骤：,0,2,3,3,6,13,16,2019/2/25,管理运筹学,3、用标号法求关键路线,步骤：,16,12,8,13,3,3,0,2019/2/25,管理运筹学,2019/2/25,管理运筹学,其他时间参数：,（1）工序(i , j) 最早开始时间,（2）工序(i , j) 最晚开始时间,2019/2/25,管理运筹学,其他时间参数：,（3）工序(i , j) 最早结束时间,（4）工序(i , j) 最晚结束时间,2019/2/25,管理运筹学,其他时间参数：,（5）工序(i , j) 的自由时差,2019/2/25,管理运筹学,课堂练习 P

29、150习题6.1,2019/2/25,管理运筹学,三、工程工期的概率分析计划评审技术（PERT）,PERT与CPM的主要区别： CPM工序时间是确定的；,PERT工序时间tij 是随机变量，而完工期T 也是随机的，由概率知识：T 服从正态分布,2019/2/25,管理运筹学,确定平均工序时间的三点估计法：,总工期,其中：,（I 为关键路线）,2019/2/25,管理运筹学,1. 给定时间T*，求工期TT*内完工的概率,PERT的内容,2019/2/25,管理运筹学,例、已知某工程网络图，以及各工序的时间参数。,TE=42.33,关键路线I为:ACFH；,解：,2019/2/25,管理运筹学,2

30、. 给定概率p，求完工可能性为p的工期,例、上例中，求完工可能性达95%的工期。,再由,2019/2/25,管理运筹学,四、网络图的调整与优化,1. 缩短工程工期问题,压缩关键工序 在非关键工序上挖掘潜力 尽量采用平行工序和交叉工序 注意关键路线的变化,2019/2/25,管理运筹学,2. 工程的时间费用分析,（1）费用构成：,直接费用：原材料、工时费等,间接费用：管理费、办公费,间接费用率一般固定，与工序无关。,2019/2/25,管理运筹学,工程的时间费用分析,求最低成本工期T*,求规定工期下的最小成本方案,2019/2/25,管理运筹学,（2）求最低成本工期T*,方法：,求出正常工期和关

31、键工序 （用CPM方法）,比较直接费用率（q） 、间接费用率（p）：,（注:当有多条关键路线时，应以各路线上最小的q之和与p比较。）,若关键路线上最小的 qp，则正常工期即为T*；,否则，在关键工序上压缩。先压缩q最小的，直至不能再压为止，再压次小的，以此类推。直至qp为止。,（注：当压缩引起出现新的关键路线时，若压要同时压。）,压缩时间t的确定：,若t取值 ，则产生了新的关键路线,2019/2/25,管理运筹学,例：设某工程有关资料如表，间接费用率p=5； 求最低费用工期。,解：画出网络图，,T=12，关键路线：A-C-D。,先压C，在C上可压缩,可节省费用：,2天，,（5-4)2=2,此时

32、出现两条关键路线，, T*=10,2019/2/25,管理运筹学,（3）求规定工期下的最小成本方案,方法：,求出正常工期和关键工序 在关键工序上压，先压缩其中直接费用率最低的，当出现多于一条的关键路线时要同时压，直至满足规定为止。,（间接费用率是确定的，与工序无关，只需考虑直接费用）,2019/2/25,管理运筹学,例、某建筑公司安装水管的工程有关资料：,2019/2/25,管理运筹学,按正常情况画出施工网络图，求完工期并找出关键工序。 现提出这项工程要60天完成，求使总应急费用最小的方案。,2019/2/25,管理运筹学,（2）计算各工序的直接费用率：,需压缩8.6天：,f压缩2.7天（不会出现新关键路线） h压缩2.2天（不会出现新关键路线）,C先压缩3.2天，出现新的关键路线。,c、d同时压缩0.5天。,（ c、d总费用率384.71g的费用率607.14。）,2019/2/25,管理运筹学,