走遍全中国
B题：走遍全中国
摘要:目前旅游在我国得到了迅速健康的发展，并极大的促进我国经济的发展。本文针对各种不同旅游航线以及价格等因素进行了讨论，可理解为路程最短问题，根据最短路线，建立最优方案的旅游花费问题。因此围绕路程问题建立数学模型。
模型Ⅰ，根据题中所提供的已知条件,又知中国共分为34个省（包括直辖市、香港、澳门、台北），根据每个省会的实际位置，利用lingo 软件计算最短路程。 经过编程计算设计较为合理。
模型Ⅱ中，根据题中所约束条件要想求最省钱的路线则根据各省市火车路线价格没有火车路线则用飞机航线价格来代替，因为飞机的价格要比火车价格多得多，利用lingo软件计算最省钱路线以及旅游路线。我们有理由认为这是一条最省钱的路线。
模型Ⅲ中，根据第一问、第二问中的利用软件建立的数学结构，用得到的最短路线与最省钱的路线两种情况进行综合考虑，分别得到了满足模型Ⅰ和模型Ⅱ得出最优方案。
模型Ⅳ中，我们所建立的数学模型主要数据来源最新互联网网站，难免存在误差；另外，根据天气变化，路线临时调整等原因，最后价格存在一定的波动情况，我们仅仅考虑了最优方案，假设其它一切不变的情况下进行数学建模。
模型Ⅴ中，根据我们所建立的数学模型，主要是利用lingo 软件计算出最短路程，然后结合实际计算出最优方案。
本章还从铁路路线价格、航空路线价格变动进行了进一步的讨论。
关键词：最短路线 最少价 最优方案 省时 误差分析 lingo求解
一 问题重述
周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案： 现需解决一下问题：
1．按地理位置（经纬度）设计最短路旅行方案；
2．如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；
3．要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；
4．对你的算法作复杂性、可行性及误差分析；
5．关于旅行商问题提出对你自己所采用的算法的理解及评价。
二 背景介绍
由于现在的生活水平的提高，出去旅游成为当今的时尚，越来越多的人利用自己生活业余的时间来游览祖国的大好和河山。但是，怎么选取旅行路线以及如何安排旅游行程便成了人们关注的问题。因此，本题中我们建立一定的数学模型来比较说明两地间不同路线不同方式的旅游模式，以取得最优方案，达到经济实惠的旅游路线。
三 问题分体
本题主要讨论怎么样取得最短旅游路线以及最经济的旅游方案。
第一问中，根据题中提供的已知条件，周游先生要游历全国34个省市，根据中国地图上各个省市位置，描绘出各个省市的位置。进而绘制出详细的旅游路线图。利用lingo 软件，根据查找的省会之间的具体，计算出最短路程。
第二问中，首先确定了出发地点与结束地点，查阅省会之间不同交通方式的价格，对比不同的价格，利用lingo 软件，得出最优方案。
第三问中，每两个省会之间的交通方式不同，造成的价格以及时间等都会不同，因此会造成与实际的误差。
第四问中，本题所建立的数学模型的复杂性，体现在对于每两个省会之间的交通费用查阅；另外，我们计算每个省会之间的具体考虑的均为直线距离，在实际生活中，并没有考虑到路程的可行性。
第五问中，关于旅行商问题，首先应该把路程最短考虑到，其次是考虑价格最低，然后综合其它因素，取得最优方案。
四 基本假设
1、在考虑最短路线时，所截取的路线均是直线考虑，不涉及实际路线要求； 2、在第二问中，每个城市停留3天，假设从A城赶往B城时，所花费的时间算在B城中停留的时间；从B城赶往C城中，所花费的时间算在C城中停留的时间；以此类推。
3、忽略因自然原因及人为原因造成的交通堵塞，航班取消等可能。 4、认为每次均可以成功订购车票。 5、认为旅途花销仅是车票的花销。 6、票价数据包括打折优惠的情况。
五 模型的建立与求解
5.1
考虑最短路线
这是一个旅行商问题，重要在找出最小权Hamilton圈，称这种圈为最优圈。
设
C=v1v2…vnv1,则对于所有适合
1
Hamilton圈
Cij=v1v2…vivjvj-1…vi+1vj+1vj+2…vnv1,它是由C中删去边vivi+1和vjvj+1添加vivj和vi+1和vj+1,得到的。
如对于某一对i和j，有
W(vivj)+w(vi+1vj+1)
则圈Cij将是圈C的一个改进。在接连进行上述一系列修改之后，最后得到一个圈不能在用此方法改进了。这个最后的圈几乎可以肯定不是最优的。但有理由认为它是比较好的。
第一题的相应线性规划问题是：
minZ=dijxij
i,j1
n
x=1 j=1,2,3,…,n
ij
i1ij
n
x=1 i=1,2,3,…,n
ij
j1ji
n
Uj>=Uk+Xkj-(N-2)*(1-Xkj)+(N-3)*Xjk Uk
Uk>=1+(N-2)*Xk 1
根据中国地图中所示
设计最短路线，利用lingo 软件设计程序 程序如下： MODEL: SETS:
city/1..34/:u;
link(city,city):d,x; ENDSETS DATA:
d = @file(juli.txt) ; ENDDATA
n=@SIZE(city);
MIN=@SUM(link:d*x);
@FOR(city(k):@sum(city(i)|i#ne#k:x(i,k))=1; @sum(city(j)|j#ne#k:x(k,j))=1;
@for(city(j)|j#gt#1#and#j#ne#k:
u(j)>=u(k)+x(k,j)-(n-2)*(1-x(k,j))+(n-3)*x(j,k)); );
@FOR(link:@BIN(x)); @for(city(k)|k#gt#1: u(k)=1+(n-2)*x(k,1)); END
各个省市（包括直辖市以及港澳台）距离表：
经运行得到结果：
X( 1, 23)=1， X( 2, 24)=1， X( 3, 2)=1， X( 4, 3)=1， X( 5, 4)=1， X( 6, 32)=1， X( 7, 8)=1， X( 8, 9)=1， X( 9, 10)=1， X( 10, 11)=1，X( 11, 1)=1，X( 12, 13)=1，X( 13, 14)=1，X( 14, 15)=1，X( 15, 17)=1，X( 16, 21)=1，X( 17, 16)=1，X( 18, 27)=1，X( 19, 18)=1，X( 20, 19)=1，X( 21, 25)=1，X( 22, 12)=1，X( 23, 22)=1，X( 24, 6)=1，X( 25, 20)=1，X( 26, 34)=1，X( 27, 28)=1，X( 28, 29)=1，X( 29, 26)=1，X( 30, 31)=1，X( 31, 7)=1， X( 32, 33)=1，X( 33, 30)=1，X( 34, 5)=1，
路线图：
1→23→22→12→13→14→15→17→16→21→25→20→19→18→27→28→29→26→34→5→4→3→2→24→6→32→33→30→31→7 →8→9→10→11→1
即最短短线旅游路线图为：成都→重庆→贵阳→昆明→南宁→海口→澳门→香港→广州→长沙→武汉→南昌→福州→台北→杭州→上海→南京→合肥→济南→天津→北京→沈阳→长春→哈尔滨→呼和浩特→太原→石家庄→郑州→西安→银川→兰州→西宁→乌鲁木齐→拉萨→成都
由程序结果可以得出最短的路程为：15697.00公里 5.2
求最省钱路线，
第二题的相应线性规划问题是：
minZ=dijxij
i,j1
n
x=1 j=1,2,3,…,n
ij
i1ij
n
x=1 i=1,2,3,…,n
ij
j1ji
n
Uj>=Uk+Xkj-(N-2)*(1-Xkj)+(N-3)*Xjk Uk
Uk>=1+(N-2)*Xk 1
具体编程如下： MODEL: SETS:
city/1..34/:u;
link(city,city):d,x; ENDSETS DATA:
d = @file(jiage.txt) ; ENDDATA
n=@SIZE(city);
MIN=@SUM(link:d*x);
@FOR(city(k):@sum(city(i)|i#ne#k:x(i,k))=1; @sum(city(j)|j#ne#k:x(k,j))=1; @for(city(j)|j#gt#1#and#j#ne#k:
u(j)>=u(k)+x(k,j)-(n-2)*(1-x(k,j))+(n-3)*x(j,k)); );
@FOR(link:@BIN(x)); @for(city(k)|k#gt#1: u(k)=1+(n-2)*x(k,1)); END
下表表示各省市直接具体票价（不含波动因素）
注：子表表示铁路路线价格表没有铁路路线则用航空路线价格表代替，……表示没有火车路线也没有飞机航线。把子表代入下程序。因为求最省钱路线则……用一个很大的数字代替如9999代入程序中
运行程序得到结果： X( 1, 25)=1，X( 2, 3)=1，X( 3, 32)=1，X( 4, 15)=1，X( 5, 4)=1，X( 6, 24)=1，X( 7, 6)=1，X( 8, 11)=1，X( 9, 7)=1，X( 10, 8)=1，X( 11, 9)=1，X( 12, 22)=1，X( 13, 12)=1，X( 14, 21)=1，X( 15, 18)=1，X( 16, 14)=1，X( 17, 16)=1，X( 18, 17)=1，X( 19, 27)=1，X( 20, 13)=1，X( 21, 19)=1，X( 22, 23)=1，X( 23, 1)=1，X( 24, 2)=1，X( 25, 34)=1，X( 26, 20)=1，X( 27, 28)=1， X( 28, 29)=1，X( 29, 26)=1，X( 30, 33)=1，X( 31, 30)=1，X( 32, 31)=1，X( 33, 5)=1，X( 34, 10)=1，
旅行路线如下序号：
1→25→34→10→8→11→9→7→6→24→2→3→32→31→30→33→5→4→15→18→17→16→14→21→19→27→28→29→26→20→13→12→22→23→1
路线图：
成都→武汉→济南→乌鲁木齐→兰州→拉萨→西宁→银川→呼和浩特→哈尔滨→长春→沈阳→太原→西安 →郑州→石家庄→天津→北京→澳门→台北→香港→广州→海口→福州→杭州→上海→南京→合肥→南昌→南宁→昆明→贵阳→重庆→成都
总价格：9902元
具体订票方案如下：
成都至武汉为乘南方航空CZ3442，至济南为厦门航空MF8562，至乌鲁木齐为火车1085，至兰州为火车T197，至拉萨为火车T222，至西宁为火车T22，至银川为火车K916，至呼和浩特为火车K885，至哈尔滨为火车1816，至长春为火车T184，至沈阳为火车T124，至太原为火车1174，至西安为火车K690，至郑州为火车T194，至石家庄为火车T89，至天津为火车T182，至北京为火车T225，至澳门为东方航空MU5183/FM807，至台北为澳门航空 NX518，至香港为中华航空 CI679，至广州为南方航空 CZ304，至海口为乘深圳航空ZH9611，至福州为深圳航空ZH9611，至杭州为火车K164，至上海为火车T33， 至南京为火车T7776，至合肥为火车K8436，至南昌为火车K311，至南宁为火车K1192，至昆明为火车K230，至贵阳为火车T61，至重庆为火车K529，至成都为火车K530。
5.3
考虑到周先生是位退休老人所以将省时和行程最短优先考虑，其次是经济问题，结合省钱、省时又方便的原则，可以结合第一、二问所找到的两条最优路线，
由于最经济的路线所经过的路程和时间比最短路线要多，可以在最短的路线方案上结合最经济路线进行改进：
成都—国航CA4445（1500元）—拉萨—T28（409元）—西宁—T28（27元）—兰州—南航CZ6952（1600元）—乌鲁木齐—南航CZ6963（1350元）—银川—K359（130元）—西安—G2002（390元）—郑州—D134（153元）—石家庄—D2061（83元）—太原—2461（70元）—呼和浩特—1813（173元）—哈尔滨—T155（87元）—长春—D24（111元）—沈阳—D4（260元）—北京—C2009（69元）—天津—T33（98元）—济南—K692（153元）—合肥—D5477（58元）—南京—D5477（93元）—上海—D5653（63元）—杭州——国航CA149（2300元）台北—厦门航空MF884（1790元）—福州—K666（87元）—南昌—T275（106元）—武汉—T263（47元）—长沙—G1021（315元）—广州—大巴（100元）—香港—快艇（100元）—澳门—乘车到珠海转南航CZ3845（600元）—海口—南航CZ3342（250元）—南宁—K482（88元）—昆明—T62（162元）—贵阳—K872（42元）—重庆—D5101（117元）—成都
六 模型评价
优点：1思路比较简单，没有太多复杂的运算过程。
2.利用的数据间的对比得到的结果，比起复杂的计算过程更直观，更让人易明白。
3.建立的模型求解最短路程时，与实际路程基本保持一致。 4提供了优化方案，以供参考。
缺点：1数据大部分参考来自于互联网，数据缺乏一定的准确性。 2没有考虑旅行路线的实际路况，一切均是最优考虑。 3数据太多，列出来比较麻烦。
七 参考文献
【1】 薛毅，动态规划，图论与网络模型，北京工业大学出版社，北京，2005 【2】 杨桂元，李天胜，徐平，线性代数，合肥工业大学出版社，合肥，2007 【3】 肖华勇，基于MATLAB和LINGO的数学实验，西北工业大学出版社，西安，
2009