数学建模之网络优化与优化算.ppt

该【数学建模之网络优化与优化算 】是由【utuhlwwue61571】上传分享，文档一共【25】页，该文档可以免费在线阅读，需要了解更多关于【数学建模之网络优化与优化算 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。单击此处添加文本具体内容，简明扼要地阐述你的观点
202X
网络优化与优化算法
一、网络优化及实例
例：中国邮递员问题(CPP-Chinese Postman Problem)
一名邮递员负责投递某个街区的邮件. 如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.
单向？
双向？
欧拉把哥尼斯堡七桥问题转化为一个图论上的问题：
给定一个图，问是否存在点不重的环游？
01
02
03
04
05
答案
的
是
否定的
因为图中没有偶度顶点
七桥问题
也没有快速求解最优解的方法
1
TSP（Travel Sales Man Problem）问题
2
例4
3
设有城市集合
4
，城市
5
到城市
6
的费用为
7
求从指定城市出发，经过所有其他城市恰好
一次，且使总费用最少的旅行路线。
8
有些问题目前找不到现成的软件
TSP问题可以通过枚举的方法用计算机求解
不同的路线共有(n-1)！条
枚举城市数与计算时间的关系
城市数 24 25 26 27 28 29 30 31
计算时间1s 24s 10m 325a
当城市个数增大到一定数量时枚举方法
行不通  !
二、最优算法与近似算法
有一些问题在计算复杂性上被称做NP困难问题,对这一类问题寻找快速的近似算法是十分有意义的。
全国数学建模竞赛题中有一些NP困难问题的
例子，需要用现有的软件结合编程进行计算，
这一类近似算法的设计需要较宽的数学知识
面和较强的创新能力
数学建模竞赛十分强调模型与
算法的创新性
如：98年竞赛题B题是TSP问题的一个变形
从县城出发分三个小组巡视受灾的地区各地的灾情，已知每个村镇所需要的停留时间以及行车速度，问如何设计各组的巡视路线才能以最快的速度掌握整个地区全部的受灾情况？
灾情巡视路线(CUMCM-1998B)
多人TSP问题的扩展
01
考虑用一个 图来代替县城结点，
02
将问题转化为一个TSP问题：