旅游花费最少问题的研究资料.doc

2009高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 海军航空工程学院 参赛队员 (打印并签名) ：1. 田树东 2. 刘杰 3. 徐舟 指导教师或指导教师组负责人 (打印并签名)： 日期 2010年 5 月 3 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2009高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 旅游方案设计问题的研究 摘要：如今越来越多的人在节假日选择旅游的方式来放松自己的身心。如何规划自己的旅游方式及旅游路线值得研究，本文先将100个城市进行模拟编号，为了方便计算将出发城市进行了重复编号，运用模拟退火算法就100个城市旅游问题建立模型，对如何设计旅游路线，乘坐何种交通工具使得所旅游时间，费用最优化进行了研究。 问题（1）是一个典型的旅行商问题，如何设计旅游路线使得所通过的总路程最短。基于退火算法，通过求解目标函数的最小值，得到了最短路线设计方案，解得了最短路程为km。 问题（2）引入了交通工具的选择，有豪华大巴和飞机可供选择，目的是旅行费用最少，经分析乘坐豪华大巴比乘坐飞机经济，因此构造出两地间旅行的费用矩阵，通过代价函数得到了最短路线设计方案，解得了最少花费为元。 问题（3）通过综合考虑行程，费用和时间等方面因素，采取系数加权的方法，将多因素的变量变成了单因素的变量，在选择交通工具时引入0-1变量，确定了什么情况下乘坐豪华大巴，什么情况下乘坐飞机，构造出了目标函数。并且通过编程求解出在费用和时间的权均为0.3的情况下，完成了对行程和目标函数的优化，解得目标函数的值为。 在其后的问题中，继续分析了模型的复杂度，可行性，误差产生的原因的进行了简单的分析，该模型理论上能够得到全局最优解，但是复杂度较高，运算量大，在计算过程中会产生一定的随机误差。 最后，对模型的优点和缺点进行了评价，指出了模型条理性强，实用性较强的优点，同时也看到了模型在运行上的复杂性，以及在求解过程中的随机性，有利于算法和模型改进和提高 关键字：旅行商问题；模拟退火算法；目标函数；系数加权 1 问题的提出 随着社会的发展和时代的进步，越来越多的人最求精神的享受，诸如旅游，休闲等项目。在旅游过程中经济上的开销和时间上的开销往往是首要考虑的。 旅游使用的交通工具各有利弊，例如在长距离旅行中汽车费用较低，但是旅途时间较为漫长，飞机费用较高却节省时间。如何让旅游者在保证旅游质量的同时使其花费的金钱和时间最少是一个值得研究的问题。 因此本文研究以下的几个问题。 1.怎样设计旅行路线使得总行程最短。 2.在单考虑经济因素的情况下，如何选择适当的旅行工具和旅行路线使得旅途中的花费最少。 3.综合考虑经济和时间因素，选择评价标准，建立数学模型，使旅行过程中的开销最为经济。 4.对上述方案是否可行以及产生的误差进行分析。 最后对数学模型进行综合的分析。 2 模型假设 （1）任意两城市之间都有豪华