图论和网络分析算法及Matlab实现GraphandNetworkAnalysis.pptx

《图论和网络分析算法及Matlab实现GraphandNetworkAnalysis.pptx》由会员分享，可在线阅读，更多相关《图论和网络分析算法及Matlab实现GraphandNetworkAnalysis.pptx（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/15涉及网络优化的数学建模问题涉及网络优化的数学建模问题1、最短路问题货柜车货柜车司机司机奉命在最短的时间内将一车货物奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网从甲地运往乙地。从甲地到乙地的公路网纵纵横交错横交错，因此有多种行车路线，这名司机应，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条恒定的，那么这一问题相当于需要找到一条从甲地到乙地的从甲地到乙地的最短路最短路。第1页/共74页2023/3/152 2、最小支撑树问题最小支撑树问题某一地区有若干个主要城市

2、，现准备修建高速公某一地区有若干个主要城市，现准备修建高速公路把这些路把这些城市连接城市连接起来，使得从其中任何一个城起来，使得从其中任何一个城市都可以经高速公路市都可以经高速公路直接或间接直接或间接到达另一个城市。到达另一个城市。假定已经知道了任意两个城市之间修建假定已经知道了任意两个城市之间修建高速公路高速公路成本成本，那么应如何决定在哪些城市间修建高速公，那么应如何决定在哪些城市间修建高速公路，使得路，使得总成本最小总成本最小？第2页/共74页2023/3/153 3、指派问题指派问题Assignment problemAssignment problem 一一家家公公司司经经理理安安排

3、排N N名名员员工工去去完完成成N N项项任任务务，每每人人一一项项。由由于于各各员员工工的的特特点点不不同同，不不同同的的员员工工去去完完成成同同一一项项任任务务时时所所获获得得的的回回报报不不同同。如如何何分分配配工作方案可以使总工作方案可以使总回报最大回报最大？第3页/共74页2023/3/154 4、中国邮递员问题、中国邮递员问题Chinese postman problemChinese postman problem一名一名邮递员邮递员负责投递某个街区的邮件。如何为负责投递某个街区的邮件。如何为他（她）设计一条最短的他（她）设计一条最短的投递路线投递路线（从邮局出（从邮局出发，经过

4、投递区内每条发，经过投递区内每条街道至少一次街道至少一次，最后返，最后返回邮局）？回邮局）？我国管梅谷教授我国管梅谷教授1960年首先提出，年首先提出，国际上称之为中国邮递员问题。国际上称之为中国邮递员问题。第4页/共74页2023/3/155 5、旅行商问题、旅行商问题Traveling salesman problemTraveling salesman problem一一名名推推销销员员准准备备前前往往若若干干城城市市推推销销产产品品。如如何何为为他他设设计计一一条条最最短短的的旅旅行行路路线线？（从从驻驻地地出出发发，经经过过每每个个城城市市恰好一次，最后返回驻地）恰好一次，最后返回驻

5、地）第5页/共74页2023/3/156 6、运输问题、运输问题Transportation problemTransportation problem 某某种种原原材材料料有有 M M个个产产地地，现现在在需需要要将将原原材材料料从从产产地地运运往往 N N个个使使用用这这些些原原材材料料的的工工厂厂。假假定定 M M个个产产地地的的产产量量和和 N N家家工工厂厂的的需需要要量量已已知知，单单位位产产品品从从任任一一产产地地到到任任一一工工厂厂的的运运费费已已知知，那那么么如如何何安安排排运输方案可以使总运输方案可以使总运输成本运输成本最低？最低？第6页/共74页2023/3/15问题的两

6、个共同特点问题的两个共同特点（1 1）目的都是从若干可能的安排或方案中寻求）目的都是从若干可能的安排或方案中寻求 某种意义下的某种意义下的最优安排最优安排或方案，数学问题称或方案，数学问题称 为最优化或为最优化或优化问题优化问题。（2 2）它们都可用）它们都可用图形图形形式直观描述，数学上把这形式直观描述，数学上把这 种与图相关的结构称为种与图相关的结构称为网络网络。图和网络相关图和网络相关 的最优化问题就是的最优化问题就是网络最优化网络最优化。网络优化问题是以网络流为研究的对象，常网络优化问题是以网络流为研究的对象，常 常被称为网络流或常被称为网络流或网络流规划网络流规划等。等。第7页/共7

7、4页 一、图论的基本概念1.图与子图e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如 G：简单图：无自环、无重边的图。第8页/共74页2023/3/15|V|=n表示图G中节点个数为n，此节点个数n也称为图G的阶|E|=m表示图G中边的个数为m任一顶点相关联的边的数目称为该顶点的度完全图：任意两点有边相连，用 表示 完全图的边，和每点的度是多少？第9页/共74页2.关联与相邻第10页/共74页第11页/共74页3.链与圈第12页/共74页4.有向图与无向图，圈，回路比较：第13页/共74页v1v2v3v5v4834217第14页/共74页第15页/共74

8、页5.树 例1 已知有5个城市，要在它们之间架设电话线网，要求任2城市都可通话（允许通过其它城市），并且电话线的根数最少。v1v2v3v5v4 特点：连通、无圈。树无圈的连通图，记为T。第16页/共74页v1v2v3v5v4树的性质：（1）树的任2点间有且仅有1链；（2）在树中任去掉1边，则不连通；（3）在树中不相邻2点间添1边，恰成1圈；（4）若树T有n个顶点，则T有n-1条边。第17页/共74页6.图的支撑树 若图G=（V，E）的子图T=（V，E）是树，则称T为G的支撑树。特点边少、点不少。性质：G连通，则G必有支撑树。证：破圈、保连通。第18页/共74页二、网络分析二、网络分析网络赋权图

9、，记D=（V，E，C），其中C=c1，cn，ci为边ei上的权（设ci ）。网络分析主要内容:最小支撑树 最短路 最大流。第19页/共74页一.最小支撑树问题问题：求网络D的支撑树，使其权和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例 2 求如图网络的最小支撑树。v5v1v3v6v4v2v7255233575711Kruskal,J.B.(1956).On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.Proceedings of the American

10、 Mathematical Society 7,48-50.第20页/共74页避圈法是一种选边的过程，其步骤如下：1.从网络D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中第21页/共74页2023/3/15对G中各边按权大小顺序排列，不妨设为W1W2Wm填写Wj对应的各边ajS=，i=0，j=1ajS构成回路？|S|=n-1=n-1ei+1=ajS=ei+1Si=i+1j=j+1j=j+1T*=S打印T*ENDYYNN第22页/共74页用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分树如图上红

11、线所示；最小权和为14。思考：破圈法是怎样做的呢？见圈就破，去掉其中权最大的。第23页/共74页最小支撑树问题的应用例子 已知有A、B、C、D、E、F六个城镇间的道路网络 如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。求能保证各城镇均能通话且总架设费用最少的架设方案。6EACBFD5109353978284第24页/共74页二.最短路问题1.问题：求网络D中一定点v1到其它点的最短路。例3 求如图网络中v1至v7的最短路，图中数字为两点间距离。v5v1v3v6v4v2v7255233575711第25页/共74页2023/3/152.方法：Dijkstra算法（

12、Dijkstra，1959）Dijkstra,E.W.(1959).A note on two problems in connexion with graphs.Numerische Mathematik 1,269271.原理：Bellman最优化原理 若P是网络G中从Vs到Vt的一条最短路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条路P1亦必是Vs到Vl的最短路。证明（反证）：若P1不是从Vs到Vl的最短路，则存在另一条 Vs到Vl的路P2使W(P2)W(P1)，若记路P中从Vl到Vt的路为P3。则有W(P2)+W(P3)300 300米米)对坡度对坡度的限制的限

13、制0.125=00.100第61页/共74页2023/3/15模型计算方法模型计算方法 (1)(1)对地图网格加密，形成图。对地图网格加密，形成图。(2)(2)计算网格的距离，用费用作为计算网格的距离，用费用作为权值。权值。(3)(3)求赋权图两点间的最短距离。求赋权图两点间的最短距离。第62页/共74页2023/3/15参考答案参考答案第63页/共74页2023/3/1519981998年全国大学生数学建模竞赛年全国大学生数学建模竞赛 灾情巡视路线，下图为某县的乡（镇）、灾情巡视路线，下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段村公路网示意图，公路边的数字为该路段的公里数。今年

14、夏天该县遭受水灾。为考的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路乡（镇）、村，又回到县政府所在地的路线。线。第64页/共74页2023/3/151.若分三组（路）巡视，试设计总路程最短且各组尽可若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。能均衡的巡视路线。2.假定巡视人员在各乡（镇）停留时间假定巡视人员在各乡（镇）停留时间T=2

15、T=2小时，在各小时，在各村停留时间村停留时间t=1t=1小时，汽车行驶速度小时，汽车行驶速度V=35V=35公里公里/小时。小时。要在要在2424小时内完成巡视，至少应分几组；给出这种分小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。组下你认为最佳的巡视路线。3.若巡视组数已定若巡视组数已定(如三组如三组)，要求尽快完成巡视，讨论，要求尽快完成巡视，讨论T，t和和V改变对最佳巡视路线的影响。改变对最佳巡视路线的影响。4.上述关于上述关于T,t和和V的假定下，如果巡视人员足够多，的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完完成巡视的最短时间是多

16、少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。成巡视的要求下，你认为最佳的巡视路线。第65页/共74页2023/3/15乡村分布图乡村分布图第66页/共74页2023/3/15点的行遍性问题点的行遍性问题1 1、图论、图论-哈密尔顿问题（是否存在经过所有点一次的圈）哈密尔顿问题（是否存在经过所有点一次的圈）2 2、组合优化、组合优化-旅行商问题（赋权图经过所有顶点至少一次）旅行商问题（赋权图经过所有顶点至少一次）非完全图的多旅行商问题非完全图的多旅行商问题v两点间的最短路长度作为两点间的权，构造完全图。两点间的最短路长度作为两点间的权，构造完全图。v两边权之和不小于第三边的权两

17、边权之和不小于第三边的权=v完全图的最优哈密尔顿圈完全图的最优哈密尔顿圈=原图的最优旅行商问题。原图的最优旅行商问题。v完全图完全图-增广完全图增广完全图=求最优哈密尔顿圈求最优哈密尔顿圈v近似算法或分组后直接搜索近似算法或分组后直接搜索v注意（1 1）两点间的最短路长度可用DijkstraDijkstra算法（2 2）多旅行商问题=最优哈密尔顿圈第67页/共74页2023/3/15线性规划模型线性规划模型第68页/共74页2023/3/15问题解答：问题解答：1 1、分三组（路）巡视，试设计总路程最短且分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。各组尽可能均衡的巡视路线。目

18、标函数：目标函数：min(C1+C2+C3)min(C1+C2+C3)限制条件：限制条件：min(C3-C1)min(C3-C1)或或 者者 ：min(C1)min(C1)2、假定巡视人员在各乡（镇）停留时间假定巡视人员在各乡（镇）停留时间T=2T=2小时，小时，在各村停留时间在各村停留时间t=1t=1小时，汽车行驶速度小时，汽车行驶速度V=35V=35公里公里/小时。要在小时。要在2424小时内完成巡视，至少应分几组；小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线给出这种分组下最佳的巡视路线。第69页/共74页2023/3/15 目标函数：目标函数：min(H1+H2+H3)mi

19、n(H1+H2+H3)花费时间：花费时间：Hi=2mi+ni+Ci/VHi=2mi+ni+Ci/V 限制条件：限制条件：min(max(Hi)min(max(Hi)总时间总时间6969小时小时=至少至少4 4组，组，4 4组的路线可以找到。组的路线可以找到。3 3、在上述关于在上述关于T,tT,t和和V V的假定下，如果巡视人员足够多，完成的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。下，你认为最佳的巡视路线。单独巡视的最短时间单独巡视的最短时间=最远距离最远距离（1）每组

20、时间不超过最远距离时间）每组时间不超过最远距离时间（2）巡视组足够少，）巡视组足够少，2222组组4 4、若巡视组数已定若巡视组数已定(如三组如三组)，要求尽快完成巡视，讨论，要求尽快完成巡视，讨论T T，t t和和V V改变对最佳巡视路线的影响。改变对最佳巡视路线的影响。讨论花费时间函数：讨论花费时间函数：Hi=2mi+ni+Ci/VHi=2mi+ni+Ci/V注意：多旅行商问题注意：多旅行商问题=单旅行商问题（单旅行商问题（LINGOLINGO）第70页/共74页2023/3/1520052005年全国大学生数学建模竞赛年全国大学生数学建模竞赛DVD在线租赁在线租赁随随着着信信息息时时代代

21、的的到到来来，网网络络成成为为人人们们生生活活中中越越来来越越不不可可或或缺缺的的元元素素之之一一。许许多多网网站站利利用用其其强强大大的的资资源源和和知知名名度度，面面向向其其会会员员群群提提供供日日益益专专业业化化和和便便捷捷化化的的服服务务。例例如如，音音像像制制品品的的在在线线租租赁赁就就是是一一种种可可行行的的服服务务。这这项项服服务务充充分分发发挥挥了了网网络络的的诸诸多多优优势势，包包括括传传播播范范围围广广泛泛、直直达达核核心心消消费费群群、强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。考考虑

22、虑如如下下的的在在线线DVD租租赁赁问问题题。顾顾客客缴缴纳纳一一定定数数量量的的月月费费成成为为会会员员，订订购购DVD租租赁赁服服务务。会会员员对对哪哪些些DVD有有兴兴趣趣，只只要要在在线线提提交交订订单单，网网站站就就会会通通过过快快递递的的方方式式尽尽可可能能满满足足要要求求。会会员员提提交交的的订订单单包包括括多多张张DVD，这这些些DVD是是基基于于其其偏偏爱爱程程度度排排序序的的。网网站站会会根根据据手手头头现现有有的的DVD数数量量和和会会员员的的订订单单进进行行分分发发。每每个个会会员员每每个个月月租租赁赁次次数数不不得得超超过过2次次，每每次次获获得得3张张DVD。会会员

23、员看看完完3张张DVD之之后后，只只需需要要将将DVD放放进进网网站站提提供供的的信信封封里里寄寄回回（邮邮费费由由网网站站承承担担），就就可可以以继继续续下下次次租租赁。请考虑以下问题：赁。请考虑以下问题：第71页/共74页2023/3/151)1)网网站站正正准准备备购购买买一一些些新新的的DVD，通通过过问问卷卷调调查查1000个个会会员员，得得到到了了愿愿意意观观看看这这些些DVD的的人人数数（表表1给给出出了了其其中中5种种DVD的的数数据据）。此此外外，历历史史数数据据显显示示，60%的的会会员员每每月月租租赁赁DVD两两次次，而而另另外外的的40%只只租租一一次次。假假设设网网站

24、站现现有有10万万个个会会员员，对对表表1中中的的每每种种DVD来来说说，应应该该至至少少准准备备多多少少张张，才才能能保保证证希希望望看看到到该该DVD的的会会员员中中至至少少50%在在一一个个月月内内能能够够看看到到该该DVD？如如果果要要求求保保证证在在三三个个月月内内至少至少95%的会员能够看到该的会员能够看到该DVD呢？呢？2）表表2中中列列出出了了网网站站手手上上100种种DVD的的现现有有张张数数和和当当前前需需要要处处理理的的1000位位会会员员的的在在线线订订单单（表表2的的数数据据格格式式示示例例如如下下表表2，具具体体数数据据请请下下），如如何何对对这这些些DVD进进行行

25、分分配配，才才能能使使会会员员获获得得最最大大的的满满意意度度？请请具具体体列列出出前前30位位会会员员（即即C0001C0030）分别获得哪些分别获得哪些DVD。3）继继续续考考虑虑表表2，并并假假设设表表2中中DVD的的现现有有数数量量全全部部为为0。如如果果你你是是网网站站经经营营管管理理人人员员，你你如如何何决决定定每每种种DVD的的购购买买量量，以以及及如如何何对对这这些些DVD进进行行分分配配，才才能能使一个月内使一个月内95%的会员得到他想看的的会员得到他想看的DVD，并且满意度最大？并且满意度最大？如果你是网站经营管理人员，你觉得在如果你是网站经营管理人员，你觉得在DVD的需求预测、购买和分配中还有哪的需求预测、购买和分配中还有哪些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。第72页/共74页2023/3/15第73页/共74页2023/3/15谢谢您的观看！第74页/共74页