基于Lingo的旅游计划制定方法

1、精选优质文档-倾情为你奉上海 南 大 学数学模型课程设计论文题目： 基于Lingo的旅游计划制定方法 班级： 信息与计算科学 姓名： 体贴的瑾色 学号： 指导教师： 日期： 2017.06 目录基于Lingo的旅游计划制定方法摘要本文针对海南十八个城市制定旅游规划，在收集了大量的数据情况下，建立评价指标，找到最优的旅游路线。对于问题一因为不要求求出具体的路程最小值，所以我们使用matlab处理海南省的地图，找到每个城市在地图的相对坐标，从而得到城市之间的相对距离。以距离为权，以旅程的长度为评价标准建立模型，规划最优路线得到最小相对距离1488。11，注意这里的最小距离并不是实际上的最小距离。对

2、于问题二将最小费用矩阵代替距离矩阵，以旅程的总车费为评价标准建立模型，规划最优路线，得到最小费用为276元。对于问题三，在一二问的基础上，综合考虑省时省钱，得到评价标准表达式，建立模型，规划最优路线。一、问题描述本题要求在不同的约束条件下规划出海南的最佳旅游路线，路线的基本要求是必须从海口出发并回到海口，并且经过且经过海南的每个城市（包括县城）一次，并且每个市县玩两天。不同的问题约束条件是：（1）要求总路程最短。（2）允许选择动车和大巴作为出行工具，规划的路线使得出行总交通费用最少。（3）综合考虑一二问的条件，得到最优路线，设定出相应的评价准则和指标，修正模型。二、模型假设（1） 城市之间路程

3、用城市的直线距离代替。（2） 近期城市之间的动车价格和大巴价格视为定值。（3） 城市之间路费取自动车价格和大巴价格的最小值。（4） 假设不同城市之间的交通工具的速度均相差不大，即旅行时间由旅行路程唯一决定。三、问题分析通过查询知道海南的市县数量总共是有18个（三沙市除外），那么显然这个问题是一个18个城市的TSP问题。用图论的内容来等价话描述为：设 是一个有向赋权图，其中将城市看做节点构成顶点集，如果和之间存在边，即表示制定的旅游方案中是从城市到城市。表示边所赋的非负权重。 那么该问题就是指在带权有向图中,寻找从指定起始节点的一条经过且仅经过一次所有节点的具有最小权值总和的闭合路径。不同的问题

4、中所赋的权重代表的内容不同：（1） 问题一中，因为不要求求出具体的最小值，所以我们使用matlab处理海南省的地图，找到每个城市在地图的具体坐标，从而得到城市之间的距离。以距离为权建立模型，规划最优路线。（2） 问题二中，针对不同城市间的交通条件，选择合适的交通方式，通过互联网票务查询得到结果。（3） 问题三中，综合考虑条件，设计出省时又省钱的最优化路线。四、符号说明 城市与城市之间的距离（路程，费用等） 与城市相对应的任意实数 城市的数量 旅行车费 旅行路程五、模型建立首先建立一二问的模型：目标函数为： 保证从每个城市只离开一次： 保证只进入每个城市一次： 变量约束： 但是满足上述变量并不能

5、保证找到最优解，因为如果生成的路径包含有两个不连通的闭合子路径，也满足上述条件，但并不符合题意。所以还要增加约束使得不出现这种情况。文献1中证明了如果满足下述条件： 其中，那么能保证不出现独立的闭合子路径。城市之间的距离估算使用如下图一所示海南省行政图作为对象，使用matlab的ginput函数，找到每个市县的具体坐标，后如下图二所示对城市进行编号，计算得到城市之间的距离矩阵，结果如下图三所示，注意这里并不需要考虑城市间是否有交通工具来往，因为查询知道相近的城市均有直达车次，只有部分相距较远的城市不可来往，而第一问要求的是路程最短，所以路线选择只可能考虑相近城市来往。城市之间车费是通过互联网票

6、务查询系统按照模型假设收集，但是有部分城市之间并无直达车次，我们规定如果去其他城市转乘次数不超过一次，那么这两个城市间的车费就是转乘后的总车费，若转乘次数超过两次，两个城市就视为不能直接来往。在第二问中，因为要求计算车费最小的路线，所以我们规定不能直接来往的城市车费记为10000元。数据结果显示如下图四。第三问要求综合考虑省时，省钱，制定最优方案。由假设条件知，本题的目标函数应该为：其中为区间的一个实数，但是因为路程和费用的量纲不同，这样得到的结果并不是很好，所以我们对目标函数做一个修正，设一二问求得的最短的路程和最少的车费分别为和，目标函数（评价标准）为： 我们假设游客对省时和省钱同样的看中

7、，即，那么目标函数为：本文的约束条件是一二问所有的约束条件。六、问题解决采用lingo编程（程序见附录）求解得到第一问的矩阵使用matlab编程（程序见附录）处理数据得到路线和路线图为：路线：1>4>3>2>6>10>9>13>14>15>16>18>17>12>11>7>8>5>1第二问模型求解后得到的轨迹图为：路线为：1>2>6>13>10>9>11>7>14>15>18>16>17>12>8>

8、5>4>3>1第三问得到的轨迹图为：路线为：1>2>6>13>10>9>14>15>16>18>17>12>11>7>3>4>8>5>1灵敏度分析：第三文中如果比较在意经济方面，那么令，则结果变为：路线为：1>3>4>5>8>12>17>18>16>15>14>7>11>9>10>13>6>2>1如果经济比较宽裕，那么令，那么结果变为：路线为：1>2>

9、6>13>10>9>14>15>16>18>17>12>11>7>8>5>4>3>1七、回答问题回答问题（1）：要使路程最短，路线应该设计为：海口=>定安=>澄迈=>临高=>儋州=>白沙=>昌江=>东方=>乐东=>五指山=>保亭=>三亚=>陵水=>万宁=>琼中=>屯昌=>琼海=>文昌=>海口回答问题（2）：要使费用最少，路线应该规划为：海口=>临高=>儋州=>东方=>白

10、沙=>昌江=>琼中=>屯昌=>乐东=>五指山=>三亚=>保亭=>陵水=>万宁=>琼海=>文昌=>定安=>澄迈=>海口回答问题（3）：如果同等看重经济和时间则路线为：海口=>临高=>儋州=>东方=>白沙=>昌江=>乐东=>五指山=>保亭=>三亚=>陵水=>万宁=>琼中=>屯昌=>澄迈=>定安=>琼海=>文昌=>海口如果较看重经济则路线为：海口=>澄迈=>定安=>文昌=>琼海=>

11、万宁=>陵水=>三亚=>保亭=>五指山=>乐东=>屯昌=>琼中=>昌江=>白沙=>东方=>儋州=>临高=>海口如果较看重时间则路线为：海口=>临高=>儋州=>东方=>白沙=>昌江=>乐东=>五指山=>保亭=>三亚=>陵水=>万宁=>琼中=>屯昌=>琼海=>文昌=>定安=>澄迈=>海口八、模型推广本文解决的问题是针对海南旅游，推广到一般情况，某人计划到个城市进行旅游，要求分别从省时，省钱和综合考虑两个方面进行规划

12、路线。设计划决策变量为 ： 目标函数为： 城市与城市之间的距离（路程，费用等）约束条件为： 九、心得体会通过本次建模实验，我对数学建模了解更加深刻了一些。本题开始我是通过使用遗传算法解决，发现虽然收敛的十分迅速，但是进入到了一个局部最优解，始终找不到全局最优解。然而使用数学建模的方法，找到约束条件，用lingo计算，很快的就找到了最优解。所以，建模中算法并非最重要的，根本还是要实实在在的建立模型。参考文献1王继强。 基于LINGO的旅行商问题的建模方法J。 计算机工程与科学,2014,(05):947-950。2姜启源，谢金星。数学模型（第四版）。北京：高等教育出版社，2011，1。3谢金星，

13、薛毅。LINGO软件的基本使用方法。北京：清华大学出版社，2005，程序附录（因为第三问综合了前两问，所以本文只附求解第三问的程序）：sets:dian/1.18/:u; link(dian,dian):d,m,x;endsetsdata:m=ole('E:jianmo01。xlsx','data2');d=ole('E:jianmo01。xlsx','data1');enddatan=size(dian);min=(sum(link(i,j)|i#ne#j:d(i,j)*x(i,j)-1488。11)/1488。11*0。5+(

14、sum(link(i,j)|i#ne#j:m(i,j)*x(i,j)-276)/276*0。5;m=ole('E:jianmo01。xlsx','data2');!费用矩阵;d=ole('E:jianmo01。xlsx','data1');!距离矩阵; for(dian(i):for(dian(j)|j#ne#i#and#j#gt#1:u(i)-u(j)+n*x(i,j)<n-1);for(link:bin(x);data:ole('E:jianmo01。xlsx',data4)=X;enddataMATLA

15、B程序：1。（求城市坐标）：a=imread('hainanditu。jpg');imshow(a);axis onx,y=ginput(18);for i=1:length(x) text(x(i),y(i),num2str(i);endcitys=x,y;save citys2。（处理数据）load chengshi%海南各市县的名字load shunxu%lingo求得的x（i，j）矩阵load citys%求得的城市坐标D=Distanse(citys);%算距离a=find(shunxu(1,:)=1);order=zeros(1,18);order(1,1,2)=1

16、,a;for i=1:16 b=find(shunxu(order(1,i+1),:)=1); order(1,i+2)=b;enddisp('最优解：')p=OutputPath(order);%输出最优解DrawPath(order,citys)%化轨迹图%输出最优解的各市县名字dazi=zeros(1,37);dazi(1:2:36)=2*order-1;dazi(2:2:36)=2*order;dazi=dazi'order=order'for i=1:36 lal(i)=chengshi(dazi(i);endhah=;for i=1:18 hah=h

17、ah,lal(2*i-1,2*i),'=>' if i=18 hah=hah,'海口' endendhah3。 (OutputPath):% 输出路径函数%输入：R 路径function p=OutputPath(R)R=R,R(1);N=length(R);p=num2str(R(1);for i=2:N p=p,'>',num2str(R(i);enddisp(p)4。画图：function DrawPath(Chrom,X)R=Chrom(1,:) Chrom(1,1); %一个随机解(个体)figure;hold onplot(X(:,1),X(:,2),'o','color',0。5,0。5,0。5)plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20)for i=1:size(X,1) text(X(i,1)+7,X(i,2)+10,num2str(i),'color',1,0,0,'FontSize'