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

第7章图与网络模型2/6/20231课件教学目标与要求【教学目标】通过对本章的学习，理解图的基本概念；掌握最小支撑树、最短路、最大流、中国邮路问题的求法；会利用相关模型解决合理组织人力、物力、财力的优化问题。【知识结构】2/6/20232课件导入案例——七桥问题18世纪德国哥尼斯堡如图（a）七座桥，能否不重复一次走完并回到出发地？（a）七桥问题示意图（b）七桥问题简单图1736年，欧拉在圣彼得堡科学院作了一次学术报告。在报告中，他证明了鉴别任一图形能否一笔画出的准则，即欧拉定理。2/6/20233课件导入案例运筹学中把一些研究对象用节点表示，对象之间的关系用连线边表示。用点、边的集合构成图。图论是研究有节点和边所组成图形的数学理论和方法。图是网络分析的基础，根据具体研究的网络对象（如：铁路网、电力网、通信网等），赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点，中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。图论广泛地应用于物理学、化学、信息论、科学管理、电子计算机等各个领域。如在管理中网络合理架设、网络承载能力分析、服务设施布点、匹配问题等。2/6/20235课件本章主要内容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货物配送问题本章小结2/6/20236课件7.1.1图的若干示例【例7.1】

有A、B、C、D、E5个球队，已比赛过，就在这两队相应的点之间连一条线.

[P1]【例7.2】8种化学药品，不能存放在同一个库房里的用连线表示。【例7.3】若在五支球队比赛中，甲胜乙表示为“甲→乙”，则右图表明A三胜一负，B和E一胜一负，C和D一胜两负。2/6/20237课件7.1.2图的基本概念次，奇点，偶点，孤立点，悬挂点，悬挂边点的关联边的数目称为的次(也称度或线度)，记为d(v)(环在计算时算作两次，称为入次和出次)；次为奇数的点称为奇点；次为偶数的点称为偶点；次为0的点称为孤立点；次为1的点称为悬挂点；与悬挂点相边关联的边称为悬挂边。【定理7.1】图中，所有顶点的次之和是边数的2倍。【定理7.2】任一个图中，奇点的个数为偶数。链，圈，路，回路，连通图点和边的交错序列中，若边各不相同称为链；封闭的链称为圈；在链中如果点也各不相同称为路；起点与终点重合的路称为回路；任意两点之间至少能找到一条链的图称为连通图。图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)2/6/20239课件7.1.2图的基本概念图7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图7.5(b)完全图，子图，支撑图（部分图）一个简单图中若任意两点之间均有边相连，称这样的图为完全图，如图7.5(b)；图

如果满足的子图；如果满足的一个支撑图（或称为部分图）。如图7.6(b)是图(a)的子图，并不是支撑图，图(c)是图(a)的支撑图。2/6/202310课件承【例7-2】这是一个染色问题,其方法:找出次数最大的点,将其与不相邻的点组成新的点集;再从其余的子图中找出次数最大的点,将其与不相邻的点组成新的点集,直到子图的点集为空.v1v8v2v7v3v6v5v4{,}{,}{,,}{}7.1.2图的基本概念至少需要3个库房2/6/202311课件7.2.1树图的概念和性质2/6/202313课件7.2.2最小支撑树的求法——避圈法任选vi,使vi∈V,

其余点在中从V与的连线中找一条最小边,

使其包含在最小支撑树内所有点均在V中?结束是否ABCDEF872594631【例7.4】求下图最小支撑树W(T*)=172/6/202314课件7.2.2最小支撑树的求法——破圈法任取一个圈,从圈中去掉一条最大的边(如果有两条或两条以上的边都是权最大的边,则任意去掉其中一条).在余下的图中重复这个步骤,直到不含圈的图为止,此时的图便是最小树.ABDEF82594631C743取回路ABC，去掉最大边[A,B]；取回路BCE，去掉最大边[B,E]；取回路BCED，去掉最大边[D,E]；取回路BCEFD，去掉最大边[B,D]W(T*)=172/6/202315课件7.3.1求两点间最短路的Dijkstra标号算法2444633223322ABCTDEFS02356789结论：最短路径SADT，或SCFT；最短路长：9

【例7.6】2/6/202317课件7.3.1求两点间最短路的Dijkstra标号算法【例7.7】用Dijkstra方法求点S到点T的最短路及路长。056813最短路线:SACT

或:SAT最短路长: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演示2/6/202318课件7.3.3求网络各点之间最短路的矩阵计算法*【例7.9】求各点间最短路矩阵解(1)构造邻接矩阵(2)计算经过1个中间点的可达矩阵一般地(3)利用递推公式计算经过1个中间点的可达矩阵自编软件ExcelORM所见即所得.2/6/202319课件7.4中国邮递员问题抽象为图的语言，就是给定一个连通图，在每边上赋予一个非负的权，要求一个圈，过每边至少一次，并使圈的总权最小。我国管梅谷教授在1962年首先提出的，因此在国际上通称为中国邮递员问题。结论1：若网络图上的所有点均为偶点，则邮递员可以走遍所有街道，做到每条街道只走一次而不重复。结论2：最短的投递路线具有这样的性质：①有奇点连线的边最多重复一次；②在该网络图的每个回路上，有重复的边的长度不超过回路总长的一半。【例7.10】

解(1)找出奇点(4个)(2)连接不超过回路长一半的边组成两对(虚线)(3)虚线重复一次,其余边只走一次(有多种走法)2/6/202321课件案例7-3货场巡视路线解(1)找出奇点(6个)(2)连接不超过回路长一半的边组成两对(虚线)(3)虚线重复一次,其余边只走一次(有多种走法)2/6/202322课件7.5网络最大流问题2/6/202323课件7.5.1基本概念2/6/202325课件7.5.1基本概念2/6/202326课件7.5.2最大流问题Ford-Fulkerson标号算法【例7.12】用标号法求网络的最大流。解给v1标号（0，+∞）[v1,v3]非饱和弧，给v3标号，标号值min{+∞,9-5}=4，即v3标号（v1,4）[v3,v6]非饱和弧，给v6标号，标号值min{4,5-0}=4，即v6标号（v3,4）[v6,v7]非饱和弧，给v7标号，标号值min{4,10-3}=4，即v7标号（v6,4）逆向追踪找到增广链v1v3v6v7,最大可调整流量ε(t)=4增广链上所有的弧均为前向弧，流量+4。2/6/202329课件案例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)最小割2/6/202330课件7.6.1最小费用流的数学模型2/6/202331课件7.6.2最小费用最大流的标号算法2/6/202332课件7.6.2最小费用最大流的标号算法承【例7.15】，用标号算法求从节点1到节点5的最小费用最大流。解赋初始流0流,构造容量网络由费用构造加权网络(零流弧以bij加权,饱和弧构造反向弧以-bij反向加权,非饱和且非零流以bij和-bij双向加权).并求最短路即增广链.在增广链上调整流量2/6/202333课件案例7-5货物配送问题三个供应商运往每个仓库最大运输量为6;两个仓库运往每个工厂的最大运输量为6;单位费用=商品价格+单位运价;仓库到工厂的运输单价为已知数;700200500400v1v3v4v2v5v6v7供应商仓库工厂(6,)(6,)(6,)(6,)(6,)(6,)234402296023000232002315023200(6,)(6,)(6,)(6,)供应商商品价格单位运价仓库1仓库2123225002270022300300+4×运送路程200+5×运送路程500+2×运送路程300+4×160=940200+5×50=450500+2×200=900300+4×40=460200+5×60=500500+2×100=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;2/6/202334课件案例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