资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,图论与网络分析,(,Graph Theory and Network Analysis),一、图论的基本概念 二、网络分析算法,三、,Matlab,实现,2024/10/4,涉及网络优化的数学建模问题,1、最短路问题,货柜车,司机,奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网,纵横交错,，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的,最短路,。,2024/10/4,2、,最小支撑树问题,某一地区有若干个主要城市，现准备修建高速公路把这些,城市连接,起来，使得从其中任何一个城市都可以经高速公路,直接或间接,到达另一个城市。假定已经知道了任意两个城市之间修建,高速公路成本,，那么应如何决定在哪些城市间修建高速公路，使得,总成本最小,？,2024/10/4,3、 指派问题,Assignment problem,一家公司经理,安排,N,名员工去完成,N,项任务，每人一项。由于各员工的,特点不同,，不同的员工去完成同一项任务时所获得的,回报不同,。如何分配工作方案可以使总,回报最大,？,2024/10/4,4、中国邮递员问题,Chinese postman problem,一名,邮递员,负责投递某个街区的邮件。如何为他（她）设计一条最短的,投递路线,（从邮局出发，经过投递区内每条,街道至少一次,，最后返回邮局）？,我国管梅谷教授,1960,年首先提出，,国际上称之为中国邮递员问题。,2024/10/4,5 、旅行商问题,Traveling salesman problem,一名,推销员,准备前往若干,城市,推销产品。如何为他设计一条,最短,的旅行路线？ （从驻地出发，经过每个城市恰好一次，最后返回驻地）,2024/10/4,6、运输问题,Transportation problem,某种原材料有,M,个产地,，现在需要将原材料从产地运往,N,个使用这些原材料的工厂。假定,M,个产地的产量和,N,家工厂,的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总,运输成本,最低？,2024/10/4,问题的两个共同特点,（1）目的都是从若干可能的安排或方案中寻求,某种意义下的,最优安排,或方案，数学问题称,为最优化或,优化问题,。,（2）它们都可用,图形,形式直观描述，数学上把这,种与图相关的结构称为,网络,。,图和网络相关,的最优化问题就是,网络最优化,。,网络优化问题是以网络流为研究的对象，常,常被称为网络流或,网络流规划,等。,2024/10/4,一、图论的基本概念,1 . 图与子图,e,1,e,2,e,3,e,5,e,6,e,4,e,7,v,3,v,2,v,1,v,4,e,2,e,3,e,5,e,6,e,4,v,3,v,2,v,1,v,4,G,1,：,如,G,：,简单图,：无自环、无重边的图。,2024/10/4,|,V|=n,表示图,G,中节点个数为,n，,此节点个数,n,也称为图,G,的,阶,|,E|=m,表示图,G,中边的个数为,m,任一顶点相关联的边的数目称为该顶点的,度,完全图,：任意两点有边相连，用 表示,完全图的边，和每点的度是多少？,2024/10/4,2 . 关联与相邻,2024/10/4,2024/10/4,3 . 链与圈,2024/10/4,4. 有向图与无向图,，圈,，回路,比较：,2024/10/4,v,1,v,2,v,3,v,5,v,4,8,3,4,2,1,7,2024/10/4,2024/10/4,5. 树,例1 已知有5个城市，要在它们之间架设电话线网，要求任2城市都可通话（允许通过其它城市），并且电话线的根数最少。,v,1,v,2,v,3,v,5,v,4,特点：连通、无圈。,树,无圈的连通图，记为,T,。,2024/10/4,v,1,v,2,v,3,v,5,v,4,树的性质：（1）树的任2点间有且仅有1链；,（2）在树中任去掉1边，则不连通；,（3）在树中不相邻2点间添1边，恰成1圈；,（4）若树,T,有,n,个顶点，则,T,有,n,-1,条边。,2024/10/4,6.图的支撑树,若图,G,=（,V,，,E,）,的子图,T,=（,V,，,E,）,是树，则称,T,为,G,的,支撑树,。,特点边少、点不少。,性质：,G,连通，则,G,必有支撑树。,证：破圈、保连通。,2024/10/4,二、网络分析,网络赋权图，记,D,=,（,V,，,E,，,C,），,其中,C,=,c,1,，,c,n,，,c,i,为边,e,i,上的权（设,c,i,）。,网络分析主要内容,:,最小,支撑,树,最短路,最大流。,2024/10/4,一. 最小支撑树问题,问题：求网络,D,的支撑树，使其权和最小。,方法：避圈法,（,Kruskal,1956,）、,破圈法,(管梅谷，1975)。,例 2 求如图网络的最小支撑树。,v,5,v,1,v,3,v,6,v,4,v,2,v,7,2,5,5,2,3,3,5,7,5,7,1,1,Kruskal, J.B. (1956). On the Shortest Spanning,Subtree,of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society,7, 48-50.,2024/10/4,避圈法是一种选边的过程，其步骤如下：,1. 从网络,D,中任选一点,v,i,，,找出与,v,i,相关联的,权最小的边,v,i,，,v,j,，,得第二个顶点,v,j,；,2. 把顶点集,V,分为互补的两部分,V,1,1,，,其中,2024/10/4,对,G,中各边按权大小顺序排列，不妨设为,W,1,W,2,W,m,填写,W,j,对应的各边,a,j,S=,，i = 0，j=1,a,j,S,构成回路？,|,S|,= n-1,e,i+1,=,a,j,S=e,i+1,S,i=i +1 j=j+1,j=j+1,T*=S,打印,T*,END,Y,Y,N,N,2024/10/4,用避圈法解例2,v,5,v,1,v,3,v,6,v,4,v,2,v,7,2,5,5,2,3,3,5,7,5,7,1,1,最小部分树如图上红线所示；,最小权和为14。,思考：破圈法是怎样做的呢？,见圈就破，去掉其中权最大的。,2024/10/4,最小支撑树问题的应用例子,已知有,A,、,B,、,C,、,D,、,E,、,F,六,个城镇间的道路网络,如图，现要在六个城镇间架设通讯网络（均沿道路架,设），每段道路上的架设费用如图。求能保证各城镇均,能通话且总架设费用最少的架设方案。,6,E,A,C,B,F,D,5,10,9,3,5,3,9,7,8,2,8,4,2024/10/4,二. 最短路问题,1. 问题：求网络,D,中一定点,v,1,到其它点的最短路。,例3,求如图网络中,v,1,至,v,7,的最短路，图中数字为两点间距离。,v,5,v,1,v,3,v,6,v,4,v,2,v,7,2,5,5,2,3,3,5,7,5,7,1,1,2024/10/4,2. 方法：,Dijkstra,算,法（,Dijkstra,，1959）,Dijkstra, E.W. (1959). A note on two problems in,connexion,with graphs.,Numerische,Mathematik,1, 269271.,原理：,Bellman,最优化原理,若,P,是网络,G,中从,V,s,到,V,t,的一条最短路，,V,l,是,P,中除,V,s,与,V,t,外的任何一个中间点，则沿,P,从,V,s,到,V,l,的一条路,P,1,亦必是,V,s,到,V,l,的最短路。,证明（反证）：,若,P,1,不是从,V,s,到,V,l,的最短路，则存在另一条,V,s,到,V,l,的路,P,2,使,W(P,2,)W(P,1,)，,若记路,P,中从,V,l,到,V,t,的路为,P,3,。,则有,W(P,2,)+W(P,3,) 300米),对坡度,的限制, 0.125= 0 0.100,2024/10/4,模型计算方法,(1),对地图网格加密，形成图。,(2),计算网格的距离，用费用作为权值。,(3) 求赋权图两点间的最短距离。,2024/10/4,参考答案,2024/10/4,1998,年全国大学生数学建模竞赛,灾情巡视路线，下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。,2024/10/4,若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。,假定巡视人员在各乡（镇）停留时间,T=2,小时，在各村停留时间,t=1,小时，汽车行驶速度,V=35,公里,/,小时。要在,24,小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。,若巡视组数已定(如三组)，要求尽快完成巡视，讨论,T，t,和,V,改变对最佳巡视路线的影响。,上述关于,T , t,和,V,的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。,2024/10/4,乡村分布图,2024/10/4,点的行遍性问题,1、图论-哈密尔顿问题（是否存在经过所有点一次的圈）,2、组合优化-旅行商问题（赋权图经过所有顶点至少一次）,非完全图的多旅行商问题,两点间的最短路长度作为两点间的权，构造完全图。,两边权之和不小于第三边的权=,完全图的最优哈密尔顿圈=原图的最优旅行商问题。,完全图-增广完全图=,求最优哈密尔顿圈,近似算法或分组后直接搜索,注意,（1）,两点间的最短路长度可用,Dijkstra,算法,（2）,多旅行商问题=最优哈密尔顿圈,2024/10/4,线性规划模型,2024/10/4,问题解答：,1、,分三组（路）巡视，试设计总路程最短且 各组尽可能均衡的巡视路线。,目标函数：,min(C1+C2+C3),限制条件：,min(C3 - C1),或,者,：,min(C1),2、,假定巡视人员在各乡（镇）停留时间,T=2,小时，在各村停留时间,t=1,小时，汽车行驶速度,V=35,公里,/,小时。要在,24,小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线,。,2024/10/4,目标函数：,min(H1+H2+H3),花费时间：,Hi=2mi+ni+Ci/V,限制条件：,min(max(Hi),总时间,69,小时,=,至少,4,组，,4,组的路线可以找到。,3、,在上述关于,T , t,和,V,的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。,单独巡视的最短时间,=,最远距离,（1）每组时间不超过最远距离时间,（2）巡视组足够少，,22,组,4、,若巡视组数已定,(,如三组,),，要求尽快完成巡视，讨论,T,，,t,和,V,改变对最佳巡视路线的影响。,讨论花费时间函数：,Hi=2mi+ni+Ci/V,注意：多旅行商问题,=,单旅行商问题（,LINGO,）,2024/10/4,2005年全国大学生数学建模竞赛,DVD,在线租赁,随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。,考虑如下的在线,DVD,租赁问题。顾客缴纳一定数量的月费成为会员，订购,DVD,租赁服务。会员对哪些,DVD,有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张,DVD,，,这些,DVD,是基于其偏爱程度排序的。网站会根据手头现有的,DVD,数量和会员的订单进行分发。每个会员每个月租赁次数不得超过,2,次，每次获得,3,张,DVD,。,会员看完,3,张,DVD,之后，只需要将,DVD,放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。请考虑以下问题：,2024/10/4,1) 网站正准备购买一些新的,DVD,，,通过问卷调查,1000,个会员，得到了愿意观看这些,DVD,的人数（表,1,给出了其中,5,种,DVD,的数据）。此外，历史数据显示，,60%,的会员每月租赁,DVD,两次，而另外的,40%,只租一次。假设网站现有,10,万个会员，对表,1,中的每种,DVD,来说，应该至少准备多少张，才能保证希望看到该,DVD,的会员中至少,50%,在一个月内能够看到该,DVD,？,如果要求保证在三个月内至少,95%,的会员能够看到该,DVD,呢？,2）,表,2,中列出了网站手上,100,种,DVD,的现有张数和当前需要处理的,1000,位会员的在线订单（表,2,的数据格式示例如下表,2,，具体数据请下），如何对这些,DVD,进行分配，才能使会员获得最大的满意度？请具体列出前,30,位会员（即,C0001C0030,）,分别获得哪些,DVD,。,3）,继续考虑表,2,，并假设表,2,中,DVD,的现有数量全部为,0,。如果你是网站经营管理人员，你如何决定每种,DVD,的购买量，以及如何对这些,DVD,进行分配，才能使一个月内,95%,的会员得到他想看的,DVD,，,并且满意度最大？,如果你是网站经营管理人员，你觉得在,DVD,的需求预测、购买和分配中还有哪些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。,2024/10/4,2024/10/4,
展开阅读全文