数学建模图论案例讲解课件

数学建模数学建模图论图论案例案例讲讲解解课课件件1B B题题 灾情巡视路线灾情巡视路线 下图为某县的乡（镇）、村公路网示意图，下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。灾情巡视路线指从全县各乡（镇）、村巡视。灾情巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的灾情巡视路线。且各组尽可能均衡的灾情巡视路线。1998年全国大学生数学建模竞赛题目B题题灾情巡灾情巡视视路路线线1998年全国大学生数学建模年全国大学生数学建模竞赛题竞赛题目目2假定巡视人员在各乡（镇）停留时间假定巡视人员在各乡（镇）停留时间T=2T=2小时，在小时，在各村停留时间各村停留时间t=1t=1小时，汽车行驶速度小时，汽车行驶速度V=35V=35公里公里/小时。小时。要要2424小时内完成巡视，至少应分几组；给出这种分组小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的灾情巡视路线。下你认为最佳的灾情巡视路线。在上述关于在上述关于T,tT,t和和V V的假定下，如果巡视人员足的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的灾情巡视路线。时间完成巡视的要求下，你认为最佳的灾情巡视路线。若巡视组数已定若巡视组数已定(如三组），要求尽快完成巡视，如三组），要求尽快完成巡视，讨论讨论T T，t t和和V V改变对最佳灾情巡视路线的影响。改变对最佳灾情巡视路线的影响。假定巡假定巡视视人人员员在各在各乡乡（镇镇）停留）停留时间时间T=34 旅行商问题旅行商问题（TSPTSPtraveling salesman problemtraveling salesman problem）一名推销员准备前往若干城市推销产品。如何为他一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商久，通常称之为旅行商(推销员）问题。推销员）问题。旅行商旅行商问题问题（TSPtravelingsalesman5哈哈 密密 尔尔 顿顿 图图 1859 1859年，数学家哈密尔顿发明了一种周游世界的游戏：年，数学家哈密尔顿发明了一种周游世界的游戏：在一个在一个1212面体的每个角点代表一个城市，问能否从某城市面体的每个角点代表一个城市，问能否从某城市出发，沿出发，沿1212面体的棱行走，经过每个城市一且仅一次，最面体的棱行走，经过每个城市一且仅一次，最后回到出发地。后回到出发地。用图论的语言来讲，就是在用图论的语言来讲，就是在1212面体图上找出生成圈。面体图上找出生成圈。哈哈密密尔尔顿顿图图1859年，数学家哈密年，数学家哈密尔尔顿发顿发明了一明了一6哈哈 密密 尔尔 顿顿 图图哈哈密密尔尔顿顿图图7推销员问题推销员问题-定义定义 流动推销员需要访问某地区的所有城镇，最流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题小这就是推销员问题 若用顶点表示城镇，边表示连接两城镇的若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于路，边上的权表示距离（或时间、费用），于是推销员问题就成为是推销员问题就成为在加权图中寻找一条经过在加权图中寻找一条经过在加权图中寻找一条经过在加权图中寻找一条经过每个顶点至少一次的最短闭通路每个顶点至少一次的最短闭通路每个顶点至少一次的最短闭通路每个顶点至少一次的最短闭通路问题问题推推销员问题销员问题-定定义义流流动动推推销员销员需要需要访问访问某地区的所有城某地区的所有城镇镇8定义在加权图定义在加权图G=(V,E)中，中，（）权最小的哈密尔顿圈称为（）权最小的哈密尔顿圈称为最佳最佳H圈圈（）经经过过每每个个顶顶点点至至少少一一次次的的权权最最小小的的闭闭通通路路称称为为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长回路，长22最佳推销员回路，长最佳推销员回路，长4定定义义在加在加权图权图G=(V,E)中，中，一般一般说说来，最佳哈来，最佳哈9数学建模数学建模图论图论案例案例讲讲解解课课件件10推销员问题近似算法：推销员问题近似算法：二边逐次修正法二边逐次修正法：推推销员问题销员问题近似算法：二近似算法：二边边逐次修正法：逐次修正法：11分析：灾情巡 视路 线 问题 是一个 寻求最佳多旅行商回路的问题。1、多旅行商问题 跟单旅行商问题的区别。单旅行商问题可以转化为加权图的最优H圈问题。多旅行商问题怎么办？2、第一问目标：总路程最短且尽可能均衡。如何表述。目标1：目标2：分析：分析：灾情巡灾情巡视视路路线线问题问题是一个是一个寻寻求最佳多旅行商回路求最佳多旅行商回路12限制条件第一问目标简化：多目标 单目标 分组：方法很多。可以给定一个初始分组，然后基于上述单目标进行调整。问题2：最小组数问题。（问题3也涉及）分析：求r组多旅行商路线，在满足题目要求限制条件下，使得每个路线都包含县城，且总体能覆盖V。并证明r-1组不可能。限制条件限制条件13限制条件：在巡视点有一定停留时间的情况下24小时完成巡视。巡视点停留：引入点权。对村乡进行编号，村权35，乡权70.时间化为距离，将点权和边权统一起来。对每一个旅行商路线，求其总权 T_i,优化的目标为使得分组的最大的总权尽量小。方法：调整分组。在给定上述目标和约束的条件下，对问题2不难得到4个旅行商路线可以满足。如何证明3个不行？限制条件：在巡限制条件：在巡视视点有一定停留点有一定停留时间时间的情况下的情况下24小小时时完成巡完成巡视视。14问题3：最短时间及最优巡视方案最短时间：县城到最远乡镇的距离。不难确定。最优巡视方案？可以按照问题2的模型确定组数。答案为22.但是如何证明21不行？思考题？问题问题3：最短：最短时间时间及最及最优优巡巡视视方案最短方案最短时间时间：县县城到最城到最远乡镇远乡镇的距的距15问题4：组数已定，讨论T,t,V的改变对最佳巡视路线的影响要尽快完成巡视,就得要求每组完成巡视时问尽量均衡,因为总的完成巡视时间按最长的完成巡视时间计算。现在讨论在均衡度允许的范围内已分成n组后，改变T,t,V对最佳巡视路线的影响。显然在分组不变的情况下,无论如何改变分组后，对每组内的最沈 封丛 视路线是没有影响的，但可能会影响各组 间的均衡性 因此该问题实际上是讨论T,t,V对分组的影响,即在不破坏原来分组均衡的条件下,T、t,V允许的最大变化范围问题问题4：组组数已定，数已定，讨论讨论T,t,V的改的改变对变对最佳巡最佳巡视视路路线线的影响要的影响要161994全国大学生数学建模竞赛题目B题锁具装箱某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从1,2,3,4,5,66个数(单位略)中任取一数。由于工艺及其它原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数;相邻两槽高度之差不能为5。满足以上条件制造出来的所有互不相同的锁具称为一批。出来的所有互不相同的锁具称为一批。从顾客的利益出发,自然希望在每批锁具中一把钥匙开一把锁。但是在当前工艺条件下,对于同一批中两个锁具是否能够互开,有以下试验结果:若二者相对应的5个槽的高度中有4个相同,另一个的高度差为1,则可能互开;在其它情形下,不可能互开。原来,销售部门在一批锁具中随意地取每60个装一箱出售。团体顾客往往购买几箱到几十箱,他们抱怨购得的锁具会出现互相开的情形。现聘聘请你为顾问,回答并解决以下问题:1994全国大学生数学建模全国大学生数学建模竞赛题竞赛题目目B题题锁锁具装箱具装箱17每一批锁具有多少个,装多少箱。为销售部门提供一种方案,包括如何装箱(仍是60个锁具一箱),如何给箱子以标志,出售时如何利用这些标志,使团体顾客不再或减少抱怨。采取你提出的方案,团体顾客的购买量不超过多少箱,就可以保证一定不会出现互开。按照原来的装箱办法,如何定量地衡量团体顾客抱怨互开的程度(试对购买一、二箱者给出具体结果)。每一批每一批锁锁具有多少个具有多少个,装多少箱。装多少箱。18称称G=(X,Y,E)为为二部图二部图.如果如果X中的每个点都与中的每个点都与Y中的中的每个点邻接每个点邻接,则称则称G=(X,Y,E)为为完备二部图完备二部图.若若 F：E R+,则称则称G=(X,Y,E,F)为为二部赋权图二部赋权图.定义定义1 设设X,Y都是非空有限顶点集都是非空有限顶点集,且且X Y=,二部图的匹配、独力集称称G=(X,Y,E)为为二部二部图图.如果如果X中的每个点中的每个点19定义定义3 若匹配若匹配M的某条边与点的某条边与点v关联关联,则称则称M饱和饱和点点v,并且称并且称v是是M的的饱和点饱和点,否则称否则称v是是M的的非饱非饱和点和点.定义定义4 设设M是图是图G的一个匹配的一个匹配,如果如果G的每一个点的每一个点都是都是M的饱和点的饱和点,则称则称M是是完美匹配完美匹配；如果；如果G中中没有另外的匹配没有另外的匹配M0,使使|M0|M|,则称则称M是是最最大匹配大匹配.含边数最多的最大匹配中所含的边数称为含边数最多的最大匹配中所含的边数称为图图G的边独立数，记为的边独立数，记为每个完美匹配都是最大匹配每个完美匹配都是最大匹配,反之不一定成立反之不一定成立.二部图的二部图的匹配、独力集匹配、独力集定定义义3若匹配若匹配M的某条的某条边边与点与点v关关联联,则则称称M饱饱和定和定义义4设设M20例例16：判断下图的匹配判断下图的匹配最大匹配最大匹配非完美匹配非完美匹配完美匹配完美匹配二部图的二部图的匹配、独力集匹配、独力集例例16：判断下判断下图图的匹配最大匹配完美匹配二部的匹配最大匹配完美匹配二部图图的匹配、独力集的匹配、独力集21定义定义5 若若图图 G的一个顶点子集中的任意两个点都互不相的一个顶点子集中的任意两个点都互不相邻邻,则称该顶点子集为为则称该顶点子集为为G的一个点独立集。图的一个点独立集。图G的独立的独立数为数为G的最大点独力集所含的点数，记为的最大点独力集所含的点数，记为定义定义6 若若图图 G的一个顶点子集的一个顶点子集K称为称为G的一个点覆盖子集，的一个点覆盖子集，如果如果G中的任意一条边都至少有一个顶点包含在中的任意一条边都至少有一个顶点包含在G中中.图图G的覆盖数为的覆盖数为G的最小点覆盖集中所含的点数，记为的最小点覆盖集中所含的点数，记为 若若G中任一个顶点都是图中任一个顶点都是图G的边集的边集S中一条边的顶点，中一条边的顶点，则称则称S为为G的一个边覆盖集。含边数最少的边覆盖集中的的一个边覆盖集。含边数最少的边覆盖集中的边数称为图边数称为图G的边覆盖数。的边覆盖数。二部图的二部图的匹配、独力集匹配、独力集定定义义5若若图图G的一个的一个顶顶点子集中的任意两个点都互不相点子集中的任意两个点都互不相邻邻,则则22二部图的二部图的匹配、独力集匹配、独力集-相关定理相关定理定理1定理2若图G没有孤立顶点，即顶点的最小度0，则定理3对于二分图G，有二部二部图图的匹配、独力集的匹配、独力集-相关定理定理相关定理定理1定定理理2若若23引理引理1 设设G=(X,Y,E)为二部图为二部图,则则 G存在存在饱和饱和X的每个点的匹配的充要条件是的每个点的匹配的充要条件是对任意对任意S ,有有|N(S)|S|.其中其中,N(S)=v|uS,v与与u相邻相邻.G存在完美匹配的充要条件是存在完美匹配的充要条件是对任意对任意S 或或S 有有|N(S)|S|.二部图的二部图的匹配、独力集匹配、独力集引理引理1设设G=(X,Y,E)为为二部二部图图,则则G24分析：6 种 高度 5 个 槽 的钥匙 最多 可能有 ，通 过排 列组 合，除 去不 满足 条件 的各种 情 况，可 以算 出一批 锁具 的总数为 5880件由于两个 锁具 对应 的 5 个 槽 高 中有 4 个 相 同，另一 个 只相 差 1，被视 为互 开，那 么它们 各 自 槽 高 之 和必为 一个 奇数、一个 偶数 另外，槽 高 之和为 奇数 和偶数 的锁 具 可 以一 一对 应，因 而各 占一 半：2 9 4 0件，槽 高 之和为奇数(或偶数)的两锁具之间不可能互开，所 以若 6 O个装一箱，2 9 4 0个锁具可 以装 4 9箱，4 9箱槽高之和为奇数或偶数的锁具，肯定不能互开 现在的问题是 4 9 箱是不是最大可能的?分析：分析：6种种高度高度5个个槽槽的的钥钥匙匙最多最多可能有可能有25将锁具的互开关系用图表示，锁具集合用 表示，其中 和 分别表示槽高之和为奇数和偶数的锁具集合。若 能 够互 开，则 两 点 连 一 边。对 问题 1 构 造 的二分 图，由于奇数 类锁 具 与偶 数类 锁 具 的对 称 性，引理 1 满 足，所 以存 在饱和 的每个顶点的匹配，而 的顶 点互不 相邻，因此从而点独立数 由于奇数类点独立集和偶数类点独立集都有2940个点,所 以 ，说 明奇数 类点集 和偶 数类 点集 都是 最大 的点 独立集,因此 4 9 箱 是 不能互 开 的最 大可 能将将锁锁具的互开关系用具的互开关系用图图表示，表示，锁锁具集合用具集合用26ThankYou!27