《管理运筹学课件第7章图与网络模型》由会员分享，可在线阅读，更多相关《管理运筹学课件第7章图与网络模型（36页珍藏版）》请在金锄头文库上搜索。
1、第第7章章图与网络模型图与网络模型教学目标与要求教学目标与要求n【教学目标教学目标】n通过对本章的学习，理解图的基本概念；掌握最小支撑树、最短路、通过对本章的学习，理解图的基本概念；掌握最小支撑树、最短路、最大流、中国邮路问题的求法；会利用相关模型解决合理组织人力、最大流、中国邮路问题的求法；会利用相关模型解决合理组织人力、物力、财力的优化问题。物力、财力的优化问题。n【知识结构知识结构】8/25/20242课件导入案例导入案例七桥问题七桥问题18世纪德国哥尼斯堡如图（世纪德国哥尼斯堡如图（a）七座桥，能否不重复一次走完并回到出）七座桥，能否不重复一次走完并回到出发地？发地？（a）七桥问题示意
2、图）七桥问题示意图（b）七桥问题简单图）七桥问题简单图1736年，欧拉在圣彼得堡科年，欧拉在圣彼得堡科学院作了一次学术报告。在学院作了一次学术报告。在报告中，他证明了鉴别任一报告中，他证明了鉴别任一图形能否一笔画出的准则，图形能否一笔画出的准则，即欧拉定理。即欧拉定理。8/25/20243课件导入案例导入案例四色问题四色问题“任何一张地图只用四种颜色任何一张地图只用四种颜色就能使有共同边界的国家着上就能使有共同边界的国家着上不同的颜色。不同的颜色。”1852年，英国搞地图着色工年，英国搞地图着色工作的格思里，首先提出了四色作的格思里，首先提出了四色问题。问题。1872年，英国数学家凯利正年，英
3、国数学家凯利正式向伦敦数学学会提出这个问式向伦敦数学学会提出这个问题，于是四色猜想成了世界数题，于是四色猜想成了世界数学界关注的问题。学界关注的问题。美国数学教授哈肯和阿佩尔美国数学教授哈肯和阿佩尔于于1976年年6月月,使用伊利诺斯使用伊利诺斯大学的电子计算机计算了大学的电子计算机计算了1200个小时，作了个小时，作了100亿个判亿个判断，终于完成了四色定理的证断，终于完成了四色定理的证明。明。不过不少数学家认为应该有不过不少数学家认为应该有一种简捷明快的书面证明方法。一种简捷明快的书面证明方法。各省用点表示各省用点表示,有边界接壤的用连线表示有边界接壤的用连线表示,则则:这张地图有几种颜色
4、这张地图有几种颜色?能区分各省的边界吗能区分各省的边界吗?8/25/20244课件导入案例导入案例运筹学中把一些研究对象用节点表示，对象之间的关系用连运筹学中把一些研究对象用节点表示，对象之间的关系用连线线边表示。用点、边的集合构成图。图论是研究有节点和边边表示。用点、边的集合构成图。图论是研究有节点和边所组成图形的数学理论和方法。图是网络分析的基础，根据所组成图形的数学理论和方法。图是网络分析的基础，根据具体研究的网络对象（如：铁路网、电力网、通信网等），具体研究的网络对象（如：铁路网、电力网、通信网等），赋予图中各边某个具体的参数，如时间、流量、费用、距离赋予图中各边某个具体的参数，如时间
5、、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点，等，规定图中各节点代表具体网络中任何一种流动的起点，中转点或终点，然后利用图论方法来研究各类网络结构和流中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。图论广泛地应用于物理学、化学、信息论、量的优化分析。图论广泛地应用于物理学、化学、信息论、科学管理、电子计算机等各个领域。如在管理中网络合理架科学管理、电子计算机等各个领域。如在管理中网络合理架设、网络承载能力分析、服务设施布点、匹配问题等。设、网络承载能力分析、服务设施布点、匹配问题等。8/25/20245课件本章主要内容本章主要内容n7.1图的基本概念图
6、的基本概念n7.2树图及图的最小支撑树树图及图的最小支撑树n7.2.1树图的基本性质树图的基本性质n7.2.2最小支撑树的求法最小支撑树的求法:避圈避圈法和破圈法法和破圈法n案例案例7-1印第安那州公路规划印第安那州公路规划问题问题n7.3最短路问题最短路问题n7.3.1两点间最短路的两点间最短路的Dijkstra标号算法标号算法n7.3.3各点间最短路的矩阵算各点间最短路的矩阵算法法*n案例案例7-2设备更新问题设备更新问题n7.4中国邮递员问题中国邮递员问题n案例案例7-3货场巡视路线货场巡视路线n7.5网络最大流问题网络最大流问题n7.5.1基本概念基本概念n7.5.2Ford-Fulk
7、erson标号算标号算法法n案例案例7-4航空公司的最大流量航空公司的最大流量n7.6最小费用流问题最小费用流问题*n7.6.1最小费用流的数学模型最小费用流的数学模型n7.6.2最小费用最大流的标号最小费用最大流的标号算法算法n案例案例7-5货物配送问题货物配送问题n本章小结本章小结8/25/20246课件7.1.1 图的若干示例【例例7.1】 有有A、B、C、D、E5个球队，个球队，已比赛过，就在这已比赛过，就在这两队相应的点之间两队相应的点之间连一条线连一条线.P1【例例7.2】8种化学药品，种化学药品，不能存放在同一个库房里不能存放在同一个库房里的用连线表示。的用连线表示。【例例7.3
8、】若在五若在五支球队比赛中，支球队比赛中，甲胜乙表示为甲胜乙表示为“甲甲乙乙”，则右，则右图表明图表明A三胜一三胜一负，负，B和和E一胜一一胜一负，负，C和和D一胜两一胜两负。负。8/25/20247课件7.1.2图的基本概念图的基本概念n图图（Graph）由点点（Vertex）和点之间的连线所构成的集合。不带箭头的连线称为边边（Edge）；带前头的连线称为弧弧（Arc）。点和边的集合称为无无向图向图（Undirectedgraph），如图7.5(a)，简称图，用G=V，E表示；点和弧的集合称为有向图有向图（Directedgraph），如图7.5(b)，用D=V，A表示。有向图去掉箭头所形成
9、的无向图称为该有向图的基础图基础图（underlyinggraph）。n端点端点，关联边关联边，相邻相邻若边e=u,vE，则称u,v是e的端点，称e是点u或v的关联边。有公共关联边的点称为点相邻；公共端点的边称为边相邻。n环环，多重边多重边，简单图简单图，多重图多重图 两个端点重合的边称为环；若两个点之间有多于一条的边，称为多重边；一个无环、无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)8/25/20248课件7.1.2图的基本概念图的基本概念n次，奇点，偶点，孤立点，悬挂点，悬挂
10、边次，奇点，偶点，孤立点，悬挂点，悬挂边点的关联边的数目称为的次(也称度或线度)，记为d(v)(环在计算时算作两次，称为入次和出次)；次为奇数的点称为奇点；次为偶数的点称为偶点；次为0的点称为孤立点；次为1的点称为悬挂点；与悬挂点相边关联的边称为悬挂边。 n【定理定理7.1】 图中，所有顶点的次之和是边数的2倍。n【定理定理7.2】 任一个图中，奇点的个数为偶数。n链，圈，路，回路，连通图链，圈，路，回路，连通图 点和边的交错序列中，若边各不相同称为链；封闭的链称为圈；在链中如果点也各不相同称为路；起点与终点重合的路称为回路；任意两点之间至少能找到一条链的图称为连通图。图7.5(a)v1v2v
11、3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)8/25/20249课件7.1.2图的基本概念图的基本概念图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)n完全图，子图，支撑图（部分图）完全图，子图，支撑图（部分图） 一个简单图中若任意两点之间均有边相连，称这样的图为完全图，如图7.5(b) ；图如果满足 的子图；如果满足 的一个支撑图（或称为部分图）。如图7.6(b)是图(a)的子图，并不是支撑图，图(c)是图(a)的支撑图。8/25/202410课件n承承【例例7-2】这是一个染色问题这是一个染色问题,其方法其方法:找
12、出次数最大的点找出次数最大的点,将其与不将其与不相邻的点组成新的点集相邻的点组成新的点集;再从其余的子图中找出次数最大的点再从其余的子图中找出次数最大的点,将其与不将其与不相邻的点组成新的点集相邻的点组成新的点集,直到子图的点集为空直到子图的点集为空.v1v8v2v7v3v6v5v4 , , , , 7.1.2图的基本概念图的基本概念n至少需要至少需要3个库房个库房8/25/202411课件7.2.1树图的概念和性质树图的概念和性质n树图，简称树，记作树图，简称树，记作T(V,E)：是一类简单而十分有用的图，：是一类简单而十分有用的图，其定义是无圈的联通图。现实生活中树图随处可见，如管其定义是
13、无圈的联通图。现实生活中树图随处可见，如管理组织机构图、决策树图、聚类分析的理组织机构图、决策树图、聚类分析的“龙骨图龙骨图”、磁盘、磁盘文件存放路径图、家族族谱图、经济管理中的因果分析图文件存放路径图、家族族谱图、经济管理中的因果分析图（鱼刺图）等等，因其与大自然中的树的特征相似而得名。（鱼刺图）等等，因其与大自然中的树的特征相似而得名。 n下面不加证明地给出树的一些重要性质。下面不加证明地给出树的一些重要性质。性质性质1 任何树图必存在悬挂点。如图任何树图必存在悬挂点。如图7.8有有3个悬挂点。个悬挂点。性质性质2 具有具有p个点的树图的边数恰好为个点的树图的边数恰好为p-1条边。如图条边
14、。如图7.8有有4个点、个点、3条边。条边。性质性质3 任何具有任何具有p个点条边的联通图是树图。个点条边的联通图是树图。性质性质4 树图中任意两点之间恰有一条链。树图中任意两点之间恰有一条链。性质性质5 树图中任意两点之间添加一条边正好构成一个圈。树图中任意两点之间添加一条边正好构成一个圈。n如果图如果图T=(V,E)是图是图G=(V,E)的支撑图，又是树图，则称的支撑图，又是树图，则称T是是G的一个支撑树（或称为部分树）。例如图的一个支撑树（或称为部分树）。例如图7.8是图是图7.6(a)的的一个支撑树。一个支撑树。8/25/202412课件7.2.1树图的概念和性质树图的概念和性质8/2
15、5/202413课件7.2.2最小支撑树的求法最小支撑树的求法避圈法避圈法任选任选vi,使使viV,其余点在其余点在中中从从V与与的连线中找一条最小边的连线中找一条最小边,使其包含在最小支撑树内使其包含在最小支撑树内所有点均在所有点均在V中中?结束结束是是否否ABCDEF872594631【例例7.4】求下图最小支撑树求下图最小支撑树W(T*)=178/25/202414课件7.2.2最小支撑树的求法最小支撑树的求法破圈法破圈法任取一个圈任取一个圈,从圈中去掉一条最大的边从圈中去掉一条最大的边(如果有两条或两如果有两条或两条以上的边都是权最大的边条以上的边都是权最大的边,则任意去掉其中一条则任
16、意去掉其中一条).在余在余下的图中重复这个步骤下的图中重复这个步骤,直到不含圈的图为止直到不含圈的图为止,此时的图此时的图便是最小树便是最小树.ABDEF82594631C743n取回路取回路ABC，去掉最大边，去掉最大边A,B；n取回路取回路BCE，去掉最大边，去掉最大边B,E；n取回路取回路BCED，去掉最大边，去掉最大边D,E；n取回路取回路BCEFD，去掉最大边，去掉最大边B,DnW(T*)=178/25/202415课件案例案例7-1印第安那州公路规划问题印第安那州公路规划问题(1)(2)(3)(4)(5)(1)Gary(1)Gary(2)Fort Wayne(2)Fort Wayn
17、e(3)Evansvile(3)Evansvile(4)Terre Haute(4)Terre Haute(5)South (5)South HendHend13213221721716416458581321322902017921721729011330316416420111319658587979303196因政治原因不能建造连接因政治原因不能建造连接(1)和和(2)的公路以及连接的公路以及连接(3)和和(5)的公路的公路.如如何建造可使总施工长度最短何建造可使总施工长度最短?123452171645829020179196113W(T*)=414WinQSB演示演示Excel演示演示
18、Lingo演示演示8/25/202416课件7.3.1求两点间最短路的求两点间最短路的Dijkstra标号算法标号算法2444633223322ABCTDEFS02356789结论：最短路径SADT，或SCFT；最短路长：9【例例7.6】8/25/202417课件7.3.1求两点间最短路的求两点间最短路的Dijkstra标号算法标号算法【例例7.7】 用用Dijkstra方法求点方法求点S到点到点T的最短路及路的最短路及路长。056813最短路线最短路线:SACT或或:SAT最短路长最短路长:13(1)给给S标号标号0(2)V=S,补集补集CV=A,B,C,T,minLSS+DSB,LSS+D
19、SA=0+5,0+6=5给给B标号标号5,S,B加粗加粗(2)V=S,B,CV=A,C,T,minLSS+DSA,LSB+DBC=0+6,5+8=6给给A标号标号6,S,A加粗加粗(3)V=S,B,A,CV=C,T,minLSA+DAC,LSA+DAT,LSB+DBC=6+2,6+7,5+6=8给给C标号标号8,A,C加粗加粗(3)V=S,B,A,C,CV=T,minLSA+DAT,LSC+DCT=6+7,8+5=13给给T标号标号13,A,C或或A,T加粗加粗WinQSB演示演示Excel演示演示Lingo演示演示8/25/202418课件7.3.3求网络各点之间最短路的矩阵计算法求网络各点
20、之间最短路的矩阵计算法*【例例7.9】求各点间最短路矩阵求各点间最短路矩阵解解(1)构造邻接矩阵构造邻接矩阵(2)计算经过计算经过1个中间点的可达矩阵个中间点的可达矩阵一般地一般地(3)利用递推公式计算经过利用递推公式计算经过1个中间点的个中间点的可达矩阵可达矩阵自编软件自编软件ExcelORM所见即所得所见即所得.8/25/202419课件案例案例7-2设备更新问题设备更新问题设备在各年年初的价格在各年年初的价格第1年第2年第3年第4年第5年1012131415使用不同使用不同时间（年）的（年）的设备所需要的所需要的维修修费用用使用年数0-11-22-33-44-5维修费用4691219v1
21、v2v3v4v5v6202941602231432332241416171819求费用最小的设备更新计划求费用最小的设备更新计划.Dijkstra标号算法：标号算法：先给先给v1标号标号“0”给给v2标号标号“14”给给v3标号标号“20”014给给v4标号标号“29”给给v5标号标号“41”给给v6标号标号“52”202941最优路线：最优路线：V1V3V6即第即第1年初购置，第年初购置，第3年初更新，第年初更新，第5年末结束。总费用：年末结束。总费用：52528/25/202420课件7.4中国邮递员问题中国邮递员问题n抽象为图的语言，就是给定一个连通图，在每边上赋予一个非负的权，抽象为图
22、的语言，就是给定一个连通图，在每边上赋予一个非负的权，要求一个圈，过每边至少一次，并使圈的总权最小。要求一个圈，过每边至少一次，并使圈的总权最小。我国管梅谷教授我国管梅谷教授在在1962年首先提出的，因此在国际上通称为中国邮递员问题。年首先提出的，因此在国际上通称为中国邮递员问题。n结论结论1：若网络图上的所有点均为偶点，则邮递员可以走遍所有街道，：若网络图上的所有点均为偶点，则邮递员可以走遍所有街道，做到每条街道只走一次而不重复。做到每条街道只走一次而不重复。n结论结论2：最短的投递路线具有这样的性质：最短的投递路线具有这样的性质：有奇点连线的边最多重有奇点连线的边最多重复一次；复一次；在该
23、网络图的每个回路上，有重复的边的长度不超过回路在该网络图的每个回路上，有重复的边的长度不超过回路总长的一半。总长的一半。【例7.10】解解(1)找出奇点找出奇点(4个个)(2)连接不超过回路长一连接不超过回路长一半的边组成两对半的边组成两对(虚线虚线)(3)虚线重复一次虚线重复一次,其余其余边只走一次边只走一次(有多种走法有多种走法)8/25/202421课件案例案例7-3货场巡视路线货场巡视路线解解(1)找出奇点找出奇点(6个个)(2)连接不超过回路长一半的边组成两对连接不超过回路长一半的边组成两对(虚线虚线)(3)虚线重复一次虚线重复一次,其余边只走一次其余边只走一次(有多种走法有多种走法
24、)8/25/202422课件7.5网络最大流问题网络最大流问题8/25/202423课件7.5.1基本概念基本概念n1. 容量网络、弧的容量与流量容量网络、弧的容量与流量n容量网络是指对网络上的每条弧都给定一个最大通过能力。容量网络是指对网络上的每条弧都给定一个最大通过能力。n从从vi到到vj的最大通过能力，记为的最大通过能力，记为c(vi,vj)或或cij，称为弧，称为弧vi,vj的容量。的容量。n在容量网络中规定一个发点在容量网络中规定一个发点s和一个收点和一个收点t,其余点称为中间点。其余点称为中间点。n在网络中给弧加载的负载量称为弧的流量，记为在网络中给弧加载的负载量称为弧的流量，记为
25、f(vi,vj)或或fij。n网络的最大流是指网络中从发点网络的最大流是指网络中从发点s到收点到收点t之间允许通过的最大流量。之间允许通过的最大流量。下图为引例的最大流，下图为引例的最大流，v1为发点，为发点，v7为收点，其他为中间点，图中各为收点，其他为中间点，图中各弧旁边的数字表示为弧旁边的数字表示为“容量容量(流量流量)”。8/25/202424课件7.5.1基本概念基本概念8/25/202425课件7.5.1基本概念基本概念8/25/202426课件7.5.1基本概念基本概念8/25/202427课件7.5.2最大流问题最大流问题Ford-Fulkerson标号算法标号算法8/25/2
26、02428课件7.5.2最大流问题最大流问题Ford-Fulkerson标号算法标号算法【例例7.12】 用用标号法求网号法求网络的最大流。的最大流。解解 给给v1标号（标号（0，+）v1,v3非饱和弧，给非饱和弧，给v3标号，标号值标号，标号值min+ ,9-5=4，即，即v3标号（标号（v1,4）v3,v6非饱和弧，给非饱和弧，给v6标号，标号值标号，标号值min4 ,5-0=4，即，即v6标号（标号（v3,4）v6,v7非饱和弧，给非饱和弧，给v7标号，标号值标号，标号值min4 ,10-3=4，即，即v7标号（标号（v6,4）逆向追踪找到增广链逆向追踪找到增广链v1v3v6v7,最大可
27、调整流量最大可调整流量(t)=4增广链上所有的弧均为前向弧，流量增广链上所有的弧均为前向弧，流量+4。8/25/202429课件案例案例7-4航空公司的最大流量航空公司的最大流量3(0)2(0)1(0)3(0)2(0)洛杉矶JSDeDL朱诺西雅图丹佛达拉斯解解 先绘制容量网络图先绘制容量网络图 再再用用Ford-Fulkerson标号算法标号算法3(2)2(2)3(2)(J,1)(S,1)(L,1)1(1)2(1)3(3)最小割最小割8/25/202430课件7.6.1最小费用流的数学模型最小费用流的数学模型8/25/202431课件7.6.2最小费用最大流的标号算法最小费用最大流的标号算法8
28、/25/202432课件7.6.2最小费用最大流的标号算法最小费用最大流的标号算法承承【例例7.15】，用标号算法求从节点，用标号算法求从节点1到节点到节点5的最小费用最大流。的最小费用最大流。解解 赋初始流赋初始流0流流,构造容量网络构造容量网络由费用构造加权网络由费用构造加权网络(零流弧以零流弧以bij加权加权,饱和弧构造反向弧以饱和弧构造反向弧以-bij反向加权反向加权,非饱非饱和且非零流以和且非零流以bij和和-bij双向加权双向加权).并求并求最短路即增广链最短路即增广链.在增广链上调整流量在增广链上调整流量8/25/202433课件案例案例7-5货物配送问题货物配送问题三个供应商运
29、往每个仓库最大运输量为三个供应商运往每个仓库最大运输量为6;两个仓库运往每个工厂的最大运输量为两个仓库运往每个工厂的最大运输量为6;单位费用单位费用=商品价格商品价格+单位运价单位运价;仓库到工厂的运输单价为已知数仓库到工厂的运输单价为已知数;700200500400v1v3v4v2v5v6v7供应商供应商 仓库仓库 工厂工厂(6,)(6,)(6,)(6,)(6,)(6,)234402296023000232002315023200(6,)(6,)(6,)(6,)供应商供应商商品价格商品价格单位运价单位运价仓库仓库1仓库仓库2123225002270022300300+4运送路程运送路程200
30、+5运送路程运送路程500+2运送路程运送路程300+4160=940200+550=450500+2200=900300+440=460200+560=500500+2100=700设设fij表示从节点表示从节点i到到j的流量的流量,则有则有:fij=6;目标总费用最小目标总费用最小:min=bijfij;供应能力限制供应能力限制:f14+f15=10; f24+f25=10;f34+f35=10;工厂需求限制工厂需求限制:f46+f56=10; f47+f57=6;中间点平衡中间点平衡:f14+f24+f34=f46+f47; f15+f25+f35=f56+f57;8/25/202434
31、课件案例案例7-5货物配送问题货物配送问题有如下有如下Lingo模型：模型：min=23440*f14+22960*f15+23150*f24+23200*f25+23200*f34+23000*f35+200*f46+700*f47+400*f56+500*f57; !总费用最小总费用最小;f14+f15=10; !产大于销，运出货物不超过各供货商供应能力产大于销，运出货物不超过各供货商供应能力;f24+f25=10;f34+f35=10;f46+f56=10; !运达货物等于工厂需求运达货物等于工厂需求;f47+f57=6;f14+f24+f34=f46+f47; !中间点平衡中间点平衡;
32、f15+f25+f35=f56+f57;f14=6;f15=6;f24=6;f25=6;f34=6;f35=6;f46=6;f47=6;f56=6;f57=6; !运量限制运量限制;Lingo模型运行结果模型运行结果Objective value: 374460.0Total solver iterations: 2 Variable Value Variable Value F15 6.000000 F46 6.000000 F24 6.000000 F56 4.000000 F35 4.000000 F57 6.000000 8/25/202435课件本章小结本章小结8/25/202436课件
