数模培训资料课件

全国数学建模竞赛培训 这是一场艰苦的战役。需要不怕苦和不怕累的精神，要有坚忍不拔的毅力。7/14/2024全国数学建模竞赛培训 这是一场艰苦的战役。需要不怕苦和1v可能面临酷暑、内容多、强度大的困难。7/14/2024可能面临酷暑、内容多、强度大的困难。8/14/20232数学建模暑期培训纪律v不允许缺课，迟到和早退的现象发生。v每一个队每一次培训或讲评，必须是三人到齐。v教练会对每一次活动考勤，并与相关学院联系，对缺课学生予以相应处罚。7/14/2024数学建模暑期培训纪律不允许缺课，迟到和早退的现象发生。8/13图论算法v参考教材：v数学建模与数学实验（赵静、但琦编）v数学建模导论（陈理荣编）v图论及其算法（殷剑宏、吴开亚编）v集合论与图论（耿素云编）7/14/2024图论算法参考教材：8/14/20234图论算法.最短路问题最短路问题.中国邮递员问题和问中国邮递员问题和问题题.匹配匹配7/14/2024图论算法.最短路问题8/14/20235图论算法（）最短路问题图论算法（）最短路问题1图图 论论 的的 基基 本本 概概 念念2最最 短短 路路 问问 题题 及及 其其 算算 法法3最最 短短 路路 的的 应应 用用4建模案例：最优截断切割问题建模案例：最优截断切割问题5实例应用实例应用7/14/2024图论算法（）最短路问题1图 论 的 基 本 概 念26图图 论论 的的 基基 本本 概概 念念一、一、图图 的的 概概 念念1图的定义图的定义2顶点的次数顶点的次数 3子图子图二、二、图图 的的 矩矩 阵阵 表表 示示1 关联矩阵关联矩阵2 邻接矩阵邻接矩阵返回返回7/14/2024图 论 的 基 本 概 念一、图 的 概 念1图的定义27定义定义有序三元组G=(V,E,)称为一个图图,如果：图的定义图的定义7/14/2024定义有序三元组G=(V,E,)称为一个图,如果：8定义定义定义定义7/14/2024定义定义8/14/202397/14/20248/14/202310返回返回7/14/2024返回8/14/202311顶点的次数（度数）顶点的次数（度数）7/14/2024顶点的次数（度数）8/14/202312例例 在一次聚会中，认识奇数个人的人数一定是偶数.返回返回7/14/2024例 在一次聚会中，认识奇数个人的人数一定是偶数.返回8/13子图子图返回返回7/14/2024子图返回8/14/202314关联矩阵关联矩阵注：假设图为简单图返回返回7/14/2024关联矩阵注：假设图为简单图返回8/14/202315邻接矩阵邻接矩阵注：假设图为简单图7/14/2024邻接矩阵注：假设图为简单图8/14/202316返回返回7/14/2024返回8/14/202317最短路问题及其算法最短路问题及其算法一、一、基本概念基本概念二、固定起点的最短路二、固定起点的最短路三、每对顶点之间的最短路三、每对顶点之间的最短路返回返回7/14/2024最短路问题及其算法一、基本概念二、固定起点的最短路三、每对18基本概念基本概念7/14/2024基本概念8/14/202319返回返回7/14/2024返回8/14/202320固定起点的最短路固定起点的最短路-DijkstraDijkstra算法算法最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此,可采用树生长的过程来求指定顶点到其余顶点的最短路7/14/2024固定起点的最短路-Dijkstra算法最短路是一条路径，且最21Dijkstra算法算法思想vDijkstra算法算法:这是荷兰计算机科学教授Edsger W.Dijkstra(1930-)在1959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项.vDijkstra算法算法是求出一个连通加权简单图中从结点a到结点z的最短路.边i,j的权(i,j)0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度.7/14/2024Dijkstra算法思想Dijkstra算法:这是荷兰计算机227/14/20248/14/202323算法步骤：算法步骤：7/14/2024算法步骤：8/14/202324 TO MATLAB(road1)7/14/2024 TO MATLAB(road1)8/14/2023257/14/20248/14/202326 1 2 34 5 6 7 8返回返回7/14/2024 1 2 34 5 6 7 8返回8/127每对顶点之间的最短路每对顶点之间的最短路-Floyd算法算法1求距离矩阵的方法求距离矩阵的方法2求路径矩阵的方法求路径矩阵的方法3查找最短路路径的方法查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤返回返回7/14/2024每对顶点之间的最短路-Floyd算法1求距离矩阵的方法228算法的基本思想算法的基本思想返回返回7/14/2024算法的基本思想返回8/14/202329算法原理算法原理 求距离矩阵的方法求距离矩阵的方法返回返回7/14/2024算法原理 求距离矩阵的方法返回8/14/202330算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R 即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径返回返回)(nR7/14/2024算法原理 求路径矩阵的方法在建立距离矩阵的同时可建立路径31i j算法原理算法原理 查找最短路路径的方法查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：返回返回7/14/2024i j算法原理 查找最短路路径的方法pkp2p1p3q32算法步骤算法步骤7/14/2024算法步骤8/14/202333 TOMATLAB(road2(floyd)返回返回7/14/2024 TOMATLAB(road2(floyd)返回8/34一、一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、选选 址址 问问 题题1 中心问题中心问题2 重心问题重心问题返回返回7/14/2024一、可化为最短路问题的多阶段决策问题二、选 址 问 题135可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题7/14/2024可化为最短路问题的多阶段决策问题8/14/2023367/14/20248/14/2023377/14/20248/14/202338返回返回7/14/2024返回8/14/202339 选址问题选址问题-中心问题中心问题 TO MATLAB(road3(floyd)7/14/2024 选址问题-中心问题 TO MATLAB(road340S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处.返回返回7/14/2024S(v1)=10,S(v2)=7,S(v3)=6,S(41 选址问题选址问题-重心问题重心问题返回返回7/14/2024 选址问题-重心问题返回8/14/202342图论算法（）图论算法（）中国邮递员问题和中国邮递员问题和问题问题7/14/2024图论算法（）8/14/202343邮路问题及邮路问题及问题问题一、中国邮递员问题一、中国邮递员问题二、推销员问题二、推销员问题三、建模案例：最佳灾情巡视路线三、建模案例：最佳灾情巡视路线（一）（一）欧拉图欧拉图（二）（二）中国邮递员问题中国邮递员问题（一）哈密尔顿图（一）哈密尔顿图（二）推销员问题（二）推销员问题7/14/2024邮路问题及问题一、中国邮递员问题二、推销员问题三、建模44 7 3 1 2 3 4 1 2 4 5 5 6 6 7 8 9割边G的边 是割边的充要条件是 不含在G的圈中 割边的定义割边的定义：设G连通，E(G),若从G中删除边 后，图G-不连通，则称边 为图G的割边7/14/2024 7 3 1 2 3 4 1 2 4 5 5 6 6 45 e3 v1 v2 v3 v4e1e2e4 e5e6欧拉图欧拉图 e3 v1 v2 v3 v4 e1e 2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v17/14/2024 e3 v1 v2 v3 v4e1e2e4 e5e6欧拉图46e3 v1 v2 v3v4e1e2e4 e5e3 v1 v2 v3v 4 e1 e2e4 e5e6欧拉图 非欧拉图返回返回7/14/2024e3 v1 v2 v3v4e1e2e4 e5e3 v1 47中国邮递员问题中国邮递员问题-定义定义7/14/2024中国邮递员问题-定义8/14/202348中国邮递员问题中国邮递员问题-算法算法 Fleury算法基本思想算法基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.7/14/2024中国邮递员问题-算法 Fleury算法基本思想：从任49 v7e3 v1v2 v3v4e1 e2e4 e5 v5 e6e6 e 7 e8 e9e107/14/2024 v7e3 v1v2 v3v4e1 e2e4 e5 v5 50 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次 解决这类问题的一般方法一般方法是：在一些点对之间在一些点对之间引入重复边（重复边与它平行的边具有相同的引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小重复边的权的总和为最小7/14/2024 若G不是欧拉图，则G的任何一个巡回经过某些边必51v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e97/14/2024v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8527/14/20248/14/202353（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对7/14/2024（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对854返回返回7/14/2024返回8/14/202355哈密尔顿图哈密尔顿图返回返回7/14/2024哈密尔顿图返回8/14/202356推销员问题推销员问题-定义定义 流动推销员需要访问某地区的所有城镇城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题推销员问题 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点每个顶点至少一次的最短闭通路问题7/14/2024推销员问题-定义 流动推销员需要访问某地区的所有城57定义定义在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最最佳佳H圈圈(Hamilton圈圈)（）经过每个顶点至少一次的权最小的闭闭通通路路称为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长47/14/2024定义在加权图G=(V,E)中，一般说来，最佳哈587/14/20248/14/202359推销员问题近似算法：推销员问题近似算法：二边逐次修正法二边逐次修正法：7/14/2024推销员问题近似算法：二边逐次修正法：8/14/202360例例对以下完备图，用二边逐次修正法求较优H圈7/14/2024例对以下完备图，用二边逐次修正法求较优H圈8/14/2061返回返回7/14/2024返回8/14/202362图论算法（）匹配图论算法（）匹配 匹配问题是运筹学的重要问题之一,也是图论研究的重点内容,它提供了解决“人员分配问题”和“最优分配问题”一种新的思想.定义定义1.设G=是无环图,ME(G),M,若M中任意两条边都不相邻,则称M M是图是图G G的一个匹配的一个匹配.若对图G的任何匹配M,均有M0)正则二分图,则G有完美匹配.由定理3可知,G有饱和V1的匹配M,再据V1=V2和推论1即知M是完美匹配.推论推论3.设G是二部划分(V1,V2)的简单二分图，且V1=V2=n，若(G)n/2，则G有完美匹配.7/14/2024定理3(Hall定理,1935)设G是有二部划分(V1,V266定理定理4.G有完美匹配O(G-S)S,SV(G),其中O(G-S)是G-S的奇数阶连通分支数目例1.有有n n张纸牌张纸牌,每张纸牌的正反两面都写上每张纸牌的正反两面都写上1,2,n1,2,n的某的某一个数一个数,证明证明:如果每个数字恰好出现两次如果每个数字恰好出现两次,则这些纸牌则这些纸牌一定可以这样摊开一定可以这样摊开,使朝上的面中使朝上的面中1,2,n1,2,n都出现都出现.证明证明:作一个二分图G=,其中V1=1,2,n，V2=y1,y2,yn表示这n张纸牌.i与yi之间连接的边数等于数i在纸牌yj中出现的次数,这样得到的图G是一个2-正则二分图,因此图G中有完美匹配,设为M=1yi1,2yi2,nyin 则只要把纸牌yi1中的1朝上,yi2中的2朝上,yin的n朝上,这样摊开,这样摊开的纸牌就能使上面中1,2,n都出现.7/14/20248/14/202367例例2.某工厂生产由6种不同颜色的纱布织成的双色布,由该厂所生产的双色布中,每一种颜色至少和其他三种颜色搭配.证明可以挑选出三种不同的双色布,它们含有所有的6种颜色.证明证明:构造图G=,其中V=v1,v2,v3,v4,v5,v6表示6种颜色,工厂生产出一种颜色vi与vj搭配而成的双色布边vi,vjE(G).由题意知,G为简单图,且每个结点的度数至少为3,下证 G中含有一个完美匹配.今设v1,v2E(G),由于d(v3)3,所以存在一个不同于v1和v2的顶点vi(4i6),使v3,viE(G),不妨设vi=4,即v3,v4E(G).7/14/2024例2.某工厂生产由6种不同颜色的纱布织成的双色布,由该8/168 如果边v5,v6E(G),由于d(v5)3,v1,v2,v3,v4中至少有3个顶点与v5相邻,即v5与边v1,v2,v3,v4中的每一边的某一个端点相邻,不妨设v1,v5E(G)和v3,v5E(G).对于顶点v6,同样与v1,v2,v3,v4中至少3个顶点相邻,即在v2和v4中至少有一个顶点与v6相邻.如果v2,v6E(G),则边v1,v5,v3,v4,v2,v6是G的一个完美匹配;如果v4,v6E(G),则v1,v2,v3,v5,v4,v6是G的一个完美匹配.综上所述,G总存在完美匹配,完美匹配中的三条边所对应的三种双色布即为所求.7/14/2024 如果边v5,v6E(G),由于d(v5)3,v69最大匹配的生成算法-匈牙利算法定义定义1.根在x的M交错子图:设M是图G的匹配,x是G中非M饱和点.G中由起点为x的M交错路所能连接的顶点集所导出的G的导出子图称为根在称为根在x的的M交错子图交错子图.定理定理1.设M是具有二部划分(V1,V2)的二分图G的匹配,xV1是非M饱和点,H是G中根在x的M交错子图的顶点集S=HV1,T=HV2,则:(1)TNG(S);(2)下述三条等价:(a)G中不存在以x为端点的M可增广路;(b)x是H中唯一的非M饱和点;(c)T=NG(S),且T=S-1.(不证)7/14/2024最大匹配的生成算法-匈牙利算法定义1.根在x的M交错子图:70匈牙利算法匈牙利算法基本思想基本思想:设G是具有二部划分(V1,V2)的二分图,从图G的任意匹配M开始.若M饱和V1,则M是G的匹配.若M不能饱和V1,则在V1中选择一个非M饱和点x,若G中存在以x为起点的M可增广路P,则M=MP就是比M更大的匹配,利用M代替M,并重复这个过程.若G中不存在以x为起点的M可增广路,则令H是根在x的M交错子图的顶点集,并令S=HV1,T=HV2,由定理1,T=NG(S),且G中不存在以x为起点的M可增广路,此时称x为检验过的非M饱和点.对V1中其它未检验过的非M饱和点重复该过程,直到V1中的所有非M饱和点全部检验过为止.当整个过程结束时,由于G中不存在M可增广路,从而M为G的最大匹配.7/14/2024匈牙利算法基本思想:设G是具有二部划分(V1,V2)的二分图71匈牙利算法步骤匈牙利算法步骤:设设G是具有二部划分是具有二部划分(V1,V2)的二分图的二分图.(1)任给初始匹配任给初始匹配M;(2)若若M饱和饱和V1则结束则结束.否则转否则转(3);(3)在在V1中找一非中找一非M饱和点饱和点x,令令S=x,T=;(4)若若N(S)=T,则停止则停止,否则任选一点否则任选一点y N(S)-T;(5)若若y为为M饱和点转饱和点转(6),否则作求一条从否则作求一条从x到到y的的M可增广可增广路路P,置置M=M P,转转(2)；(6)由于由于y是是M饱和点饱和点,故故M中有一边中有一边y,u,置置S=S u,T=T y,转转(4).7/14/2024匈牙利算法步骤:8/14/202372例1.如图G所示,V1=x1,x2,x3,x4,x5,V2=y1,y2,y3,y4,y5，试求图G的最大匹配.x1,x2 x3 x4 x5y1 y2 y3 y4 y5图图ax1 x2 x3 x4 x5y1 y2 y3 y4 y5图图b7/14/2024例1.如图G所示,V1=x1,x2,x3,x4,x5,73解:任取初始匹配M=x2y2,x3y3,x5y5,如图(a)中虚线所示.解题过程如下表:MxSTN(S)y N(S)-Ty,u MPx2y2,x3y3,x5y5x1x1y2,y3y2饱和饱和y2,x2x1,x2y2y1,y2,y3,y4,y5y1非饱非饱和和(x1y2x2y1)x1y2,x2y1,x3y3 x5y5x4x4y2,x3y2饱和饱和y2,x1x4,x1y2y2,y3y3饱和饱和y3,x3x4,x1,x3y2,y3y2,y3N(S)=T,停止停止7/14/2024解:任取初始匹配M=x2y2,x3y3,x5y5,如图(74因此,M=x1y2,x2y1,x3y3,x5y5即为图G的最大匹配,如图(b)虚线所示.7/14/2024因此,M=x1y2,x2y1,x3y3,x5y5即为图G75 最优匹配最优匹配定义定义1.最优匹配最优匹配:在加权图中求一个总权最大的完在加权图中求一个总权最大的完美匹配美匹配,这种匹配这种匹配称为称为最优匹配最优匹配.定义定义2.已知G是具有二部划分(V1,V2)的完全加权二分图,映射L:V(G)R,满足对G的每条边e=x,y,均有L(x)+L(y)(x,y),其中(x,y)表示边x,y的权,则称则称L为为G的可行顶标的可行顶标.令令EL=x,y x,y E(G),L(x)+L(y)=(x,y),GL为以为以EL为为边集的边集的G的生成子的生成子图图,则称则称GL为为L等子图等子图.说明说明:可行顶标总可行顶标总是存在的是存在的,例如例如:7/14/2024 最优匹配定义1.最优匹配:在加权图中求一个总权最大的完美76定理定理1.设设L L是是G G的可行顶标的可行顶标.若若L L等子图等子图G GL L有完美匹配有完美匹配M,M,则则M M是是G G的最优匹配的最优匹配.基于定理基于定理1的在一个加权二分图的在一个加权二分图(Km,n,)中求最优匹配的中求最优匹配的有效算法有效算法Kuhn-munkres算法算法:(1)(1)从任意可行顶标从任意可行顶标(如平凡标号如平凡标号)L)L开始开始,确定确定L L等子图等子图G GL L,并且并且在在G GL L中选取匹配中选取匹配M.M.若若M M饱和饱和V V1 1,则则M M是完美匹配是完美匹配,也即也即M M是最优是最优匹配匹配,算法终止算法终止,否则转入否则转入(2)(2)步步.(2)(2)匈牙利算法终止于匈牙利算法终止于S S V V1 1,T,T V V2 2且使且使N NGLGL(S)=T,(S)=T,计算计算a aL L,确确定新的可行顶标定新的可行顶标L,L,并以并以LL替代替代L,L,以以G GLL替代替代G GL L转入转入(1)(1)步步.7/14/2024定理1.设L是G的可行顶标.若L等子图GL有完美匹配77例例1.已知完全二分图已知完全二分图k5,5,其中其中V1=x1,x2,x3,x4,x5,V2=y1,y2,y3,y4,y5,且且k5,5的权矩阵为的权矩阵为A,求求k5,5的最的最优匹配优匹配.7/14/2024例1.已知完全二分图k5,5,其中V1=x1,x2,x3,78