数学建模基础知识.ppt

我们介绍三种优化模型:?图论?动态优化?排队论重点:图论模型的数学建模案例分析基本方法?机理分析?测试分析根据对客观事物特性的认识,找出反映内部机理的数量规律将研究对象看作“黑箱”,通过对量测数据的统计分析,找出与数据拟合最好的模型?二者结合机理分析建立模型结构,测试分析确定模型参数数学建模的方法和步骤数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用一、图论方法?最短路问题?两个指定顶点之间的最短路径—给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,找一条最短铁路线(Dijkstra算法)?每对顶点之间的最短路径(Dijkstra算法、Floyd算法)?最小生成树问题?连线问题—欲修筑连接多个城市的铁路设计一个线路图,使总造价最低(prim算法、Kruskal算法)?图的匹配问题?人员分派问题:n个工作人员去做n份工作,每人适合做其中一份或几份,问能否每人都有一份适合的工作?如果不能,最多几人可以有适合的工作?(匈牙利算法)?遍历性问题?中国邮递员问题—邮递员发送邮件时,要从邮局出发,经过他投递范围内的每条街道至少一次,然后返回邮局,但邮递员希望选择一条行程最短的路线?最小费用最大流问题?在运输问题中,人们总是希望在完成运输任务的同时,寻求一个使总的运输费用最小的运输方案(1)基本概念(2)固定起点的最短路(3)每对顶点之间的最短路1、最短路问题基本概念通路44112544141vevevevevWvv?道路4332264521141vevevevevevTvv?路径4521141vevevPvv?定义1在无向图G=(V,E,?)中:(1)顶点与边相互交错且iiivve1)(???(i=1,2,…k)的有限非空序列)(12110kkkvevevevw???称为一条从0v到kv的通路,记为kvvW0(2)边不重复但顶点可重复的通路称为道路,记为kvvT0(3)边与顶点均不重复的通路称为路径,记为kvvP0固定起点的最短路从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短?交通网络可用带权图来表示。顶点表示城市名称,边表示两个城市有路连通,边上的权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径,不是指路径上边数之和最少,而是指路径上各边的权值之和最小。另外,若两个顶点之间没有边,则认为两个顶点无通路,但有可能有间接通路(从其它顶点达到)。路径上的开始顶点(出发点)称为源点,路径上的最后一个顶点称为终点,并假定讨论的权值不能为负数。从一个顶点到其余各顶点的最短路径问题:给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径,并限定各边上的权值大于或等于0。采用狄克斯特拉(Dijkstra)算法求解基本思想是:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组:第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径v,…vk,就将vk加入到集合S中,直到全部顶点都加入到S中,算法就结束了)第二组为其余未确定最短路径的顶点集合(用U表示)。按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。