数学建模旅游商bgf问题 3

1、B题：走遍全中国 摘要:目前旅游在我国得到了迅速健康的发展，并极大的促进我国经济的发展。本文针对各种不同旅游航线以及价格等因素进行了讨论，可理解为路程最短问题，根据最短路线，建立最优方案的旅游花费问题。因此围绕路程问题建立数学模型。模型，根据题中所提供的已知条件,又知中国共分为34个省（包括直辖市、香港、澳门、台北），根据每个省会的实际位置，利用lingo 软件计算最短路程。经过编程计算设计较为合理。模型中，根据题中所约束条件要想求最省钱的路线则根据各省市火车路线价格没有火车路线则用飞机航线价格来代替，因为飞机的价格要比火车价格多得多，利用lingo软件计算最省钱路线以及旅游路线。我们有理由认

2、为这是一条最省钱的路线。模型中，根据第一问、第二问中的利用软件建立的数学结构，用得到的最短路线与最省钱的路线两种情况进行综合考虑，分别得到了满足模型和模型得出最优方案。模型中，我们所建立的数学模型主要数据来源最新互联网网站，难免存在误差；另外，根据天气变化，路线临时调整等原因，最后价格存在一定的波动情况，我们仅仅考虑了最优方案，假设其它一切不变的情况下进行数学建模。模型中，根据我们所建立的数学模型，主要是利用lingo 软件计算出最短路程，然后结合实际计算出最优方案。本章还从铁路路线价格、航空路线价格变动进行了进一步的讨论。关键词：最短路线 最少价 最优方案 省时 误差分析 lingo求解一

3、问题重述周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：现需解决一下问题：1按地理位置（经纬度）设计最短路旅行方案；2如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；3 要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；4对你的算法作复杂性、可行性及误差分析；5关于旅行商问题提出对你自己所采用的算法的理解及评价。二 背景介绍由于现在的生活水平的提高，出去旅游成为当今的时尚，越来越多的人利用自己生活业余的时间来游览祖国的大好和河

4、山。但是，怎么选取旅行路线以及如何安排旅游行程便成了人们关注的问题。因此，本题中我们建立一定的数学模型来比较说明两地间不同路线不同方式的旅游模式，以取得最优方案，达到经济实惠的旅游路线。三 问题分体 本题主要讨论怎么样取得最短旅游路线以及最经济的旅游方案。第一问中，根据题中提供的已知条件，周游先生要游历全国34个省市，根据中国地图上各个省市位置，描绘出各个省市的位置。进而绘制出详细的旅游路线图。利用lingo 软件，根据查找的省会之间的具体，计算出最短路程。第二问中，首先确定了出发地点与结束地点，查阅省会之间不同交通方式的价格，对比不同的价格，利用lingo 软件，得出最优方案。第三问中，每两

5、个省会之间的交通方式不同，造成的价格以及时间等都会不同，因此会造成与实际的误差。第四问中，本题所建立的数学模型的复杂性，体现在对于每两个省会之间的交通费用查阅；另外，我们计算每个省会之间的具体考虑的均为直线距离，在实际生活中，并没有考虑到路程的可行性。第五问中，关于旅行商问题，首先应该把路程最短考虑到，其次是考虑价格最低，然后综合其它因素，取得最优方案。四 基本假设1、在考虑最短路线时，所截取的路线均是直线考虑，不涉及实际路线要求；2、在第二问中，每个城市停留3天，假设从A城赶往B城时，所花费的时间算在B城中停留的时间；从B城赶往C城中，所花费的时间算在C城中停留的时间；以此类推。3、忽略因自

6、然原因及人为原因造成的交通堵塞，航班取消等可能。4、认为每次均可以成功订购车票。5、认为旅途花销仅是车票的花销。6、票价数据包括打折优惠的情况。五 模型的建立与求解5.1 考虑最短路线这是一个旅行商问题，重要在找出最小权Hamilton圈，称这种圈为最优圈。设C=v1v2vnv1,则对于所有适合1<i+1<j<n的I和j，可以得到一个新的Hamilton圈Cij=v1v2vivjvj-1vi+1vj+1vj+2vnv1,它是由C中删去边vivi+1和vjvj+1添加vivj和vi+1和vj+1,得到的。如对于某一对i和j，有 W(vivj)+w(vi+1vj+1)<w(

7、vivi+1)+w(vjvj+1)则圈Cij将是圈C的一个改进。在接连进行上述一系列修改之后，最后得到一个圈不能在用此方法改进了。这个最后的圈几乎可以肯定不是最优的。但有理由认为它是比较好的。第一题的相应线性规划问题是：minZ=1j=1,2,3,n=1i=1,2,3,nUj>=Uk+Xkj-(N-2)*(1-Xkj)+(N-3)*XjkUk<=N-1-(N-2)*X1 kUk>=1+(N-2)*Xk 1根据中国地图中所示设计最短路线，利用lingo 软件设计程序程序如下：MODEL:SETS:city/1.34/:u;link(city,city):d,x;ENDSETSD

8、ATA:d = file(juli.txt) ;ENDDATAn=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)<=n-1-(n-2)*x(1,k);u(k)>=1+(n-2)*x(k,1);

9、END各个省市（包括直辖市以及港澳台）距离表：附表 1.(juli.txt)城市（公里）哈尔滨1长春2沈阳3北京4 天津5呼和浩特6银川7兰州8西宁9哈尔滨10245513105710711316185921842295长春224502728638571167170320312154沈阳35132720625606976150918001950北京41057863625011141789211861333天津51071857606111050495312331391呼和浩特6131611679764175040537872985银川71859170315098929535370346446兰州

10、8218420311800118612338723460197西宁9229521541950133313919854461970乌鲁木齐10305630022911242325162011167016271442拉萨11357534073197257426102247170613901255昆明12314929382678209420751946152612341288南宁13303928002537204819942027175615351659海口14322930022729228922272316208918962019澳门15289726442383198719122081194218

11、001957广州16283826192210188918131971182916961860香港17284125982340196218832068193918261979台北18235021211872171716121975206920782275福州19230020541803155314631779184318292028南昌20212418871624125811641410141514001590长沙21229620601787133812761407129712141388贵阳22277725632290174017071643132010731196重庆232528229923

12、83146414471336983746886成都24258023912133152915341327889594688武汉2520011770149810529801156114511381332合肥261760151312479018061110123513161503杭州27183615851327113010291399156816501846上海2816871445119510639531375159417101904南京291676144111708997961163133814401636郑州301653142911736315796937778961089西安311994178

13、21522917915770525508702太原32152112611017410434334554791961石家庄33132311238592482663927189631133济南341297107080336327364697111711355城市（公里）乌鲁木齐10拉萨11昆明12南宁13海口14澳门15广州16香港17台北18哈尔滨1305635753149303932292897283828412350长春2300234072938280030022644261925982121沈阳3291131972678253727292383221023401872北京424232574

14、2094204822891987188919621717天津5251626102075199422271912181318831612呼和浩特6201122471946202723162081197120681975银川7167017061526175620891942189219392069兰州8162713901234153518961800169618262078西宁9144212551288165920191957186019792275乌鲁木齐10016082499301233883386329234123712拉萨1116080125818862214238423252441304

15、6昆明122499125806249551141108611931885南宁133012188662403695345065991359海口143388221495536904054594701275澳门15338623841141534405011868877广州163292232510865064591180126863香港17341224411193599470681260808台北18371230461885135912758778638080福州1934692791165611651084733688662261南昌2030452413136810001110767674720688

16、长沙21284921301069759952691576671932贵阳22249915644264708278677789031510重庆232284148562779111461100100011341584成都242066125363797913481339125113721831武汉2527562232128710541235949838927961合肥2629012500160113321482114710481108871杭州2732422801181114411501113010471070602上海2832702905195416411675128312171228700南京2

17、930112654174414601586122611371176837郑州30244121871500143116721414130413921338西安31212117591182127815961434131514291593太原32219321771700172819971761164417421670石家庄33234123481826180220431780167117511603济南34260025331870176019471657154816221379城市（公里）福州19南昌20长沙21贵阳22重庆23成都24武汉25合肥26杭州27哈尔滨123002124229627772

18、5282580200117601836长春2205418872060256322992391177015131585沈阳3180316241787229023832133149812471327北京415531258133817401464152910529011130天津51463116412761707144715349808061029呼和浩特6177914101407164313361327115611101399银川71843141512971320983889114512351568兰州81829140012141073746594113813161650西宁92028159013

19、881196886688133215031846乌鲁木齐10346930452849249922842066275629013242拉萨11279124132130156414851253223225002801昆明12165613681069426627637128716011811南宁1311651000759470791979105413321441海口141084111095282711461348123514821501澳门157337676918671100133994911471130广州166886745767781000125183810481047香/p>

20、9031134137292711081070台北18261688932151015841831961871602福州190434677126213271579707679479南昌2043403059459371182281378442长沙216773050638643895298588744贵阳221262945638033452387911801385重庆231327937643334025775810501331成都2415791182895523257097912561252武汉257072812988797589790313566合肥2667937858811801050125631

21、30343杭州274794427441385133112525663430上海28612601898153114461663687406165南京29678474709132312021407455151245郑州30111172473211258731006469473798西安3113539237768825676206488251151太原321468108210741372107811258257981116石家庄331408106911091471119112688267351024济南3412069151016149212531377719536781城市（公里）上海28南京29郑

22、州30西安31太原32石家庄33济南34哈尔滨11687167616531994152113231297长春21445144114291782126111231070沈阳311951170117315221017859803北京41063899631917410248363天津5953796579915434266273呼和浩特613751163693770334392646银川715941338777525554718971兰州8171014408965087919631171西宁919041636108970296111331355乌鲁木齐1032703011244121212193234

23、12600拉萨112905265421871759217723482533昆明121954174415001182170018261870南宁131641146013411278172818021760海口141675158616721596199720431947澳门151283122614141434176117801657广州161217113713041315164416711548香港171228117613921429174217511622台北1870083713381593167016031379福州1961267811111353146814081206南昌206014747

24、2492310821069915长沙21898709732776107411091016贵阳22153113231125882137214711492重庆2314461202873567107811911253成都24166314071006620112512681377武汉25687455469648825826719合肥26406151473825798735536杭州27165245798115111161024781上海280266831121711151000738南京292660562949868781546郑州308315620429357370377西安311217949429

25、0518650774太原3211158683575180172417石家庄3310007813706501720269济南347385463777744172690经运行得到结果：X( 1, 6)=1， X( 2, 1)=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, 24)=1，X( 12, 13)=1，X( 13, 14)=1，X( 14, 15)=1，X( 15, 17)=1，X( 16, 21)=1，X( 17, 16

26、)=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, 23)=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，路线图：16323330317 8910112423221213141517162125201918272829263454321即最短短线旅游路线图为

27、：哈尔滨呼和浩特太原石家庄郑州西安银川兰州西宁乌鲁木齐拉萨成都重庆贵阳昆明南宁海口澳门香港广州长沙武汉南昌福州台北杭州上海南京合肥济南天津北京沈阳长春哈尔滨由程序结果可以得出最短的路程为：15697.00公里5.2求最省钱路线，第二题的相应线性规划问题是：minZ=1j=1,2,3,n=1i=1,2,3,nUj>=Uk+Xkj-(N-2)*(1-Xkj)+(N-3)*XjkUk<=N-1-(N-2)*X1 kUk>=1+(N-2)*Xk 1具体编程如下：MODEL:SETS:city/1.34/:u;link(city,city):d,x;ENDSETSDATA:d = fi

28、le(jiage.txt) ;ENDDATAn=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)<=n-1-(n-2)*x(1,k);u(k)>=1+(n-2)*x(k,1);END下表表示各省

29、市直接具体票价（不含波动因素） 附表2.(jiage.txt)城市价格（元）哈尔滨1长春2沈阳3北京4 天津5呼和浩特6银川7兰州8哈尔滨108713426326219814301379长春28709322422417614071109沈阳313493017217227016551649北京4263224172068159282365天津52622241726801678011941呼和浩特61981762701591670103246银川7143014071655282801103091兰州81379110916493651941246910西宁91247824107440112129541

30、2077乌鲁木齐1016701541173560924131076750365拉萨11198265325922045410昆明1274210581830539170016001348490南宁13121013961359466103696010771048海口141351136513205321014156010572110澳门1518031902196012802080151015941786广州16597569532428449510290494香港171890156918709471470117712611453台北1819732072240012902290168017641956福州

31、1914271132486264391122813521550南昌20276255416383298387684233长沙21510486449324339416237401贵阳2213201050144945818441054914938重庆2312201200110940113431024306成都249101278500391410244189256武汉25999155858066087967011101110合肥264163723302462168431158355杭州274864584103303124281355428上海28466428401306282401428410南京29

32、428383355256234355383365郑州30391355312164183282282256西安31473437391256282157183164太原3220816615714015990905166石家庄33330290246901012081655324济南3433029023413098262904365城市价格（元）西宁9乌鲁木齐10拉萨11昆明12南宁13海口14澳门15广州16哈尔滨112471670742121013511803597长春282415411058139613651902569沈阳31074173519821830135913201960532北京44

33、016096535394665321280428天津51212241325921700103610142080449呼和浩特69541076160096015601510510银川712075020451348107710571594290兰州877365410490104821101786494西宁906383835708518692000516乌鲁木齐1063809021300113919661166拉萨1138301709162418903290755昆明12570902170901956601816339南宁138511300162419503481900183海口1486911391

34、89066034801809183澳门152000196632901816190018090广州1651611667553391831830香港1716671633295797015671649750台北1821702136310014862070229613801150福州19155014661060346810223南昌2010131056212179897216长沙21428869674324216312172贵阳2272611181802153201592185重庆23339557597246282529339成都24290516557240365969383武汉25922135217

35、191097996861544合肥26989609221993013141073298杭州27132066226844863654372120330上海284376536835003914661570345南京294016096535323721024401郑州30298532557458365437330西安312014665003724371259401太原327179562177107518401443426石家庄33355579609500428494383济南343913442095863281929383城市价格（元）香港17台北18福州19南昌20长沙21贵阳22重庆23成都24

36、哈尔滨118901973142727651013201220910长春2156920721132255486105012001278沈阳31870240048641644914491109550北京4264383324458401391天津5147022903912983391844410呼和浩特611771680122838741610541343244银川71261176413526842379141024189兰州8145319561550233401938306256西宁91667217015501013428726339290乌鲁木齐1016332136146610568691118

37、557516拉萨11295731006741802597557昆明1297014861060212324153246240南宁1315672070346179216201282365海口1416492296810897312592529969澳门151380广州167501150223216172185339383香港17086099016101640台北1886002219福州199900153201355416449南昌201530885157301345长沙212018850216240298贵阳22355157216078140重庆23161041630124078093成都24164

38、02219449345298140930武汉259491060818953500402合肥262401241083700324339杭州2710401329183159224365428437上海281220224183256391410473南京2919504901256145666449355391郑州30324282201365290290西安31208262298169183195太原3210413303301040185194石家庄331323345282416355345济南343722462721630391428城市价格（元）武汉25合肥26杭州27上海28南京29郑州30西安

39、31太原32哈尔滨1999416486466428391473208长春21558372458428383355437166沈阳3580330410401355312391157北京4246330306256164256140天津5879216312282234183282159呼和浩特667084342840135528215790银川7111011581355428383282183905兰州81110355428410365256164166西宁99229891320437401298201717乌鲁木齐101352609662653609532466956拉萨1117192219268

40、46836535575002177昆明1210979304865005324583721075南宁1399613143653913723654371840海口148611073437466102443712591443澳门1521201570广州16544298330345401330401426香港17104012201950台北1813294901福州199492401832242563242081041南昌201060124159183145282262330长沙218181083224256666201298330贵阳229537003653914493651691040重庆23500

41、324428410355290183185成都24402339437473391290195194武汉2501300582547675902562941合肥261300011611670145256256杭州27582116073124246330339上海2854711673093224312306南京2967570124930164262256郑州309021452462241640130159西安315622563303122621300103太原329412563393062561591030石家庄33120220829027221611120884济南34520153256216159159256134城市价格（元）石家庄33济南34哈尔滨1330330长春2290290沈阳3246234北京490130天津510198呼和浩特6208262银川71