数学建模 (2).doc

旅游线路优化设计摘要随着人们生活水平不断提高，越来越多的人会选择在节假日出去旅游。然在旅游的之前人们往往会想，怎样才能花最少的费用、时间游览更多的地方，怎样设计路线才能在有限的费用、时间内游览更多的地方。这就需要我们建立高效实用的数学模型来解决这些问题。针对此，本文研究的是旅游线路优化问题。首先，本文对旅游线路优化问题转化为纯数学模型。这是典型的TSP问题，可以用图论中的狄克斯特拉算法。为了简化问题，我们忽略了等车堵车以及天气等问题；针对第一问，我们将各地转化成图论上的点，将两地之间用线段连接，再对各条线段赋权值，由于这问要求费用最少，故权值定义为两地之间的最少费用然后列出影响旅游费用的时间，在规划出目标函数及约束条件。搜集相关数据，用lingo软件得出结果。然后，针对第二题，思路与第一问基本相同，所不同的是需要对两地之间的权值进行另外定义，因为此题要求在费用不限的情况下，求浏览十个景点所需的最少时间，故此题将权值定义为两地旅途过程所花费最少时间。其次，对于第三题，约束条件有所变化，限制一定的费用，目标是游览跟多的景点数目。对此我们将在个地所需最少费用列出，找出费用较多的地方，所得结果应尽量避免出现这几个地方，在此基础上我们同样列出目标函数及约束条件，再由lingo软件求解得出。再次，对于第四题，与问题三类似，只不过约束条件是时间，想尽可能浏览更多地方。对此我们将在各地的逗留时间以及在旅途上所花费的时间做了比较，得出所花时间较多的一些景点。最后，对于第五题，它是问题三与四的综合，既要求费用的限制也要时间的限制，为此我们将限制条件增加，建立模型。关键词：TSP优化问题 图论狄克斯特拉算法 lingo 一、问题重述随着人们生活水平的提高，旅游逐渐成为最热门的户外活动之一。旅游可以给人们带来很多好处，在旅游的过程中，我们不仅可以感受大自然之美、放松心情，而且可以领略不同地方的文化气息、拓宽视野。旅游者在今年十月一日8点之后从安徽芜湖出发，到全国一些著名景点旅游，最后回到芜湖。由于跟团旅游会受到限制，旅游者打算自己背包出游。出行路途中有以下几个条件：（A）城际交通出行可以乘火车（含高铁）、长途汽车或飞机（不允许包车或包及），并且车票或机票可预定到。（B）市内交通出行可乘公交车（含专线大巴、小巴）、地铁或出租车。（C）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票）。晚上20：:00至次日早晨7：:00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。（D）假设景点的开放时间为8:00至18:00.根据以上条件考虑到旅游者的以下需求：问题一：在时间不限的情况下，游览全部景点，旅游费用最省；问题二：在旅游费用不限的情况下，游览全部景点，旅游时间最短；问题三：在旅游费用一定的情况下，游览尽可能多的景点；问题四：在时间一定的情况下，游览尽可能多的景点；问题五：在时间和旅游费用都一定的情况下，游览尽可能多的景点。针对以上几种情况，建立相关的数学模型并为该旅行者设计详细的行程表，行程表中应包括具体的交通信息（车次、航班号、起止时间、票价等）、宾馆地点和名称，门票费用，在景点的停留时间等信息。二、问题分析2.1 问题背景分析随着人们生活水平不断提高，越来越多的人会选择在节假日游览一下祖国的大好河山，领略一下各地的风土人情和人文气息。然在旅游的之前人们往往会想，怎样才能花最少的费用、时间游览更多的地方，怎样设计路线才能在有限的费用、时间内游览更多的地方。这就需要我们建立高效实用的数学模型来解决这些问题。对于问题一，要求在时间不限的情况下，求解整个旅程的最少费用。由于旅游费用包括交通费、住宿费、景点门票、基本费用（如，吃饭，水，常用生活用品），要使费用最小，就必须严格控制交通费、住宿费、景点门票及基本费，然而像住宿费与基本费只与时间有关，景点门票费用是改变不了的，剩下的交通费可以通过选择不同的交通方式达到费用最低。该问题属于旅行商问题，可以用图论中的狄克斯特拉算法 (Dijkstra algorithm, 1959)，下面给出狄克斯特拉算法运行程序：狄克斯特拉算法的作用是计算两节点之间或一个节点到所有节点之间的最短路令 dij 表示 vi 到 vj 的直接距离(两点之间有边)，若两点之间没有边，则令 dij = ，若两点之间是有向边，则 dji = ；令 dii = 0，s 表示始点，t 表示终点0、令始点Ts=0，并用框住，所有其它节点临时标记 Tj= ；1、从 vs 出发，对其相邻节点 vj1 进行临时标记，有 Tj1=ds,j1 ；2、在所有临时标记中找出最小者，并用框住，设其为 vr 。若此时全部节点都永久标记，算法结束；否则到下一步；3、从新的永久标记节点 vr 出发，对其相邻的临时标记节点进行再标记，设 vj2 为其相邻节点，则 Tj2=minTj2, Tr+dr,j2 ，返回第2步。在此问题上我们将权值定义为路费。对于问题二，要求在旅游费用不限的情况下，求解在整个旅程中所花的时间最少，由于在各地的最少逗留时间已经确定，唯一能够对时间起到影响的便是选用不同的交通方式，不同的交通方式其价格不同直接导致从一个地方到另外一个地方的所花的时间也不一样。这一问题和问题二极为相似，将权值定义为时间，然后用lingo软件进行编程。对于问题三，要求在一定的费用限制下，尽可能多的游览景点。对于问题四，要求在一定时间的限制下，尽可能多的游览景点。与问题三很相似对于问题五，要求在一定的费用及时间的限制下，尽可能多的游览景点。这是问题三与问题四的综合。内容要点：什么问题、需要建立什么样的模型、用什么方法来求解三、模型假设与约定1、忽略买票等待的时间在旅游期间；2、忽略乘坐出租车时经过收费路段所交的费用；3、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不做考虑；4、所有旅馆都未客满，并且忽略从旅馆到火车站或景点的时间；5、列车车次和飞机航班没有晚点等情况发生；6、列车和飞机的票足够，没有买不到票的情况发生；7、景点的开放，列车和航班的运营不受天气的影响；8、该旅行者是成人，不考虑学生和小孩；9、将城市和路径的关系转化为图论问题；四、符号说明及名词定义Xij 路线决策变量（01变量）Lij 从i地到j地的路费及在车上的一些必要费用 （i，j=1211）Pi 地区景点的第一门票费用（单位：元）（i=1，210）Pij i景点和j景点的门票费用之和（单位：元）（i=1，210）T 在所有景点停留的总时间，包括在景点的游玩时间和停留住宿等时间（单位：天）A 每天的基本消费60（单位：元）M 旅游总共的消费（单位：元）S 旅游总共的用时（单位：小时）Sij i景点和j景点的所用时间之和，（单位：小时）（i=1，210）Tij 从i景点到j景点的时间，包括旅途时间、停留等车时间、住宿时间（单位：小时）（i,j=1,211）Ti 在景点i的观光时间（单位：小时）（i=1，210）五、模型建立及求解51 问题1：511模型的建立要求在时间不限的情况下，求解整个旅程的最少费用。即在时间无限的情况下，从芜湖出发求游览完全部经典所需花费的费用最小，我们采用图论中的Dijkstra算法求解，不同的景点采用顶点代替，两点之间的权值定义为这一段旅程所用的最小费用。影响费用的因素：交通费总的旅游费用住宿费、基本费景点门票查出各地之间的路费（采用火车，相对便宜）：费用(元)芜湖常州青岛北京祁县洛阳黄山武汉西安九江舟山芜湖0421581542401024110414051112常州42015014018012573361165120193青岛1581500116120245360373363371422北京154140116094106182210210225493祁县240180120940184248379109337569洛阳10212524510618402878733125546黄山41733601822482870205206120200武汉104361373210379872050267177674西安140165363210109332062670207313九江511203712253371251201772070169舟山1121934224935692462006743131690目标函数的确定：用Lij表示i景点到j景点的途中花费，并引入路线决策变量Xij1 经过i到j的路段0 不经过i到j的路段Xij=用Pj表示j地区景点的第一门票费用， 则总费用目标函数为：约束条件的确定： 由于每个景点只能有一条边出去，所以对j景点Xij之和影等于1，既： i=1,2.11 同理，每个景点只能有一条边进去，所以对i景点Xij之和也应等于1，既: i=1,211模型：min512模型求解芜湖九江庐山舟山普陀山黄山常州恐龙园青岛崂山八达岭长城祁县乔家大院兵马俑龙门石窟具体旅程安排图：52 问题2：521 模型建立要求在费用不限的情况下，求解整个旅程的最少用时。即在费用无限的情况下，从芜湖出发求游览完全部经典所需用的时间最小，我们采用图论中的Dijkstra算法求解，当然，得用尽量快的交通方式，对此我们仍然用不同的景点采用顶点代替，两点之间的权值定义为这一段旅程所用的最小时间。影响费用的因素：旅途用时总用时住宿用时景点用时目标函数的确定：用Lij表示i景点到j景点的途中花费，并引入路线决策变量Xij1 经过i到j的路段0 不经过i到j的路段Xij=用Tij表示从i景点到j景点的时间，包括旅途是时间、停留等车时间、住宿时间（单位：小时）（i,j=1,211）Ti表示在景点i的观光时间（i=1，210）则总时间，既目标函数为：约束条件的确定 由于每个景点只能有一条边出去，所以对j景点Xij之和影等于1，既： i=1,2.11522 模型求解53 问题3：在游客准备了2000元旅行费的情况下，想尽可能多的游览景点，要求游览的景点数最多。也就是说，从芜湖出发，尽量观赏多个景点，不能重复，然后再回到芜湖，使得这一过程中所的费用不超过2000元。在这一过程中我们不仅要考虑到景点所用的车费，还要考虑景点的门票费用，使得这两者相加起来尽可能的少。在去景点的过程中要尽量选择火车作为的交通工具。531 模型的建立基于第一问得出的旅游行程表，我们对其进行优化。由于题目给出了约束条件，旅游经费不超过2000元，所以我们将行程划分为21部分（包括10个景点和11条线路）。然后统计出每一部分所要花费的经费，如下表所示：表二：各地花费经费表（单位：元）芜湖常州舟山黄山九江武汉016823226020084洛阳西安祁县北京青岛124944485164芜湖常州常州宁波宁波黄山黄山九江九江武汉武汉洛阳427389935792洛阳西安西安祁县祁县北京北京青岛青岛芜湖55399415899由上表可以看出，黄山、普陀、九江和常州所花费的经费占10个旅游景点的前4位，这四个景点的总经费大约为915元，所以先不考虑黄山、普陀、九江和常州这四个景点。尽量避免这四个景点。对其余的景点根据最短路径重新安排行程，避免住宿，减少不必要的花费我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。已经分析该题是已知费用的最大限度求最佳路径问题，因此要选择到下一景点总的最低费用作为去下一景点的前提条件且剩余费用要足够回到芜湖。如前面模型，我们把两景点的最省路费作为赋权值，在一定程度上，各景点间的距离与两点间的单程最省路费是成正比的，因此把两景点的最短路费作为权值是可行的。影响景点数的因素：不多于2000元的费用旅途坐车费用住宿及基本费用门票费用 目标函数的确定：假设总费用未知，但满足条件（=2000元），用M表示用Pij表示i景点和j景点的门票费用之和，（单位：元）（i=1，210）用Lij表示i景点到j景点的途中花费，并引入路线决策变量Xij1 经过i到j的路段0 不经过i到j的路段Xij=用C表示旅游的景点数目则最多景点数，既目标函数为： C= 约束条件的确定：由于M=车费+基本费用+门票费，因此用函数表示为： M= 由于每个景点只能有一条边出去，所以对j景点Xij之和影等于1，既： 或0 i=1,2.11 同理，每个景点只能有一条边进去，所以对i景点Xij之和也应等于1，既： 或0 i=1,211应该注意的是，除了起点和终点（都是芜湖）以外，各边不构成Hamilton圈。综上分析，可以建立多种回归的Hamilton圈的线性规划模型： i=1,211532 模型的求解54 问题4在游客只有五天可以旅游的情况下，想尽可能多的游览景点。也就是说，从芜湖出发，在仅有的时间内尽量观赏多个景点，不能重复，然后再回到芜湖，使得这一过程中所到的景点数最多。在这一过程中我们不仅要考虑到坐车、等车行程中所用的时间，还要考虑到在景点停留的时间，要使得这两者相加起来尽可能的少。因此再在去景点的过程中要尽量选择飞机作为交通工具，且尽量减少转机（转车）次数。541 模型的建立 基于第二问得出的旅游行程表。我们对其进行优化。由于题目给出了约束条件，旅游时间不超过5天，也就是120小时，所以我们将行程划分为21部分（包括10个景点和11条线路）。然后统计出每一部分所要花费的时间，如下表所示：表六：各地花费时间表（单位：小时）芜湖常州西安太原青岛舟山029.514719.521.5武汉九江黄山北京洛阳2121.517.513.54芜湖常州常州西安西安太原太原青岛青岛舟山舟山武汉620.751.251.52武汉九江九江黄山黄山北京北京洛阳洛阳芜湖51021.57.5我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解相应问题。已经分析该题是已知确定的时间限制求解最佳路径问题，因此要考虑到在时间最充分利用的前提下五天之内回到芜湖。如前面模型，我们把两景点的最省时间作为赋权值w（e），在一定程度上，各景点间的距离与两点间的单程最省路费是成正比的，因此把两景点的最短时间作为权值w（e）是可行的。影响景点数的因素：不多于五天的时间旅馆住宿时间景点逗留时间坐车转车时间坐车转车时间目标函数的确定：假设游玩的天数未知，用S表示，但满足条件（=120小时）用Sij表示i景点和j景点的所用时间之和，（单位：小时）（i=1，210）用Tij表示从i景点到j景点的时间，（单位：小时）（i,j=1,211）并引入路线决策变量Xij1 经过i到j的路段0 不经过i到j的路段洛阳市龙门石窟九江市庐山八达岭长城秦始皇兵马俑芜湖常州市恐龙园1 经过i到j的路段0 不经过i到j的路段不多于五天的费用费用旅游景点观赏停留时间旅馆住宿时间坐车（飞机）、转车（转机）时间秦始皇兵马俑武汉市黄鹤楼Xij=用C表示旅游的景点数目则最多景点数，既目标函数为： C=约束条件的确定：由于S=等车、转车时间+住宿时间+景点停留时间，因此用函数表示为： S= 由于每个景点只能有一条边出去，所以对j景点Xij之和影等于1，既： 或0 i=1,2.11 同理，每个景点只能有一条边进去，所以对i景点Xij之和也应等于1，既： 或0 i=1,211应该注意的是，除了起点和终点（都是芜湖）以外，各边不构成Hamilton圈。3、模型建立综上分析，可以建立多种回归的Hamilton圈的线性规划模型： i=1,211542 模型的求解55 问题5基于对三、四问题的分析下，在游客只有五天时间和2000元费用可以旅游的情况下，想尽可能多的游览景点。也就是说，从芜湖出发，在仅有的时间和有限的经费内尽量观赏多个景点，不能重复，然后再回到芜湖，使得这一过程中所到的景点数最多。在这一过程中我们不仅要考虑到坐车、等车行程中所用的时间和费用，还要考虑到在景点停留的时间和门票费，要使得这两者相加起来尽可能的少。因此要综合考虑三、四两种情况。551 模型的建立我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解相应问题。已经分析该题是已知时间限制和费用制约的前提下求解最佳路径问题，因此要考虑到能充分利用五天时间和2000元费用回到芜湖。在时间和费用都有约束的条件下，选择一个作为约束条件，减少目标规划。目标函数的确定： 假设总费用未知，用M表示，但满足条件（=2000元）假设游玩的天数未知，用S表示，但满足条件（=level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i);););for(link:bin(x);for(cities(i)|i#gt#1: level(i)=1+(n-2)*x(i,1););End 51 第二题代码：内容要点：搜集的相关资料、所编程序的运行结果、计算框图、详细图表。主要结果数据，应在正文中列出，不怕重复。 全国大学生数学建模竞赛论文格式规范l 本科组参赛队从A、B题中任选一题，专科组参赛队从C、D题中任选一题。l 论文用白色A4纸单面打印；上下左右各留出至少2.5厘米的页边距；从左侧装订。l 论文第一页为承诺书，具体内容和格式见本规范第二页。l 论文第二页为编号专用页，用于赛区和全国评阅前后对论文进行编号，具体内容和格式见本规范第三页。l 论文题目和摘要写在论文第三页上，从第四页开始是论文正文。l 论文从第三页开始编写页码，页码必须位于每页页脚中部，用阿拉伯数字从“1”开始连续编号。l 论文不能有页眉，论文中不