最短路徑問題

《MATLAB及應用》課程論文實踐選題：最短路徑問題專業(yè)班級：10級信信息管理與信息系統(tǒng)1班指導教師：周宏宇成績評定：最短路徑問題摘要:在圖論當中，任意兩點間的最短路徑問題，運用Dijkstra算法，F(xiàn)lord算法，匈牙利算法等都可以就解決這類相關(guān)問題,本文主要就是運用圖論相關(guān)知識，來分析問題的。在問題一中，需要為貨車司機選擇一條從地點1到地點11的最短時間問題，其實際歸結(jié)為求一個兩點間最短路徑問題，運用運籌學中的網(wǎng)絡(luò)模型相關(guān)知識，建立了一個一個0-1線性模型，并最終求的其結(jié)果，最短時間為21，貨車司機的運輸路線為。運用Floyd算法解決問題二，并且運用Matlab軟件編程，F(xiàn)loyd算法與Matlab軟件編程所得出的結(jié)果一致，最后得出了一個最短航程表，及任意兩點間的最短航程圖。本文的最大亮點在于將問題二進行更深一步的拓展，從問題實際出發(fā)，從公司的差旅費用最小出發(fā)，利用Mtlab軟件編程的出了公司到個城市間差旅費用最小圖，從而更能為公司節(jié)省本錢。C1C2C3C4C5C6C1051.561.5503416C254.8024324840C366240163254.5C450321601638.5C5344827.516050C614.835.550.334.348.80任意城市間差旅費用最小其次是本文結(jié)果的準確性，問題一運用Lingo軟件編程，和WinQSB軟件，所得出結(jié)果都是一致的，問題二更是運用Floyd算法，Matlab軟件編程，WinQSB軟件，大大地保證了結(jié)果的準確性，并且十分恰當?shù)剡\用WinQSB軟件將作圖功能，把每一提的最短路徑都清晰的描繪出來，更加直觀地將結(jié)果展現(xiàn)出來。關(guān)鍵字：MatlabLingoWinQSBFloyd算法0-1規(guī)劃問題重述問題一需要解決的問題是在一個城市交通網(wǎng)絡(luò)中〔圖一〕，如何從地點1找到一條時間最短路徑通往地點11，在這個城市交通網(wǎng)絡(luò)中，有單向道，也有雙向道，即如何處理一個有向圖與無向圖結(jié)合的圖論問題，并且是一個兩點間的最短路徑問題：1010237411659813512210615887993227圖〔一〕問題二闡述的是某公司員工往來于六個城市間，給出了這六個城市間的直達航班票價〔表二〕，需要為這家公司提供出這六個城市間任意兩點間的最小航班費用表表〔二〕二、問題分析問題一的分析：實際問題是貨車運輸問題，貨車運輸從起點1到終點11，一般情況下，不存在貨物往回運輸，所以地點1到地點8是可以看成是一個單向道，即8指向1，同樣的地點8也是指向地點9的。假設(shè)貨物到達地點9時，貨物要運送到終點，那么地點9只能指向地點10，同理貨物到達地頂點點7，只能是往地點6的方向運輸。如果貨物到達地點5時，貨物只有經(jīng)過5691011，才是最短的，所以在這里地點5指向地點6.同理3指向5，得出圖〔二〕，這樣按照時間消耗的目的，將一個有向圖與無向圖結(jié)合的圖，轉(zhuǎn)化為一個單純的有向圖，這將有利于問題的分析。圖〔二〕問題二的分析；通過題目給出的六個城市間的直達航班票價〔表二〕，可以將其繪成無向圖〔圖三〕，可以將其轉(zhuǎn)換成一個圖輪問題，即求一個具有六個頂點無向圖的任意兩點間的最短路徑問題，這里用到圖論當中的Flord算法。圖〔三〕三、根本假設(shè)1、貨車在各路段中所花時間數(shù)據(jù)屬實。2、貨車在行駛中是按勻速行駛3、貨運車在路途中無意外發(fā)生，無需返回原地。4、假設(shè)天氣等一些客觀因素不影響交通運輸。5、飛機航班不存在延誤現(xiàn)象。6、公司員工轉(zhuǎn)機過程中不存在逗留現(xiàn)象。四、符號說明1、：貨車從地點到地點所花的時間：2、：貨車司機是否選擇地點到地點，；3、公司員工選擇從城市到城市的航班，；4、，插入點；5、：插入點后的路徑；五、模型的建立與求解問題1的模型建立與求解跟據(jù)已得出的分析再加上題目所給的條件，可以得出其賦全矩陣〔表〔三〕〕：·v1v2v3v4v5v6v7v8v9v10v11v108∞∞∞∞78∞∞∞v2∞03∞∞∞∞∞∞∞∞v3∞∞056∞5∞∞∞∞v4∞∞∞011∞∞∞∞∞12v5∞∞6∞02∞∞∞∞10v6∞∞∞∞20∞∞3∞∞v7∞∞∞∞∞90∞∞∞∞v8∞∞∞∞∞∞∞09∞∞v9∞∞∞∞7∞∞∞02∞v10∞∞∞∞∞∞∞∞202v11∞∞∞∞∞∞∞∞∞∞0表〔三〕建立如下0-1規(guī)劃數(shù)學模型：運用Lingo軟件輸入一個線性規(guī)劃程序〔見附錄〔一〕〕，分析得出如下結(jié)果：formtotimetimev1v888v8v9917v9v10219v10v11221v1v11=21v1v2=8v1v3=11v1v4=16v1v5=17v1v6=16v1v7=7v1v8=8v1v9=17v1v10=19表〔四〕模型一的結(jié)果分析:利用WinQSB軟件中的Networkmodel,選擇ShortPathproblem,輸入問題一的賦權(quán)矩陣〔表〕輸入如下數(shù)據(jù)：圖〔三〕得出結(jié)果表〔見附錄三〕，并得出如下直觀圖：圖〔四〕圖四中可以看出的最短路徑為21，所以模型一的最優(yōu)解可以得到驗證為，，，所以貨車司機應選路線最短，所花時間最短為21。問題2的模型建立與求解6.2.1由問題2的分析，可利用圖論方法、Floyd算法及WinQSB軟件求解該問題,由問題中所給的各個節(jié)點的坐標進行如下的Floyd算法步驟：以及得出每次插入點的路徑變化〔見附錄表〔三〕〕，得出六個城市間的任意兩點間的最短路徑表和最終選擇路徑矩陣：C1C2C3C4C5C6C103545352510C235015203025C345150102035C435201001025C525302010035C610253525350最短航程圖由Matlab編程〔見附錄五〕運行得出的結(jié)果與Floyd算法一致、問題二的結(jié)果分析利用WinQSB軟件求得這6個城市間的任意兩點最短航程見〔附錄四〕，并得出直觀圖：六、模型二的擴展在問題二該公司員工出差途中，在搭乘航班過程所使用的總時間，都算作公司損失時間，此時公司差旅費用=每小時員工正常創(chuàng)造價值航班總時間+票價。公司員工搭乘航班時間是航班總飛行時間是與飛機飛行時間和員工轉(zhuǎn)乘時間有關(guān)，計算公司員工出差從地到地，公司差旅費用最少。①員工在六個城市C1,C2,C3,C4,C5,C6個機場等待重新登機起飛所等待的時間〔機場估算〕，如下：②假設(shè)：航程越長飛行時間越長票價越貴，這三者間存在聯(lián)系，查找數(shù)據(jù)得兩個城市之間飛行時間〔機場估算〕，如下：航班飛行時間=航班飛行總時間=飛機飛行時間+員工重新登機時間。公司員工為公司創(chuàng)造價值每小時〔=30〕元〔公司估計值〕。公司差旅費用=員工為公司創(chuàng)造價值航班總時間+票價。通過計算得：公司差旅費用=票價+飛行總時間，根據(jù)此矩陣的出如下列圖形：利用Matlab軟件編程求解〔程序見附錄七〕，整理結(jié)果得出任意城市差旅費用最小表〔四〕，并利用WinQSB軟件得出如下任意城市間差旅費用最小圖：C1C2C3C4C5C6C1051.561.5503416C254.8024324840C366240163254.5C450321601638.5C5344827.516050C614.835.550.334.348.80任意城市間差旅費用最小表〔四〕任意城市間差旅費用最小圖七、模型的評價問題一的模型評價運用了Lingo編程、利用WinQSB軟件驗證，大大地減少了計算量，同時提高了計算的準確性。模型一求最短路徑問題，將問題按實際常理出發(fā)，將一個有向與無向結(jié)合的圖，轉(zhuǎn)化為一個單一的有向圖，使得問題變得簡化易解，將模型建立為一個線性規(guī)劃問題，該模型有利于解決一些解決常見的最短路問題，并且其Lingo程序只需改動相關(guān)數(shù)據(jù)便可適用于常見的求最短路問題。問題二的模型評價采用了Floyd算法并利用Matlab軟件編程，再利用WinQSB軟件，確保了結(jié)果的準確性，并以圖表的形式，更加直觀清晰地展示出每一個城市到任意城市的最短路徑。針對問題二，從實際問題出發(fā)，對問題進行了拓展，求出了公司差旅費用最小矩陣，更加有利于為公司節(jié)省最大費用。但由于渠道不暢，對于拓展內(nèi)容的相關(guān)數(shù)據(jù)的可靠性還有待核實，但這并不會減掉模型拓展內(nèi)容的豐富性，并不會抹掉其內(nèi)在的，實質(zhì)性魅力。八、參考文獻[1]熊偉，運籌學，第二版，北京：機械工業(yè)出版社，2011。[2]薛毅，數(shù)學建模根底，第二版，北京：科學出版社，2011。[3]魏巍,Matlab應用數(shù)學工具箱技術(shù)手冊，北京：國防工業(yè)出版社，2004。[4]姜啟源謝金星葉俊，數(shù)學模型，第三版：高等教育出版社，2007。[5]韓中庚宋明武邵廣紀，數(shù)學建模競賽獲獎?wù)撐木x與點評，北京：科學出版社，2007。九、附錄附錄一〔問題一中的Lingo程序〕：model:!vij表示選擇從地點i到地點j；!eij表示從地點i到地點j貨車司機所花時間；[obj]min=v12*e12+v17*e17+v18*e18+v23*e23+v34*e34+v37*e37+v35*e35+v411*e411+v45*e45+v511*e511+v56*e56+v69*e69+v76*e76+v89*e89+v910*e910+v95*e95+v1011*e1011;[a]v12+v17+v18=1;[b]v18-v89=0;[c]v17+v37-v76=0;[d]v12-v23=0;[e]v23-v34-v37-v35=0;[f]v34-v411-v45=0;[g]v35+v45+v95-v56-v511=0;[h]v76+v56-v69=0;[l]v89+v69-v95-v910=0;[n]v910-v1011=0;[o]v411+v511+v1011=1;@bin(v12);@bin(v17);@bin(v18);@bin(v76);@bin(v89);@bin(v35);@bin(v37);@bin(v23);@bin(v34);@bin(v45);@bin(v411);@bin(v511);@bin(v56);@bin(v69);@bin(v95);@bin(v910);@bin(v1011);data:e12=8;e23=3;e34=5;e411=12;e37=5;e17=7;e18=8;e45=1;e35=6;e76=9;e56=2;e511=10;e89=9;e910=2;e1011=2;e95=7;e69=3;enddataend附錄二〔問題一中的Lingo程序的運行結(jié)果〕：Feasiblesolutionfound.Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:0VariableValueV120.000000V170.000000V181.000000V891.000000V370.000000V760.000000V230.000000V340.000000V350.000000V4110.000000V450.000000V950.000000V560.000000V5110.000000V690.000000V9101.000000V10111.000000E128.000000E233.000000E345.000000E41112.00000E375.000000E177.000000E188.000000E451.000000E356.000000E769.000000E562.000000E51110.00000E899.000000E9102.000000E10112.000000E957.000000E693.000000RowSlackorSurplusA0.000000B0.000000C0.000000D0.000000E0.000000F0.000000G0.000000H0.000000L0.000000N0.000000O0.000000附錄三問題一在WinQSB軟件中運行的結(jié)果：附錄四問題二在WinQSB軟件中運行的結(jié)果，任意兩點間的最短航程表到各個城市的最短航程到各個城市的最短航程到各個城市的最短航程到各個城市的最短航程到各個城市的最短航程到各個城市的最短航程附錄五問題二在進行Floydj算法進行插值時，每次插值所發(fā)生的選擇路徑的變化：附錄六問題二用Matlab軟件編程程序與運行結(jié)果：>>clear>>n=6;>>a=zeros(n);>>a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;>>a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;>>a(4,5)=10;a(4,6)=25;a(5,6)=55;>>a=a+a';M=max(max(a))*n^2;%M為充分大的正實數(shù)>>a=a+((a==0)-eye(n))*M;>>path=zeros(n);>>fork=1:nfori=1:nforj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendend>>a,path運行結(jié)果：a,patha=035453525103501520302545150102035352010010252530201003510253525350path=065500600040500004500000040001004010附錄七問題二的拓展用Matlab軟件編程程序與運行結(jié)果：>>n=6;>>a=zeros(n);>>a(1,2)=69.5;a(1,4)=61;a(1,5)=34;a(1,6)=16;>>a(2,1)=71;a(2,3)=24;a(2,4)=32;a(2,6)=40;>>a(3,2)=24;a(3,4)=16;a(3,5)=32;>>a(4,1)=53.5;a(4,2)=32;a(4,3)=16;a(4,5)=16;a(4,6)=38.5;>>a(5,1)=34;a(5,3)=27.5;a(5,4)=16;a(5,6)=76;>>a(6,1)=14.8;a(6,2)=35.5;a(6,4)=34.3;a(6,5)=76;>