数学建模 雷涛罗睿辞王尧汪瑜婧
数学建模 雷涛 罗睿辞 王尧 汪瑜婧
数学建模的定义 目前还没有统一的定义 数学模型是为一种特殊目的而建立 的一个抽象的、简化的结构。 ·描述现实世界的一部分特征 ·表现事物之间的一部分客观联系
数学建模的定义 • 目前还没有统一的定义 • 数学模型是为一种特殊目的而建立 的一个抽象的、简化的结构。 • 描述现实世界的一部分特征 • 表现事物之间的一部分客观联系
数学模型的分类 ·微分方程模型 差分方程模型 层次分析模型 线性规划模型 动态规划模型 图论模型 其它模型
数学模型的分类 • 微分方程模型 • 差分方程模型 • 层次分析模型 • 线性规划模型 • 动态规划模型 • 图论模型 • 其它模型
主要内容 建模的方法和步骤 汪瑜婧 图论模型的建立 罗睿辞 图论模型的选择和关系的简化 雷涛 其它数学模型举例 王尧
主要内容 • 建模的方法和步骤 ——汪瑜婧 • 图论模型的建立 ——罗睿辞 • 图论模型的选择和关系的简化 ——雷涛 • 其它数学模型举例 ——王尧
建模的方法和步骤 模型准备 模型假设 模型的建立 模型求解与分析 模型检验 模型应用
建模的方法和步骤 • 模型准备 • 模型假设 • 模型的建立 • 模型求解与分析 • 模型检验 • 模型应用
问题的提出 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为公交线路的总数