任务及要求
《数学模型》课程结业论文
走遍全国问题
I
任务及要求
任 务 书
[要求]
1、将所给的问题翻译成汉语；
2、给论文起个题目（名字或标题） 3、根据任务来完成数学模型论文；
4、论文书写格式要求按给定要求书写；
5、态度要认真，要独立思考，独立完成任务；
6、论文上交时间：6月1日前（要求交纸质论文和电子文档）。 7、严禁抄袭行为，若发现抄袭，则成绩记为“不及格”。
[任务]
周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：
1．按地理位置（经纬度）设计最短路旅行方案；
2．如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；
3． 要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；
4．对你的算法作复杂性、可行性及误差分析；
5．关于旅行商问题提出对你自己所采用的算法的理解及评价。
评语：
成绩
任课教师签字 年 月 日
II
成 绩 评 定 单
摘要
摘 要
随着社会的发展、人们生活水平的提高，旅游日益成为现实社会的热点，为了得到一个比较实惠的旅游方案，我们需要有一套比较完善的预算体系，建立这样一套体系是一个多目标的决策问题。这一问题的重点在于经济、时间等因素融入预算体系，使得预算的一个旅行方案更完善、更合理。本文就周先生如何制定旅行方案，以实现路径最短，费用最少，时间最短的问题进行研究。在考虑旅行费用与路线，时间和交通工具的关系之后，我们以实现路径最短与费用时间最少为目标，进行了系统建模。根据此问题，我们首先建立模拟退火算法模型，然后对模型进行求解编程，再应用Matlab对模型编程求解和运行后得到一最短路径（此路径是两城市坐标之间的距离）。我们进一步分析和讨论得到的结果得出几种可行的算法。我们在模拟退火算法得到的路径基础上，对路线进行局部地调整（一是参照《用遗传算法求解旅行商问题》【1】等相关问题的求解文献来调整，二是对华北、长江流域用图论进行局部调整），再把这些可行方法进行优化和改进得到六个可行方案（这些方案也是用两城市之间的直线距离来求解最短路径）。根据这六个方案，我们再建立几个简化模型，对于简化模型，我们根据实际情况，查找票源【2】、城市之间的实际里程（飞机的里程以两地之间的直线距离算）等，给出了相应的具体数据和路线图。我们再运用穷举搜索法，一一检验，寻找最短实际里程、最低票价及最短乘车（机）历时。把各个方案进行一个全面的分析、比较后，得到一优化方案，由优化方案结果分析表明模型的正确性、实际性和有效性。最后根据一种更符合实际情况的假设，对模型进一步优化，建立了更加有效、更加节省时间和费用的优化方案，从而达到省时、省钱和方便的目的。
关键词：最短路径、费用最少、时间最短、模拟退火法、Matlab应用、穷举搜索法、
简化、旅行商问题
I
目录
目 录
一.问题重述 .......................................................................................................................... 1 二.问题分析 .......................................................................................................................... 1 三.基本假设： ...................................................................................................................... 2 四.模型定义及建立： .......................................................................................................... 2 （一）.模型定义： .............................................................................................................. 2 （二）.模型建立： .............................................................................................................. 3 五.模型求解： ...................................................................................................................... 3 六.优化结果及误差分析： ................................................................................................ 17 （一）.优化结果分析 ........................................................................................................ 17 （二）.误差分析 ................................................................................................................ 18 七.模型评价 ： .................................................................................................................. 18 参考文献： ......................................................................................................................... 19 附录： ................................................................................................................................. 19
I
数学模型课程结业论文
一.问题重述
周先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：
1．按地理位置（经纬度）设计最短路旅行方案；
2．如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；
3．要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；
4．对你的算法作复杂性、可行性及误差分析；
5．关于旅行商问题提出对你自己所采用的算法的理解及评价。
二.问题分析
对于旅游问题，考虑各个省会之间的实际距离即路线距离和交通工具的选择，分析得出一条最短的旅游路径，以达到省时，省钱又方便的目的。对于调整和改进后得到的几种路线来说，在一个周期T（例如一年）开始时，每种可供选择的交通工具的费用已知，且价格（火车及飞机票价格）在一个周期内相对不变。周先生选择价格最低的一个交通工具（如果存在多个最低价格，周先生则选择最快的交通工具），因此一个周期内路线和交通工具已经确定。我们可以将问题分为两部分：旅行最短路线、费用时间最少。就问题一(旅行路线)来说，由于各省会之间的路线不一，因此存在一个路线问题。问题二（最经济）和问题三（省时、方便），由于所乘交通工具的多样性，因此存在考虑费用和时间问题（也就是购票问题）。评价标准：因为同时要考虑三个方面的问题，各个问题的最优方案很难会一致，所以我们以三个方面问题的最优方案重复的次数来认为是不是最优方案。比如某个方案在两个问题中都是最有方案，那么这个方案就是本题的最佳方案。如果三个问题的最优方案不重复，那么我们就以路程和时间为主要因素来确定最优方案。
1
走遍全国问题 - 图文
