数学建模之网络优化与优化算法ppt课件.ppt
《数学建模之网络优化与优化算法ppt课件.ppt》由会员分享,可在线阅读,更多相关《数学建模之网络优化与优化算法ppt课件.ppt(25页珍藏版)》请在文库网上搜索。
1、网络优化与优化算法 1 例:中国 (CPP-Chinese Postman Problem) 一名邮递员负责投递某个街区的邮件. 如何设计一条最短 的投递路线(从邮局出发,经过投递区内每条街道至少一次 ,最后返回邮局)?由于这一问题是我国学者管梅谷教授 1960年首先提出的,所以国际上称之为中国邮递员问题. 一、网络优化及实例 单向? 双向? 2 n欧拉把哥尼斯堡七桥问题转化为一个 图论上的问题: 3 七桥问题 答案 的 是 否定的否定的 因为图中没有偶度顶点 4 有些问题目前找不到现成的软件 n也没有快速求解最优解的方法 TSP(Travel Sales Man Problem)问题 例4
2、设有城市集合 ,城市 到城市的费用为 求从指定城市出发,经过所有其他城市恰好 一次,且使总费用最少的旅行路线。 5 TSP问题可以通过枚举的方 法用计算机求解 n不同的路线共有(n-1)!条 枚举城市数与计算时间的关系 城市数 24 25 26 27 28 29 30 31 计算时间1s 24s 10m 4.3h 4.9d 136.5d10.8a 325a 当城市个数增大到一定数量时枚举方法 行不通 ! 6 二、最优算法与近似算法 n有一些问题在计算复杂性上被称做NP困难问题, 对这一类问题寻找快速的近似算法是十分有意义 的。 全国数学建模竞赛题中有一些NP困难问题的 例子,需要用现有的软件结
3、合编程进行计算, 这一类近似算法的设计需要较宽的数学知识 面和较强的创新能力 数学建模竞赛十分强调模型与 算法的创新性 7 如:98年竞赛题B题是TSP问题 的一个变形 n从县城出发分三个小组巡视受灾的地区各地的 灾情,已知每个村镇所需要的停留时间以及行 车速度,问如何设计各组的巡视路线才能以最 快的速度掌握整个地区全部的受灾情况? 8 灾情巡视路线(CUMCM-1998B) 多人TSP问题的扩展 9 考虑用一个 图来代替县城结点, 将问题转化为一个TSP问题: 10 再将三点收缩成一点,就得到 一个三个巡视组的TSP巡视路线 接下来的工作是要均衡各个巡视小组 的工作时间(十分复杂的工作!)
4、11 05年杭州电子科技大学校内竞赛题B题 是一个网络优化问题 桥梁选址问题 设下图中每一个圆点代表一个区,连接各圆点的 直线代表公路,粗实线代表交通主干线,曲线代 表一条河流。随着城市经济发展,为了便利河两岸 的交通,决定在适当的位置造桥。假设河流北侧 A到D段有沿岸公路,河的南侧当前还没有修建沿 岸公路。试分别就以下问题讨论: 12 n问题一:河流为东西向的水平直线,各 区规模大致相同。 1.总建设费用最低的桥梁位置和与之配套的 公路设计方案; 2.以便捷交通为原则的最佳桥梁位置和公路 设计方案。 问题二:河流为图中曲线,分别讨论总建设费 用最小化和以便捷交通为原则的建设方案。 问题三:如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 网络 优化 算法 ppt 课件