运筹学课件第7章 图与网络模型

第7章图与网络模型重庆三峡学院关文忠管理运筹学课件2020年1月21日星期二教学目标与要求【教学目标】通过对本章的学习，理解图的基本概念；掌握最小支撑树、最短路、最大流、中国邮路问题的求法；会利用相关模型解决合理组织人力、物力、财力的优化问题。【知识结构】图与网络模型图的基本概念最大流问题最小支撑树最小费用流排课等匹配问题各种网络优化回到始点最佳路线最短路问题中国邮路问题多服务设施布点单服务设施布点规划论管理运筹学课件2020年1月21日星期二导入案例——七桥问题18世纪德国哥尼斯堡如图（a）七座桥，能否不重复一次走完并回到出发地？CABD（a）七桥问题示意图（b）七桥问题简单图1736年，欧拉在圣彼得堡科学院作了一次学术报告。在报告中，他证明了鉴别任一图形能否一笔画出的准则，即欧拉定理。管理运筹学课件2020年1月21日星期二导入案例——四色问题“任何一张地图只用四种颜色就能使有共同边界的国家着上不同的颜色。”1852年，英国搞地图着色工作的格思里，首先提出了四色问题。1872年，英国数学家凯利正式向伦敦数学学会提出这个问题，于是四色猜想成了世界数学界关注的问题。美国数学教授哈肯和阿佩尔于1976年6月,使用伊利诺斯大学的电子计算机计算了1200个小时，作了100亿个判断，终于完成了四色定理的证明。不过不少数学家认为应该有一种简捷明快的书面证明方法。各省用点表示,有边界接壤的用连线表示,则:这张地图有几种颜色?能区分各省的边界吗?管理运筹学课件2020年1月21日星期二导入案例运筹学中把一些研究对象用节点表示，对象之间的关系用连线边表示。用点、边的集合构成图。图论是研究有节点和边所组成图形的数学理论和方法。图是网络分析的基础，根据具体研究的网络对象（如：铁路网、电力网、通信网等），赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点，中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。图论广泛地应用于物理学、化学、信息论、科学管理、电子计算机等各个领域。如在管理中网络合理架设、网络承载能力分析、服务设施布点、匹配问题等。管理运筹学课件2020年1月21日星期二本章主要内容7.1图的基本概念7.2树图及图的最小支撑树7.2.1树图的基本性质7.2.2最小支撑树的求法:避圈法和破圈法案例7-1印第安那州公路规划问题7.3最短路问题7.3.1两点间最短路的Dijkstra标号算法7.3.3各点间最短路的矩阵算法*案例7-2设备更新问题7.4中国邮递员问题案例7-3货场巡视路线7.5网络最大流问题7.5.1基本概念7.5.2Ford-Fulkerson标号算法案例7-4航空公司的最大流量7.6最小费用流问题*7.6.1最小费用流的数学模型7.6.2最小费用最大流的标号算法案例7-5货物配送问题本章小结管理运筹学课件2020年1月21日星期二7.1.1图的若干示例【例7.1】有A、B、C、D、E5个球队，已比赛过，就在这两队相应的点之间连一条线.[P1]ABCED【例7.2】8种化学药品，不能存放在同一个库房里的用连线表示。【例7.3】若在五支球队比赛中，甲胜乙表示为“甲→乙”，则右图表明A三胜一负，B和E一胜一负，C和D一胜两负。管理运筹学课件2020年1月21日星期二7.1.2图的基本概念图（Graph）由点（Vertex）和点之间的连线所构成的集合。不带箭头的连线称为边（Edge）；带前头的连线称为弧（Arc）。点和边的集合称为无向图（Undirectedgraph），如图7.5(a)，简称图，用G={V，E}表示；点和弧的集合称为有向图（Directedgraph），如图7.5(b)，用D={V，A}表示。有向图去掉箭头所形成的无向图称为该有向图的基础图（underlyinggraph）。端点，关联边，相邻若边e=[u,v]∈E，则称u,v是e的端点，称e是点u或v的关联边。有公共关联边的点称为点相邻；公共端点的边称为边相邻。环，多重边，简单图，多重图两个端点重合的边称为环；若两个点之间有多于一条的边，称为多重边；一个无环、无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)管理运筹学课件2020年1月21日星期二7.1.2图的基本概念次，奇点，偶点，孤立点，悬挂点，悬挂边点的关联边的数目称为的次(也称度或线度)，记为d(v)(环在计算时算作两次，称为入次和出次)；次为奇数的点称为奇点；次为偶数的点称为偶点；次为0的点称为孤立点；次为1的点称为悬挂点；与悬挂点相边关联的边称为悬挂边。【定理7.1】图中，所有顶点的次之和是边数的2倍。【定理7.2】任一个图中，奇点的个数为偶数。链，圈，路，回路，连通图点和边的交错序列中，若边各不相同称为链；封闭的链称为圈；在链中如果点也各不相同称为路；起点与终点重合的路称为回路；任意两点之间至少能找到一条链的图称为连通图。图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)管理运筹学课件2020年1月21日星期二7.1.2图的基本概念,VVEEGG及则称是图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)完全图，子图，支撑图（部分图）一个简单图中若任意两点之间均有边相连，称这样的图为完全图，如图7.5(b)；图如果满足的子图；如果满足的一个支撑图（或称为部分图）。如图7.6(b)是图(a)的子图，并不是支撑图，图(c)是图(a)的支撑图。(,)(,)GVEGVE和,VVEEGG及则称是管理运筹学课件2020年1月21日星期二承【例7-2】这是一个染色问题,其方法:找出次数最大的点,将其与不相邻的点组成新的点集;再从其余的子图中找出次数最大的点,将其与不相邻的点组成新的点集,直到子图的点集为空.v1v8v2v7v3v6v5v4{,}{,}{,,}{}7.1.2图的基本概念至少需要3个库房管理运筹学课件2020年1月21日星期二7.2.1树图的概念和性质树图，简称树，记作T(V,E)：是一类简单而十分有用的图，其定义是无圈的联通图。现实生活中树图随处可见，如管理组织机构图、决策树图、聚类分析的“龙骨图”、磁盘文件存放路径图、家族族谱图、经济管理中的因果分析图（鱼刺图）等等，因其与大自然中的树的特征相似而得名。下面不加证明地给出树的一些重要性质。性质1任何树图必存在悬挂点。如图7.8有3个悬挂点。性质2具有p个点的树图的边数恰好为p-1条边。如图7.8有4个点、3条边。性质3任何具有p个点条边的联通图是树图。性质4树图中任意两点之间恰有一条链。性质5树图中任意两点之间添加一条边正好构成一个圈。如果图T=(V,E’)是图G=(V,E)的支撑图，又是树图，则称T是G的一个支撑树（或称为部分树）。例如图7.8是图7.6(a)的一个支撑树。管理运筹学课件2020年1月21日星期二7.2.1树图的概念和性质管理运筹学课件2020年1月21日星期二7.2.2最小支撑树的求法——避圈法任选vi,使vi∈V,其余点在中VV从V与的连线中找一条最小边,使其包含在最小支撑树内所有点均在V中?结束是,\iiVvVVvV否ABCDEF872594631【例7.4】求下图最小支撑树W(T*)=17管理运筹学课件2020年1月21日星期二7.2.2最小支撑树的求法——破圈法任取一个圈,从圈中去掉一条最大的边(如果有两条或两条以上的边都是权最大的边,则任意去掉其中一条).在余下的图中重复这个步骤,直到不含圈的图为止,此时的图便是最小树.ABDEF82594631C743取回路ABC，去掉最大边[A,B]；取回路BCE，去掉最大边[B,E]；取回路BCED，去掉最大边[D,E]；取回路BCEFD，去掉最大边[B,D]W(T*)=17管理运筹学课件2020年1月21日星期二案例7-1印第安那州公路规划问题(1)(2)(3)(4)(5)(1)Gary(2)FortWayne(3)Evansvile(4)TerreHaute(5)SouthHend—13221716458132—29020179217290—113303164201113—1965879303196—因政治原因不能建造连接(1)和(2)的公路以及连接(3)和(5)的公路.如何建造可使总施工长度最短?123452171645829020179196113W(T*)=414WinQSB演示Excel演示Lingo演示管理运筹学课件2020年1月21日星期二7.3.1求两点间最短路的Dijkstra标号算法2444633223322ABCTDEFS02356789结论：最短路径SADT，或SCFT；最短路长：9【例7.6】管理运筹学课件2020年1月21日星期二7.3.1求两点间最短路的Dijkstra标号算法【例7.7】用Dijkstra方法求点S到点T的最短路及路长。6536725SATBC056813最短路线:SACT或:SAT最短路长:13(1)给S标号0(2)V={S},补集CV={A,B,C,T},min{LSS+DSB,LSS+DSA}={0+5,0+6}=5给B标号5,[S,B]加粗(2)V={S,B},CV={A,C,T},min{LSS+DSA,LSB+DBC}={0+6,5+8}=6给A标号6,[S,A]加粗(3)V={S,B,A},CV={C,T},min{LSA+DAC,LSA+DAT,LSB+DBC}={6+2,6+7,5+6}=8给C标号8,[A,C]加粗(3)V={S,B,A,C},CV={T},min{LSA+DAT,LSC+DCT}={6+7,8+5}=13给T标号13,[A,C]或[A,T]加粗WinQSB演示Excel演示Lingo演示管理运筹学课件2020年1月21日星期二7.3.3求网络各点之间最短路的矩阵计算法*2444633223322SABCTDEF【例7.9】求各点间最短路矩阵(0)0232034630243204402364203243023220D解(1)构造邻接矩阵(1)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)min{,,,,,,,}SBSSSBSAABSBBBSCCBSDDBSEEBSFFBSTTBddddddddddddddddd{0,23,0,32,,4,,}3(1)(0)(0)min{}ijirrjddd(2)计算经过1个中间点的可达矩阵一般地(3)利用递推公式计算经过1个中间点的可达矩阵自编软件ExcelORM所见即所得.管理运筹学课件2020年1月21日星期二案例7-2设备更新问题设备在各年年初的价格第1年第2年第3年第4年第5年1012131415使用不同时间（年）的设备所需要的维修费用使用年数0-11-22-33-44-5维修费用4691219v1v2v3v4v5v6202941602231432332241416171819求费用最小的设备更新计划.Dijkstra标号算法：先给v1标号“0”给v2标号“14”给v3标号“20”011121113111411151116014020minmin02914041060vvvvvvvvvvvvvvvvvvvvLdLdLdLdLd111311141115111