运筹学课件第7章图与网络模型.ppt
第7章 图与网络模型,重庆三峡学院 关文忠http:/,管理运筹学课件,2023/8/27,教学目标与要求,【教学目标】通过对本章的学习，理解图的基本概念；掌握最小支撑树、最短路、最大流、中国邮路问题的求法；会利用相关模型解决合理组织人力、物力、财力的优化问题。【知识结构】,管理运筹学课件,2023/8/27,导入案例七桥问题,18世纪德国哥尼斯堡如图（a）七座桥，能否不重复一次走完并回到出发地？,（a）七桥问题示意图,（b）七桥问题简单图,1736年，欧拉在圣彼得堡科学院作了一次学术报告。在报告中，他证明了鉴别任一图形能否一笔画出的准则，即欧拉定理。,管理运筹学课件,2023/8/27,导入案例四色问题,“任何一张地图只用四种颜色就能使有共同边界的国家着上不同的颜色。”1852年，英国搞地图着色工作的格思里，首先提出了四色问题。1872年，英国数学家凯利正式向伦敦数学学会提出这个问题，于是四色猜想成了世界数学界关注的问题。美国数学教授哈肯和阿佩尔于1976年6月,使用伊利诺斯大学的电子计算机计算了1200个小时，作了100亿个判断，终于完成了四色定理的证明。不过不少数学家认为应该有一种简捷明快的书面证明方法。,各省用点表示,有边界接壤的用连线表示,则:,这张地图有几种颜色?能区分各省的边界吗?,管理运筹学课件,2023/8/27,导入案例,运筹学中把一些研究对象用节点表示，对象之间的关系用连线边表示。用点、边的集合构成图。图论是研究有节点和边所组成图形的数学理论和方法。图是网络分析的基础，根据具体研究的网络对象（如：铁路网、电力网、通信网等），赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点，中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。图论广泛地应用于物理学、化学、信息论、科学管理、电子计算机等各个领域。如在管理中网络合理架设、网络承载能力分析、服务设施布点、匹配问题等。,管理运筹学课件,2023/8/27,本章主要内容,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.2 Ford-Fulkerson标号算法案例7-4 航空公司的最大流量7.6 最小费用流问题*7.6.1 最小费用流的数学模型7.6.2 最小费用最大流的标号算法案例7-5 货物配送问题本章小结,管理运筹学课件,2023/8/27,7.1.1 图的若干示例,【例7.1】有A、B、C、D、E5个球队，已比赛过，就在这两队相应的点之间连一条线.,P1,【例7.2】8种化学药品，不能存放在同一个库房里的用连线表示。,【例7.3】若在五支球队比赛中，甲胜乙表示为“甲乙”，则右图表明A三胜一负，B和E一胜一负，C和D一胜两负。,管理运筹学课件,2023/8/27,7.1.2 图的基本概念,图（Graph）由点（Vertex）和点之间的连线所构成的集合。不带箭头的连线称为边（Edge）；带前头的连线称为弧（Arc）。点和边的集合称为无向图（Undirected graph），如图7.5(a)，简称图，用G=V，E表示；点和弧的集合称为有向图（Directed graph），如图7.5(b)，用D=V，A表示。有向图去掉箭头所形成的无向图称为该有向图的基础图（underlying graph）。端点，关联边，相邻 若边 e=u,vE，则称 u,v是e 的端点，称e 是点u或v的关联边。有公共关联边的点称为点相邻；公共端点的边称为边相邻。环，多重边，简单图，多重图 两个端点重合的边称为环；若两个点之间有多于一条的边，称为多重边；一个无环、无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。,管理运筹学课件,2023/8/27,7.1.2 图的基本概念,次，奇点，偶点，孤立点，悬挂点，悬挂边 点的关联边的数目称为的次(也称度或线度)，记为d(v)(环在计算时算作两次，称为入次和出次)；次为奇数的点称为奇点；次为偶数的点称为偶点；次为0的点称为孤立点；次为1的点称为悬挂点；与悬挂点相边关联的边称为悬挂边。【定理7.1】图中，所有顶点的次之和是边数的2倍。【定理7.2】任一个图中，奇点的个数为偶数。链，圈，路，回路，连通图 点和边的交错序列中，若边各不相同称为链；封闭的链称为圈；在链中如果点也各不相同称为路；起点与终点重合的路称为回路；任意两点之间至少能找到一条链的图称为连通图。,管理运筹学课件,2023/8/27,7.1.2 图的基本概念,完全图，子图，支撑图（部分图）一个简单图中若任意两点之间均有边相连，称这样的图为完全图，如图7.5(b)；图如果满足 的子图；如果满足 的一个支撑图（或称为部分图）。如图7.6(b)是图(a)的子图，并不是支撑图，图(c)是图(a)的支撑图。,管理运筹学课件,2023/8/27,承【例7-2】这是一个染色问题,其方法:找出次数最大的点,将其与不相邻的点组成新的点集;再从其余的子图中找出次数最大的点,将其与不相邻的点组成新的点集,直到子图的点集为空.,v1,v8,v2,v7,v3,v6,v5,v4,7.1.2 图的基本概念,至少需要3个库房,管理运筹学课件,2023/8/27,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)的一个支撑树。,管理运筹学课件,2023/8/27,7.2.1 树图的概念和性质,管理运筹学课件,2023/8/27,7.2.2 最小支撑树的求法避圈法,任选vi,使viV,其余点在 中,A,B,C,D,E,F,8,7,2,5,9,4,6,3,1,【例7.4】求下图最小支撑树,W(T*)=17,管理运筹学课件,2023/8/27,7.2.2 最小支撑树的求法破圈法,任取一个圈,从圈中去掉一条最大的边(如果有两条或两条以上的边都是权最大的边,则任意去掉其中一条).在余下的图中重复这个步骤,直到不含圈的图为止,此时的图便是最小树.,A,B,D,E,F,2,4,3,1,C,7,4,3,取回路ABC，去掉最大边A,B；取回路BCE，去掉最大边B,E；取回路BCED，去掉最大边D,E；取回路BCEFD，去掉最大边B,DW(T*)=17,管理运筹学课件,2023/8/27,案例7-1 印第安那州公路规划问题,因政治原因不能建造连接(1)和(2)的公路以及连接(3)和(5)的公路.如何建造可使总施工长度最短?,1,2,3,4,5,58,79,113,W(T*)=414WinQSB演示Excel演示Lingo演示,管理运筹学课件,2023/8/27,7.3.1 求两点间最短路的Dijkstra标号算法,2,4,4,4,6,3,3,2,2,3,3,2,2,A,B,C,T,D,E,F,S,0,2,3,5,6,7,8,9,结论：最短路径SADT，或SCFT；最短路长：9,【例7.6】,管理运筹学课件,2023/8/27,7.3.1 求两点间最短路的Dijkstra标号算法,【例7.7】用Dijkstra方法求点S到点T的最短路及路长。,0,5,6,8,13,最短路线:SACT 或:SAT最短路长:13,(1)给S标号0(2)V=S,补集CV=A,B,C,T,minLSS+DSB,LSS+DSA=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演示,管理运筹学课件,2023/8/27,7.3.3 求网络各点之间最短路的矩阵计算法*,【例7.9】求各点间最短路矩阵,解(1)构造邻接矩阵,(2)计算经过1个中间点的可达矩阵,一般地,(3)利用递推公式计算经过1个中间点的可达矩阵,自编软件ExcelORM所见即所得.,管理运筹学课件,2023/8/27,案例7-2 设备更新问题,设备在各年年初的价格,使用不同时间（年）的设备所需要的维修费用,求费用最小的设备更新计划.,Dijkstra标号算法：先给v1标号“0”给v2标号“14”给v3标号“20”,0,14,给v4标号“29”给v5标号“41”给v6标号“52”,20,29,41,最优路线：V1V3V6即第1年初购置，第3年初更新，第5年末结束。总费用：52,52,管理运筹学课件,2023/8/27,7.4 中国邮递员问题,抽象为图的语言，就是给定一个连通图，在每边上赋予一个非负的权，要求一个圈，过每边至少一次，并使圈的总权最小。我国管梅谷教授在1962年首先提出的，因此在国际上通称为中国邮递员问题。结论1：若网络图上的所有点均为偶点，则邮递员可以走遍所有街道，做到每条街道只走一次而不重复。结论2：最短的投递路线具有这样的性质：有奇点连线的边最多重复一次；在该网络图的每个回路上，有重复的边的长度不超过回路总长的一半。,【例7.10】,解(1)找出奇点(4个)(2)连接不超过回路长一半的边组成两对(虚线)(3)虚线重复一次,其余边只走一次(有多种走法),管理运筹学课件,2023/8/27,案例7-3 货场巡视路线,解(1)找出奇点(6个)(2)连接不超过回路长一半的边组成两对(虚线)(3)虚线重复一次,其余边只走一次(有多种走法),管理运筹学课件,2023/8/27,7.5 网络最大流问题,管理运筹学课件,2023/8/27,7.5.1 基本概念,1.容量网络、弧的容量与流量容量网络是指对网络上的每条弧都给定一个最大通过能力。从vi到vj的最大通过能力，记为c(vi,vj)或cij，称为弧vi,vj的容量。在容量网络中规定一个发点s和一个收点t,其余点称为中间点。在网络中给弧加载的负载量称为弧的流量，记为f(vi,vj)或fij。网络的最大流是指网络中从发点s到收点t之间允许通过的最大流量。下图为引例的最大流，v1为发点，v7为收点，其他为中间点，图中各弧旁边的数字表示为“容量(流量)”。,管理运筹学课件,2023/8/27,7.5.1 基本概念,管理运筹学课件,2023/8/27,7.5.1 基本概念,管理运筹学课件,2023/8/27,7.5.1 基本概念,管理运筹学课件,2023/8/27,7.5.2 最大流问题Ford-Fulkerson标号算法,管理运筹学课件,2023/8/27,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,最大可调整流量(t)=4增广链上所有的弧均为前向弧，流量+4。,管理运筹学课件,2023/8/27,案例7-4 航空公司的最大流量,3(0),2(0),1(0),3(0),2(0),洛杉矶,J,S,De,D,L,朱诺 西雅图 丹佛 达拉斯,解 先绘制容量网络图 再用Ford-Fulkerson标号算法,3(2),2(2),3(2),(J,1),(S,1),(L,1),1(1),2(1),3(3),最小割,管理运筹学课件,2023/8/27,7.6.1 最小费用流的数学模型,管理运筹学课件,2023/8/27,7.6.2 最小费用最大流的标号算法,管理运筹学课件,2023/8/27,7.6.2 最小费用最大流的标号算法,承【例7.15】，用标号算法求从节点1到节点5的最小费用最大流。,解 赋初始流0流,构造容量网络,由费用构造加权网络(零流弧以bij加权,饱和弧构造反向弧以-bij反向加权,非饱和且非零流以bij和-bij双向加权).并求最短路即增广链.,在增广链上调整流量,管理运筹学课件,2023/8/27,案例7-5 货物配送问题,三个供应商运往每个仓库最大运输量为6;两个仓库运往每个工厂的最大运输量为6;单位费用=商品价格+单位运价;仓库到工厂的运输单价为已知数;,供应商 仓库 工厂,设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;,管理运筹学课件,2023/8/27,案例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;!中间点平衡;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,管理运筹学课件,2023/8/27,本章小结,
