数学建模论文最佳旅游路线.doc

最佳旅游路线设计院系:信息科学与技术学院保证书我们仔细阅读了大学牛数学建模竞赛的竞赛规则，我们完全明口在竞赛 开始后不能以任何方式与队外的任何人讨论有关竞赛试题的求解内容，抄袭别人 的成果也是违反竞赛规则的，如被发现将会受到严肃处置我们也知道如果引用 别人的成果或其他公开的资料（包括网上查到的资料）必须按照规定的参考文献 的表述方式在正文和参考文献111明确列出为了确保竞赛的公正、公平性，我们保证严格遵守竞赛规则参赛院系：信息科学与技术学院参赛队员:2008年6月28日最佳旅游路线设计摘要为了提出合适的旅游线路，从实际情况出发考虑，本文建立了合适的线路 选择模型，并给出了一些结果问题一为既考虑旅游消费，乂考虑旅游的景点数的旅游线路选择问题本 文对去各景点间的路费、景点门票、在景点内每天的平均消费加以考虑，建立了 0-1规划模型对于多H标模型，我们采用适当的拟合将多H标转化为单H标 并使用li昭软件编程得出最优旅游线路及合适的旅游吋间为：二号线：成都f 乐山一峨嵋，最合适的旅游吋间均为1天；三号线：成都f四姑娘山f丹巴，最 合适的旅游时间均为1天；四号线：成都f都江堰f青城山，最合适的旅游时间 为都江堰2天，青城山1天；五号线：成都f康定，最合适的旅游吋间为1天。

并对最优线路给出了详细的评价问题二，在代表时间充裕的条件下仅考虑旅游的交通费用，我们把各景点 看成是纯数学小的点，利用图论的知识求解在建模中，我们把各景点间的路费 作为巡回图边的邻接矩阵权，使原题巧妙的转化为了图论中旅行商问题（即最短 路问题），建立了线性规划模型，利用lingo软件求解得到最少的交通费用为 427. 00元，最佳的旅游路线为：成都一青城山一都江堰-＞四姑娘山一丹巴一黄 龙f九寨沟f海螺沟f康定f峨眉f乐山f成都问题三在问题一的基础上增加了对代表旅游意向的考虑，建模思路与问题一 大致相同我们把代表的旅游意向刻画为代表对旅游路线的满意度，然后在问题 一的基础上增加一个H标函数，即在整个旅游线路中满意度最高建立了多H标 优化模型，采用同样的方法把多H标规划问题转化为单H标问题利用li昭软件 求解得到：旅游的景点总数是7个，总的满意度是4. 08,各条路线的满意度分 别为0.2, 0. 78, 0. 85, 0. 80, 0.85下而是求得的最佳旅游路线以及最合适的 旅游吋间：二号线：成都一乐山一峨嵋，最合适的旅游时间为前者2天，后者1 天；三号线：成都-＞四姑娘山一丹巴，最合适的旅游吋间为前者1天，后者2 天；四号线：成都一都江堰，最合适的旅游吋间为2天；五号线：成都一海螺 沟f康定，最合适的旅游时间均为1天。

最后，我们对整个过程进行了科学性的评价并提出了使用Dijkstra算法 和遗传算法解题的思路关键词：0-1规划 线性规划 多FI标规划lingo遗传算法Dijkstra算法1问题重述随着牛活水平的提高，旅游逐渐成为最热门的户外活动之一在旅游的过程 中，我们不仅可以感受大自然的美，而且可以领略不同地方的文化气息，乡土风 情在这里考虑到旅游者的以下需求：1•旅游的费用尽可能最省；2.观赏的旅游 景点尽可能多；3•旅游者对旅游路线的满意度尽可能高设计合适的旅游线路方 案来满足旅游者的各种需求，其核心是线路选择的模型与算法，应该从实际情况 出发考虑，满足旅游者的各种不同需求在这里只针对将要來参加西南交通大学数学系召开的“ X X学术会议”的來 自国内外的许多著名学者，为其设计合适的旅游路线需要解决如下问题：1 •根据提供的五条线路，要求设计出合适的旅游路线，使得会议代表能在 10天内花最少的钱，游最多的地方2•上面考虑的是只有十天吋间的情况，当代表吋间非常充裕（比如一个月） 时，可以游完所有的景点才离开，设计合适的旅游路线，使在四川境内的交通费 用尽量地节省3•根据主办方对代表的游意调查，充分考虑这些代表的意愿，为设计代表们 合适的旅游路线，使他们在会议结束后的10天时间内花最少的钱游尽可能多的 地方。

2条件假设1. 假设查阅的数据基本符合事实2. 假设各景点间的路费及各景点的门票长期基本保持不变3. 假设在问题一中不考虑每一•条路线的最优，而是考虑整个旅游过程的最优问 题4. 假设代表在某景点旅游的最长时间不超过3天3符号说明模型一中:y,——第Z条线路中第）个景点（0-1变量）P,——第i条路线第丿•个景点的门票（单位：元）知——在第i条路线第丿•个景点平均每天的基本消费（单位：冗）<——第i条路线的平均路费（单位：元）c——10天中旅游的景点总数n——10天中的总消费（单位：7L）r, ——在第i条线路第j个景点观赏的总吋间（单位：天）模型二中:X..——路线决策变量（0-1变量）叫j——i景点到丿景点间的路费（单位：元）L——总路费（单位：7L）模型三中：s’——去第i条线路的满意度/；-0——去第,条线路的满意度上限/；•,——去第i条线路的满意度下限k——整个旅游过程中的满意度之和4问题分析题FI背景：随着我国经济实力的提高，人们的牛活水平也不断的提高旅游 也随之成为很热门的户外活动旅游不仅可以释放心情，也可以感受到大自然的 美，不同的风土人情，不同的人文气息所以越来越多的人把旅游作为一种享受。

在旅游的吋候，人们往往会想，怎样才能花最少的钱游最多的地方，怎样的 旅游路线才能够使自己最满意这样就要求我们建立适半的数学模型来解决这些 问题首先我们知道本问题属于旅游线路的优化问题为了建立模型，首先应该将 各景点线路转化为纯数学形式的点线的集合，进行图论方而的分析1 •本问题要解决两方而的问题：在10天的旅游吋间内，满足（1）旅游的 费用尽可能少；（2）观赏的旅游景点尽可能多根据这些需求，可以从以下两种 方案入手：（1） 建立多FI标优化模型，考虑分层序列法，以旅游费用尽可能少为第一 H 标，观赏的景点尽可能多作为第二H标在第一H标求得的可行解集里搜索满足 第二H标的路线，将该路线作为最合适的旅游路线2） 同样建立多H标规划模型，通过适当的拟合或线性加权，把多H标转化 为单H标在这里还把各景点的门票和毎天的平均消费考虑进去，以增加模型的 实用性分析上面的两种方案可知，方案一求出来的旅游线路不一定是最佳线路，因 为当在满足旅游费用尽可能少吋，得到的线路不一定就满足第二个条件，即观赏 的景点尽可能多所以方案一•存在一定的问题，我们选择方案二，用通过适当的 拟合把多H标转化为一个单H标求解模型。

下而给出各条线路的平均路费，各景点的门票，以及各景点平均每天的基本 消费：戈路线路一线路二线路三线路四线路五价格(元)项目九寨沟黄龙乐山峨眉四姑 娘山川巴祁江堰W城 山海螺沟康定平均路费1083510520100门票22020090120905090909040每天平均消费120801001201009010010013090表二各条线路平均路费、各景点的门票、各景点平均每夭的基本硝费(单伐：元丿2.在代表的吋间比较充裕的条件下，可以把所有的景区参观完，要求建立 合适的模型，使得交通费用尽量最省这时代表就是从成都出发，逐一到达各个 景点(不能重复到达)，观赏完所有景点Z后返回成都根据上而分析可知，该问题屈于旅行商问题(Traveling Salesmaii PToblem, TSP)o为了建立模型，首先应该将各景点转化为纯数学形式的点线的集合，进行 图论方面的分析下面给出旅行商问题的定义：旅行商问题：一位销售商从N个城市川的某一城市出发，不重复地走完其余 NT个城市并回到原出发点，在所有可能路径中求出路径长度最短的一•条•用数 学语言描述TSP,即给定一•组M个城市和它们两两Z间的直达距离，寻找一•条闭 合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。

用图语言来描述 TSP:给出一个图G= (V, E),每边eWE上有非负权值w(e),寻找G的Ham订ton 圈C,使得C的总权W(c)=工 w(e)e=E(c)最小TSP问题是一个典型的组合优化问题，其可能的搜索路径随着城市数HN 的增加呈指数增长，属于NP完全问题了解了以上知识后，我们更加确定了该问题就是旅行商问题只是在实际的 处理中，我们把两景点的路费作为赋权值w(e),在一定程度丄，各景点间的距离 与这两点间的单程路费是成止比的，所以把两景点的路费作为权值w(e)是可行 的下表给出的是任意两景点间的单程车费路费\警成都九寨黄龙乐山峨眉山四姑 娘山丹巴都江 堰青城山海螺 沟康定成都01081004235105110122010090九寨108015200130100120100100220200黄龙100150180190901109090210190乐山422001800201501706060100120峨眉山3513019020015018080885070四姑娘山105100901501500603038150120丹巴110120110170180600909813080都江垠12100906088309008160140青城山20100906080389880170150海螺沟11022021010050150130160170030康定902001901207012080140150300表二 各景点问的单程路费(单住：元丿3.本题与问题一基本一样，只是在问题一的基础上充分考虑了代表对各条旅 游路线的旅游意向。

为了建立合适的数学模型，我们首先根据附件一在SPSS软件中统计出100 位代表对各条线路的旅游意向100位代表对各条旅游路线的旅游意向见下表：一号线二号线三号线四号线五号线去20%12%15%20%15%不去14%22%15%15%15%无所谓66%66%70%65%70%表三 100住代表■对各条彖游路线的彖游意向从上而的数据分析可知，持“无所谓”态度的代表大约占65%-70%,持“去” 态度的代表约占12%-20%,持“不去”态度的代表约占14%-22%对一号路线来说,“去”的有20%, “无所谓”的有66%,即是这部分人有可能参加这条路线也有可能不参加这条路线也就是说如果去一•号路线，那么就至少有20%的人满意我们在这里把变量看作是去一号线的满意度，即是0.2<5,<0.86, 之，要是不去一号线，。