数学建模旅游商bgf问题 3.doc

《数学建模旅游商bgf问题 3.doc》由会员分享，可在线阅读，更多相关《数学建模旅游商bgf问题 3.doc（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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

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

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

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

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

7、一对i和j，有 W(vivj)+w(vi+1vj+1)=Uk+Xkj-(N-2)*(1-Xkj)+(N-3)*XjkUk=1+(N-2)*Xk 1根据中国地图中所示设计最短路线，利用lingo 软件设计程序程序如下：MODEL:SETS:city/1.34/:u;link(city,city):d,x;ENDSETSDATA: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

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

9、1057863625011141789211861333天津51071857606111050495312331391呼和浩特6131611679764175040537872985银川71859170315098929535370346446兰州8218420311800118612338723460197西宁9229521541950133313919854461970乌鲁木齐10305630022911242325162011167016271442拉萨11357534073197257426102247170613901255昆明1231492938267820942075194615

10、2612341288南宁13303928002537204819942027175615351659海口14322930022729228922272316208918962019澳门15289726442383198719122081194218001957广州16283826192210188918131971182916961860香港17284125982340196218832068193918261979台北18235021211872171716121975206920782275福州19230020541803155314631779184318292028南昌20212418

11、871624125811641410141514001590长沙21229620601787133812761407129712141388贵阳22277725632290174017071643132010731196重庆23252822992383146414471336983746886成都24258023912133152915341327889594688武汉2520011770149810529801156114511381332合肥261760151312479018061110123513161503杭州2718361585132711301029139915681650184

12、6上海2816871445119510639531375159417101904南京291676144111708997961163133814401636郑州301653142911736315796937778961089西安31199417821522917915770525508702太原32152112611017410434334554791961石家庄33132311238592482663927189631133济南341297107080336327364697111711355城市（公里）乌鲁木齐10拉萨11昆明12南宁13海口14澳门15广州16香港17台北18哈尔滨13

13、05635753149303932292897283828412350长春2300234072938280030022644261925982121沈阳3291131972678253727292383221023401872北京4242325742094204822891987188919621717天津5251626102075199422271912181318831612呼和浩特6201122471946202723162081197120681975银川7167017061526175620891942189219392069兰州816271390123415351896180016

14、9618262078西宁9144212551288165920191957186019792275乌鲁木齐10016082499301233883386329234123712拉萨11160801258188622142384232524413046昆明122499125806249551141108611931885南宁133012188662403695345065991359海口143388221495536904054594701275澳门15338623841141534405011868877广州163292232510865064591180126863香港17341224411

15、193599470681260808台北18371230461885135912758778638080福州1934692791165611651084733688662261南昌2030452413136810001110767674720688长沙21284921301069759952691576671932贵阳22249915644264708278677789031510重庆232284148562779111461100100011341584成都242066125363797913481339125113721831武汉252756223212871054123594983892

16、7961合肥2629012500160113321482114710481108871杭州2732422801181114411501113010471070602上海2832702905195416411675128312171228700南京2930112654174414601586122611371176837郑州30244121871500143116721414130413921338西安31212117591182127815961434131514291593太原32219321771700172819971761164417421670石家庄33234123481826180

17、220431780167117511603济南34260025331870176019471657154816221379城市（公里）福州19南昌20长沙21贵阳22重庆23成都24武汉25合肥26杭州27哈尔滨1230021242296277725282580200117601836长春2205418872060256322992391177015131585沈阳3180316241787229023832133149812471327北京415531258133817401464152910529011130天津51463116412761707144715349808061029呼和浩特

18、6177914101407164313361327115611101399银川71843141512971320983889114512351568兰州81829140012141073746594113813161650西宁92028159013881196886688133215031846乌鲁木齐10346930452849249922842066275629013242拉萨11279124132130156414851253223225002801昆明12165613681069426627637128716011811南宁1311651000759470791979105413321

19、441海口141084111095282711461348123514821501澳门157337676918671100133994911471130广州166886745767781000125183810481047香港176627206719031134137292711081070台北18261688932151015841831961871602福州190434677126213271579707679479南昌2043403059459371182281378442长沙216773050638643895298588744贵阳221262945638033452387911801

20、385重庆231327937643334025775810501331成都2415791182895523257097912561252武汉257072812988797589790313566合肥266793785881180105012563130343杭州274794427441385133112525663430上海28612601898153114461663687406165南京29678474709132312021407455151245郑州30111172473211258731006469473798西安3113539237768825676206488251151太原32

21、1468108210741372107811258257981116石家庄331408106911091471119112688267351024济南3412069151016149212531377719536781城市（公里）上海28南京29郑州30西安31太原32石家庄33济南34哈尔滨11687167616531994152113231297长春21445144114291782126111231070沈阳311951170117315221017859803北京41063899631917410248363天津5953796579915434266273呼和浩特61375116369

22、3770334392646银川715941338777525554718971兰州8171014408965087919631171西宁919041636108970296111331355乌鲁木齐103270301124412121219323412600拉萨112905265421871759217723482533昆明121954174415001182170018261870南宁131641146013411278172818021760海口141675158616721596199720431947澳门151283122614141434176117801657广州161217113

23、713041315164416711548香港171228117613921429174217511622台北1870083713381593167016031379福州1961267811111353146814081206南昌2060147472492310821069915长沙21898709732776107411091016贵阳22153113231125882137214711492重庆2314461202873567107811911253成都24166314071006620112512681377武汉25687455469648825826719合肥2640615147382

24、5798735536杭州27165245798115111161024781上海280266831121711151000738南京292660562949868781546郑州308315620429357370377西安3112179494290518650774太原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

25、( 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)=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(

26、31, 7)=1， X( 32, 33)=1，X( 33, 30)=1，X( 34, 5)=1，路线图：16323330317 8910112423221213141517162125201918272829263454321即最短短线旅游路线图为：哈尔滨呼和浩特太原石家庄郑州西安银川兰州西宁乌鲁木齐拉萨成都重庆贵阳昆明南宁海口澳门香港广州长沙武汉南昌福州台北杭州上海南京合肥济南天津北京沈阳长春哈尔滨由程序结果可以得出最短的路程为：15697.00公里5.2求最省钱路线，第二题的相应线性规划问题是：minZ=1j=1,2,3,n=1i=1,2,3,nUj=Uk+Xkj-(N-2)*(1-Xkj

27、)+(N-3)*XjkUk=1+(N-2)*Xk 1具体编程如下：MODEL:SETS:city/1.34/:u;link(city,city):d,x;ENDSETSDATA:d = file(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(l

28、ink:BIN(x);for(city(k)|k#gt#1:u(k)=1+(n-2)*x(k,1);END下表表示各省市直接具体票价（不含波动因素） 附表2.(jiage.txt)城市价格（元）哈尔滨1长春2沈阳3北京4 天津5呼和浩特6银川7兰州8哈尔滨108713426326219814301379长春28709322422417614071109沈阳313493017217227016551649北京4263224172068159282365天津52622241726801678011941呼和浩特61981762701591670103246银川7143014071655282801

29、103091兰州81379110916493651941246910西宁912478241074401121295412077乌鲁木齐1016701541173560924131076750365拉萨11198265325922045410昆明1274210581830539170016001348490南宁13121013961359466103696010771048海口141351136513205321014156010572110澳门1518031902196012802080151015941786广州16597569532428449510290494香港171890156918

30、709471470117712611453台北1819732072240012902290168017641956福州1914271132486264391122813521550南昌20276255416383298387684233长沙21510486449324339416237401贵阳2213201050144945818441054914938重庆2312201200110940113431024306成都249101278500391410244189256武汉25999155858066087967011101110合肥264163723302462168431158355杭州

31、274864584103303124281355428上海28466428401306282401428410南京29428383355256234355383365郑州30391355312164183282282256西安31473437391256282157183164太原3220816615714015990905166石家庄33330290246901012081655324济南3433029023413098262904365城市价格（元）西宁9乌鲁木齐10拉萨11昆明12南宁13海口14澳门15广州16哈尔滨112471670742121013511803597长春282415

32、411058139613651902569沈阳31074173519821830135913201960532北京44016096535394665321280428天津51212241325921700103610142080449呼和浩特69541076160096015601510510银川712075020451348107710571594290兰州877365410490104821101786494西宁906383835708518692000516乌鲁木齐1063809021300113919661166拉萨1138301709162418903290755昆明12570902

33、170901956601816339南宁138511300162419503481900183海口148691139189066034801809183澳门152000196632901816190018090广州1651611667553391831830香港1716671633295797015671649750台北1821702136310014862070229613801150福州19155014661060346810223南昌2010131056212179897216长沙21428869674324216312172贵阳2272611181802153201592185重庆23

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