旅游线路优化设计。
摘要。随着人们生活水平不断提高，越来越多的人会选择在节假日出去旅游。然在旅游的之前人们往往会想，怎样才能花最少的费用、时间游览更多的地方，怎样设计路线才能在有限的费用、时间内游览更多的地方。
这就需要我们建立高效实用的数学模型来解决这些问题。针对此，本文研究的是旅游线路优化问题。
首先，本文对旅游线路优化问题转化为纯数学模型。这是典型的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=min，返回第2步。
在此问题上我们将权值定义为路费。
对于问题二，要求在旅游费用不限的情况下，求解在整个旅程中所花的时间最少，由于在各地的最少逗留时间已经确定，唯一能够对时间起到影响的便是选用不同的交通方式，不同的交通方式其**不同直接导致从一个地方到另外一个地方的所花的时间也不一样。这一问题和问题二极为相似，将权值定义为时间，然后用lingo软件进行编程。
对于问题三，要求在一定的费用限制下，尽可能多的游览景点。
对于问题四，要求在一定时间的限制下，尽可能多的游览景点。与问题三很相似。
对于问题五，要求在一定的费用及时间的限制下，尽可能多的游览景点。这是问题三与问题四的综合。
内容要点：什么问题、需要建立什么样的模型、用什么方法来求解。
三、模型假设与约定。
1、忽略买票等待的时间在旅游期间；
2、忽略乘坐出租车时经过收费路段所交的费用；
3、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不做考虑；
4、所有旅馆都未客满，并且忽略从旅馆到火车站或景点的时间；
5、列车车次和飞机航班没有晚点等情况发生；
6、列车和飞机的票足够，没有买不到票的情况发生；
7、景点的开放，列车和航班的运营不受天气的影响；
8、该旅行者是**，不考虑学生和小孩；
9、将城市和路径的关系转化为图论问题；
四、符号说明及名词定义。
xij ——路线决策变量（0—1变量）
lij ——从i地到j地的路费及在车上的一些必要费用 （i，j=12……11）
pi ——地区景点的第一门票费用（单位：元）（i=1，2……10）
pij ——i景点和j景点的门票费用之和（单位：元）（i=1，2……10）
t ——在所有景点停留的总时间，包括在景点的游玩时间和停留住宿等时间（单位：天）
a ——每天的基本消费60（单位：元）
m ——旅游总共的消费（单位：元）
s ——旅游总共的用时（单位：小时）
sij ——i景点和j景点的所用时间之和，（单位：小时）（i=1，2……10）
tij ——从i景点到j景点的时间，包括旅途时间、停留等车时间、住宿时间（单位：小时）（i,j=1,2……11）
ti ——在景点i的观光时间（单位：小时）（i=1，2……10）
五、模型建立及求解。
5．1 问题1：
5．1．1模型的建立。
要求在时间不限的情况下，求解整个旅程的最少费用。即在时间无限的情况下，从芜湖出发求游览完全部经典所需花费的费用最小，我们采用图论中的dijkstra算法求解，不同的景点采用顶点代替，两点之间的权值定义为这一段旅程所用的最小费用。
影响费用的因素：
查出各地之间的路费（采用火车，相对便宜）：
目标函数的确定：
用lij表示i景点到j景点的途中花费，并引入路线决策变量xij
xij=用pj表示j地区景点的第一门票费用，
则总费用目标函数为：
约束条件的确定：
由于每个景点只能有一条边出去，所以对j景点xij之和影等于1，既：
i=1,2...11
同理，每个景点只能有一条边进去，所以对i景点xij之和也应等于1，既：
i=1,2……11
模型：min
5．1．2模型求解。
具体旅程安排图：
5．2 问题2：
5．2．1 模型建立。
要求在费用不限的情况下，求解整个旅程的最少用时。即在费用无限的情况下，从芜湖出发求游览完全部经典所需用的时间最小，我们采用图论中的dijkstra算法求解，当然，得用尽量快的交通方式，对此我们仍然用不同的景点采用顶点代替，两点之间的权值定义为这一段旅程所用的最小时间。
影响费用的因素：
目标函数的确定：
用lij表示i景点到j景点的途中花费，并引入路线决策变量xij
xij=用tij表示从i景点到j景点的时间，包括旅途是时间、停留等车时间、住宿时间（单位：小时）（i,j=1,2……11）
ti表示在景点i的观光时间（i=1，2……10）
则总时间，既目标函数为：
约束条件的确定。
由于每个景点只能有一条边出去，所以对j景点xij之和影等于1，既：
i=1,2...11
5．2．2 模型求解。
5．3 问题3：
在游客准备了2000元旅行费的情况下，想尽可能多的游览景点，要求游览的景点数最多。也就是说，从芜湖出发，尽量观赏多个景点，不能重复，然后再回到芜湖，使得这一过程中所的费用不超过2000元。在这一过程中我们不仅要考虑到景点所用的车费，还要考虑景点的门票费用，使得这两者相加起来尽可能的少。
在去景点的过程中要尽量选择火车作为的交通工具。
数学建模作业 2
数学模型作业。作业题目 最优 求解。任课教师。班级。学生姓名 学生学号。求解最优 摘要。人们经常要求经济学家们对将来的经济进行 在进行 时，往往离不开各种各样的统计信息。例如，在 通货膨胀率时，经济学家们就要用到生产者 指数 失业率和生产利用能力等方面的统计信息，将这些统计信息输入到计算 模型中，就...
2 数学小建模
趣味数学大家玩 二 1 缪勒 莱耶错觉。看看上面的带箭头的两条直线，猜猜看哪条更长？是上面那条吗？2 回环诗图。3 数学小建模。1 烤面包的时间。史密斯家里有一个老式的烤面包器，一次只能放两片面包，每片烤一面。要烤另一面，你得取出面包片，把它们翻个面，然后再放回到烤面包器中去。烤面包器对放在它上面的...
数学建模2试题A
东华大学20 20 学年第 1 学期期 末 试题 a 踏实学习，弘扬正气 诚信做人，诚实考试 作弊可耻，后果自负。课程名称 数学建模 2 使用专业。班级姓名学号。一 简答题 40分，每小题10分 1.10分 考虑带有阻滞因素的食饵 x 捕食者 y 模型。这里参数a,b,c,d,r均为正数。试解释各参...