數(shù)學(xué)建模有關(guān)緊急調(diào)兵和最佳乘車路線問(wèn)題

《數(shù)學(xué)模型與數(shù)學(xué)軟件綜合訓(xùn)練》論文二最佳乘車路線蘭州理工大學(xué)計(jì)通院信息與計(jì)算科學(xué)專業(yè)2009年春季學(xué)期一前言 3 31論文摘要 32問(wèn)題重述與分析 33假設(shè)與模型 33.1模型假設(shè) 33.2模型建立 43.3問(wèn)題求解 4三最佳乘車路線 61論文摘要 62問(wèn)題重述與分析 63假設(shè)與模型 63.1模型假設(shè) 63.2符號(hào)說(shuō)明 6 7 7 1參考文獻(xiàn)一 2參考文獻(xiàn)二 206500125劉永旺09年春數(shù)學(xué)模型與數(shù)學(xué)軟件綜合訓(xùn)練一前言在現(xiàn)實(shí)生活中我們有許多實(shí)際問(wèn)題需要解決，而怎么去解決這些問(wèn)題就成為我們要討論的主要問(wèn)題，通常采用建立數(shù)學(xué)模型的方法，這樣如何合理建立所要解決問(wèn)題的模型就成了關(guān)鍵，所建立的數(shù)學(xué)模型不僅要在模型假設(shè)中通過(guò)分析研究能得到所要的結(jié)果，而且必須具有可行性，通過(guò)模型建立能夠最終解在數(shù)學(xué)模型的建立過(guò)程中分析問(wèn)題是關(guān)鍵，首先應(yīng)該搞清楚需要解決什么問(wèn)題，然后從問(wèn)題入手考慮通過(guò)什么方法用哪些因素能一步得到要求因素，其中會(huì)用到我們學(xué)過(guò)的數(shù)學(xué)知識(shí)，用合適的建立模型的方法，如本模型步中用到的單因素模型，逐步回歸模型等模型，通過(guò)數(shù)據(jù)擬合相應(yīng)函數(shù)等方法，通過(guò)函數(shù)分析并結(jié)合圖形，判斷優(yōu)化方案，并考慮各組成因素的變化情況，同時(shí)考慮各因素的交互效應(yīng)，這樣才能建立出合理的數(shù)學(xué)模型。在模型建立過(guò)程中借助圖表，曲線圖的功能更加直觀，簡(jiǎn)要易懂，并對(duì)所建模型作進(jìn)一步分析和改進(jìn)，使得所建模型更能反映實(shí)際情況。1論文摘要由于軍事上的需要，需將甲地n名戰(zhàn)斗人員(不包括駕駛員)緊急調(diào)運(yùn)之乙地：但是由于運(yùn)輸車輛不足，m輛車無(wú)法保證每個(gè)戰(zhàn)斗人員都乘上車。為了使這n名戰(zhàn)斗人員以最短的時(shí)間到達(dá)目的地，必須得有一部分戰(zhàn)斗人員緊急行軍，這樣就可以保證所有人員同時(shí)到達(dá)目的地。2問(wèn)題重述與分析由于戰(zhàn)斗需要，所有人員必須在最短時(shí)間里同時(shí)到達(dá)，才能保證需求。目前是車少人多，所有人不能同時(shí)乘車到達(dá)目的地，有一部分人需要行軍前進(jìn)。現(xiàn)有m輛車，n人，每輛車可以載b人。車輛先運(yùn)走一部分行軍速度慢的，到達(dá)一定的地方，然后這些人行軍，車輛返回在后面的行軍人中間運(yùn)走相對(duì)行軍慢的，以此類推，車輛最后運(yùn)的人員和所有的戰(zhàn)斗人員同時(shí)到達(dá)目的地。3假設(shè)與模型3.1模型假設(shè)1)將這n名戰(zhàn)斗人員中最后一個(gè)運(yùn)到乙地算完成任務(wù)，以部隊(duì)從甲地出發(fā)起，到第n名戰(zhàn)斗人員到達(dá)乙地的運(yùn)輸時(shí)間為目標(biāo)，不考慮先期到達(dá)戰(zhàn)斗人員的軍事價(jià)值；2)車速和人行速均按最大速度計(jì)算，不考慮人員勞累和車輛加油問(wèn)題，也不考慮道路的影響；3)戰(zhàn)斗人員上下車的時(shí)間可忽略不計(jì)；4)設(shè)每輛車載b人(不包括駕駛員);車速是人行軍速度的k倍(k>1);5)設(shè)j是大于1的整數(shù)，如當(dāng)j=2時(shí)，說(shuō)明n名戰(zhàn)斗人員一分為二，一半乘車，一半行軍，到了中途某一點(diǎn)，讓乘車人員下車行軍前進(jìn)，車輛返回接另一部分人員，最后和第一批人員同時(shí)到306500125劉永旺09年春數(shù)學(xué)模型與數(shù)學(xué)軟件綜合訓(xùn)練3.2模型建立設(shè)甲地到乙地距離為1個(gè)長(zhǎng)度單位，人行軍速度為1個(gè)速度單位，車速為k。設(shè)最優(yōu)方案中人行軍路程為y(因同時(shí)到達(dá)，每個(gè)人行軍路程都是y),則每個(gè)人乘車路程為1-設(shè)最有調(diào)運(yùn)方案中，車向前行走的路程為x(因m輛車同時(shí)到達(dá)，車速相同，每輛車前進(jìn)路程為x),后退路程為x-1,x>1。最優(yōu)方案中人與車同時(shí)到達(dá)乙地，所用時(shí)間相同，所以因?yàn)閚=mbj,所以車向前時(shí)，mb個(gè)人乘車，車向后開(kāi)時(shí)，無(wú)人乘車：而車向前開(kāi)的時(shí)間為x/k,向后開(kāi)的時(shí)間為(x-1)/k,所以在最優(yōu)調(diào)運(yùn)方案中，平均乘車人數(shù)為：所以在最有方案中最小平均速度的最大值上界(在車和人同時(shí)到達(dá)乙地的方案可行時(shí))為：由(3)式可見(jiàn)平均速度大于人行軍速度，且k越大平均速度越大，j越大，平均速度越小，顯然是合理而根據(jù)(1)式，最優(yōu)方案的平均速度為：由此可得到關(guān)于x,y的方程組解次方程組得：2x-2=(k-1)y,由(6)式可見(jiàn)，其余條件相同情況下車速越快，戰(zhàn)斗人員行軍路程越短，這也說(shuō)明公式是正確的。在達(dá)最大速度情況下，人行軍路程與車行軍路程均已求出，下一步我們考慮實(shí)現(xiàn)這一上界的方案。顯然使平均速度達(dá)(3)式的任一可行方案均為最優(yōu)方案，但其中某方案使人員上下車次數(shù)越少，車輛調(diào)3.3問(wèn)題求解1)開(kāi)始讓車滿載，車和人同時(shí)出發(fā)；406500125劉永旺09年春數(shù)學(xué)模型與數(shù)學(xué)軟件綜合訓(xùn)練與最后一批人相遇時(shí)共后退：56500125劉永旺09年春數(shù)學(xué)模型與數(shù)學(xué)軟件綜合訓(xùn)練1論文摘要利用城市公交網(wǎng)構(gòu)建了基于公交站點(diǎn)的網(wǎng)絡(luò)圖。把各個(gè)站點(diǎn)看作圖的節(jié)點(diǎn)，站點(diǎn)間的線路看作圖的邊，站點(diǎn)間到達(dá)所需的花費(fèi)作為邊的權(quán)值。同時(shí)把公汽、地鐵、看作兩種不同的交通方式來(lái)處理。公交線路選擇的數(shù)學(xué)模型是一般圖的最短路問(wèn)題，利用改進(jìn)的基于廣度優(yōu)先搜索算法，按照乘車次數(shù)、乘車關(guān)鍵詞：網(wǎng)絡(luò)圖換乘公共站點(diǎn)最短路徑問(wèn)題2問(wèn)題重述與分析隨著社會(huì)的高速發(fā)展，城市建設(shè)也越來(lái)越繁華，因此，出門乘車路線的最優(yōu)選擇便成為當(dāng)代城市人必須面對(duì)的一個(gè)問(wèn)題。針對(duì)這一問(wèn)題，建立最佳乘車路線模型系統(tǒng)供人們參考，以滿足查詢者對(duì)線路的各種不同需求。該系統(tǒng)核心是線路選擇的數(shù)學(xué)模型與算法。本文擬解決如下問(wèn)1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。根據(jù)數(shù)據(jù)，利用模型與算法，求出以下6對(duì)起始站→終到站的最佳路線。2、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，給出任意3假設(shè)與模型3.1模型假設(shè)1)在問(wèn)題一，只在任意兩條線路的公共站點(diǎn)進(jìn)行公汽換乘；2)對(duì)轉(zhuǎn)乘次數(shù)無(wú)限定；3)如果下行線是上行線的原路返回，不考慮上行和下行線路間進(jìn)行換乘；4)環(huán)行線路是雙向環(huán)路5)線路的換乘中，等車時(shí)間=平均耗時(shí)3.2符號(hào)說(shuō)明Start:起始站點(diǎn)End:目的站點(diǎn)Fce:乘車費(fèi)用BusNum:乘車次數(shù)Time:乘車時(shí)間C(ij):i站點(diǎn)到j(luò)站點(diǎn)的權(quán)值，表示乘車費(fèi)用或者乘車時(shí)間或乘車次數(shù)，也可表示反映乘車費(fèi)用和時(shí)間及乘車次數(shù)的綜合信息值EDGE[]:結(jié)構(gòu)體數(shù)組，存儲(chǔ)網(wǎng)絡(luò)圖中所有邊的信息Road[]:存儲(chǔ)路徑數(shù)組Road[i]:在最優(yōu)路線i節(jié)點(diǎn)的前驅(qū)Max:理論上花費(fèi)最大值，賦值MyMAX3.3模型的建立轉(zhuǎn)乘次數(shù)最少或乘車費(fèi)用最低),找出一條到達(dá)目的地(End)的最優(yōu)線路。定義一把站點(diǎn)i到站點(diǎn)j的乘車時(shí)間或乘車次數(shù)或乘車費(fèi)用稱做i到j(luò)的花費(fèi)。定義二圖1公交網(wǎng)絡(luò)示意圖(非真實(shí)地理位置圖)1所示，把各個(gè)站點(diǎn)之間所必需的花費(fèi)看作對(duì)應(yīng)邊上的權(quán)(權(quán)>0)。公交網(wǎng)就轉(zhuǎn)化成圖論中的加權(quán)圖。因?yàn)榇嬖诃h(huán)行線路，在本題中，此題將圖轉(zhuǎn)化成為一般圖的圖論問(wèn)題，即在給定的加權(quán)一般圖中，從起點(diǎn)(Start)出發(fā)，沿一條線路到達(dá)目的地(End),使花費(fèi)最少。因此，該問(wèn)題的數(shù)學(xué)模型是含有回路的一般有向圖的最短路!3.4問(wèn)題的求解僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法，求出6對(duì)起始站→終706500125劉永旺09年春數(shù)學(xué)模型與數(shù)學(xué)軟件綜合訓(xùn)練FeeFee:價(jià)錢BusNum:轉(zhuǎn)乘次數(shù)Time:耗費(fèi)時(shí)間u:邊的結(jié)點(diǎn)nxt:在此線路中的u下一個(gè)節(jié)點(diǎn)最佳路線的選擇，首先設(shè)置一個(gè)統(tǒng)一的準(zhǔn)則。在一般網(wǎng)絡(luò)圖中，可以利用普通Dijkstra算法進(jìn)行最短距離求解，但公交網(wǎng)絡(luò)圖節(jié)點(diǎn)數(shù)目龐大，運(yùn)算耗時(shí)過(guò)長(zhǎng)，且運(yùn)算所得結(jié)果可能不符合人們的實(shí)際需求，所以不宜采用此算法[2]。在本題中，采用了良好的數(shù)據(jù)結(jié)構(gòu)并結(jié)合改進(jìn)的算法達(dá)到查詢所需時(shí)間少的要2準(zhǔn)則：6種可能的順序。1)乘車次數(shù)乘車時(shí)間乘車費(fèi)用2)乘車次數(shù)乘車費(fèi)用乘車時(shí)間3)乘車時(shí)間乘車次數(shù)乘車費(fèi)用4)乘車時(shí)間乘車費(fèi)用乘車次數(shù)5)乘車費(fèi)用乘車次數(shù)乘車時(shí)間6)乘車費(fèi)用乘車時(shí)間乘車次數(shù)在本題中，由于網(wǎng)絡(luò)圖結(jié)構(gòu)較復(fù)雜，節(jié)點(diǎn)數(shù)量龐大，簡(jiǎn)單利用Dijkstm算法效果不好，耗時(shí)較長(zhǎng)，并且得到的解可能是理論上的最優(yōu)解，但卻不符合實(shí)際情況。發(fā)現(xiàn)利用一種較為特殊的數(shù)據(jù)結(jié)構(gòu)來(lái)表達(dá)圖時(shí)，利用根據(jù)實(shí)際情況得到的推論，結(jié)合基于改進(jìn)的廣搜算法，可以得到符合實(shí)際的最優(yōu)解。1)數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)體+鏈表U圖2INDEX[J]表示以1為起始點(diǎn)的第一條邊在EDGEJ中存儲(chǔ)的下標(biāo)位置。公交線路可能存在的公共邊，在結(jié)構(gòu)體數(shù)組中首先表現(xiàn)為Bus不同，此外，F(xiàn)ce,BusNum,Time也會(huì)相應(yīng)的不同。這樣起點(diǎn)和終點(diǎn)相同的一條邊會(huì)因?yàn)锽us的不同而作為不同的邊來(lái)處理，但同樣都放到鄰接表中。算法實(shí)現(xiàn)過(guò)程中，根據(jù)不同的準(zhǔn)則只可能去選擇其中某一個(gè)邊。2)推論：C(i?j)表示節(jié)點(diǎn)i到節(jié)點(diǎn)j所用最優(yōu)的乘車次數(shù)或時(shí)間或費(fèi)用。乘車次數(shù)：當(dāng)在j點(diǎn)轉(zhuǎn)乘時(shí)，因?yàn)榇嬖谝淮螕Q車乘車時(shí)間：當(dāng)在j點(diǎn)轉(zhuǎn)乘時(shí)，因?yàn)閾Q乘需要耗時(shí)當(dāng)在j點(diǎn)不轉(zhuǎn)乘時(shí)C(i,j)+CG,k)=C(,k)當(dāng)在j點(diǎn)不轉(zhuǎn)乘時(shí)如果線路是一票制C(ij)+C(j.k)=C(i.k)如果是分段計(jì)價(jià)C(ij)+CG.k)>=C(i.k)3)算法步驟(1):確定矩陣的最初值。以線路為主體，根據(jù)費(fèi)用價(jià)格準(zhǔn)則和節(jié)點(diǎn)間的距離和單位距離的耗時(shí)，可以簡(jiǎn)單的得到同一條線路中的C(i,j)。如果ij不在同一條線路，則C(i.j)賦值為最大值Max;(2):確定兩個(gè)節(jié)點(diǎn)集合A和B,AUB為全；部節(jié)點(diǎn)集合。A中初始節(jié)點(diǎn)為所給節(jié)點(diǎn)Start;(3):根據(jù)確定的準(zhǔn)則和推論，從B中尋找一個(gè)節(jié)點(diǎn)k,其到A中任意節(jié)點(diǎn)的C(i.k)最小，則C(Start,k)=C(i,k).存儲(chǔ)Road(k)=i;k歸入A、B中除去節(jié)點(diǎn)k。如果k!=End,轉(zhuǎn)(3);否則轉(zhuǎn)(4);(4):得到最優(yōu)解即C(Start,k)。用Road(k)及其回溯，可以得到最優(yōu)路徑，結(jié)束；4)問(wèn)題結(jié)果：(以>>表示人們對(duì)線路選擇中各因素的優(yōu)先級(jí))一乘車次數(shù)最少的路線表1)乘車次數(shù)>>乘車費(fèi)用>>乘車時(shí)間起始點(diǎn)點(diǎn)乘車次數(shù)費(fèi)用時(shí)間行車路線2333S1557-L84-S1919-L189-S232233S148-L308-S36-L156-S22表2)乘車次數(shù)>>乘車時(shí)間>>乘車費(fèi)用起始點(diǎn)點(diǎn)乘車次數(shù)時(shí)間費(fèi)用行車路線2333S1557-L84-S1919-L189-S242333S148-L308-S36-L156-S22二乘車費(fèi)用最少的路線表1)乘車費(fèi)用>>乘車時(shí)間>>乘車次數(shù)起始點(diǎn)點(diǎn)費(fèi)用乘車次數(shù)行車路線33S3359-L15-S2903-L485-S133S1557-L84-S1919-L189-S33S971-L13-S2517-L290-S2233S148-L308-S36-L156-S906500125劉永旺09年春數(shù)學(xué)模型與數(shù)學(xué)軟件綜合訓(xùn)練22表2)乘車費(fèi)用>>乘車次數(shù)>>乘車時(shí)間起始點(diǎn)點(diǎn)費(fèi)用乘車次數(shù)時(shí)間行車路線3233S1557-L84-S1919-L189-S322233S148-L308-S36-L156-S22三乘車費(fèi)用最小的路線表1)乘車時(shí)間>>轉(zhuǎn)車次數(shù)>>乘車費(fèi)用起始點(diǎn)點(diǎn)時(shí)]乘車次數(shù)費(fèi)用行車路線33S3359-L15-S2903-L485-S144S1557-L84-S1919-L189-S3186-L91-33S971-L13-S2517-L290-S55S8-L198-S1691-L476-S2085-L17-S609-L328-44S148-L308-S3604-L81-S2361-L156-S33表2)乘車時(shí)間>>乘車費(fèi)用>>乘車次數(shù)起始點(diǎn)日的點(diǎn)時(shí)間費(fèi)用乘車次數(shù)行車路線33S3359-L15-S2903-L485-S144S1557-L84-S1919-1189-53186-L91-33S971-L13-S2517-L290-S55S8-L198-S1691-L476-S2085-L17-44S148-L308-S3604-L81-S2361-L156-S33通過(guò)這次數(shù)學(xué)建模與數(shù)學(xué)軟件綜合訓(xùn)練，不僅使我掌握了部分?jǐn)?shù)學(xué)軟件的使用，特別是像等軟件已經(jīng)有了初步的認(rèn)識(shí)和掌握，還有公式編輯器這個(gè)數(shù)學(xué)軟件也是我新近接觸到的數(shù)學(xué)軟件，通過(guò)使用才發(fā)現(xiàn)這個(gè)軟件在編輯數(shù)學(xué)公式等方面有很大的優(yōu)勢(shì)，也使我認(rèn)識(shí)到自己接觸的知識(shí)面很窄，對(duì)于好多數(shù)學(xué)知識(shí)很欠缺。而另一個(gè)方面我也真正嘗試到了數(shù)學(xué)建模的樂(lè)趣，以前自己因?yàn)檎J(rèn)識(shí)有限，對(duì)數(shù)學(xué)建模根本不了解，現(xiàn)在通過(guò)對(duì)數(shù)學(xué)建模課程的學(xué)習(xí)以及對(duì)數(shù)學(xué)建模的綜合訓(xùn)練，使我對(duì)數(shù)學(xué)建模才有了真正的了解，從理論到實(shí)踐，在整整兩星期的時(shí)間里，可以說(shuō)得是苦多于甜，但是我可以學(xué)到很多很多的東西，同時(shí)也可以鞏固了以前所學(xué)過(guò)的知識(shí)，而且還學(xué)到了很多