数学建模题目080420省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,玩具、照片、飞机、火箭模型,实物模型,地图、电路图、分子结构图,符号模型,模型,是为了一定目标，对客观事物一部分,进行简缩、抽象、提炼出来,原型,替换物,模型,集中反应了,原型,中人们需要那一部分特征,1.2,从现实对象到数学模型,我们常见模型,第1页,你碰到过数学模型,“,航行问题”,用,x,表示船速，,y,表示水速，列出方程：,答：船速每小时,20,千米,/,小时,.,甲乙两地相距,750,千米，船从甲到乙顺水航行需,30,小时，,从乙到甲逆水航行需,50,小时，问船速度是多少,?,x,=,20,y,=,5,求解,第2页,航行问题,建立数学模型基本步骤,作出简化假设（船速、水速为常数）；,用符号表示相关量（,x,y,表示船速和水速）；,用物理定律（匀速运动距离等于速度乘以,时间）列出数学式子（二元一次方程）；,求解得到数学解答（,x,=20,y,=5,）；,回答原问题（船速每小时,20,千米,/,小时）。,第3页,数学模型,(Mathematical Model),和,数学建模（,Mathematical Modeling),对于一个,现实对象,，为了一个,特定目标,，,依据其,内在规律,，作出必要,简化假设,，,利用适当,数学工具,，得到一个,数学结构,。,建立数学模型全过程,（包含表述、求解、解释、检验等）,数学模型,数学建模,第4页,1.3,数学建模主要意义,电子计算机出现及飞速发展；,数学以空前广度和深度向一切领域渗透。,数学建模作为用数学方法处理实际问题第一步，越来越受到人们重视。,在普通工程技术领域数学建模依然大有用武之地；,在高新技术领域数学建模几乎是必不可少工具；,数学进入一些新领域，为数学建模开辟了许多处女地。,第5页,数学建模详细应用,分析与设计,预报与决议,控制与优化,规划与管理,数学建模,计算机技术,知识经济,如虎添翼,第6页,数学建模基本方法,机理分析,测试分析,依据对客观事物特征认识，,找出反应内部机理数量规律,将对象看作“黑箱”,经过对量测数据,统计分析，找出与数据拟合最好模型,机理分析没有统一方法，主要经过实例研究,(Case Studies),来学习。以下建模主要指机理分析。,二者结合,用机理分析建立模型结构,用测试分析确定模型参数,1.4,数学建模方法和步骤,第7页,数学建模普通步骤,模型准备,模型假设,模型组成,模型求解,模型分析,模型检验,模型应用,模,型,准,备,了解实际背景,明确建模目标,搜集相关信息,掌握对象特征,形成一个,比较清楚,问题,第8页,模,型,假,设,针对问题特点和建模目标,作出合理、简化假设,在合理与简化之间作出折中,模,型,构,成,用数学语言、符号描述问题,发挥想像力,使用类比法,尽可能采取简单数学工具,数学建模普通步骤,第9页,模型,求解,各种数学方法、软件和计算机技术,如结果误差分析、统计分析、,模型对数据稳定性分析,模型,分析,模型,检验,与实际现象、数据比较，,检验模型合理性、适用性,模型应用,数学建模普通步骤,第10页,数学建模全过程,现实对象信息,数学模型,现实对象解答,数学模型解答,表述,求解,解释,验证,(,归纳,),(,演绎,),表述,求解,解释,验证,依据建模目标和信息将实际问题“翻译”成数学问题,选择适当数学方法求得数学模型解答,将数学语言表述解答“翻译”回实际对象,用现实对象信息检验得到解答,实践,现实世界,数学世界,理论,实践,第11页,近几年全国大学生数学建模竞赛题,第12页,第13页,第14页,第15页,第16页,第17页,真是月亮惹祸吗?,第18页,三国人物：谁是天下第一？,第19页,图论与网络优化,一、最小生成树问题,二、最短路问题,第20页,哥尼斯堡七桥问题,C,A,D,B,抽象为图问题：,图,G(V,E),能经过每条边恰好一次回到原点 每个顶点与偶数条边相关联,图,G(V,E),Fleury,算法,网络优化及实例,从某点出发，经过图上每条边恰好一次回到原点,Euler,周游,图,G(V,E),有,Euler,周游 图,G(V,E),无奇点,第21页,例：中国邮递员问题,(CPP-Chinese Postman Problem),一名邮递员负责投递某个街区邮件,.,怎样设计一条最短投递路线,(,从邮局出发，经过投递区内每条街道,最少一次,，最终返回邮局,),？因为这一问题是我国学者,管梅谷,教授,1960,年首先提出，所以国际上称之为中国邮递员问题,.,给定一个图，问是否存在点不重的环游？,例：,1973,年，,John,和,Edmonds,结合,Fleury,算法给出好算法,第22页,图与网路基本概念,6.1.1,图与网路,顶点(,Vertex,),物理实体、事物、概念,普通,用,v,i,表示,边(,Edge,),顶,点间连线，表示相关联,普通,用,e,ij,表示,图(,Graph,),顶,点和边集合,普通用 G(,V,E,)表示,顶,点集,V,=,v,1,v,2,v,n,边集,E,=,e,ij,网路,(,Network,),边上含有表示连接强度权值，如,w,ij,又称加权图,(,Weighted graph,)第23页,全部边都没有方向图称为无向图,在无向图中,e,ij,=,e,ji,，或,(,v,i,v,j,)=(,v,j,v,i,),当全部边都有方向时，称为有向图，用,G(,V,A,),表示,在有向图中，有向边又称为弧，用,a,ij,表示，,i,j,次序是不能颠倒，图中弧方向用箭头标识,图中现有边又有弧，称为混合图,无向图与有向图,第24页,第25页,返回,完备图,二元图,完备二元图,第26页,顶点次数,第27页,例,在一次聚会中，认识奇数个人人数一定是偶数。,返回,第28页,子图,返回,第29页,关联矩阵,注：假设图为简单图,返回,第30页,邻接矩阵,注：假设图为简单图,第31页,返回,第32页,例 甲、乙、丙、丁、戊五个球队比赛情况。,v,5,v,1,v,3,v,4,v,2,v,1,v,2,v,3,v,4,v,5,v,5,v,1,v,3,v,4,v,2,第33页,某单位储存八种化学药品，其中一些药品不能存放在同一个仓库，考虑所需最少仓库数,v,5,v,1,v,2,v,3,v,4,v,6,v,7,v,8,最少四个库房：,1,，,2,，,5,，,8,任意两个不能同存,1,，,3,，,4,，,7,2,5,8,，,6,第34页,边与顶点均不重复通路称为路径,路：,v,i1,v,i2,v,in-2,v,in-1,v,in,v,i3,v,ij,v,ik,jk,路径,第35页,返回,第36页无圈连通图,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,树：,G,生成树,(spanning tree):T(V,E,),是图,G(V,E),子图,且是一棵树,最小生成树,:T(V,E,),是图,G(V,E),全部生成树中权重最小一棵,第37页,树,图与最小生成树,普通研究无向图,树图：倒置树，根,(,root,),在上，树叶,(,leaf,),在下,多级辐射制电信网络、管理指标体系、家谱、分类学、组织结构等都是经典树图,第38页,例 在五个村庄之间修路，使任一村庄可到其余各村庄。已知各村庄间修路所需费用以下列图，考虑费用最省方案。,v,5,v,1,v,2,v,3,v,4,50,15,30,10,30,10,25,20,40,50,(,万元,),1,2,3,4,5,1,50,30,40,25,2,50,15,30,50,3,30,15,10,10,4,40,30,10,20,5,25,50,10,20,问题即为求对应图最小生成树,第39页,最小生成树求解方法：,避圈法；破圈法,避圈法,v,2,v,3,v,4,50,15,30,10,30,10,25,20,40,50,1,2,3,4,v,1,v,5,v,1,v,2,v,3,v,4,1510,10,25,权重为,60,最小生成树为：,v,5,Kruskal,算法,第40页,v,2,v,3,v,4,50,15,30,10,30,10,25,20,40,50,v,1,v,5,6,3,5,4,2,1,权重为,60,最小生成树为：,破,圈法,v,5,v,1,v,2,v,3,v,4,15,10,10,25,第41页,权矩阵,v,1,v,2,v,3,v,4,v,5,v,1,50,30,40,25,v,2,50,15,30,50,v,3,30,15,10,10,v,4,40,30,10,20,v,5,25,50,10,20,(w,ij,)=,第,1,列叉,第,1,行最小圈,.,圈列叉,第1,，,5,行最小圈,.,圈列叉,v,1,v,2,v,3,v,4,v,5,v,1,50,30,40,25,v,2,50,15,30,50,v,3,30,15,10,10,v,4,40,30,10,20,v,5,25,50,10,20,第,1,4,5,行最小圈,.,圈列叉,v,5,25,v,1,v,5,25,v,1,v,3,10,第42页,权矩阵,v,1,v,2,v,3,v,4,v,5,v,1,50,30,40,25,v,2,50,15,30,50,v,3,30,15,10,10,v,4,40,30,10,20,v,5,25,50,10,20,(w,ij,)=,第,1,列叉,第,1,行最小圈,圈列叉,第,1,，,5,行最小圈,.,圈列叉,v,1,v,2,v,3,v,4,v,5,v,1,50,30,40,25,v,2,50,15,30,50,v,3,30,15,10,10,v,4,40,30,10,20,v,5,25,50,10,20,第,1,4,5,行最小圈,.,圈列叉,v,1,v,2,v,3,v,4,v,5,v,1,50,30,40,25,v,2,50,15,30,50,v,3,30,15,10,10,v,4,40,30,10,20,v,5,25,50,10,20,第,1,3,4,5,行最小圈,.,圈列叉,v,1,v,2,v,3,v,4,v,5,v,1,50,30,40,25v,2,50,15,30,50,v,3,30,15,10,10,v,4,40,30,10,20,v,5,25,50,10,20,v,5,v,1,v,2,v,3,v,4,15,10,10,25,v,5,25,v,1,v,5,25,v,1,v,3,10,v,5,v,1,v,4,10,10,25,v,3,第43页,一、问题提法及应用背景,（,1,）问题提法,寻求网络中两点间最短路就是寻求连接这两个点边,总权数为最小通路,。,（,2,）应用背景,管道铺设、线路安排、厂区布局、设备更新等。,最短路问题,(,非负权,),第44页,二、最短路算法：,1,D,氏标号法（,Dijkstra,）,（,1,）求解思绪,从始点出发，逐步,次序地向外探寻,，,每向外延伸一步都要求是,最短。,（,2,）使用条件,网络中,全部弧权,均,非负,，即 。,第45页,最短路问题,(,非负权,),例 有五个位置，其间路都是单行道。详细方向及距离见下列图。求由位置,1,到其它各个位置怎么走路途最短。,v,5,v,1,v,2,v,3,v,4,2,4,4,3,10,1,2,1,转化为求,v,1,到其它全部顶点最短路,权矩阵,v,1,v,2,v,3,v,4,v,5,v,1,1,10,5,4,v,2,4,v,3,3,2,v,4,2,v,5,1,(w,ij,)=,5,第46页,v,1,v,2,v,3,v,4,v,5,v,1,1,10,5,4,v,2,4,v,3,3,2,v,4,2,v,5,1,(w,ij,)=,第,1,列叉,第,1,行最小圈,.,圈列叉,1,v,1,v,2,v,3,v,4,v,5,v,1,1,10,5,4,v,2,5,v,3,3,2,v,4,2,v,5,1,1,对应行加,1,第,1,2,行最小圈,圈列叉,4,对应行加,4,第,1,2,5,行最小圈,圈列叉,v,1,v,2,v,3,v,4,v,5,v,1,1,10,5,4,v,2,5,v,3,3,2,v,4,2,v,5,5,1,4,5,对应行加,5,第,1,2,4,5,行最小圈,圈列叉,v,1,v,2,v,3,v,4,v,5,v,1,1,10,5,4,v2,5,v,3,3,2,v,4,7,v,5,5,1,4,5,7,第47页,可化为最短路问题多阶段决议问题,第48页,返回,第49页,选址问题,-,中心问题,第50页,S(v,1,)=10,S(v,2,)=7,S(v,3,)=6,S(v,4,)=8.5,S(v,5,)=7,S(v,6,)=7,S(v,7,)=8.5,S(v,3,)=6,故应将消防站设在v,3,处。,返回,第51页,选址问题,-,重心问题,返回,第52页,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,e,6,欧 拉 图,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,周游,：,v1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,e,5,v,1,欧拉道路：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,欧拉,周游,：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,e,6,v,1,第53页,图,G(V,E),有,Euler,周游充要条件是图,G(V,E),无奇点,Fleury,算法,-,基本思想,：从任一点出发，每当访问一条边时，先要进行检验假如可供访问边不只一条，则应选一条不是未访问边集导出子图,割边,作为访问边，直到没有边可选择为止,.,割边定义,：设,G,连通，,e E(G),若从,G,中删除边,e,后，图,G-e,不连通，则称边,e,为图,G,割边,V,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,V,5,V,6,e,6,e,7,e,8,e,9,割边,G边e是割边充要条件是e不含在G圈中,第54页,V,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,V,5,V,6,e,6,e,7,e,8,e,9,e,10,第55页,中国邮递员问题,-,算法,若G不是欧拉图，则G任何一个巡回经过一些边必定多于一次,处理这类问题普通方法是，在一些点对之间,引入重复边（重复边与它平行边含有相同权），使原图成为欧拉图，但希望全部添加重复边,权总和为最小,第56页,V,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,V,5,V,6,e,6,e,7,e,8,e,9,第57页,第58页,（）求出,G1,最小权理想匹配,M,，得到奇次顶点最正确配对,第59页,第60页,返回,第61页,哈 密 尔 顿 图,返回,第62页,推销员问题,-,定义,流动推销员需要访问某地域全部城镇，最终回到出发点问怎样安排旅行路线使总行程最小这就是,推销员问题,若用顶点表示城镇，边表示连接两城镇路，边上权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点最少一次最短闭通路问题,第63页,定义,在加权图,G=(V,E),中，,（）权最小哈密尔顿圈称为,最正确,H,圈,（）经过每个顶点最少一次权最小闭通路称为,最正确推销员回路,普通说来，最正确哈密尔顿圈不一定是最正确推销员回路，一样最正确推销员回路也不一定是最正确哈密尔顿圈,H,回路，长,22,最正确推销员回路，长,4,第64页,第65页,推销员问题近似算法：,二边逐次修正法,：,第66页,第67页,