数学建模题目080420课件

玩具、照片、飞机、火箭模型……~实物模型地图、电路图、分子结构图……~符号模型模型是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物模型集中反映了原型中人们需要的那一部分特征1.2

从现实对象到数学模型我们常见的模型玩具、照片、飞机、火箭模型……~实物模型地图、电路图、分1你碰到过的数学模型——“航行问题”用x

表示船速，y表示水速，列出方程：答：船速每小时20千米/小时.甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需50小时，问船的速度是多少?x=20y=5求解你碰到过的数学模型——“航行问题”用x表示船速，y表示2航行问题建立数学模型的基本步骤作出简化假设（船速、水速为常数）；用符号表示有关量（x,y表示船速和水速）；用物理定律（匀速运动的距离等于速度乘以时间）列出数学式子（二元一次方程）；求解得到数学解答（x=20,y=5）；回答原问题（船速每小时20千米/小时）。航行问题建立数学模型的基本步骤作出简化假设（船速、水速为常3数学模型(MathematicalModel)和数学建模（MathematicalModeling)对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。建立数学模型的全过程（包括表述、求解、解释、检验等）数学模型数学建模数学模型(MathematicalModel)和对于一41.3

数学建模的重要意义电子计算机的出现及飞速发展；数学以空前的广度和深度向一切领域渗透。数学建模作为用数学方法解决实际问题的第一步，越来越受到人们的重视。

在一般工程技术领域数学建模仍然大有用武之地；

在高新技术领域数学建模几乎是必不可少的工具；

数学进入一些新领域，为数学建模开辟了许多处女地。1.3数学建模的重要意义电子计算机的出现及飞速发展；5数学建模的具体应用

分析与设计

预报与决策

控制与优化

规划与管理数学建模计算机技术知识经济如虎添翼数学建模的具体应用分析与设计预报与决策控制与优化规6数学建模的基本方法机理分析测试分析根据对客观事物特性的认识，找出反映内部机理的数量规律将对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究(CaseStudies)来学习。以下建模主要指机理分析。二者结合用机理分析建立模型结构,用测试分析确定模型参数1.4

数学建模的方法和步骤数学建模的基本方法机理分析测试分析根据对客观事物特性的认识7数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用模型准备了解实际背景明确建模目的搜集有关信息掌握对象特征形成一个比较清晰的‘问题’数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析8模型假设针对问题特点和建模目的作出合理的、简化的假设在合理与简化之间作出折中模型构成用数学的语言、符号描述问题发挥想像力使用类比法尽量采用简单的数学工具数学建模的一般步骤模针对问题特点和建模目的作出合理的、简化的假设在合理与简化之9模型求解各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型分析模型检验与实际现象、数据比较，检验模型的合理性、适用性模型应用数学建模的一般步骤模型各种数学方法、软件和计算机技术如结果的误差分析、统计分析10数学建模的全过程现实对象的信息数学模型现实对象的解答数学模型的解答表述求解解释验证(归纳)(演绎)表述求解解释验证根据建模目的和信息将实际问题“翻译”成数学问题选择适当的数学方法求得数学模型的解答将数学语言表述的解答“翻译”回实际对象用现实对象的信息检验得到的解答实践现实世界数学世界理论实践数学建模的全过程现实对象的信息数学模型现实对象的解答数学模型11

近几年全国大学生数学建模竞赛题近几年全国大学生数学建模竞赛题12数学建模题目080420课件13数学建模题目080420课件14数学建模题目080420课件15数学建模题目080420课件16数学建模题目080420课件17真是月亮惹的祸吗?真是月亮惹的祸吗?18三国人物：谁是天下第一？三国人物：谁是天下第一？19图论与网络优化一、最小生成树问题二、最短路问题图论与网络优化一、最小生成树问题二、最短路问题20哥尼斯堡七桥问题CADB抽象为图的问题：图G(V,E)能经过每条边恰好一次回到原点每个顶点与偶数条边相关联图G(V,E)Fleury算法网络优化及实例从某点出发，经过图上每条边恰好一次回到原点—Euler环游图G(V,E)有Euler环游图G(V,E)无奇点哥尼斯堡七桥问题CADB抽象为图的问题：图G(V,E)能经过21例：中国邮递员问题(CPP-ChinesePostmanProblem)一名邮递员负责投递某个街区的邮件.如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.给定一个图，问是否存在点不重的环游？例：1973年，John和Edmonds结合Fleury算法给出好算法例：中国邮递员问题(CPP-ChinesePostman22图与网路的基本概念6.1.1图与网路顶点(Vertex)物理实体、事物、概念一般用vi

表示边(Edge)顶点间的连线，表示有关联一般用eij

表示图(Graph)顶点和边的集合一般用G(V,E)表示顶点集V={v1,v2,…,vn}边集E={eij}网路(Network)边上具有表示连接强度的权值，如wij又称加权图(Weightedgraph)图与网路的基本概念6.1.1图与网路网路(Net23所有边都没有方向的图称为无向图在无向图中eij=eji，或(vi,vj)=(vj,vi)当所有边都有方向时，称为有向图，用G(V,A)表示在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图无向图与有向图所有边都没有方向的图称为无向图无向图与有向图24数学建模题目080420课件25返回完备图

二元图

完备二元图

返回完备图二元图完备二元图26顶点的次数顶点的次数27例在一次聚会中，认识奇数个人的人数一定是偶数。返回例在一次聚会中，认识奇数个人的人数一定是偶数。返回28子图返回子图返回29关联矩阵注：假设图为简单图返回关联矩阵注：假设图为简单图返回30邻接矩阵注：假设图为简单图邻接矩阵注：假设图为简单图31返回返回32例甲、乙、丙、丁、戊五个球队比赛情况。v5v1v3v4v2v1v2v3v4v5v5v1v3v4v2例甲、乙、丙、丁、戊五个球队比赛情况。v5v1v3v4v233某单位储存八种化学药品，其中某些药品不能存放在同一个仓库，考虑所需最少仓库数v5v1v2v3v4v6v7v8至少四个库房：1，2，5，8任意两个不能同存1，3，4，7258，6某单位储存八种化学药品，其中某些药品不能存放在同一个仓库，考34边与顶点均不重复的通路称为路径路：vi1vi2vin-2……vin-1vinvi3vij≠vik,j≠k……路径边与顶点均不重复的通路称为路径路：vi1vi2vin-2…35返回返回36无圈连通图v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8树：G的生成树(spanningtree):T(V,E’)是图G(V,E)的子图,且是一棵树最小生成树:T(V,E’)是图G(V,E)所有生成树中权重最小的一棵无圈连通图v1v2v3v4v5v6v7v8v1v2v3v4v37树图与最小生成树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图树图与最小生成树一般研究无向图38例在五个村庄之间修路，使任一村庄可到其余各村庄。已知各村庄间修路所需费用如下图，考虑费用最省方案。v5v1v2v3v450153010301025204050(万元)123451∞5030402525010104403010∞20525501020∞问题即为求对应图的最小生成树例在五个村庄之间修路，使任一村庄可到其余各村庄。已知各村庄39最小生成树求解方法：避圈法；破圈法避圈法v2v3v4501530103010252040501234v1v5v1v2v3v415101025权重为60最小生成树为：v5Kruskal算法最小生成树求解方法：避圈法；破圈法避圈法v2v3v4501540v2v3v450153010301025204050v1v5635421权重为60最小生成树为：破圈法v5v1v2v3v415101025v2v3v450153010301025204050v1v541权矩阵v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞(wij)=第1列叉,第1行最小圈.圈列叉第1，5行最小圈.圈列叉v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞第1,4,5行最小圈.圈列叉v525v1v525v1v310权矩阵v1v2v3v4v5v1∞50304025v25042权矩阵v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞(wij)=第1列叉,第1行最小圈.圈列叉第1，5行最小圈.圈列叉v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞第1,4,5行最小圈.圈列叉v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞第1,3,4,5行最小圈.圈列叉v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞v5v1v2v3v415101025v525v1v525v1v310v5v1v4101025v3权矩阵v1v2v3v4v5v1∞50304025v25043一、问题的提法及应用背景

（1）问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的通路。（2）应用背景——管道铺设、线路安排、厂区布局、设备更新等。最短路问题(非负权)一、问题的提法及应用背景（1）问题的提法——寻求网络中两点44二、最短路算法：

1．D氏标号法（Dijkstra）（1）求解思路——从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。

（2）使用条件——网络中所有的弧权均

非负，即。二、最短路算法：

1．D氏标号法（Dijkstra）（2）45最短路问题(非负权)例有五个位置，其间的路都是单行道。具体方向及距离见下图。求由位置1到其他各个位置怎么走路途最短。v5v1v2v3v4244310121转化为求v1到其他所有顶点的最短路权矩阵v1v2

v3v4v5v1

∞11054v2∞∞∞∞4v3∞3∞∞2v4∞∞2∞∞v5∞∞∞1∞(wij)=5最短路问题(非负权)例有五个位置，其间的路都是单行道。具体46v1v2

v3v4v5v1

∞11054v2∞∞∞∞4v3∞3∞∞2v4∞∞2∞∞v5∞∞∞1∞(wij)=第1列叉,第1行最小圈.圈列叉1v1v2

v3v4v5v1

∞11054v2∞∞∞∞5v3∞3∞∞2v4∞∞2∞∞v5∞∞∞1∞1对应行加1,第1,2行最小圈,圈列叉4对应行加4,第1,2,5行最小圈,圈列叉v1v2

v3v4v5v1

∞11054v2∞∞∞∞5v3∞3∞∞2v4∞∞2∞∞v5∞∞∞5∞145对应行加5,第1,2,4,5行最小圈,圈列叉v1v2

v3v4v5v1

∞11054v2∞∞∞∞5v3∞3∞∞2v4∞∞7∞∞v5∞∞∞5∞1457v1v2v3v4v5v1∞11054v2∞∞∞∞4v3∞47可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题48返回返回49

选址问题--中心问题选址问题--中心问题50S(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处。返回S(v1)=10,S(v2)=7,S(v3)=6,S(51

选址问题--重心问题返回选址问题--重心问题返回52e3v1v2v3v4e1e2e4e5e6欧拉图e3v1v2v3v4e1e2e4e5环游

：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉环游：v1e1v2e2v3e5v1e4v4e3v3e6v1e3v1v2v3v4e1e2e4e5e6欧拉图e3v1v53图G(V,E)有Euler环游充要条件是图G(V,E)无奇点

Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.割边的定义：设G连通，eE(G),若从G中删除边e后，图G-{e}不连通，则称边e为图G的割边．V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边G的边e是割边的充要条件是e不含在G的圈中．图G(V,E)有Euler环游充要条件是图G(V,E)无奇点54V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10V7e3v1v2v3v4e1e2e4e5V5V6e6e7e85