2015年五一數(shù)學(xué)建模a題不確定性下的最短路徑問題--cumt賴增強(qiáng)

1、2015 年暑期數(shù)學(xué)建模培訓(xùn)第一次模擬 年暑期數(shù)學(xué)建模培訓(xùn)第一次模擬承諾書 承諾書我們仔細(xì)閱讀了數(shù)學(xué)建模聯(lián)賽的競賽規(guī)則。我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與本隊(duì)以外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其它公開的資料（包括網(wǎng)上查到的資料） ，必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭

2、重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們愿意承擔(dān)由此引起的一切后果。我們授權(quán)數(shù)學(xué)建模聯(lián)賽賽組委會，可將我們的論文以任何形式進(jìn)行公開展示（包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等） 。我們參賽選擇的題號為（從 A/B/C 中選擇一項(xiàng)填寫）： 我們的參賽報(bào)名號為： 參賽組別（研究生或本科或?qū)？疲罕究扑鶎賹W(xué)校（請?zhí)顚懲暾娜┲袊V業(yè)大學(xué)南湖校區(qū)參賽隊(duì)員 (

3、打印并簽名) ：1. 賴增強(qiáng)2. 蘭衛(wèi)旗3. 李康杰日期：2015 年 8 月 11 日獲獎(jiǎng)證書郵寄地址：中國礦業(yè)大學(xué)南湖校區(qū)桃 4B5032 郵政編碼：221116收件人姓名：賴增強(qiáng) 聯(lián)系電話：183612308561不確定條件下的最優(yōu)路徑問題摘要本文針對如何在復(fù)雜的交通環(huán)境下尋找一條可靠、快速、安全的最優(yōu)路徑的問題，考慮到交通堵塞、惡劣天氣、路途成本等不確定因素對司機(jī)路徑選

4、擇的影響，建立多個(gè)不確定條件下的最優(yōu)路徑模型。 對于問題一，我們在各個(gè)路段所用時(shí)間服從正態(tài)分布 N(μ，δ2)的基礎(chǔ)上,建立了在不確定條件下求最短路的 NP 模型，給每個(gè)路段設(shè)定一個(gè)預(yù)留到達(dá)的時(shí)間 t，為了盡可能準(zhǔn)確的到達(dá)目的地，選取 95%的概率，滿足 P{T≤t}?95%,那么最優(yōu)路徑的定義就是預(yù)留時(shí)間最小的那個(gè)路徑，將其轉(zhuǎn)換為標(biāo)準(zhǔn)的正態(tài)分 布，通過標(biāo)準(zhǔn)的正態(tài)分布得到了在不確定性條件下車輛從起點(diǎn)到終點(diǎn)預(yù)留時(shí)間的數(shù)學(xué)表達(dá)式：t=μ+

5、δ。計(jì)算得對應(yīng)的 t（繞城）=34.645min，t（市區(qū)） Φ ? 1=54.675min，那么最優(yōu)路徑為繞城快速路。對于問題二，在第一問定義的基礎(chǔ)上進(jìn)一步引入 Bool 系數(shù) ,在搜集得 β(a,k)到的具體的交通網(wǎng)絡(luò)中，建立了一個(gè)從起點(diǎn)到終點(diǎn)路徑為 的正 ∑na = 1β(a,k)Tlinka態(tài)分布，通過求最小預(yù)留時(shí)間 t(min)=E[ ]+,得出最優(yōu)路徑 Tpathk Φ ? 1 Var[Tpathk ]的算法。其中 E E[

6、 ]， = [TpathK ] = ∑na = 1β(a,k) Tlinka Var[Tpathk ] ∑na = 1β(a,k)Var[Tlink a，但 的根式不具有線性可加性。不能用經(jīng)典的 dijkstra 算法求解。 ] Var[Tpathk ]對此采用基于雙目標(biāo)規(guī)劃的思路，利用第 K 短路徑算法，分別對 E[ ]， Tpathk Var[,運(yùn)用 matlab 編程，找出各自前十條最短路徑。之后在其并集中找出最 Tpat

7、hk ]優(yōu)路徑：V1→V3→V4→V8。由此建立了求最短路的 NPK 模型。最后從時(shí)間的漸進(jìn)性態(tài)上分析模型的復(fù)雜性和收斂性。對于問題三，我們只考慮各路段空間上的相關(guān)性，并用概率論中的協(xié)方差 來表示這種耦合關(guān)系，建立了 NPK 模型。得出可靠時(shí)間的數(shù)學(xué)表達(dá)式 t= E+ ；求解得最優(yōu)路徑： [TpathK ] Φ ? 1(ρ) ∑na = 1δ(a,k)Var[Tlinka + ∑na = 2cov(a ? 1,a)V1->V