数学建模(走遍全国)

12010年中国矿业大学徐海学院暑期数学建模集训承诺书我们仔细阅读了中国矿业大学徐海学院暑期数学建模集训的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C中选择一项填写）：A我们的参赛号为：201001参赛队员(打印并签名)：1.王奎2.仇文阳3.刘新云指导教师或指导教师组负责人(打印并签名)：教练组日期：2010年8月24日评阅编号（由组委会评阅前进行编号）：22010年中国矿业大学徐海学院暑期数学建模集训编号专用页评阅编号（由组委会评阅前进行编号）：评阅记录（可供评阅时使用）：评阅人评分备注统一编号：评阅编号：3A题：旅行方案张先生喜爱旅游，梦想游遍中国。今年他计划利用假期，从南京出发到全国所有的省份的省会城市、四个直辖市、两个特别行政区旅游。请你为他按下面要求制定旅行方案：1、根据地理位置设计行程，做到最短路线；2、张先生想7月1日出发，采取航空或铁路出行，每到一个城市游玩3天，若通过互联网订票，请为他设计最经济的订票方案；3、综合考虑时间短、经济、方便等因素，设定评价准则，调整你的方案。4走遍全中国摘要要从34个城市中制定最短的旅游路线，本文主要采动态规划方法求解，当然空间复杂性及时间复杂性都十分庞大。因此，为解决问题（1），本文采用分区域旅游，然后依次进行动态规划。这样就可以很好的解决了旅游城市数量大的缺点此方法节约计算资源，具有良好的可扩展性和实用性，给问题（2）和问题（3）奠定很好的基础。随着问题（1）的解决，问题（2）和问题（3）都是在问题一得出的路线最优解的前提下，设计省钱、省时又方便的互联网订票方案。本文将这个问题归结为多属性决策的问题。用层次分析法求解。（一）信息的获取：我们将中国交通网上把具体的时刻表、价位表、打折等相关的信息进行整理（见下文）。周先生的满意度本文主要通过对大部分人的满意度调查表的结果进行分析。（二）排序和择优：本文从不同的方面考虑各个属性的权值和所占的空间。得出的部分结果为：南京→上海→杭州→台北→福州→南昌→长沙→武汉→广州→香港→澳门→海口→南宁→贵阳→昆明→重庆→成都→拉萨→乌鲁木齐→西宁→兰州→银川→呼和浩特→北京→哈尔滨→长春→沈阳→天津→济南→石家庄→太原→西安→郑州→合肥→南京总距离：15917Km经济支出：20040元最优时间：102天关键词：动态分析层次分析经纬度、最短路线、订票方案、graph软件、满意度、MAYTLAB程序、综合评价5一、问题重述与分析1.1问题重述张先生喜爱旅游，梦想游遍中国。今年他计划利用假期，从南京出发到全国所有的省份的省会城市、四个直辖市、两个特别行政区旅游。请你为他按下面要求制定旅行方案：1、根据地理位置设计行程，做到最短路线；2、张先生想7月1日出发，采取航空或铁路出行，每到一个城市游玩3天，若通过互联网订票，请为他设计最经济的订票方案；3、综合考虑时间短、经济、方便等因素，设定评价准则，调整你的方案。1.2问题分析随着人们生活水平的不断提高，旅游已经成为人们忠爱的休闲方式之一。在制定旅游计划的同时需要考虑很多方面的问题，比如：旅游路线的选择、交通工具的选择、旅途用时、经济花销等等。为了在完成旅游计划的基础上实现省时、方便、经济的目标，需要制定一个最优的旅游方案。本文给出张先生的旅游计划既游遍中国的省会城市、直辖市、香港、澳门以及台北，要求达到旅途最短、经济、省时又方便的目的，为了实现这一目标，需要制定一个最优的旅游方案。首先要实现旅途最短，本问题属于多点的距离最短的问题，很显然，如果利用传统的动态规划解法在N为34的情况下，解法的空间复杂性及时间复杂性都十分庞大，不利于旅行方案的确定，因此，我们采用区域化的动态规划解法。将全国各个地方先进行区域划分，每一个区域进行动态分析。最后在通过各个区域的动态分析。最终达到游遍全国各个省会距离最短的目的。问题（2）和问题（3）都是模型的优化问题。我们主要是考虑了时间短、经济、方便、舒适等各个方面的因素等。本文将其归结为多重属性的决策问题。6二、模型的基本假设和符号说明2.1模型假设1.假设在旅途中旅游车的准时出发到达,且不考虑突发事件干扰车子的行程;2.在旅游的过程中,当天旅游目的地附近都有宾馆,且第一天的目的地就是第二天的出发点；3.在每个城市的吃饭、购物、在城市中观光景点等所需的费用费用视为相同；4.假设周先生自带充足食物，并不考虑住宿问题；在旅行过程中只考虑购票的经济花费，不考虑其他的消费5.票价不考虑除打折以外的其他优惠；6.旅游的这段时间内不会有价格变化;7.假设经纬线是均匀的；8.假设球面的地图可以看成平面；9.假设问题（3）中，参考的调查数据都是真实可靠地；10.假设周先生直接可以订购到台北的机票。2.2符号说明0A………………………………………………………………………………南京1A………………………………………………………………………………合肥2A………………………………………………………………………………郑州3A………………………………………………………………………………西安4A………………………………………………………………………………太原5A………………………………………………………………………………石家庄6A………………………………………………………………………………济南7A………………………………………………………………………………天津8A………………………………………………………………………………沈阳9A………………………………………………………………………………长春10A………………………………………………………………………………哈尔滨11A………………………………………………………………………………北京712A………………………………………………………………………………呼和浩特13A………………………………………………………………………………银川14A………………………………………………………………………………兰州15A………………………………………………………………………………西宁16A………………………………………………………………………………乌鲁木齐17A………………………………………………………………………………拉萨18A………………………………………………………………………………成都19A………………………………………………………………………………重庆20A………………………………………………………………………………昆明21A………………………………………………………………………………贵阳22A………………………………………………………………………………南宁23A………………………………………………………………………………海口24A………………………………………………………………………………澳门25A………………………………………………………………………………香港26A………………………………………………………………………………广州27A………………………………………………………………………………武汉28A………………………………………………………………………………长沙29A………………………………………………………………………………南昌30A………………………………………………………………………………福州31A………………………………………………………………………………台北32A………………………………………………………………………………杭州33A………………………………………………………………………………上海8三、模型的建立及求解3.1问题（1）模型的建立及求解3.1.1模型的建立定义（1）1()nnfA表示由1nA到nA的最短距离（2）1()nnfB表示由1nB到nA的最短距离下面用动态规划的方法计算。最短线路问题的特性：如果最短线路在第k站通过点kP，则这一线路在由kP出发到达终点的那一部分线路，对于从点kP到达终点所有可能选择的不同线路来说，必定也是距离最短的。（反正法）。最短线路问题的这一特性启示我们，从最后一段开始，用从后向前逐步递推的方法，求出各点到6A的最短线路，最后求得从0A到6A的最短线路。地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。A0A1B1D2C2B2A2A3B3C3A4A4A4A5B5A6图一k=6时：设65()fA表示由5A到6A的最短距离；65()fB表示由5B到6A的最短距离取min（65()fA，65()fB）9k=5时（1）从4A出发，有两种选择，到5A或5B，设54()fA表示由4A到6A的最短距离。45(,)dAA表示4A到5A的距离，54()uA表示从4A到5A或5B的选择，则54()fA=45654565(,)()min(,)()dAAfAdABfB54()uA=5B，最短线路是4A-5A-6A（2）从4B出发也有两种选择，即到4A或5B。54()fB，545(,)dBA，545(,)dBB，54()uB的定义与（1）类似，则54()fB=5456554565(,)()min(,)()dBAfAdBBfB54()uB=5B最短路线是4B-5B-6A（3）从4C出发，同样有54()fC=5456554565(,)()min(,)()dCAfAdCBfB545()uCB，最短线路是4C-5B-6Ak=4时：分别以3A,3B,3C为出发点计算得434544343454(,)()()min(,)()dAAfAfAdABfB434()uAB，最短线路是3A-4B-5B-6A434544343454(,)()()min(,)()dBBfBfBdBCfC434()uBB，最短线路是3B-4B-5B-6A434544343454(,)()()min(,)()dCBfBfCdCCfC434()uCB，最短线路是3C-4B-5B-6A10k=3时：分别以2A，2B，2C，2D为出发点计算得323433232343(,)()()min(,)()dAAfAfAdABfB323()uAA，323()uBA最短线路是2A-2B-4B-5B-6A323433232343(,)()()min(,)()dBAfAfBdBBfB323()uBA，最短线路是2B-3A-4B-5B-6A323433232343(,)()()min(,)()dCBfBfCdCCfC323()uCB，最短线路是2C-3B-4B-5B-6A323433232343(,)()()min(,)()dDBfBfDdDCfC323()uDC,最短线路是2D-3C-4B-5B-6Ak=2时分别以1A，1B为出发点计算得21232212123221232(,)()()min(,)()(,)()dAAfAfAdABfBdACfC212()uAB，最短线路是1A-2B-3A-4B-5B-6A21232212123221232(,)()()min(,)()(,)()dBBfBfBdBCfCdBDfD212()uBC，最短路线是1B-2C-3B-4B-5B-6Ak=1时出发点只有0A，计算得101211010121(,)()()min(,)()dAAfAfAdABfB