最廉價飛機(jī)線路的選擇摘要：改革開發(fā)以來，我國的經(jīng)濟(jì)發(fā)展迅速，人民生活水平逐漸提高，2010年，我國GDP超越日本，排名世界第二。我國經(jīng)濟(jì)的發(fā)展，使人們對交通運(yùn)輸提出越來越多的需求，而民航作為航空運(yùn)輸工具，在交通工具中起到十分重要的作用，新型飛機(jī)（民用）快速、續(xù)航能力強(qiáng)、安全、便捷的特點(diǎn)受到越來越多的人青睞。如果從交錯復(fù)雜的飛機(jī)線路中找到最廉價的線路，不僅減少了中途時間，而且大大節(jié)省了開支費(fèi)用，為企業(yè)和個人帶來可觀的經(jīng)濟(jì)效益。本文從航班網(wǎng)絡(luò)的實(shí)際特點(diǎn)出發(fā)，對航班線路網(wǎng)和票價進(jìn)行分析，將最佳路徑搜索問題轉(zhuǎn)化為圖論中的最短路徑的問題，通過對最短路徑算法的分析，實(shí)現(xiàn)了Floyd算法求航班網(wǎng)絡(luò)中的最短路徑，將之建立模型，并描述了用matlab程序進(jìn)行求解的過程。關(guān)鍵詞：最短路matlabFloyd算法#問題提出北京的一科技公司由于業(yè)務(wù)的需要，其總經(jīng)理每周要往返于總公司與各個子公司之間，其出行所乘坐的交通工具是飛機(jī)，各個城市間的飛機(jī)線路，及票價如下表城市北京天津南京青島上海廣州深圳西安武漢杭州北京050INF4025101214INF15天津5001520INF2520INF1716南京INF1501020INFINF2628INF青島4020100102532221821上海25INF201005516INF2124廣州1025INF255501724INF25深圳1220INF3216170162718西安14INF2622INF241601819武漢INF17281821INF2718020杭州1516INF2124251819200（注：數(shù)字代表價格，INF表示城市之間沒有線路。）問怎樣才能算出一張任意城市間的最廉價路線表。問題分析若網(wǎng)絡(luò)中的每條邊都有一個數(shù)值（長度、成本、時間等），則找出兩節(jié)點(diǎn)（通常是源節(jié)點(diǎn)和阱節(jié)點(diǎn)）之間總權(quán)和最小的路徑就是最短路問題。最短路問題是網(wǎng)絡(luò)理論解決的典型問題之一，可用來解決管路鋪設(shè)、線路安裝、廠區(qū)布局和設(shè)備更新等實(shí)際問題。最短路問題，我們通常歸屬為三類：單源最短路徑問題、確定起點(diǎn)終點(diǎn)的最短路徑問題、全局最短路徑問題———求圖中所有的最短路徑。題中要求算出一張任意城市間的最廉價路線表，屬于全局最短路問題，并且使得該公司總經(jīng)理能夠與各個子公司之間自由往返。（此兩點(diǎn)為主要約束條件）我們確定本題為全局最短路問題，并采用Floyd算法，具體原理如下：（1）求距離矩陣的方法根據(jù)路線及票價表建立帶權(quán)矩陣W，并把帶權(quán)鄰接矩陣我w作為距離矩陣的初始值，即D（0）=的初始值，即D（0）=（d（o））=Wijvxvr]D（i）=（d（i）），其中di=minid（o）,d（o）+d（o）J，d⑴是從v到v的只允ijvxvijiji11jijiJ許以'作為中間點(diǎn)的路徑中最短路的長度。D（2）=（d⑵），其中d2=min{d⑴,d⑴+d⑴},ijvxvijij122j允許以v，v作為中間點(diǎn)的路徑中最短路的長度。2i1d⑵是從v到v的只ijijv，1vDvD（v）=（d（v）=min{d（v-i）,d（v-1）+d（v-1）},d（v）是從vijijijvjijiv、……、v2v到v的只允許v、j1作為中間點(diǎn)的路徑中最短路的長度。即是從v至Uv中間可插入如何ij頂點(diǎn)的路徑中最短路的長度，因此D（v）即是距離矩陣。（2）求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R,R=（r），丫的含義是從v至UvJvxvijiJ的最短路徑要經(jīng)過點(diǎn)號為r的點(diǎn)。ijR（o）=（r（o））,r（o）=jijvxvij每求得一個D（k）時，按下列方式產(chǎn)生相應(yīng)的新的R（k）:廠kd,若d>d（k-1）+d（k-1）r（k）=vijikkjijr（k一i）,否則ij即當(dāng)v被插入任何兩點(diǎn)間的最短路徑時，被記錄在R（k）中，依次求得D（k）時k求得R（k），可由R（v）來查找任何點(diǎn)對之間最短的路徑。（3）查找最短路徑的方法TOC\o"1-5"\h\z若r（v）=p，則點(diǎn)p是點(diǎn)i到j(luò)的最短距離的中間點(diǎn)，然后用同樣的方法再ij11分頭查找。若：向點(diǎn)i追溯得：r（v）=p,r（v）=p,...,r（v）=pip12ip23ipkk向點(diǎn)j追溯得：r（v）=q,r（v）=q,...,r（v）=j則由點(diǎn)i到j(luò)的最短路的路徑為：i，p，…，p:p，q，q，…，q，j。k2112m模型假設(shè)各城市間的飛機(jī)線路固定不變各城市間飛機(jī)線路的票價不改變忽略乘客除票價以外的各項(xiàng)開銷費(fèi)用不考慮雷雨云、低云、大風(fēng)、雷暴、冰雹等主要天氣因素對飛行的影響。模型建立4．1建立帶權(quán)鄰接矩陣根據(jù)飛機(jī)路線及票價表建立帶權(quán)鄰接矩陣，在帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次構(gòu)造出v個矩陣D（i）、D⑵、…、D（v），使最后得到的矩陣D（v）為飛機(jī)的廉價矩陣。050g4025101214g155001520g2520g1716g1501020gg2628g402010010253222182125g201005516g21241025g255501724g251220g321617016271814g2622g241601819g17281821g27180201516g2124251819200W=4．2采用floyd算法步驟為:D:i到j(luò)的最短距離i,jR:i到j(luò)之間的插入點(diǎn)i,j輸入帶權(quán)鄰接距陣w賦初值：對所有i,j,wTd,jTr,k二1.TOC\o"1-5"\h\zi,ji,ji,j更新D,R:對所有i,j若d+d<d，則i,ji,ji,kk,ji,jd+dTd,kTr.i,kk,ji,ji,j⑶若k二v，停止；否則k+1Tk，轉(zhuǎn)(2).模型求解運(yùn)行程序得：D=0314035251012143215310152030252035171640150102035352628313520100102526221821253020100331632212410253525330172442251220352616170162718143526223224160181932172818214227180201516312124251819200R=110855678810102344679910823454289252345658910143457749101244767821012255678910193446789108234527891012245678910結(jié)果分析根據(jù)模型求解，分析得出任意兩個城市之間最廉價線路及票價為（橫線可逆）：北京—天津：北京—杭州—天津；31北京—南京：北京—西安—南京；40北京—青島：北京—上海—青島；35北京—上海：北京—上海；25北京—廣州：北京—廣州；10北京—深圳：北京—深圳；12北京—西安：北京—西安；14北京—武漢：北京—西安—武漢；32北京—杭州：北京—杭州；15天津—南京：天津—南京；15天津—青島：天津—青島；20天津—上海：天津—青島—上海；30天津—廣州：天津—廣州；25天津—深圳：天津—深圳；20天津—西安：天津—武漢—西安；35天津—武漢：天津—武漢；17天津—杭州：天津—杭州；16南京—青島：南京—青島；10南京—上海：南京—上海；20南京—廣州：南京—青島—廣州；35南京—深圳：南京—天津—深圳；35南京—西安：南京—西安；26南京—武漢：南京—武漢；28；南京—杭州：南京—天津—杭州；31青島—上海：青島—上海；10青島—廣州：青島—廣州；25青島—深圳：青島—上?！钲?；26青島—西安：青島—西安；22青島—武漢：青島—武漢；18青島—杭州：青島—杭州；21上?！獜V州：上海—深圳—廣州；33上?！钲冢荷虾！钲冢?6上?！靼玻荷虾！鄭u—西安；32上?！錆h：上?！錆h；21上?！贾荩荷虾！贾?；24廣州—深圳：廣州—深圳；17廣州—西安：廣州—西安；24廣州—武漢：廣州—天津—武漢；42廣州—杭州：廣州——杭州；25深圳—西安：深圳—西安；16深圳—武漢：深圳—武漢；27深圳—杭州：深圳—杭州18西安—武漢：西安—武漢；18西安—杭州：西安—杭州；19方案評價本文把所解決的問題歸結(jié)為最短路問題，建立的數(shù)學(xué)模型清晰合理。運(yùn)用MATLAB軟件處理數(shù)據(jù)和進(jìn)行運(yùn)算，降低運(yùn)算量，簡單易行，有很大的可操作性。且所得數(shù)據(jù)較為合理可靠。在實(shí)際運(yùn)用本方案中還應(yīng)考慮自然因素對飛機(jī)航行的影響，還需根據(jù)實(shí)際情況進(jìn)行靈活改變。參考文獻(xiàn)［1］趙靜數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)［M］高等教育出版社2000.11［2］張靜李濤任意城市間最短路徑的matlab語言實(shí)現(xiàn)J］九江學(xué)院學(xué)報2007［3］百度百科Floy算法/view/14495.htm2011.6.14［4］百度百科最短路問題/view/838916.htm2011.6.151mar+-ab卅諭洞-Road"mano5*inf\4F2P10m1護(hù)inf\15-50?0?IP20?inf?25?20?inf?Ir16-inf"15"0-10"20"inf"inf"26"28"inf-4Fom25m2N102r2Pinf\2*IFF5PIPinf\2廠24-IF2Pinf\2P5POu2護(hù)inf\25-IN2*inf\3NIPlrFIP2r一于1護(hù)inf\2P2Ninf\2護(hù)IPF1019-inf\lr2