数学建模交流.ppt

数学建模 雷涛 罗睿辞 王尧 汪瑜婧 数学建模的定义 目前还没有统一的定义 数学模型是为一种特殊目的而建立的一个抽象的、简化的结构。 描述现实世界的一部分特征 表现事物之间的一部分客观联系 数学模型的分类 微分方程模型 差分方程模型 层次分析模型 线性规划模型 动态规划模型 图论模型 其它模型 主要内容 建模的方法和步骤 ——汪瑜婧 图论模型的建立 ——罗睿辞 图论模型的选择和关系的简化 ——雷涛 其它数学模型举例 ——王尧 建模的方法和步骤 模型准备 模型假设 模型的建立 模型求解与分析 模型检验 模型应用 问题的提出 2007CUMCM B题 乘公交，看奥运 给定若干条公交线路，以及在每条公交线路中任意相邻的两站之间所花费的时间。 并且给定乘客在任意站点换乘的耗时 要求给出任意两公汽站点之间线路选择问题的一般数学模型与算法，求出最佳的公交线路. 模型的假设 对”最优”的理解有三个具有代表性的指标： 时间最短 花费最少 最方便（换乘次数最少） 不同的人群对最优的理解不同,需要根据实际定义.可以根据需要定义代价函数,三个指标的权重不同,代价值也不同。 以时间最短为例 模型的建立 G=(V,E) 每个车站：G的顶点 每条公交线路相邻两点的连线：G的边 边的权重：耗费时间 点的权重：换乘时间 并不是一个简单图，两点间可能有多条边 与经典最短路径问题比较 考虑a经过b到c的最短路径 由于有换乘的情况，只记录任意两点间的最短路径是不够的。 并非一个标准的图论模型 转化成标准的图论模型 回顾上图 导致无法使用标准算法原因: Min(a,b)和Min(b,c)之间需要计算附加耗时 不用换车的线路成为最佳路径 改进的想法:一次性地处理不用换车的情况 模型的求解 标准算法: 每次选择一个新顶点进行扩展 所有顶点扩展完毕即为最优解 修改后的算法 每次对一个顶点所能选择的所有公交线路扩展 所有不用换乘就能到达的顶点均在一次中处理 所有顶点扩展完毕即为最优解. 算法描述 一次将扩展出多个顶点,用最小值堆保存 初始: 起点对应的节点S入堆；并赋予标志信息Time(S)=0 取堆顶,对此定点,逐一枚举所有不用换乘就能到达的顶点,更新堆中对应点的标志信息. 不断重复取堆顶的过程,直到取出的顶点为最终目标T Time(T)即为所求 举例说明算法步骤 问题重述 加入步行的因素,即任意两个车站之间人都可能通过步行到达,并给出步行的时间代价. 由于每两点之间均有步行路径,每次扩展都将涉及到所有顶点,复杂度增加不少 改进的办法 预处理 找到两个相邻顶点之间路径的最小值,如果它加上两个顶点的权值之后后,仍然小于一些其它的路径,就可以将其它路径删除.这样至少 可以删除不少步行路径 考虑实际情况,可设定步行时间的上限. 算法的总结 关键在于如何解决换乘的耗时 扩展节点的策略与经典算法不同 算法实际用到了分支界限法的思想 类似于回溯法，但是求解的目标不同。 目标：找到使目标函数取极值的解。 分支界限法思想 以广度优先或以最小耗费（最大效益）优先的方式有哪些信誉好的足球投注网站问题的解空间树 从一个点开始，每次以一定的策略扩展一些结点。每一个活结点一旦成为扩展结点，就一次性产生其所有子结点，并从活节点中移除。在产生 的子结点中，导致不可行解或导致非最优解的子结点被舍弃，其余的加入活结点表中。 选择扩展的节点 从活结点表中选择下一扩展结点可能有不同的方式 队列式分支限界法：先入先出的原则 优先队列式分支限界法：选择优先级最高的节点进行扩展 最大效益问题：最大值堆 最小耗费问题：最小值堆 一个简单的例子 印刷电路板将布线区域划分为n×m个方格阵列 精确的电路板布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。 布线时电路只能沿直线或直角布线。 为避免线路相交，已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。 建模步骤的总结 模型的准备 提出问题，搜集数据。 模型的假设 根据实际情况，提出合理的假设简化问题。 模型的建立 根据所作的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，构造各个量间的等式关系或其它数学结构。 建模步骤的总结 模型的分析与求解 已建立的模型是否有标准解法 转化成标准模型 对已有的标准解法修改，以适应模型的求解 模型的检验 灵敏性，鲁棒性 模型的应用 图论模型的引入 引例 现有6个人，任意两人之间或者相互认识，或者相互不认识，证明这6个人中，或者有3个人彼此都认识，或者有3个人彼此不认识 思路一 只有6个人，人数非常少，可以枚举任意两人之间的关系，然后判断每一种情况是否符合题意。如果