数学建模论文 旅游中国

旅游中国摘要旅游中国是一个旅行商问题，本文给出了从西安出发走遍全国各省会城市，直辖市及港澳台的一条旅游路线，主要从旅行时间，路费，方便程度来进行合理建模和分析，得到最终方案。问题一，我们查到34个城市的经纬度，用matlab编程，把经纬度化成弧度，计算出各个城市间的球面距离，得到一个3434的邻接矩阵，建立旅行商的混合整数规划模型，利用lingo求解得到最短路程为15677.05千米，其具体路线为：西安郑州济南沈阳长春哈尔滨天津北京石家庄太原呼和浩特银川兰州西宁乌鲁木齐拉萨昆明贵阳南宁海口广州澳门香港台北福州杭州上海南京合肥武汉南昌长沙重庆成都西安.问题二要求设计最经济的旅行互联网上订票方案。我们通过查询资料得出全国所有省会之间的火车、动车以及飞机票价，由于在三种出行方式（硬卧、动车、飞机）中，硬卧比其它两种出行方式的花费小，所以我们选择硬卧作为首要考虑的出行方式。其次，在实际中两地之间存在没有直达列车的情况，在求解过程中利用问题一的混合整数线性规划模型中的lingo程序进行求解，得到最小花费为：10108元，相应的最佳旅行路线为：西安→拉萨→西宁→兰州→银川→呼和浩特→北京→沈阳→长春→哈尔滨→天津→济南→南京→合肥→南昌→福州→杭州→上海→澳门→台北→香港→广州→海口→长沙→南宁→昆明→贵阳→成都→重庆→乌鲁木齐→重庆→武汉→广州→石家庄→太原→西安。问题三是从省钱、省时又方便三个方面来考虑得出最优旅行方案，即就是衡量对时间和价钱之间的倾向比。我们给出了火车、飞机的时间和票价的权重，通过计算每种交通工具的总权重，来选择合适的交通工具。最后再根据方便这个因素，进行相应调整。问题四和问题五主要是在我们计算过程中，通过实际操作和体会，对我们的算法进行客观评价和深入理解。关键词：旅行商问题LINGO求解MATLAB求解加权求最优一、问题重述秦先生要从西安出发到全国各个省会城市、直辖市等共34个城市去旅游，以下是要解决的问题：问题1：按地理位置（经纬度）设计最短路旅行方案（即旅行商问题）。问题2：2011年9月1日秦先生从西安市出发，每个城市停留3天，可选择航空、铁路（快车卧铺、动车），设计最经济的旅行互联网上订票方案。问题3：综合考虑省钱、省时又方便，设定评价准则，建立数学模型，修订方案。问题4：对算法作复杂性、可行性及误差分析。问题5：关于旅行商问题给出对所采用的算法的理解及评价。二、模型假设1、设计最短路线时所用的两城市间的距离为球面距离。2、忽略因自然原因及人为原因造成的交通堵塞，航班取消等可能。3、每次均可以成功订购票，并且按照题目要求，快车均定卧铺票。三、符号说明ijx：0-1变量；ijc：表示从i城市到j城市的距离；iu：额外变量；iq：快卧的总权重；iQ：动车的总权重；im：不同城市间快卧的票价；iM：不同城市间动车的票价；it：不同城市间快卧所用的时间；iT：不同城市间动车所用的时间；im,iM，it,iT：标准化后的数据；四、问题分析5.1问题一的分析问题一寻找一条从西安出发，走遍其余33个城市，又回到西安的最短的路线。将每个城市看成图中的一个节点，各节点之间的路看成对应节点的边，各节点之间的地表距离看做对应边上的权，问题就自然转换为一个图论问题，即旅行商问题（TSP模型），我们用的方法是把TSP模型转化成混合整数线性规划模型，然后用lingo求解。5.2问题二的分析题目要求给出最经济的旅行方案，而飞机比火车贵，所以两个城市之间首先考虑快卧和动车，只有两城市之间没有快卧和动车时，才选用飞机。5.3问题三的分析本问题在第二问的基础上加强了需要考虑的限制性因素，即要求所给的交通工具方案不仅省钱而且还要节省时间，另外还有一个不确定的量就是要方便。首先我们只考虑省钱和省时，最后再从方便的角度出发，在省钱和省时的基础之上进行相应的调整。五、模型建立6.1问题一的模型混合整数线性规划模型：引入0-1整数变量ijx（ij）:ijx=1表示路线从i到j，ijx=0表示不走i-j路线，则TSP模型可表示为：minZ=niijnjijxc11，其中ijc表示从i城市到j城市的距离，因为ijx是0-1变量，所以目标函数Z表示了从某个城市出发，走遍若干城市的最短路线。约束条件为：s.t.jinjixjinjxijnixijniijnjij,,...2,1,,1,0,,,...2,1,1,,,...2,1,111其中前两个条件限制了每个城市走且只走一次，最后一个条件说明x为0-1变量。但这个模型含有子巡回的路线（如4-5-6-4），显然不能作为TSP的解。这里，我们运用一种在原模型上附加约束条件以避免产生子巡回的方法。把额外变量),,3,2(niui附加到问题中。可把这些变量看作是连续的（显然这些变量在最优解中取整数值）。现在附加下面形式的约束条件：njinxnuuijji2,1u可以理解为每个节点的度，这个约束条件是为了让每个节点的度相同，都等于2，这样就保证了每个城市只走一次，避免了子巡回的情况。这样就转化成了一个混合整数线性规划模型：niunjixnjinxnuunixnjxtsxcziijijjinjijniijnjijiijij,,3,2,0,,2,1,,1,02,1,,2,1,1,,2,1,1..min111,6.2问题二（1）模型假设本题中由于动车和飞机票价的上下浮动比较大，且不管怎么样他们的价格都要比火车价格贵，所以我们假设任何时候坐火车都要比坐动车和飞机便宜，但是因为从大陆去港澳台没有火车，所以我们假定去港澳台做飞机。（2）模型的建立与求解我们将各城市之间火车票价格矩阵，通过matlab编程得到任意两个城市之间的最小票价矩阵。不能直接到达的用虚拟价格代替。然后利用问题一的混合整数线性规划模型中的LINGO程序进行求解，得到最小花费为：10108.00元。最佳旅行路线为：西安→拉萨→西宁→兰州→银川→呼和浩特→北京→沈阳→长春→哈尔滨→天津→济南→南京→合肥→南昌→福州→杭州→上海→澳门→台北→香港→广州→海口→长沙→南宁→昆明→贵阳→成都→重庆→乌鲁木齐→重庆→武汉→广州→石家庄→太原→西安始发站终点站乘车方式车票价格西安拉萨火车518拉萨西宁火车395西宁兰州火车84兰州银川火车93银川呼和浩特火车169呼和浩特北京火车165北京沈阳火车177沈阳长春火车98长春哈尔滨火车92哈尔滨天津火车271天津济南火车103济南南京火车165南京合肥火车75合肥南昌火车80南昌福州火车157福州杭州火车191杭州上海火车80上海澳门飞机530澳门台北飞机1800台北香港飞机1896香港广州飞机560广州海口火车191海口长沙火车323长沙南宁火车224南宁昆明火车201昆明贵阳火车157贵阳成都火车145成都重庆火车98重庆乌鲁木齐火车178乌鲁木齐重庆火车178重庆武汉火车271武汉广州火车133广州石家庄火车115石家庄太原火车89太原西安火车1066.3问题三的模型由于要均衡考虑价钱和时间，因此需要对快卧和动车的价钱和时间进行权重（iq，iQ）比较。设秦先生对价钱的权重为a=0.4106,对时间的权重为b=0.3155。首先查出从一个城市出发到另一个城市的快卧和动车的价钱（im,iM）和相应时间（it,iT），再对其进行标准化，标准化后的数据分别为im,iM，it,iT。则有：iq=aim+bit;iQ=aiM+biT;最后比较快卧和动车的权重。如果iqiQ,选择动车；反之则选快卧。由于飞机的价钱高，时间短的特点，需要对飞机的价钱和时间另给权重：a=0.0456;b=0.4056;不同的人对价钱和时间的要求不同，本题只针对秦先生拟定了一个权重，如果对不同的人，只需改动权重，再代入计算即可。最后再来考虑方便。我们得到以下几个因素：（1）如果选用火车，看它的出发时间与到达时间是在晚上还是白天。把出发与到达都在白天定位方便；（2）火车站的某个时段是否拥挤。把不拥挤定为方便；（3）如果快车与动车权重之差小于410，也就是认为快车与动车权重相等，此时选坐动车方便，因为考虑到动车比较舒适；（4）尽量避免中途转站的情形；六、模型求解7.1问题一的求解：首先根据每个城市的经纬度，用matlab计算出每两个城市之间的球面距离。然后以距离作为图中对应边的权，用lingo求解混合整数线性规划模型得到的最短旅游路线如下表：路程单位：千米城市旅游顺序到下一个城市的距离城市旅游顺序到下一个城市的距离西安1444.72南宁19343.81郑州2391.01海口20456.28济南3781.4广州21278.1沈阳4278.83澳门2212.267长春5230.75香港23760.01哈尔滨61042台北24241.04天津795.964福州25465.83北京8239.19杭州26157.58石家庄9181.17上海27285.74太原10336.43南京28134.48呼和浩特11513.71合肥29314.3银川12341.49武汉30254.74兰州13186.01南昌31291.57西宁141435.1长沙32625.41乌鲁木齐151598重庆33249.76拉萨161220.4成都34597.41昆明17426.42西安35贵阳18466.13总路程15677.05旅游路线图7.2问题二7.2.1模型一的结果：西安动车郑州动车济南快车沈阳动车长春动车哈尔滨快车天津动车北京动车石家庄动车太原动车呼和浩特快车银川动车兰州动车西宁飞机乌鲁木齐飞机拉萨飞机昆明动车贵阳快车南宁飞机海口飞机广州飞机澳门动车香港飞机台北飞机福州快车杭州动车上海动车南京动车合肥动车武汉动车南昌动车长沙快车重庆动车成都快车西安7.2.2模型二的结果：价格单位：元城市旅游顺序到下一个城市的距离飞机动车快车西安1444.7273郑州2391.0145济南3781.4120沈阳4278.8328长春5230.7523哈尔滨6104290天津795.96413北京8239.1944石家庄9181.1716太原10336.4343呼和浩特11513.7146银川12341.4934兰州13186.0138西宁141435.11130乌鲁木齐1515981730拉萨161220.42500昆明17426.4246贵阳18466.13116南宁19343.81500海口20456.28290广州21278.11303澳门2212.267坐船914.4香港23760.011684台北24241.041160福州25465.8394杭州26157.5829上海27285.7441南京28134.4824合肥29314.354武汉30254.7452南昌31291.5763长沙32625.4188重庆33249.7636成都34597.4199西安35共计：12566.4元7.3问题三的求解旅游顺序城市飞机票价快卧票价动车票价飞机权重动车权重快车权重最终选择票价1西安101473155-0.271290.1682330.160625飞机10142郑州52645200-0.291480.84333-0.13725飞机5263济南6601370.08902901.261728飞机6604沈阳140828930.300251-0.16153-0.56178快车285长春96923410.390252-0.47365-0.65174快车236哈尔滨530902810.0115431.8791611.319621飞机5307天津13400-0.69446-0.85017快车138北京39440-0.37739-0.29936动车449石家庄22160-0.78037-0.52713动车1610太原1091430.79190-0.06185快车4311呼和浩