數(shù)學建模有關緊急調兵和最佳乘車路線問題

1、數(shù)學模型與數(shù)學軟件綜合訓練論文 訓練題訓練題目：一目：一 緊緊急急調調兵兵問題問題 二二 最佳乘最佳乘車車路路線線 學號：學號： 姓名：姓名：劉永旺 蘭州理工大學計通院信息與計算科學專業(yè) 2009 年春季學期 目目 錄錄 一前言一前言.3 二緊急調兵問題二緊急調兵問題.3 1 論文摘要.3 2 問題重述與分析.3 3 假設與模型.3 3.1 模型假設.3 3.2 模型建立.4 3.3 問題求解.4 三最佳乘車路線三最佳乘車路線.6 1 論文摘要.6 2 問題重述與分析.6 3 假設與模型.6 3.1 模型假設.6 3.2 符號說明.6 3.3 模型的建立.7 3.4 問題的求解.7 四四 總結

2、總結.10 五五 參考文獻參考文獻.11 1 參考文獻一 .11 2 參考文獻二 .11 一前言一前言 在現(xiàn)實生活中我們有許多實際問題需要解決，而怎么去解決這些問題就成為我們要討論的主要問題， 通常采用建立數(shù)學模型的方法，這樣如何合理建立所要解決問題的模型就成了關鍵，所建立的數(shù)學模型 不僅要在模型假設中通過分析研究能得到所要的結果，而且必須具有可行性，通過模型建立能夠最終解 決問題，這是我們建立數(shù)學模型的目的。 在數(shù)學模型的建立過程中分析問題是關鍵，首先應該搞清楚需要解決什么問題，然后從問題入手考 慮通過什么方法用哪些因素能一步得到要求因素，其中會用到我們學過的數(shù)學知識，用合適的建立模型 的方

3、法，如本模型步中用到的單因素模型，逐步回歸模型等模型，通過數(shù)據(jù)擬合相應函數(shù)等方法，通過 函數(shù)分析并結合圖形，判斷優(yōu)化方案，并考慮各組成因素的變化情況，同時考慮各因素的交互效應，這 樣才能建立出合理的數(shù)學模型。在模型建立過程中借助圖表，曲線圖的功能更加直觀，簡要易懂，并對 所建模型作進一步分析和改進，使得所建模型更能反映實際情況。 二緊急調兵問題二緊急調兵問題 1 1 論文摘要論文摘要 由于軍事上的需要，需將甲地 n 名戰(zhàn)斗人員（不包括駕駛員）緊急調運之乙地。但是由于運輸車輛 不足，m 輛車無法保證每個戰(zhàn)斗人員都乘上車。為了使這 n 名戰(zhàn)斗人員以最短的時間到達目的地，必須 得有一部分戰(zhàn)斗人員緊急

4、行軍，這樣就可以保證所有人員同時到達目的地。 關鍵詞：緊急調兵；人行軍；時間最短 2 2 問題重述與分析問題重述與分析 由于戰(zhàn)斗需要，所有人員必須在最短時間里同時到達，才能保證需求。目前是車少人多，所有人不 能同時乘車到達目的地，有一部分人需要行軍前進?，F(xiàn)有 m 輛車，n 人，每輛車可以載 b 人。車輛先運 走一部分行軍速度慢的，到達一定的地方，然后這些人行軍，車輛返回在后面的行軍人中間運走相對行 軍慢的，以此類推，車輛最后運的人員和所有的戰(zhàn)斗人員同時到達目的地。 3 3 假設與模型假設與模型 3.13.1 模型假設模型假設 1) 將這 n 名戰(zhàn)斗人員中最后一個運到乙地算完成任務，以部隊從甲地

5、出發(fā)起，到第 n 名戰(zhàn)斗人員 到達乙地的運輸時間為目標，不考慮先期到達戰(zhàn)斗人員的軍事價值; 2) 車速和人行速均按最大速度計算，不考慮人員勞累和車輛加油問題，也不考慮道路的影響; 3) 戰(zhàn)斗人員上下車的時間可忽略不計; 4) 設每輛車載 b 人（不包括駕駛員） ；車速是人行軍速度的 k 倍（k1）; 5) 設 j 是大于 1 的整數(shù)，如當 j=2 時，說明 n 名戰(zhàn)斗人員一分為二，一半乘車，一半行軍，到了 中途某一點，讓乘車人員下車行軍前進，車輛返回接另一部分人員，最后和第一批人員同時到 達目的地。 3.23.2 模型建立模型建立 設甲地到乙地距離為 1 個長度單位，人行軍速度為 1 個速度單

6、位，車速為 k。 設最優(yōu)方案中人行軍路程為 y（因同時到達，每個人行軍路程都是 y） ，則每個人乘車路程為 1- y，0y1。 最優(yōu)方案中人與車同時到達乙地，所用時間相同，所以 y+（1-y）=, (1) 21x k 因為 n=mbj，所以車向前時，mb 個人乘車，車向后開時，無人乘車；而車向前開的時間為 x/k，向后開 的時間為（x-1）/k，所以在最優(yōu)調運方案中，平均乘車人數(shù)為 : (2) 121 (0*)/ 21 xxxxmb mb kkkx 所以在最有方案中最小平均速度的最大值上界（在車和人同時到達乙地的方案可行時）為： (3) 1(1) (*)/11 2121(21)(21) xmb

7、xmbkkx knnxmb xxnxxj 由（3）式可見平均速度大于人行軍速度，且 k 越大平均速度越大，j 越大，平均速度越小，顯然是合理 的。 而根據(jù)（1）式，最優(yōu)方案的平均速度為： (4)1 (21)21 k xjx (k-1)x 由此可得到關于 x,y 的方程組 1 (21)1 (1) k xjky (k-1)x 1 (21)21 k xjx (k-1)x 解次方程組得：2x-2=(k-1)y, (5) (1) 12 kj x kj (6) 2(1) 12 j y kj 由（6）式可見，其余條件相同情況下車速越 快，戰(zhàn)斗人員行軍路程越短，這也說明公式是正確的。 在達最大速度情況下，人行

8、軍路程與車行軍路程均已求出，下一步我們考慮實現(xiàn)這一上界的方案。 顯然使平均速度達（3）式的任一可行方案均為最優(yōu)方案，但其中某方案使人員上下車次數(shù)越少，車輛調 整方向次數(shù)越少，越方便，實際效果越好。 3.33.3 問題求解問題求解 1）開始讓車滿載，車和人同時出發(fā)； 2）當車開到 1-y 地方，讓車商的戰(zhàn)斗人員下車行軍前進，車輛往回開； 3）當返回車輛遇上正在行軍的戰(zhàn)斗人員時，讓其中任意 mb 個人乘車前進，余下的人繼續(xù)行軍前進； 4）當車遇到正在前面行軍的戰(zhàn)斗人員時，停車，并讓車上 mb 個人下車與這一批人一起行軍前進，車輛 再返回； 5）如此直至最后 mb 個戰(zhàn)斗人員也上車，并與其他戰(zhàn)斗人員

9、共同到達乙地。 這樣在行進的過程中，一前一后的兩個集團，有時共（j-1）mb 個人在行軍前進，mb 個人在這兩個 集團之間乘車由后往前趕。而當車輛返回時，兩大集團共計 n 個人在行軍前進。隨著時間的推移，第一 集團每次增加 mb 個人，第二集團每次減少 mb 個人，直至第二集團完全消失，第一集團達（j-1）mb 人， 與最后乘車的 mb 人同時到達乙地。 由于 n=mbj，顯然這一方案是可行的。則只需證明此方案是最優(yōu)的即可： 前已計算最佳方案中每個人應步行的距離為 y，應乘車前進的距離是 1-y。因每個人不是乘車就是行 軍前進，故只要乘車距離達到 1-y，即達到了理想的平均速度。由方案可知，第

10、一批乘車人員恰好乘車前 進 1-y，余下行軍，路程為 y，應y+(1-y)/k時到達。第二批乘車人后來趕上第一批乘車人，表明在出發(fā)至 相遇這一段時間內平均速度相同。因行軍速度與車速一定，故一定乘車時間相同，行軍時間相同 ，因而 乘車路程也為 1-y，加上后來行軍路程，總行軍路程為 y，故實現(xiàn)了最優(yōu)方案。類似的，前（j-1）批乘車 人員都行軍 y 乘車路程為（1-y） 。 最后一批乘車人在乘車時，車向前走了（j-1） （1-y） ，第一次車輛后退的距離為： 1 1 (1)(1) * 11 y y ky k k kk 與最后一批人相遇時共后退： (1)(1)(1) 1 jky k 則實際前進了:

11、(1)(1)(1) (1)(1) 1 1 (1)(1)(1) 1 2 (1)(1) 1 jy k jy k k jy k jy k 將 y 用（6）式代入，得車輛在與最后一批人相遇時，離甲地距離為： 2(1)2 (1)(1) 121 12 (1) 121 12 (1)() 121 2(1) 12 j j kj k k j kj k k j kj k j kj y 所以最后一批人乘車距離也是 1-y，故故 n 個人與車同時到達乙地，方案確是最優(yōu)的。 三最佳乘車路線三最佳乘車路線 1 1 論文摘要論文摘要 利用城市公交網(wǎng)構建了基于公交站點的網(wǎng)絡圖。把各個站點看作圖的節(jié)點，站點間的線路看作圖的 邊，

12、站點間到達所需的花費作為邊的權值。同時把公汽、地鐵、看作兩種不同的交通方式來處理。公交 線路選擇的數(shù)學模型是一般圖的最短路問題，利用改進的基于廣度優(yōu)先搜索算法，按照乘車次數(shù)、乘車 費用、乘車時間不同順序準則給出了各種最優(yōu)線路方案。 關鍵詞：網(wǎng)絡圖 換乘 公共站點 最短路徑問題 2 2 問題重述與分析問題重述與分析 隨著社會的高速發(fā)展，城市建設也越來越繁華，因此，出門乘車路線的最優(yōu)選擇便成為當代城市人 必須面對的一個問題。針對這一問題，建立最佳乘車路線模型系統(tǒng)供人們參考，以滿足查詢者對線路的 各種不同需求。該系統(tǒng)核心是線路選擇的數(shù)學模型與算法。本文擬解決如下問題： 1、僅考慮公汽線路，給出任意兩

13、公汽站點之間線路選擇問題的一般數(shù)學模型與算法。根據(jù)數(shù)據(jù)，利用模 型與算法，求出以下 6 對起始站終到站的最佳路線。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676 2、假設又知道所有站點之間的步行時間，給出任意兩站點之間線路選擇問題的數(shù)學模型。 3 3 假設與模型假設與模型 3.13.1 模型假設模型假設 1）在問題一，只在任意兩條線路的公共站點進行公汽換乘； 2）對轉乘次數(shù)無限定； 3）如果下行線是上行線的原路返回，不考慮上行和下行線路間進行換乘； 4）環(huán)行線路

14、是雙向環(huán)路 5）線路的換乘中，等車時間 = 平均耗時 3.23.2 符號說明符號說明 Start : 起始站點 End: 目的站點 Fee: 乘車費用 BusNum: 乘車次數(shù) Time: 乘車時間 C(i,j) : i 站點到 j 站點的權值，表示乘車費用或者乘車時間或乘車次數(shù)，也可表示反映乘車費用和時間及 乘車次數(shù)的綜合信息值 EDGE:結構體數(shù)組，存儲網(wǎng)絡圖中所有邊的信息 Road:存儲路徑數(shù)組 Roadi: 在最優(yōu)路線 i 節(jié)點的前驅 Max:理論上花費最大值，賦值 MyMAX 3.33.3 模型的建立模型的建立 本題要求在某城市公交網(wǎng)絡中, 從給出的起點(Start)出發(fā),根據(jù)對線路

15、的不同選擇準則(乘車時間最短或 轉乘次數(shù)最少或乘車費用最低)，找出一條到達目的地(End)的最優(yōu)線路。 定義一 把站點 i 到站點 j 的乘車時間或乘車次數(shù)或乘車費用稱做 i 到 j 的花費。 定義二 設有一個有限點集 1,2, ,Vn 其中1,2, ,n 稱為節(jié)點（頂點） ；弧集 ( , )|,Ai jiV jV 其中( , ) i j 稱為從節(jié)點i到節(jié)點 j 直接連接的?。ɑ蛴邢蜻叄?；由點集V和弧集 A 組成的圖稱為有向圖，記為 ( ,)DV A 。一條路是指由節(jié)點組成的有限序列 12 , , p i ii ，其中 1 ( ,)(1,2,1) kk i iA kp 。當 2p ,且 1p

16、 ii 時，這條路便稱為回路。不含回路的圖叫做非循環(huán) 圖1； 圖公交網(wǎng)絡示意圖（非真實地理位置圖） 在公交網(wǎng)中,我們把每個站點看作圖中的一個節(jié)點，把站點之間的線路看作圖中對應節(jié)點的邊，如圖 所示，把各個站點之間所必需的花費看作對應邊上的權(權0)。公交網(wǎng)就轉化成圖論中的加權圖。因為 存在環(huán)行線路，在本題中，此題將圖轉化成為一般圖的圖論問題，即在給定的加權一般圖中，從起點 (Start)出發(fā)，沿一條線路到達目的地(End)，使花費最少。因此，該問題的數(shù)學模型是含有回路的一般有向 圖的最短路！ 3.43.4 問題的求解問題的求解 僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算

17、法，求出 6 對起始站終 到站之間的最佳路線。 1.問題分析： 最佳路線的選擇，首先設置一個統(tǒng)一的準則。在一般網(wǎng)絡圖中，可以利用普通 Dijkstra 算法進行最短 距離求解，但公交網(wǎng)絡圖節(jié)點數(shù)目龐大，運算耗時過長，且運算所得結果可能不符合人們的實際需求， 所以不宜采用此算法2。在本題中，采用了良好的數(shù)據(jù)結構并結合改進的算法達到查詢所需時間少的要 求。 2 準則： 6 種可能的順序。 1)乘車次數(shù) 乘車時間 乘車費用 2)乘車次數(shù) 乘車費用 乘車時間 3)乘車時間 乘車次數(shù) 乘車費用 4）乘車時間 乘車費用 乘車次數(shù) 5)乘車費用 乘車次數(shù) 乘車時間 6)乘車費用 乘車時間 乘車次數(shù) 3 算法

18、： 在本題中，由于網(wǎng)絡圖結構較復雜，節(jié)點數(shù)量龐大，簡單利用 Dijkstra 算法效果不好，耗時較長，并 且得到的解可能是理論上的最優(yōu)解，但卻不符合實際情況。 發(fā)現(xiàn)利用一種較為特殊的數(shù)據(jù)結構來表達圖 時，利用根據(jù)實際情況得到的推論，結合基于改進的廣搜算法，可以得到符合實際的最優(yōu)解。 1)數(shù)據(jù)結構: 結構體 + 鏈表 Fee BusNum Fee: 價錢 BusNum: 轉乘次數(shù) Time: 耗費時間 u: 邊的結點 Bus: 線路 nxt: 在此線路中的 u 下一個節(jié)點 1-1 邊結構體 edge 圖 2 INDEXI表示以 I 為起始點的第一條邊在 EDGE中存儲的下標位置。 公交線路可能存

19、在的公共邊，在結構體數(shù)組中首先表現(xiàn)為 Bus 不同，此外，F(xiàn)ee,BusNum,Time 也會相 應的不同。這樣起點和終點相同的一條邊會因為 Bus 的不同而作為不同的邊來處理，但同樣都放到鄰接 表中。算法實現(xiàn)過程中，根據(jù)不同的準則只可能去選擇其中某一個邊。 2) 推論: C(i,j)+C(j,k) = C(i,k) C(i,j) 表示節(jié)點 i 到節(jié)點 j 所用最優(yōu)的乘車次數(shù)或時間或費用。 證明: C(i,j)=M C(j,k)=N 乘車次數(shù): 當在 j 點轉乘時, 因為存在一次換車 M+N = C(i,j)+C(j,k) C(i,k) 當在 j 點不轉乘時, C(i,j)+C(j,k) =

20、C(i,k) 乘車時間: 當在 j 點轉乘時, 因為換乘需要耗時 C(i,j)+C(j,k) C(i,k) 當在 j 點不轉乘時 C(i,j)+C(j,k) = C(i,k) 乘車費用: 當在 j 點轉乘時, 因為換車要重新上車,肯定要重新付費， C(i,j)+C(j,k) = C(i,k) 當在 j 點不轉乘時 如果線路是一票制 C(i,j)+C(j,k) = C(i,k) 如果是分段計價 C(i,j)+C(j,k) = C(i,k) 證明完畢。 根據(jù)推論,可以得到 C(i,k)的最小值,即得到最優(yōu)解。 3) 算法步驟 編程實現(xiàn)了對問題的求解。 算法的過程即是 C(i,j)矩陣的實現(xiàn)。 （1

21、）: 確定矩陣的最初值。以線路為主體，根據(jù)費用價格準則和節(jié)點間的距離和單位距離的耗時，可以 簡單的得到同一條線路中的 C(i,j)。如果 i,j 不在同一條線路，則 C(i,j)賦值為最大值 Max； （2）: 確定兩個節(jié)點集合 A 和 B，A U B 為全；部節(jié)點集合。 A 中初始節(jié)點為所給節(jié)點 Start； （3）: 根據(jù)確定的準則和推論，從 B 中尋找一個節(jié)點 k，其到 A 中任意節(jié)點的 C(i,k) 最小，則 C(Start,k) =C(i,k).存儲 Road(k) = i； k 歸入 A、B 中除去節(jié)點 k。如果 k != End,轉（3） ； 否則轉（4） ； （4）:得到最優(yōu)解

22、即 C(Start,k)。用 Road(k)及其回溯，可以得到最優(yōu)路徑，結束； 4） 問題結果：（以 表示人們對線路選擇中各因素的優(yōu)先級） 一 乘車次數(shù)最少的路線 Time U Bus Nxt 表 1）乘車次數(shù) 乘車費用 乘車時間 起始 點 目的 點 乘車 次數(shù) 費 用 時 間 行車路線 S3359S182823106S3359-L436-S1784-L167-S1828 S1557S048133111S1557-L84-S1919-L189-S3186-L460-S481 S0971S048523139S971-L13-S2322-L417-S485 S0008S00732288S8-L35

23、5-S2263-L345-S73 S0148S048533111S148-L308-S36-L156-S2210-L417-S485 S0087S36762270S87-L454-S3496-L209-S3676 表 2）乘車次數(shù) 乘車時間 乘車費用 起始 點 目的 點 乘車 次數(shù) 時 間 費 用 行車路線 S3359S182821063S3359-L436-S1784-L167-S1828 S1557S048131113S1557-L84-S1919-L189-S3186-L460-S481 S0971S048521334S971-L13-S2184-L417-S485 S0008S0073

24、2823S8-L159-S491-L459-S73 S0148S048531113S148-L308-S36-L156-S2210-L417-S485 S0087S36762702S87-L454-S3496-L209-S3676 二 乘車費用最少的路線 表 1） 乘車費用 乘車時間 乘車次數(shù) 起始 點 目的 點 費 用 時 間 乘車 次數(shù) 行車路線 S3359S18283693S3359-L15-S2903-L485-S1784-L167-S1828 S1557S048131113S1557-L84-S1919-L189-S3186-L460-S481 S0971S048531083S971

25、-L13-S2517-L290-S2159-L469-S485 S0008S00732882S8-L355-S2263-L345-S73 S0148S048531113S148-L308-S36-L156-S2210-L417-S485 S0087S36762702S87-L454-S3496-L209-S3676 表 2） 乘車費用 乘車次數(shù) 乘車時間 起始 點 目的 點 費 用 乘車 次數(shù) 時 間 行車路線 S3359S182832106S3359-L436-S1784-L167-S1828 S1557S048133111S1557-L84-S1919-L189-S3186-L460-S4

26、81 S0971S048532139S971-L13-S2322-L417-S485 S0008S00732288S8-L355-S2263-L345-S73 S0148S048533111S148-L308-S36-L156-S2210-L417-S485 S0087S36762270S87-L454-S3496-L209-S3676 三 乘車費用最小的路線 表 1） 乘車時間 轉車次數(shù) 乘車費用 起始 點 目的 點 時 間 乘車 次數(shù) 費 用 行車路線 S3359S18286933S3359-L15-S2903-L485-S1784-L167-S1828 S1557S048110444S1

27、557-L84-S1919-L189-S3186-L91-S902-L254-S481 S0971S048510833S971-L13-S2517-L290-S2159-L469-S485 S0008S00736455 S8-L198-S1691-L476-S2085-L17-S609-L328-S525- L103-S73 S0148S048510744S148-L308-S3604-L81-S2361-L156-S2210-L417-S485 S0087S36765133S87-L206-S88-L231-S427-L97-S3676 表 2） 乘車時間 乘車費用 乘車次數(shù) 起始 點 目的 點 時 間 費 用 乘車 次數(shù) 行車路線 S3359S18286933S3359-L15-S2903-L485-S1784-L167-S1828 S1557S048110444S1557-L84-S1919-L189-S3186-L91-S902-L254-S481 S0971S048510833S971-L13-S2517-L290-S2159-L469-S485 S0008S00736455 S8-L198-S1691-L476-S2085-L17-S609-L328-S