北京大学:《数据结构与算法》课程教学资源(实习讲义)数学建模

数学建模 雷涛罗睿辞王尧汪瑜婧
数学建模 雷涛 罗睿辞 王尧 汪瑜婧

数学建模的定义 目前还没有统一的定义 数学模型是为一种特殊目的而建立 的一个抽象的、简化的结构。 ·描述现实世界的一部分特征 ·表现事物之间的一部分客观联系
数学建模的定义 • 目前还没有统一的定义 • 数学模型是为一种特殊目的而建立 的一个抽象的、简化的结构。 • 描述现实世界的一部分特征 • 表现事物之间的一部分客观联系

数学模型的分类 ·微分方程模型 差分方程模型 层次分析模型 线性规划模型 动态规划模型 图论模型 其它模型
数学模型的分类 • 微分方程模型 • 差分方程模型 • 层次分析模型 • 线性规划模型 • 动态规划模型 • 图论模型 • 其它模型

主要内容 建模的方法和步骤 汪瑜婧 图论模型的建立 罗睿辞 图论模型的选择和关系的简化 雷涛 其它数学模型举例 王尧
主要内容 • 建模的方法和步骤 ——汪瑜婧 • 图论模型的建立 ——罗睿辞 • 图论模型的选择和关系的简化 ——雷涛 • 其它数学模型举例 ——王尧

建模的方法和步骤 模型准备 模型假设 模型的建立 模型求解与分析 模型检验 模型应用
建模的方法和步骤 • 模型准备 • 模型假设 • 模型的建立 • 模型求解与分析 • 模型检验 • 模型应用

问题的提出 2007 CUMCM B题乘公交,看奥运 给定若干条公交线路,以及在每条公交线 路中任意相邻的两站之间所花费的时间 并且给定乘客在任意站点换乘的耗时 要求给出任意两公汽站点之间线路选择问 题的一般数学模型与算法,求出最佳的公 交线路
问题的提出 • 2007CUMCM B题 乘公交,看奥运 • 给定若干条公交线路,以及在每条公交线 路中任意相邻的两站之间所花费的时间。 • 并且给定乘客在任意站点换乘的耗时 • 要求给出任意两公汽站点之间线路选择问 题的一般数学模型与算法,求出最佳的公 交线路

模型的假设 对”最优”的理解有三个具有代表性的指模 时间最短 花费最少 最方便(换乘次数最少) 不同的人群对最优的理解不同,需要根据实 际定义可以根据需要定义代价函数,三个指 标的权重不同,代价值也不同 以时间最短为例
模型的假设 • 对”最优”的理解有三个具有代表性的指标: • 时间最短 • 花费最少 • 最方便(换乘次数最少) • 不同的人群对最优的理解不同,需要根据实 际定义.可以根据需要定义代价函数,三个指 标的权重不同,代价值也不同。 • 以时间最短为例

模型的建立 G=(V, B 每个车站:G的顶点 每条公交线路相邻两点的连线:G的边 边的权重:耗费时间点的权重:换乘时间 并不是一个简单图,两点间可能有多条边 7 5 b(8)
模型的建立 • G=(V,E) • 每个车站:G的顶点 • 每条公交线路相邻两点的连线:G的边 • 边的权重:耗费时间 点的权重:换乘时间 • 并不是一个简单图,两点间可能有多条边 5 9 3 7 a c b(8)

与经典最短路径问题比较 ·考虑a经过b到c的最短路径 由于有换乘的情况,只记录任意两点间的 最短路径是不够的 ·并非一个标准的图论模型 7 Min(a, b )=5 Min (b, c)=3 5 Min(a,C)=5+6=11 b(8)
• 考虑a经过b到c的最短路径 • 由于有换乘的情况,只记录任意两点间的 最短路径是不够的。 • 并非一个标准的图论模型 与经典最短路径问题比较 5 6 7 a c b(8) Min(a,b)=5 Min(b,c)=3 Min(a,c)=5+6=11 3

转化成标准的图论模型 每条公交线路抽象 为一层 层与层之间相连的 顶点均代表同一个 车站 C2 它们之间的边(虚 线)的权值为换乘 C3 花费的时间 调用MM次 Dijkstra算法才能得到最优解 M为公交线路的总数
转化成标准的图论模型 • 每条公交线路抽象 为一层 • 层与层之间相连的 顶点均代表同一个 车站 • 它们之间的边(虚 线)的权值为换乘 花费的时间 • 调用M*M次Dijkstra算法才能得到最优解 • M为公交线路的总数
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)搜索引擎技术介绍.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)搜索引擎技术介绍.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)图论习题课.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)图论习题课.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)数学建模与问题求解.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)数学建模与问题求解.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)动态规划.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)动态规划.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)分治法与时间复杂度计算.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)分治法与时间复杂度计算.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)贪心法.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)贪心法.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)回溯(Backtracking)基本原理.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)回溯(Backtracking)基本原理.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)基本算法与枚举法.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)基本算法与枚举法.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)租房信息专业搜索引擎项目计划书.doc
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)浅谈软件项目管理.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)浅谈软件项目管理.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习课件PPT)测试、性能和可扩展性.pdf
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)贪心法.ppt
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)算法优化.ppt
- 北京大学:《数据结构与算法》课程教学资源(实习讲义)递归、回溯与剪枝.ppt
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)课程简介、概论.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)第一章 概论.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)第二章 线性表、栈和队列.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班PPT课件)第二章 线性表、栈和队列.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)第三章 字符串.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班PPT课件)第三章 字符串.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)第四章 二叉树.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班PPT课件)第四章 二叉树.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)第五章 树.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班PPT课件)第五章 树.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)第六章 图.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班PPT课件)第六章 图.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)第七章 内排序.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班PPT课件)第七章 内排序.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)第八章 文件管理和外排序.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班PPT课件)第八章 文件管理和外排序.pdf
- 北京大学:《数据结构与算法》课程教学资源(实验班讲义)第九章 检索.pdf