最短路徑問(wèn)題.doc

最短路徑問(wèn)題摘要在圖論當(dāng)中，任意兩點(diǎn)間的最短路徑問(wèn)題，運(yùn)用Dijkstra算法，F(xiàn)lord算法，匈牙利算法等都可以就解決這類(lèi)相關(guān)問(wèn)題,本文主要就是運(yùn)用圖論相關(guān)知識(shí)，來(lái)分析問(wèn)題的。在問(wèn)題一中，需要為貨車(chē)司機(jī)選擇一條從地點(diǎn)1到地點(diǎn)11的最短時(shí)間問(wèn)題，其實(shí)際歸結(jié)為求一個(gè)兩點(diǎn)間最短路徑問(wèn)題，運(yùn)用運(yùn)籌學(xué)中的網(wǎng)絡(luò)模型相關(guān)知識(shí)，建立了一個(gè)一個(gè)0-1線性模型，并最終求的其結(jié)果，最短時(shí)間為21，貨車(chē)司機(jī)的運(yùn)輸路線為。運(yùn)用Floyd算法解決問(wèn)題二，并且運(yùn)用Matlab軟件編程，F(xiàn)loyd算法與Matlab軟件編程所得出的結(jié)果一致，最后得出了一個(gè)最短航程表，及任意兩點(diǎn)間的最短航程圖。本文的最大亮點(diǎn)在于將問(wèn)題二進(jìn)行更深一步的拓展，從問(wèn)題實(shí)際出發(fā)，從公司的差旅費(fèi)用最小出發(fā)，利用Mtlab軟件編程的出了公司到個(gè)城市間差旅費(fèi)用最小圖，從而更能為公司節(jié)省成本。C1C2C3C4C5C6C1051.561.5503416C254.8024324840C366240163254.5C450321601638.5C5344827.516050C614.835.550.334.348.80 任意城市間差旅費(fèi)用最小 其次是本文結(jié)果的準(zhǔn)確性，問(wèn)題一運(yùn)用Lingo軟件編程，和WinQSB軟件，所得出結(jié)果都是一致的，問(wèn)題二更是運(yùn)用Floyd算法，Matlab軟件編程，WinQSB軟件，大大地保證了結(jié)果的準(zhǔn)確性，并且十分恰當(dāng)?shù)剡\(yùn)用WinQSB軟件將作圖功能，把每一提的最短路徑都清晰的描繪出來(lái)，更加直觀地將結(jié)果展現(xiàn)出來(lái)。關(guān)鍵字：Matlab Lingo WinQSB Floyd算法 0-1規(guī)劃 一、 問(wèn)題重述問(wèn)題一需要解決的問(wèn)題是在一個(gè)城市交通網(wǎng)絡(luò)中（圖一），如何從地點(diǎn)1找到一條時(shí)間最短路徑通往地點(diǎn)11，在這個(gè)城市交通網(wǎng)絡(luò)中，有單向道，也有雙向道，即如何處理一個(gè)有向圖與無(wú)向圖結(jié)合的圖論問(wèn)題，并且是一個(gè)兩點(diǎn)間的最短路徑問(wèn)題：10237411659813512210615887993227圖（一）問(wèn)題二闡述的是某公司員工往來(lái)于六個(gè)城市間，給出了這六個(gè)城市間的直達(dá)航班票價(jià)（表二），需要為這家公司提供出這六個(gè)城市間任意兩點(diǎn)間的最小航班費(fèi)用表表（二）二、問(wèn)題分析4.1問(wèn)題一的分析：實(shí)際問(wèn)題是貨車(chē)運(yùn)輸問(wèn)題，貨車(chē)運(yùn)輸從起點(diǎn)1到終點(diǎn)11，一般情況下，不存在貨物往回運(yùn)輸，所以地點(diǎn)1到地點(diǎn)8是可以看成是一個(gè)單向道，即8指向1，同樣的地點(diǎn)8也是指向地點(diǎn)9的。假設(shè)貨物到達(dá)地點(diǎn)9時(shí)，貨物要運(yùn)送到終點(diǎn)，則地點(diǎn)9只能指向地點(diǎn)10，同理貨物到達(dá)地頂點(diǎn)點(diǎn)7，只能是往地點(diǎn)6的方向運(yùn)輸。如果貨物到達(dá)地點(diǎn)5時(shí)，貨物只有經(jīng)過(guò)5 6 9 10 11，才是最短的，所以在這里地點(diǎn)5指向地點(diǎn)6.同理3指向5，得出圖（二），這樣按照時(shí)間耗費(fèi)的目的，將一個(gè)有向圖與無(wú)向圖結(jié)合的圖，轉(zhuǎn)化為一個(gè)單純的有向圖，這將有利于問(wèn)題的分析。 圖（二）4.2問(wèn)題二的分析；通過(guò)題目給出的六個(gè)城市間的直達(dá)航班票價(jià)（表二），可以將其繪成無(wú)向圖（圖三），可以將其轉(zhuǎn)換成一個(gè)圖輪問(wèn)題，即求一個(gè)具有六個(gè)頂點(diǎn)無(wú)向圖的任意兩點(diǎn)間的最短路徑問(wèn)題，這里用到圖論當(dāng)中的Flord算法。 圖（三）三、基本假設(shè)1、貨車(chē)在各路段中所花時(shí)間數(shù)據(jù)屬實(shí)。2、貨車(chē)在行駛中是按勻速行駛3、貨運(yùn)車(chē)在路途中無(wú)意外發(fā)生，無(wú)需返回原地。4、假設(shè)天氣等一些客觀因素不影響交通運(yùn)輸。5、飛機(jī)航班不存在延誤現(xiàn)象。6、公司員工轉(zhuǎn)機(jī)過(guò)程中不存在逗留現(xiàn)象。四、符號(hào)說(shuō)明1、：貨車(chē)從地點(diǎn)到地點(diǎn)所花的時(shí)間：2、：貨車(chē)司機(jī)是否選擇地點(diǎn)到地點(diǎn)，； 3、公司員工選擇從城市到城市的航班，；4、，插入點(diǎn)；5、：插入點(diǎn)后的路徑；五、模型的建立與求解6.1 問(wèn)題1的模型建立與求解6.1.1跟據(jù)已得出的分析再加上題目所給的已知條件，可以得出其賦全矩陣（表（三）：v1v2v3v4v5v6v7v8v9v10v11v10878v203v30565v401112v560210v6203v790v809v9702v10202v110表（三）建立如下0-1規(guī)劃數(shù)學(xué)模型：運(yùn)用Lingo軟件輸入一個(gè)線性規(guī)劃程序（見(jiàn)附錄（一），分析得出如下結(jié)果：formtotimetimev1v888v8v9917v9v10219v10v11221v1v11=21v1v2=8v1v3=11v1v4=16v1v5=17v1v6=16v1v7=7v1v8=8v1v9=17v1v10=19表（四）6.1.2模型一的結(jié)果分析: 利用WinQSB軟件中的Network model,選擇Short Path problem,輸入問(wèn)題一的賦權(quán)矩陣（表 ）輸入如下數(shù)據(jù)：圖（三）得出結(jié)果表（見(jiàn)附錄三），并得出如下直觀圖： 圖（四）圖四中可以看出的最短路徑為21，所以模型一的最優(yōu)解可以得到驗(yàn)證為，所以貨車(chē)司機(jī)應(yīng)選路線最短，所花時(shí)間最短為21。6.2 問(wèn)題2的模型建立與求解 6.2.1由問(wèn)題2的分析，可利用圖論方法、Floyd算法及WinQSB軟件求解該問(wèn)題, 由問(wèn)題中所給的各個(gè)節(jié)點(diǎn)的坐標(biāo)進(jìn)行如下的Floyd算法步驟： 以及得出每次插入點(diǎn)的路徑變化（見(jiàn)附錄表（三），得出六個(gè)城市間的任意兩點(diǎn)間的最短路徑表和最終選擇路徑矩陣：C1C2C3C4C5C6C103545352510C235015203025C345150102035C435201001025C525302010035C610253525350 最短航程圖由Matlab編程（見(jiàn)附錄五）運(yùn)行得出的結(jié)果與Floyd算法一致、 6.2.2問(wèn)題二的結(jié)果分析 利用WinQSB軟件求得這6個(gè)城市間的任意兩點(diǎn)最短航程見(jiàn)（附錄四），并得出直觀圖：六、模型二的擴(kuò)展在問(wèn)題二該公司員工出差途中，在搭乘航班過(guò)程所使用的總時(shí)間，都算作公司損失時(shí)間，此時(shí)公司差旅費(fèi)用=每小時(shí)員工正常創(chuàng)造價(jià)值航班總時(shí)間+票價(jià)。公司員工搭乘航班時(shí)間是航班總飛行時(shí)間是與飛機(jī)飛行時(shí)間和員工轉(zhuǎn)乘時(shí)間有關(guān)，計(jì)算公司員工出差從地到地，公司差旅費(fèi)用最少。員工在六個(gè)城市C1,C2,C3,C4,C5,C6個(gè)機(jī)場(chǎng)等待重新登機(jī)起飛所等待的時(shí)間（機(jī)場(chǎng)估算），如下： 假設(shè)：航程越長(zhǎng)飛行時(shí)間越長(zhǎng)票價(jià)越貴，這三者間存在聯(lián)系，查找數(shù)據(jù)得兩個(gè)城市之間飛行時(shí)間（機(jī)場(chǎng)估算），如下：航班飛行時(shí)間=航班飛行總時(shí)間=飛機(jī)飛行時(shí)間+員工重新登機(jī)時(shí)間。公司員工為公司創(chuàng)造價(jià)值每小時(shí)（=30）元（公司估計(jì)值）。公司差旅費(fèi)用=員工為公司創(chuàng)造價(jià)值航班總時(shí)間+票價(jià)。通過(guò)計(jì)算得：公司差旅費(fèi)用=票價(jià)+飛行總時(shí)間，根據(jù)此矩陣的出如下圖形：利用Matlab軟件編程求解（程序見(jiàn)附錄七），整理結(jié)果得出任意城市差旅費(fèi)用最小表（四），并利用WinQSB軟件得出如下任意城市間差旅費(fèi)用最小圖：C1C2C3C4C5C6C1051.561.5503416C254.8024324840C366240163254.5C450321601638.5C5344827.516050C614.835.550.334.348.80任意城市間差旅費(fèi)用最小表（四）任意城市間差旅費(fèi)用最小圖 七、模型的評(píng)價(jià)問(wèn)題一的模型評(píng)價(jià)運(yùn)用了Lingo編程、利用WinQSB軟件驗(yàn)證，大大地減少了計(jì)算量，同時(shí)提高了計(jì)算的準(zhǔn)確性。模型一求最短路徑問(wèn)題，將問(wèn)題按實(shí)際常理出發(fā)，將一個(gè)有向與無(wú)向結(jié)合的圖，轉(zhuǎn)化為一個(gè)單一的有向圖，使得問(wèn)題變得簡(jiǎn)化易解，將模型建立為一個(gè)線性規(guī)劃問(wèn)題，該模型有利于解決一些解決常見(jiàn)的最短路問(wèn)題，并且其Lingo程序只需改動(dòng)相關(guān)數(shù)據(jù)便可適用于常見(jiàn)的求最短路問(wèn)題。問(wèn)題二的模型評(píng)價(jià)采用了Floyd算法并利用Matlab軟件編程，再利用WinQSB軟件，確保了結(jié)果的準(zhǔn)確性，并以圖表的形式，更加直觀清晰地展示出每一個(gè)城市到任意城市的最短路徑。針對(duì)問(wèn)題二，從實(shí)際問(wèn)題出發(fā)，對(duì)問(wèn)題進(jìn)行了拓展，求出了公司差旅費(fèi)用最小矩陣，更加有利于為公司節(jié)省最大費(fèi)用。但由于渠道不暢，對(duì)于拓展內(nèi)容的相關(guān)數(shù)據(jù)的可靠性還有待核實(shí)，但這并不會(huì)減掉模型拓展內(nèi)容的豐富性，并不會(huì)抹掉其內(nèi)在的，實(shí)質(zhì)性魅力。八、參考文獻(xiàn)1 熊偉，運(yùn)籌學(xué)，第二版，北京：機(jī)械工業(yè)出版社，2011。2 薛毅，數(shù)學(xué)建?；A(chǔ)，第二版，北京：科學(xué)出版社，2011。3 魏巍, Matlab應(yīng)用數(shù)學(xué)工具箱技術(shù)手冊(cè)，北京：國(guó)防工業(yè)出版社，2004。4 姜啟源 謝金星 葉俊，數(shù)學(xué)模型，第三版：高等教育出版社，2007。5 韓中庚 宋明武 邵廣紀(jì)，數(shù)學(xué)建模競(jìng)賽獲獎(jiǎng)?wù)撐木x與點(diǎn)評(píng)，北京：科學(xué)出版社，2007。九、附錄附錄一（問(wèn)題一中的Lingo程序）： model: ! vij表示選擇從地點(diǎn)i到地點(diǎn)j； ! eij表示從地點(diǎn)i到地點(diǎn)j貨車(chē)司機(jī)所花時(shí)間； objmin=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; av12+v17+v18=1; bv18-v89=0; cv17+v37-v76=0; dv12-v23=0; ev23-v34-v37-v35=0; fv34-v411-v45=0; gv35+v45+v95-v56-v511=0; hv76+v56-v69=0; lv89+v69-v95-v910=0; nv910-v1011=0; ov411+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附錄二（問(wèn)題一中的Lingo程序的運(yùn)行結(jié)果）： Feasible solution found. Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0Variable ValueV12 0.000000V17 0.000000V18 1.000000V89 1.000000V37 0.000000V76 0.000000V23 0.000000V34 0.000000V35 0.000000V411 0.000000V45 0.000000V95 0.000000V56 0.000000V511 0.000000V69 0.000000V910 1.000000V1011 1.000000E12 8.000000E23 3.000000E34 5.000000E411 12.00000E37 5.000000E17 7.000000E18 8.000000E45 1.000000E35 6.000000E76 9.000000E56 2.000000E511 10.00000E89 9.000000E910 2.000000E1011 2.000000E95 7.000000E69 3.000000Row Slack or SurplusA 0.000000B 0.000000C 0.000000D 0.000000E 0.000000F 0.000000G 0.000000H 0.000000L 0.000000N 0.000000O 0.000000附錄三問(wèn)題一在WinQSB軟件中運(yùn)行的結(jié)果：附錄四 問(wèn)題二在WinQSB軟件中運(yùn)行的結(jié)果，任意兩點(diǎn)間的最短航程表 到各個(gè)城市的最短航程到各個(gè)城市的最短航程到各個(gè)城市的最短航程到各個(gè)城市的最短航程到各個(gè)城市的最短航程到各個(gè)城市的最短航程 附錄五問(wèn)題二在進(jìn)行Floydj算法進(jìn)行插值時(shí)，每次插值所發(fā)生的選擇路徑的變化： 附錄六問(wèn)題二用Matlab軟件編程程序與運(yùn)行結(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)*n2; %M為充分大的正實(shí)數(shù) a=a+(a=0)-eye(n)*M; path=zeros(n); for k=1:nfor i=1:n for j=1:n if a(i,j)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end end end a, path運(yùn)行結(jié)果： a, path a = 0 35 45 35 25 10 35 0 15 20 30 25 45 15 0 10 20 35 35 20 10 0 10 25 25 30 20 10 0 35 10 25 35 25 35 0path = 0 6 5 5 0 0 6 0 0 0 4 0 5 0 0 0 0 4 5 0 0 0 0 0 0 4 0 0 0 1 0 0 4 0 1 0 附錄七問(wèn)題二的拓展用Matlab軟件編程程序與運(yùn)行結(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(