数学建模题目080420.ppt

,1985年由美国工业与应用数学学会和美国运筹 学会联合主办大学生数学建模竞赛（ MCM ),1.1 数学建模由来, 在上世纪70年代末和80年代初，英国著名的剑 桥大学专门为研究生开设了数学建模课程, 数学建模作为一门崭新的课程在20世纪80年代 进入我国高校，萧树铁先生1983年在清华大学首次为本科生讲授数学模型课程，他是我国高校开设数学模型课程的创始人,玩具、照片、飞机、火箭模型 , 实物模型,地图、电路图、分子结构图 , 符号模型,模型是为了一定目的，对客观事物的一部分 进行简缩、抽象、提炼出来的原型的替代物,模型集中反映了原型中人们需要的那一部分特征,1.2 从现实对象到数学模型,我们常见的模型,你碰到过的数学模型“航行问题”,用 x 表示船速，y 表示水速，列出方程：,答：船速每小时20千米/小时.,甲乙两地相距750千米，船从甲到乙顺水航行需30小时， 从乙到甲逆水航行需50小时，问船的速度是多少?,x =20 y =5,航行问题建立数学模型的基本步骤,作出简化假设（船速、水速为常数）；,用符号表示有关量（x, y表示船速和水速）；,用物理定律（匀速运动的距离等于速度乘以 时间）列出数学式子（二元一次方程）；,求解得到数学解答（x=20, y=5）；,回答原问题（船速每小时20千米/小时）。,数学模型 (Mathematical Model) 和 数学建模（Mathematical Modeling),对于一个现实对象，为了一个特定目的， 根据其内在规律，作出必要的简化假设， 运用适当的数学工具，得到的一个数学结构。,建立数学模型的全过程 （包括表述、求解、解释、检验等）,数学模型,数学建模,1.3 数学建模的重要意义,电子计算机的出现及飞速发展；,数学以空前的广度和深度向一切领域渗透。,数学建模作为用数学方法解决实际问题的第一步， 越来越受到人们的重视。,在一般工程技术领域数学建模仍然大有用武之地；,在高新技术领域数学建模几乎是必不可少的工具；,数学进入一些新领域，为数学建模开辟了许多处女地。,数学建模的具体应用,分析与设计,预报与决策,控制与优化,规划与管理,数学建模,计算机技术,知识经济,数学建模的基本方法,机理分析,测试分析,根据对客观事物特性的认识， 找出反映内部机理的数量规律,将对象看作“黑箱”,通过对量测数据的 统计分析，找出与数据拟合最好的模型,机理分析没有统一的方法，主要通过实例研究 (Case Studies)来学习。以下建模主要指机理分析。,二者结合,用机理分析建立模型结构, 用测试分析确定模型参数,1.4 数学建模的方法和步骤,数学建模的一般步骤,模 型 准 备,了解实际背景,明确建模目的,搜集有关信息,掌握对象特征,形成一个 比较清晰 的问题,模 型 假 设,针对问题特点和建模目的,作出合理的、简化的假设,在合理与简化之间作出折中,模 型 构 成,用数学的语言、符号描述问题,发挥想像力,使用类比法,尽量采用简单的数学工具,数学建模的一般步骤,模型 求解,各种数学方法、软件和计算机技术,如结果的误差分析、统计分析、 模型对数据的稳定性分析,模型 分析,模型 检验,与实际现象、数据比较， 检验模型的合理性、适用性,模型应用,数学建模的一般步骤,数学建模的全过程,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),表述,求解,解释,验证,根据建模目的和信息将实际问题“翻译”成数学问题,选择适当的数学方法求得数学模型的解答,将数学语言表述的解答“翻译”回实际对象,用现实对象的信息检验得到的解答,实践,现实世界,数学世界,近几年全国大学生数学建模竞赛题,真是月亮惹的祸吗?,三国人物：谁是天下第一？,图论与网络优化,一、最小生成树问题,二、最短路问题,哥尼斯堡七桥问题,C,A,D,B,抽象为图的问题：,图G(V,E)能经过每条边恰好一次回到原点 每个顶点与偶数条边相关联,图G(V,E),Fleury算法,网络优化及实例,从某点出发，经过图上每条边恰好一次回到原点Euler环游,图G(V,E)有Euler环游 图G(V,E)无奇点,例：中国邮递员问题(CPP-Chinese Postman Problem) 一名邮递员负责投递某个街区的邮件.如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.,给定一个图，问是否存在点不重的环游？,例：,1973年，John和 Edmonds结合Fleury算法给出好算法,图与网路的基本概念,6.1.1 图与网路 顶点 (Vertex) 物理实体、事物、概念 一般用 vi 表示 边 (Edge) 顶点间的连线，表示有关联 一般用 eij 表示 图 (Graph) 顶点和边的集合 一般用 G(V,E) 表示 顶点集 V=v1,v2, vn 边集E=eij ,网路 (Network) 边上具有表示连接强度的权值，如 wij 又称加权图(Weighted graph),所有边都没有方向的图称为无向图 在无向图中 eij=eji，或 (vi, vj)=(vj, vi) 当所有边都有方向时，称为有向图，用G(V,A)表示 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序是不能颠倒的，图中弧的方向用箭头标识 图中既有边又有弧，称为混合图,无向图与有向图,返回,完备图,二元图,完备二元图,顶点的次数,例 在一次聚会中，认识奇数个人的人数一定是偶数。,返回,子图,返回,关联矩阵,注：假设图为简单图,返回,邻接矩阵,注：假设图为简单图,返回,例 甲、乙、丙、丁、戊五个球队比赛情况。,v5,v1,v3,v4,v2,v1,v2,v3,v4,v5,v5,v1,v3,v4,某单位储存八种化学药品，其中某些药品不能存放在同一个仓库，考虑所需最少仓库数,v5,v1,v2,v3,v4,v6,v7,v8,至少四个库房：1，2，5，8任意两个不能同存,1，3，4，7,2,5,8，6,边与顶点均不重复的通路称为路径,路：,vi1,vi2,vin-2,vin-1,vin,vi3,vijvik, jk,路径,返回,无圈连通图,v1,v2,v3,v4,v5,v6,v7,v8,v1,v2,v3,v4,v5,v6,v7,v8,v1,v2,v3,v4,v5,v6,v7,v8,树：,G的生成树(spanning tree): T(V,E)是图 G(V,E)的子图,且是一棵树,最小生成树: T(V,E)是图G(V,E)所有生成树中权重最小的一棵,树图与最小生成树,一般研究无向图 树图：倒置的树，根(root)在上，树叶(leaf)在下 多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图,例 在五个村庄之间修路，使任一村庄可到其余各村庄。已知各村庄间修路所需费用如下图，考虑费用最省方案。,v5,v1,v2,v3,v4,50,15,30,10,30,10,25,20,40,50,问题即为求对应图的最小生成树,最小生成树求解方法：避圈法；破圈法,避圈法,v2,v3,v4,50,15,30,10,30,10,25,20,40,50,1,2,3,4,v1,v5,v1,v2,v3,v4,15,10,10,25,权重为60,最小生成树为：,v5,Kruskal算法,v2,v3,v4,50,15,30,10,30,10,25,20,40,50,v1,v5,6,3,5,4,2,1,权重为60,最小生成树为：,破圈法,v5,v1,v2,v3,v4,15,10,10,25,权矩阵,(wij)=,第1列叉,第1行最小圈.圈列叉,第1，5行最小圈.圈列叉,第1,4,5行最小圈.圈列叉,v5,25,v1,v5,25,v1,v3,10,权矩阵,(wij)=,第1列叉,第1行最小圈.圈列叉,第1，5行最小圈.圈列叉,第1,4,5行最小圈.圈列叉,第1,3,4,5行最小圈.圈列叉,v5,v1,v2,v3,v4,15,10,10,25,v5,25,v1,v5,25,v1,v3,10,v5,v1,v4,10,10,25,v3,一、问题的提法及应用背景,（1）问题的提法寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的通路。 （2）应用背景管道铺设、线路安排、厂区布局、设备更新等。,最短路问题(非负权),二、最短路算法：,1 D氏标号法（Dijkstra） （1）求解思路从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。,（2）使用条件网络中所有的弧权均 非负，即 。,最短路问题(非负权),例 有五个位置，其间的路都是单行道。具体方向及距离见下图。求由位置1到其他各个位置怎么走路途最短。,v5,v1,v2,v3,v4,2,4,4,3,10,1,2,1,转化为求v1到其他所有顶点的最短路,权矩阵,(wij)=,5,(wij)=,第1列叉,第1行最小圈.圈列叉,1,1,对应行加1,第1,2行最小圈,圈列叉,4,对应行加4,第1,2,5行最小圈,圈列叉,1,4,5,对应行加5,第1,2,4,5行最小圈,圈列叉,1,4,5,7,可化为最短路问题的多阶段决策问题,返回,选址问题-中心问题,S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5,S(v3)=6,故应将消防站设在v3处。,返回,选址问题-重心问题,返回,欧 拉 图,环游 ：v1e1v2e2v3e5v1e4v4e3v3e5v1,欧拉道路：v1e1v2e2v3e5v1e4v4e3v3,欧拉环游 ：v1e1v2e2v3e5v1e4v4e3v3e6v1,图G(V,E)有Euler环游充要条件是图G(V,E)无奇点,Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.,割边的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边,G的边e是割边的充要条件是e不含在G的圈中,中国邮递员问题-算法,若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是，在一些点对之间 引入重复边（重复边与它平行的边具有相同的权）， 使原图成为欧拉图，但希望所有添加的重复边的 权的总和为最小,（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对,返回,哈 密 尔 顿 图,返回,推销员问题-定义,流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最