數(shù)學建模走遍全國

1、2010年中國礦業(yè)大學徐海學院暑期數(shù)學建模集訓承 諾 書我們仔細閱讀了中國礦業(yè)大學徐海學院暑期數(shù)學建模集訓的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C中選擇一項填寫）： A 我們的參賽號為

2、： 201001 參賽隊員 (打印并簽名) ：1. 王奎 2. 仇文陽 3. 劉新云 指導教師或指導教師組負責人 (打印并簽名)： 教練組 日期： 2010 年 8 月24 日評閱編號（由組委會評閱前進行編號）：2010年中國礦業(yè)大學徐海學院暑期數(shù)學建模集訓編 號 專 用 頁評閱編號（由組委會評閱前進行編號）：評閱記錄（可供評閱時使用）：評閱人評分備注統(tǒng)一編號：評閱編號：A題：旅行方案張先生喜愛旅游，夢想游遍中國。今年他計劃利用假期，從南京出發(fā)到全國所有的省份的省會城市、四個直轄市、兩個特別行政區(qū)旅游。請你為他按下面要求制定旅行方案：1、根據(jù)地理位置設(shè)計行程，做到最短路線；2、張先生想7月1日

3、出發(fā)，采取航空或鐵路出行，每到一個城市游玩3天，若通過互聯(lián)網(wǎng)訂票，請為他設(shè)計最經(jīng)濟的訂票方案；3、綜合考慮時間短、經(jīng)濟、方便等因素，設(shè)定評價準則，調(diào)整你的方案。走遍全中國摘要要從34個城市中制定最短的旅游路線，本文主要采動態(tài)規(guī)劃方法求解，當然空間復雜性及時間復雜性都十分龐大。因此，為解決問題（1），本文采用分區(qū)域旅游，然后依次進行動態(tài)規(guī)劃。這樣就可以很好的解決了旅游城市數(shù)量大的缺點此方法節(jié)約計算資源，具有良好的可擴展性和實用性，給問題（2）和問題（3）奠定很好的基礎(chǔ)。隨著問題（1）的解決，問題（2）和問題（3）都是在問題一得出的路線最優(yōu)解的前提下，設(shè)計省錢、省時又方便的互聯(lián)網(wǎng)訂票方案。本文將這

4、個問題歸結(jié)為多屬性決策的問題。用層次分析法求解。（一）信息的獲取：我們將中國交通網(wǎng)上把具體的時刻表、價位表、打折等相關(guān)的信息進行整理（見下文）。周先生的滿意度本文主要通過對大部分人的滿意度調(diào)查表的結(jié)果進行分析。（二）排序和擇優(yōu)：本文從不同的方面考慮各個屬性的權(quán)值和所占的空間。得出的部分結(jié)果為：南京上海 杭州臺北福州南昌長沙武漢廣州香港澳門?？谀蠈庂F陽昆明重慶成都拉薩烏魯木齊西寧蘭州銀川呼和浩特北京哈爾濱長春沈陽天津濟南石家莊太原西安鄭州合肥南京總距離：15917Km經(jīng)濟支出：20040元 最優(yōu)時間：102天關(guān)鍵詞：動態(tài)分析 層次分析 經(jīng)緯度、最短路線、訂票方案、graph軟件、滿意度、MAYT

5、LAB程序、 綜合評價一、問題重述與分析1.1 問題重述張先生喜愛旅游，夢想游遍中國。今年他計劃利用假期，從南京出發(fā)到全國所有的省份的省會城市、四個直轄市、兩個特別行政區(qū)旅游。請你為他按下面要求制定旅行方案：1、根據(jù)地理位置設(shè)計行程，做到最短路線；2、張先生想7月1日出發(fā)，采取航空或鐵路出行，每到一個城市游玩3天，若通過互聯(lián)網(wǎng)訂票，請為他設(shè)計最經(jīng)濟的訂票方案；3、綜合考慮時間短、經(jīng)濟、方便等因素，設(shè)定評價準則，調(diào)整你的方案。1.2 問題分析隨著人們生活水平的不斷提高，旅游已經(jīng)成為人們忠愛的休閑方式之一。在制定旅游計劃的同時需要考慮很多方面的問題，比如：旅游路線的選擇、交通工具的選擇、旅途用時、

6、經(jīng)濟花銷等等。為了在完成旅游計劃的基礎(chǔ)上實現(xiàn)省時、方便、經(jīng)濟的目標，需要制定一個最優(yōu)的旅游方案。本文給出張先生的旅游計劃既游遍中國的省會城市、直轄市、香港、澳門以及臺北，要求達到旅途最短、經(jīng)濟、省時又方便的目的，為了實現(xiàn)這一目標，需要制定一個最優(yōu)的旅游方案。首先要實現(xiàn)旅途最短，本問題屬于多點的距離最短的問題，很顯然，如果利用傳統(tǒng)的動態(tài)規(guī)劃解法在N為34的情況下，解法的空間復雜性及時間復雜性都十分龐大，不利于旅行方案的確定，因此，我們采用區(qū)域化的動態(tài)規(guī)劃解法。將全國各個地方先進行區(qū)域劃分，每一個區(qū)域進行動態(tài)分析。最后在通過各個區(qū)域的動態(tài)分析。最終達到游遍全國各個省會距離最短的目的。問題（2）和問

7、題（3）都是模型的優(yōu)化問題。我們主要是考慮了時間短、經(jīng)濟、方便、舒適等各個方面的因素等。本文將其歸結(jié)為多重屬性的決策問題。二、 模型的基本假設(shè)和符號說明2.1 模型假設(shè)1. 假設(shè)在旅途中旅游車的準時出發(fā)到達,且不考慮突發(fā)事件干擾車子的行程;2. 在旅游的過程中,當天旅游目的地附近都有賓館,且第一天的目的地就是第二天的出發(fā)點；3. 在每個城市的吃飯、購物、在城市中觀光景點等所需的費用費用視為相同；4. 假設(shè)周先生自帶充足食物，并不考慮住宿問題；在旅行過程中只考慮購票的經(jīng)濟花費，不考慮其他的消費5. 票價不考慮除打折以外的其他優(yōu)惠；6. 旅游的這段時間內(nèi)不會有價格變化;7. 假設(shè)經(jīng)緯線是均勻的；8

8、. 假設(shè)球面的地圖可以看成平面；9. 假設(shè)問題（3）中，參考的調(diào)查數(shù)據(jù)都是真實可靠地；10. 假設(shè)周先生直接可以訂購到臺北的機票。2.2符號說明南京合肥鄭州西安太原石家莊濟南天津沈陽長春哈爾濱北京呼和浩特銀川蘭州西寧烏魯木齊拉薩成都重慶昆明貴陽南寧?？诎拈T香港廣州武漢長沙南昌福州臺北杭州上海三、 模型的建立及求解3.1 問題（1）模型的建立及求解 模型的建立定義（1）表示由到的最短距離 （2）表示由到的最短距離下面用動態(tài)規(guī)劃的方法計算。最短線路問題的特性：如果最短線路在第k站通過點，則這一線路在由出發(fā)到達終點的那一部分線路，對于從點到達終點所有可能選擇的不同線路來說，必定也是距離最短的。（反正

9、法）。最短線路問題的這一特性啟示我們，從最后一段開始，用從后向前逐步遞推的方法，求出各點到的最短線路，最后求得從到的最短線路。地圖中每個頂點代表一個城市，兩個城市間的連線代表道路，連線上的數(shù)值代表道路長度。圖一k=6時：設(shè)表示由到的最短距離；表示由到的最短距離取min（，）k=5時（1）從出發(fā)，有兩種選擇，到或，設(shè)表示由到的最短距離。表示到的距離，表示從到或的選擇，則 = =，最短線路是-（2）從出發(fā)也有兩種選擇，即到或。，的定義與（1）類似，則=最短路線是-（3）從出發(fā)，同樣有 = ，最短線路是-k=4時：分別以,為出發(fā)點計算得，最短線路是-，最短線路是-，最短線路是- k=3時：分別以，為

10、出發(fā)點計算得，最短線路是-，最短線路是-，最短線路是-,最短線路是-k=2時分別以，為出發(fā)點計算得，最短線路是-，最短路線是-k=1時出發(fā)點只有，計算得，最短路線是-圖二現(xiàn)在，我們想從城市到達城市。怎樣走才能使得路徑最短，最短路徑的長度是多少？ 如上圖所示，從城市a出發(fā)，按照與城市a的路徑長度劃分階段。階段0包含的出發(fā)城市有階段1所含的城市有階段2包含的出發(fā)城市有階段3包含的出發(fā)城市有階段4包含城市這種劃分可以明確每個城市的次序，因為階段的劃分具有如下性質(zhì)階段i的取值只與階段i+1有關(guān)，階段i+1的取值只對階段i的取值產(chǎn)生影響：每個階段的順序是確定的，不可以調(diào)換任兩個階段的順序；我們從階段4的

11、城市出發(fā)，按照階段的順序倒推至階段0的城市。定義（1）表示由到的最短距離 （2）表示由到的最短距離分別以,為出發(fā)點計算得，最短線路是-，最短線路是-，最短線路是- 分別以，為出發(fā)點計算得，最短線路是-，最短線路是-，最短線路是-,最短線路是-k=2時分別以，為出發(fā)點計算得，最短線路是-，最短路線是-k=1時出發(fā)點只有，計算得，最短路線是- 模型的求解地區(qū)名稱經(jīng)度緯度北京E116°28N39°54上海E121°29N31°14天津E117°11N39°09重慶E106°32N29°32哈爾濱E126°41N

12、45°45長春E125°19N43°52沈陽E123°24N41°50呼和浩特E111°48N40°49石家莊E114°28N38°02太原E112°34N37°52濟南E117°N36°38鄭州E113°42N34°48西安E108°54N34°16蘭州E103°49N36°03銀川E106°1N38°20西寧E101°45N36°38烏魯木齊E 87°3

13、6N43°48合肥E117°18N31°51南京E118°50N32°02杭州E120°09N30°14長沙E113°N28°11南昌E115°52N28°41武漢E114°21N30°37成都E104°05N30°39貴陽E106°42N26°35福州E119°18N26°05廣州E113°15N23°08?？贓110°20N20°02南寧E108°20N

14、22°48昆明E102°41N25°拉薩E 91°10N29°40香港E114°10N22°18澳門E113°30N22°12臺北E121°31N25°03表一 （1-1）實際距離Km（實際距離） （1-2）經(jīng)過計算的部分距離城市南京上海杭州合肥拉薩烏魯木齊緯度118.81121.47120.16117.2391.1187.62經(jīng)度32.0631.2430.2831.8229.6643.83距離南京上海杭州合肥拉薩烏魯木齊南京0267.79235.95151.462650.333008

15、.07上海267.790164.51406.992906.583266.77杭州235.95164.510327.452791.623228.1合肥151.46406.99327.4502501.962901.82拉薩2650.332906.582791.622501.9601605.68烏魯木齊3008.073266.773228.12901.821605.680將數(shù)據(jù)代入模型最短距離為15917Km不難得到如圖所示的利用EXCEL，建立適當坐標系生成折線圖，如圖所示圖33.2 問題（2）與（3）模型的建立及求解 模型的建立在模型（1）的基礎(chǔ)上，本文主要通過層次分析法對第二個問題進行建模分析

16、。目標層就是選擇怎么樣的交通方式方案層是有什么樣交通方式準則層就是價格、時間、距離、方式。下面就問題（2）進行討論。選擇方式方式價格距離時間存在的交通方式圖四設(shè)某層有n個因素，要比較它們對上一層某一準則（或目標）的影響程度，確定在該層中相對于某一準則所占的比重。（即把n個因素對上層某一目標的影響程度排序）用表示第個因素相對于第個因素的比較結(jié)果，則A則稱為成對比較矩陣：交通方式的選擇價格P（x）0.4時間T(x)0.3距離L(x)0.2方式M (x)0.1交通情況T or F 表二 模型的求解1、對最優(yōu)解路徑的求解（對問題（1）的改進）（1）對于每個決策因素的重要性程度周游先生賦以下值：（3）假

17、設(shè)周游先生對于不同里程區(qū)間的三種交通方式的滿意度賦以下值：963893769（4）假設(shè)周游先生對于不同出發(fā)時間區(qū)間的滿意度賦以下值：1234567823567973第二問的路線：南京上海杭州臺北福州南昌長沙武漢廣州香港澳門海口南寧貴陽昆明重慶成都拉薩西寧蘭州烏魯木齊蘭州銀川呼和浩特北京哈爾濱長春沈陽天津濟南石家莊太原西安鄭州合肥南京全程共34段路程，除去5段乘坐飛機的還剩29段。而在這29段中有很多兩城市之間的距離很短根本用不上坐飛機。（8）利用MATLAB計算每段旅途的每個車次或航班的滿意度，再取其中滿意度最高的車次或航班作為最佳互聯(lián)網(wǎng)訂票標準，以此類推，得出全國路線的最佳訂票方案。車次 始

18、發(fā)站 車輛類型 發(fā)時 到時 歷時 硬臥中T224/T221拉薩空調(diào)特快13:1020:3931:29:00486/502/519T24/T21拉薩空調(diào)特快13:1020:3931:29:00486/502/519K542/K543重慶北空調(diào)快速7:5516:2232:27:00437/452/467K452/K453成都空調(diào)快速8:5318:5434:01:00437/452/467K594/K595杭州空調(diào)快速12:2918:3630:07:00437/452/467K1208/K1205上?？焖?:4014:2336:43:00269/279/289T52/T53上?？照{(diào)特快14:1516

19、:0125:46:00437/452/4671354/1351連云港東空調(diào)普快4:3217:0036:28:00407/422/4371085濟南普快2:439:1030:27:00249/259/2691043西安普快23:397:0031:21:00249/259/269T192/T193漢口空調(diào)特快8:1610:2326:07:00437/452/467T197鄭州空調(diào)特快5:217:2526:04:00437/452/4671045商丘普快6:0313:5231:49:00249/259/269T69北京西空調(diào)特快8:4110:4226:01:00437/452/467其中出發(fā)時間與到

20、達時間按轉(zhuǎn)換，其中為計算采用格式，為24小時制時間。在MATLAB命令窗口輸入運行程序得到最佳車次或航班，按此類推，得到整個路線的車次或航班。結(jié)果如下表（詳細參考請見附錄-最佳訂票方案）：路線哈爾濱長春：長春沈陽：沈陽天津：天津北京：北京呼和浩特：呼和浩特太原車次或航班D26D22D178T5681/T5684JD52898L9946/HU9946滿意度（H）8.57588.39397.12128.54557.57586.7576路線太原石家莊：石家莊濟南：濟南鄭州：鄭州西安：西安銀川：銀川蘭州：車次或航班D166或D167MU5154或MU5529D157G2007HU7848MU2301或

21、MU5154滿意度（H）8.57584.06066.48487.51528.45456.5455路線蘭州西寧：西寧烏魯木齊：烏魯木齊拉薩：拉薩昆明：昆明成都：成都重慶：車次或航班T213CZ3629HU7893或CA4420MU58383U8819或MU5849D5110或D5112滿意度（H）8.36366.66676.66675.78797.09098.0909路線重慶貴陽：貴陽南寧：南寧海口：?？趶V州：廣州澳門：澳門香港：車次或航班MU2603HU7520GS7520或HU7520ZH9612大巴輪船滿意度（H）7.36367.90917.93947.63647.6977.5455路線香

22、港臺北：臺北福州:福州南昌：南昌長沙：長沙武漢：武漢合肥：車次或航班CI914KA481或KA662CZ8150或3U8960T146或T147D150D5477或D3051或D3054滿意度（H）6.63645.45457.84857.57587.15158.0909路線合肥南京：南京杭州：杭州上海：上海哈爾濱： 車次或航班D5481或D5484D5589D56769C8869滿意度（H）8.33337.39398.63646.9394注：其中廣州到澳門與澳門到香港因在網(wǎng)上無法進行動車、特快臥鋪、航班的訂票，所以本文分別用大巴與輪船作為交通工具，計算滿意度時均采用的標準。由附錄-最佳訂票方案

23、中數(shù)據(jù)計算得：總行程時間，因為每個城市停留3天（出去哈爾濱）總的停留天數(shù)為，完成旅游計劃總用時，即5月1日從哈爾濱出發(fā)，環(huán)游中國后8月11日返回哈爾濱；購票總價；總行程；平均滿意度。如果對以上結(jié)果又不滿意之處，可通過調(diào)整因素重要性程度與滿意度來重新決定訂票方案。最佳訂票方案：經(jīng)過模型（2）的計算和查詢火車和飛機航班線路和票價，得到最佳的訂票方案（起點南京）為：路徑車次或航班出發(fā)時間到達時間旅途用時（min)里程(km)票價（元）滿意度哈爾濱長春：D2615:3817:24106246918.5758長春沈陽：D2215:1817:331353001118.3939沈陽天津：D17813:141

24、7:442706893517.1212天津北京：T5681/T568413:5615:1882127978.5455北京呼和浩特：JD528918:4519:4560416.063627.5758呼和浩特太原：8L994620:1521:1055336.724046.7576HU994620:1521:1055336.724306.7576太原石家莊：D166/D16717:1918:3374225848.5758石家莊濟南：MU5154/MU55297:5518:45650270.4813214.0606濟南鄭州：D15718:2023:303106682486.4848鄭州西安：G2007

25、15:0017:261465053907.5152西安銀川：HU784816:4517:5065525.172138.4545銀川蘭州：MU2301/MU515413:3518:20285351.45306.5455蘭州西寧：T21317:4420:03139216508.3636西寧烏魯木齊：CZ362916:1518:351401437.117436.6667烏魯木齊拉薩：HU7893/CA44208:5016:404701602.5720556.6667拉薩昆明：MU583811:2515:002151264.3417935.7879昆明成都：3U881916:3017:4070638.

26、177107.0909MU584916:2517:3570638.177187.0909成都重慶：D511013:2415:251213151178.0909D511216:5618:551193151178.0909重慶貴陽：MU260318:3019:3060334.624407.3636貴陽南寧：HU752016:1017:0555448.953787.9091南寧海口：GS752017:5518:4045374.292847.9394HU752017:5518:4045374.293017.9394?？趶V州：ZH961216:4017:4060459.945007.6364廣州澳門：大

27、巴10:0012:00120110.92807.697澳門香港：輪船9:0011:0012061.77607.5455香港臺北：CI91415:3517:15100817.728606.6364臺北福州:KA481/KA66214:5019:00250248.840905.4545福州南昌：CZ815018:3019:4070443.021607.84853U896013:0014:1070443.022367.8485南昌長沙：T146/T14713:2018:172974191187.5758長沙武漢：D1507:2610:351893621357.1515武漢合肥：D54777:588:

28、5658156808.0909D3051/D305412:20130909合肥南京：D5481/D548414:1715:26691561148.3333南京杭州：D558912:2716:412545041877.3939杭州上海：D567615:5517:2792173648.6364上海哈爾濱：9C886916:4519:301651326.266206.9394四、模型的誤差分析1、本模型利用動態(tài)規(guī)劃計算最短路徑時是依據(jù)的兩兩城市之間的最短距離，而實際上兩城市之間的行車里程并不是兩兩城市之間的直接距離。2、實際里程或航程并不是球面直接距離，因此模型（1）得出的

29、總路徑長度與模型（2）的出的結(jié)果有一定差距。 3、本模型在選取車次時判斷標準為人為主觀因素，在具有了普遍性的同時也具有了隨機性，為減少隨機性，可通過多次打分，得出較多個結(jié)果，再從中選取最優(yōu)解。4、在旅途中會遇到很多客觀的不定因素，比如天氣問題等，會使正常計劃受到一定的影響。五、 模型復雜性分析1、模型的復雜性：（1）運用動態(tài)分析法解決游遍全國的省會城市、直轄市、香港、澳門、臺北這一問題還是比較困難的，數(shù)據(jù)量很大。本文主要是將數(shù)據(jù)量降低，將全國各地省會進行區(qū)域性劃分。然后再運用動態(tài)分析解決了模型（1）。模型（1）來計算完成旅游計劃的最短行程，相對于傳統(tǒng)的動態(tài)規(guī)劃解法，達到了省時、簡便的效果，大大

30、降低了計算的復雜性。（2）如何方便的訂票，本文充分考慮了地域這個問題。比如說不能坐火車到臺灣。并且好多地方時不能直接通火車的?；蛘邥r間的問題考慮直接用飛機相對的也是比較舒適的。在模型（1）的基礎(chǔ)上，適當?shù)恼{(diào)整。給出了模型（2）、（3）的求解；綜合考慮了出行方式，出發(fā)時間，到達時間，旅行用時，旅行路程，票價等的重要性給出比較主觀的結(jié)論（3）建立的模型能與實際緊密聯(lián)系，結(jié)合實際情況對所提出的問題進行求解，使模型更貼近實際，達到了運用數(shù)學知識解決實際問題的目的。六、 模型可行性與推廣本案例建立的模型解決了旅游出行優(yōu)化問題，采用了動態(tài)分析的方法解決了最短路徑問題，運用決策分析方法解決了旅行費用優(yōu)化問題

31、。因此，本模型還可以運用于很多領(lǐng)域類似的關(guān)于路徑優(yōu)化以及經(jīng)濟優(yōu)化的問題，如:輸油管道的鋪設(shè)問題、郵遞員送信問題、交通運輸問題、快遞的投送等。參考文獻1彭紅軍 張偉 中國礦業(yè)大學徐海學院 層次分析法講義 2 彭紅軍 張偉中國礦業(yè)大學徐海學院 動態(tài)分析講義3 吳文虎 王建德，青少年國際和全國信息學（計算機）奧林匹克競賽指導組合數(shù)學的算法與程序設(shè)計，清華大學出版社，1997年版4 薛定宇等. 高等運用數(shù)學的MATLAB求解. 北京：清華大學出版社. 2008.105 王莉，李文權(quán)，公共交通系統(tǒng)，東南大學學報，第34卷第2期：第265頁，2004年3月。6張興永 朱開永 數(shù)學建模入門 煤炭工業(yè)出版社2

32、008.10附錄最佳訂票方案：路徑車次或航班出發(fā)時間到達時間旅途用時（min)里程(km)票價（元）滿意度哈爾濱長春：D2615:3817:24106246918.5758長春沈陽：D2215:1817:331353001118.3939沈陽天津：D17813:1417:442706893517.1212天津北京：T5681/T568413:5615:1882127978.5455北京呼和浩特：JD528918:4519:4560416.063627.5758呼和浩特太原：8L994620:1521:1055336.724046.7576HU994620:1521:1055336.724306.7576太原石家莊：D166/D16717:1918:3374225848.5758石家莊濟南：MU5154/MU55297:5518:45650270.4813214.0606濟南鄭州：D15718:2023:303106682486.4848鄭州西安：G200715:0017:26146505