《天津大学管理学课件第二章图论》由会员分享，可在线阅读，更多相关《天津大学管理学课件第二章图论（110页珍藏版）》请在金锄头文库上搜索。
1、第二章 图论与网络分析 图的基本概念图的基本概念 网络分析网络分析最小支撑树问题最小支撑树问题 最短路径问题最短路径问题网络最大流问题网络最大流问题网络计划问题网络计划问题8/2/2024管理运筹学ABCDACBD图论起源图论起源哥尼斯堡七桥问题哥尼斯堡七桥问题结论：结论：每个结点关联的边数均为偶数。每个结点关联的边数均为偶数。问题：问题：一个散步者能否从任一块陆地出发，走过七一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？座桥，且每座桥只走过一次，最后回到出发点？8/2/2024管理运筹学1 图的基本概念图的基本概念由点和边组成，记作由点和边组成，记作G=(V
2、，E)，其中其中V=v1，v2，vn为为结点的集合，结点的集合，E=e1，e2，em 为边的集合。为边的集合。点表示研究对象点表示研究对象边表示表示研究对象之间的特定关系边表示表示研究对象之间的特定关系1. 图图8/2/2024管理运筹学图图无向图，记作无向图，记作G=(V，E)有向图，记作有向图，记作D=(V，A)例例1：哥尼斯堡桥问题的图为一个无向图。：哥尼斯堡桥问题的图为一个无向图。有向图的边有向图的边称为称为弧弧。例例2：五个球队的比赛情况，：五个球队的比赛情况，v1v2表示表示v1胜胜v2。v1v2v3v4v52、图的分类、图的分类8/2/2024管理运筹学v1v2v3v4v53、链
3、与路、圈与回路、链与路、圈与回路链链点边交错的序列点边交错的序列圈圈起点起点=终点的链终点的链路路点弧交错的序列点弧交错的序列回路回路起点起点=终点的路终点的路v1v2v3v4v5无向图：无向图：有向图：有向图：8/2/2024管理运筹学4、连通图、连通图任何两点之间至少存在一条链的图称为连通图，任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。否则称为不连通图。G1G2G1为为不连通图，不连通图， G2为连通图为连通图例例 ：8/2/2024管理运筹学5、支撑子图、支撑子图图图G=(V，E)和和G=(V ，E )，若，若V =V 且且E E ，则称则称G 为为G的的支撑子图支撑子图
4、。G2为为G1的支撑子图的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2例例 ：8/2/2024管理运筹学6、赋权图（网络）、赋权图（网络）图的每条边都有一个表示一定实际含义的图的每条边都有一个表示一定实际含义的权数，称为权数，称为赋权图赋权图。记作。记作D=(V，A，C)。55.5v1v2v3v4v53.57.5423例例 ：8/2/2024管理运筹学2 最小支撑树问题最小支撑树问题本节主要内容：本节主要内容：树树支撑树支撑树最小支撑树最小支撑树 例例今今有有煤煤气气站站A，将将给给一一居居民民区区供供应应煤煤气气，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，铺铺设设
5、各各用用户户点点的的煤煤气气管管道道所所需需的的费费用用（单单位位：万万元元）如如图图边边上上的的数数字字所所示示。要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222254526345318/2/2024管理运筹学1、树中任两点中有且仅有一条链；树中任两点中有且仅有一条链；2、树任删去一边则不连通，故树是使图保持连通且具有最少边数、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。的一种图形。3、边数边数 = 顶点数顶点数 1。树树无圈连通图无圈连通图(A)(B)(C)树的性质：树的性
6、质：例例 判断下面图形哪个是树：判断下面图形哪个是树：一、树的概念与性质一、树的概念与性质8/2/2024管理运筹学 若一个图若一个图 G =（V , E）的支撑子图的支撑子图 T=（V , E） 构成树，则称构成树，则称 T 为为G的支撑树的支撑树，又称，又称生成树生成树、部分树部分树。二、二、图的支撑树图的支撑树(G)(G1)(G2)(G3)(G4)例例8/2/2024管理运筹学例例 某地新建某地新建5处居民点，拟修处居民点，拟修道路连接道路连接5处，经勘测其道路可铺处，经勘测其道路可铺成如图所示。为使成如图所示。为使5处居民点都有处居民点都有道路相连，问至少要铺几条路？道路相连，问至少要
7、铺几条路？解：解：该问题实为求图该问题实为求图的支撑树问题，的支撑树问题，共需铺共需铺4条路。条路。v1v2v3v4v5 图的支撑树的应用举例图的支撑树的应用举例v1v2v3v4v555.57.53.54238/2/2024管理运筹学问题：问题：求网络的支撑树，使其权和最小。求网络的支撑树，使其权和最小。三、最小支撑树问题三、最小支撑树问题55.5v1v2v3v4v57.53.5423算法算法1（避圈法）：（避圈法）：把边按权从小到大依次把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，添入图中，若出现圈，则删去其中最大边，直至填满直至填满n-1条边为止（条边为止（n为结点数）为结点数
8、） 。例例 求上例中的最小支撑树求上例中的最小支撑树解：解：3v12v4v545v23.5v38/2/2024管理运筹学算法算法2（破圈法）：（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。至图中不存在圈。55.5v1v2v3v4v57.53.54238/2/2024管理运筹学算法算法2（破圈法）：（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。至图中不存在圈。55.5v1v2v3v4v53.54238/2/2024管理运筹学算法算法2（破圈法）：
9、（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。至图中不存在圈。5v1v2v3v4v53.54238/2/2024管理运筹学算法算法2（破圈法）：（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。至图中不存在圈。5v1v2v3v4v53.5238/2/2024管理运筹学 例例今今有有煤煤气气站站A，将将给给一一居居民民区区供供应应煤煤气气，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，铺铺设设各各用用户户点点的的煤煤气气管管道道所所需需的
10、的费费用用（单单位位：万万元元）如如图图边边上上的的数数字字所所示示。要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222254526345318/2/2024管理运筹学 例例今今有有煤煤气气站站A，将将给给一一居居民民区区供供应应煤煤气气，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，铺铺设设各各用用户户点点的的煤煤气气管管道道所所需需的的费费用用（单单位位：万万元元）如如图图边边上上的的数数字字所所示示。要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线
11、，并求所需的总费用。3.5ABCDEFGHIJKS2222224526345318/2/2024管理运筹学 例例今今有有煤煤气气站站A，将将给给一一居居民民区区供供应应煤煤气气，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，铺铺设设各各用用户户点点的的煤煤气气管管道道所所需需的的费费用用（单单位位：万万元元）如如图图边边上上的的数数字字所所示示。要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222526345318/2/2024管理运筹学 例例今今有有煤煤气气站站A，将将给给一一居居民民区
12、区供供应应煤煤气气，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，铺铺设设各各用用户户点点的的煤煤气气管管道道所所需需的的费费用用（单单位位：万万元元）如如图图边边上上的的数数字字所所示示。要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222226345318/2/2024管理运筹学 例例今今有有煤煤气气站站A，将将给给一一居居民民区区供供应应煤煤气气，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，铺铺设设各各用用户户点点的的煤煤气气管管道道所所需需的的费费用用（单单位位：万万元
13、元）如如图图边边上上的的数数字字所所示示。要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS22222226345318/2/2024管理运筹学 例例今今有有煤煤气气站站A，将将给给一一居居民民区区供供应应煤煤气气，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，铺铺设设各各用用户户点点的的煤煤气气管管道道所所需需的的费费用用（单单位位：万万元元）如如图图边边上上的的数数字字所所示示。要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。IABCDEFGHJ
14、KS2222222345318/2/2024管理运筹学 例例今今有有煤煤气气站站A，将将给给一一居居民民区区供供应应煤煤气气，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，铺铺设设各各用用户户点点的的煤煤气气管管道道所所需需的的费费用用（单单位位：万万元元）如如图图边边上上的的数数字字所所示示。要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为此即为最经济的煤气管道路线，所需的总费用为25万元万元8/2/2024管理运筹学案例分析：案例分析：
15、默登公司的联网问题默登公司的联网问题 默登（默登（ModernModern）公司的管理层决定铺设最先进的公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图光纤网络，为它的主要中心之间提供高速通信。图1 1中的节点显示了该公司主要中心的分布图。虚线是铺中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。（单位：百万美元）。 问：问：需要铺设哪些光缆使得总成本最低？需要铺设哪些光缆使得总成本最低？ A AB BC CE EG GF FD D2 25 52 27 74 45 5
16、7 71 13 31 14 44 4图图1 1 光缆铺设费用图光缆铺设费用图8/2/2024管理运筹学案例分析：案例分析：默登公司的联网问题默登公司的联网问题ABCEGFD225131图图 1 光缆铺设最小费用图光缆铺设最小费用图8/2/2024管理运筹学3 最短路问题最短路问题问题：问题：求网络中起点到其它点之间的一求网络中起点到其它点之间的一条最短路线。条最短路线。v2v1v3v4v5v6v7v8v9163222266133101044例例 求网络中求网络中v1到到v9的最短路的最短路8/2/2024管理运筹学算法：算法：Dijkstra（狄克斯拉）标号法狄克斯拉）标号法基本思想：基本思想
17、：从起点从起点vs开始，逐步给每个结开始，逐步给每个结点点vj标号标号dj，vi，其中其中dj为起点为起点vs到到vj的的最短距离，最短距离，vi为该最短路线上的前一节点。为该最短路线上的前一节点。8/2/2024管理运筹学10v2v1v3v4v5v6v7v8v916322226613310440, v11, v1(1) 给起点给起点v1标号标号0, v1(3) 考虑所有这样的边考虑所有这样的边vi , vj，其中其中viVA， vjVB，挑选挑选其中与起点其中与起点v1距离最短（距离最短（mindi+cij）的）的vj，对，对vj进行标号进行标号(4) 重复重复(2)、(3)，直至终点，直至
18、终点vn标上号标上号dn, vi，则，则dn即为即为v1 vn的最短距离，反向追踪可求出最短路。的最短距离，反向追踪可求出最短路。步骤：步骤：(2) 把顶点集把顶点集V分成分成VA：已标号点集已标号点集VB：未标号点集未标号点集8/2/2024管理运筹学0, v11, v13, v1(1) 给起点给起点v1标号标号0, v1(3) 考虑所有这样的边考虑所有这样的边vi , vj，其中其中viVA， vjVB，挑选挑选其中与起点其中与起点v1距离最短（距离最短（mindi+cij）的）的vj，对，对vj进行标号进行标号(4) 重复重复(2)、( 3)，直至终点，直至终点vn标上号标上号dn, v
19、i，则，则dn即为即为v1 vn的最短距离，反向追踪可求出最短路。的最短距离，反向追踪可求出最短路。步骤：步骤：(2) 把顶点集把顶点集V分成分成VA：已标号点集已标号点集VB：未标号点集未标号点集10v2v1v3v4v5v6v7v8v916322226613310448/2/2024管理运筹学0, v11, v13, v15, v310v2v1v3v4v5v6v7v8v916322226613310448/2/2024管理运筹学0, v11, v13, v15, v36, v210v2v1v3v4v5v6v7v8v916322226613310448/2/2024管理运筹学0, v11, v
20、13, v15, v36, v29, v510v2v1v3v4v5v6v7v8v916322226613310448/2/2024管理运筹学0, v11, v13, v15, v36, v29, v510, v510v2v1v3v4v5v6v7v8v916322226613310448/2/2024管理运筹学0, v11, v13, v15, v36, v29, v510, v512, v5此时终点此时终点v9已标号已标号12, v5，则，则12即为即为v1 vn的最的最短距离，反向追踪可求出最短路短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v916322226613310
21、448/2/2024管理运筹学0, v11, v13, v15, v36, v29, v510, v512, v5v1到到v9的最短路为：的最短路为：v1 v3 v2 v5 v9，最短距离为最短距离为1210v2v1v3v4v5v6v7v8v916322226613310448/2/2024管理运筹学课堂练习课堂练习 P129 习题习题5.30, v14, v13, v15, v26, v29, v77, v4/ v68.5, v66, v2v2v1v5v4v3v6v8v7v943232.5335234218/2/2024管理运筹学课堂练习课堂练习 无向图情形无向图情形求网络中求网络中v1至至
22、v7的最短路。的最短路。v1v2v3v4v5v6v72253557157138/2/2024管理运筹学课堂练习课堂练习 无向图情形无向图情形答案（答案（1）：）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v68/2/2024管理运筹学课堂练习课堂练习 无向图情形无向图情形答案（答案（2）：）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v68/2/2024管理运筹学最短路模型的应用最短路模型的应用设备更新问题设备更新问题（P119 例例 5.3）v2v1
23、v3v4v5v6第第i年年12345价格价格ai11 11121213使用寿命使用寿命 01 122334 45费用费用bj56811180,v116,v122,v130,v141,v153,v3/v416分析分析：结点结点：V=v1，v6， vi表示第表示第i年初；年初；边边： E=(vi，vj) 表示第表示第i年初购买，用至第年初购买，用至第j年初；年初；i= 1,5; j= 2,6权权cij： i年初年初 j年初的费用，即年初的费用，即cij= i年初购买费年初购买费+（j-i）年里的维修费年里的维修费30224159162230411723311723188/2/2024管理运筹学4
24、网络最大流问题网络最大流问题引例：下图为引例：下图为V1到到V6的一交通网，权表示相应运输线的最的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从大通过能力，制定一方案，使从V1到到V6的产品数量最多。的产品数量最多。v2v1v3v4v5v6810417553116353122133628/2/2024管理运筹学设有网络设有网络D=(V, A, C)，其中其中C=cij， cij为弧为弧(vi,vj)上的容量，现在上的容量，现在D上要通过一个流上要通过一个流f=fij， fij为弧为弧(vi,vj)上的流量。上的流量。 问题：问题：如何安排如何安排fij，可使网络可使网络D上的总流量
25、上的总流量V最大？最大？v2v1v3v4v5v681041755311635312213362一、一般提法：一、一般提法：8/2/2024管理运筹学二、最大流问题的模型二、最大流问题的模型max v=v（f） 容量约束容量约束平衡约束平衡约束s.t.v2Vsv3v4v5Vt81041755311635312213362注：满足约束条件的流注：满足约束条件的流f称为可行流称为可行流8/2/2024管理运筹学三、基本概念与定理三、基本概念与定理1. 弧按流量分为弧按流量分为饱和弧饱和弧 fij=cij非饱和弧非饱和弧 fijp，则正常工期即为则正常工期即为T*；v 否则，在关键工序上压缩。先压缩否
26、则，在关键工序上压缩。先压缩q最小的，直至不能最小的，直至不能再压为止，再压次小的，以此类推。直至再压为止，再压次小的，以此类推。直至qp为止。为止。（注：注：当压缩引起出现新的关键路线时，若压要同时压。）当压缩引起出现新的关键路线时，若压要同时压。）v 压缩时间压缩时间t的确定：的确定：若若t取值取值 ，则产生了则产生了新的关键路线新的关键路线8/2/2024管理运筹学例例：设某工程有关资料如表，间接费用率：设某工程有关资料如表，间接费用率p=5； 求最低费用工期。求最低费用工期。工序工序紧前紧前工序工序工序工序时间时间直接直接费用率费用率可压可压天数天数A/3/BA731CA443DC56
27、2解解：画出网络图，：画出网络图， T=12，关键路线：关键路线：A-C-D。1234A(3)B(7)C(4)D(5) 先先压压C，在，在C上可压缩上可压缩可节省费用：可节省费用：2天，天，（5-4)2=2 此时出现两条关键路线，此时出现两条关键路线， T*=101234A(3)B(7)C(2)D(5)直接费用之和直接费用之和3+45，故不能再压。，故不能再压。此时需此时需B、C同时压，但其同时压，但其8/2/2024管理运筹学（3）求规定工期下的最小成本方案）求规定工期下的最小成本方案方法：方法： 求出正常工期和关键工序求出正常工期和关键工序 在关键工序上压，先压缩其中直接费用率最低的，在关
28、键工序上压，先压缩其中直接费用率最低的，当出现多于一条的关键路线时要同时压，直至满足当出现多于一条的关键路线时要同时压，直至满足规定为止。规定为止。（间接费用率是确定的，与工序无关，只需考虑直接费用）（间接费用率是确定的，与工序无关，只需考虑直接费用）8/2/2024管理运筹学例、某建筑公司安装水管的工程有关资料：例、某建筑公司安装水管的工程有关资料：工作工作紧前紧前工作工作正常情况正常情况应急情况应急情况时间（天）时间（天）费用（元）费用（元）时间（天）时间（天） 费用（元）费用（元）a/11.7240/ba3.2752110ca25.24500157200da18.048017600ed9
29、.05408710fb,c7.7168051800ge,f16.84000145700hg7.2160051775ie,f12.8500912988/2/2024管理运筹学(1)按正常情况画出施工网络图，求完工期并找出关按正常情况画出施工网络图，求完工期并找出关键工序。键工序。(2) 现提出这项工程要现提出这项工程要60天完成，求使总应急费用天完成，求使总应急费用最小的方案。最小的方案。14276835a(11.7)b(3.2)c (25.2 )d(18.0)e(9.0)f (7.7)g(16.8)h(7.2)i (12.8)b (0)解：解： （1）网络图如下：）网络图如下：标号法求得：正常
30、工期标号法求得：正常工期T=68.6天，天，关键工序：关键工序：a-c-f-g-h8/2/2024管理运筹学（2）计算各工序的直接费用率：）计算各工序的直接费用率：工序工序abcdefghi可压时间可压时间/1.210.2112.72.82.23.8直接费用率直接费用率 / 29.17264.7112017044.4607.1479.55 367.8914276835a(11.7)b(3.2)c (25.2 )d(18.0)e(9.0)f (7.7)g(16.8)h(7.2)i (12.8)b (0)需压缩需压缩8.6天：天：f压缩压缩2.7天（不会出现新关键路线）天（不会出现新关键路线）h压缩压缩2.2天（不会出现新关键路线）天（不会出现新关键路线）还需压缩还需压缩3.7天天C先压缩先压缩3.2天，出现新的关键路线。天，出现新的关键路线。c、d同时压缩同时压缩0.5天。天。 （ c、d总费用率总费用率384.71g的费用的费用率率607.14。）。）还需压缩还需压缩0.5天天8/2/2024管理运筹学8/2/2024管理运筹学
