暑期集訓(xùn)1-乘公交看奧運(yùn)2007B

數(shù)學(xué)建模競(jìng)賽案例選講

—乘公交看奧運(yùn)2007B主講：費(fèi)文龍答疑：feiwl@126.com課件：sxjmnuist@126.com,密碼nuist2011數(shù)學(xué)建模暑期集訓(xùn)2007B題目：我國(guó)人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題。針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。請(qǐng)你們解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站→終到站之間的最佳路線（要有清晰的評(píng)價(jià)說明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同時(shí)考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。2023/1/12數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com【附錄1】基本參數(shù)設(shè)定相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)：3分鐘相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)：2.5分鐘公汽換乘公汽平均耗時(shí)：5分鐘(其中步行時(shí)間2分鐘)地鐵換乘地鐵平均耗時(shí)：4分鐘(其中步行時(shí)間2分鐘)地鐵換乘公汽平均耗時(shí)：7分鐘(其中步行時(shí)間4分鐘)公汽換乘地鐵平均耗時(shí)：6分鐘(其中步行時(shí)間4分鐘)公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種，標(biāo)記于線路后；其中分段計(jì)價(jià)的票價(jià)為：0～20站：1元；21～40站：2元；40站以上：3元地鐵票價(jià)：3元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡(jiǎn)化問題而作的假設(shè)，未必與實(shí)際數(shù)據(jù)完全吻合。

【附錄2】公交線路及相關(guān)信息（見數(shù)據(jù)文件B2007data.rar）2023/1/12數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.comCUMCM-2007B賽題分析

應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模-----建模及建模競(jìng)賽的意義

競(jìng)賽評(píng)閱標(biāo)準(zhǔn)-----一般原則及主要問題

優(yōu)化模型的創(chuàng)新-----2007B題分析數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12數(shù)學(xué)建模：實(shí)際與數(shù)學(xué)之間的橋梁實(shí)際問題數(shù)學(xué)MathematicalModeling

現(xiàn)實(shí)對(duì)象的信息數(shù)學(xué)模型現(xiàn)實(shí)對(duì)象的解答數(shù)學(xué)模型的解答表述求解解釋驗(yàn)證(歸納)(演繹)數(shù)學(xué)建模的全過程數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12學(xué)生歡迎：“一次參賽，終身受益”研究生導(dǎo)師們的認(rèn)同企業(yè)界的認(rèn)同／贊助教育改革同行的認(rèn)同：“成功范例”國(guó)際同行的認(rèn)同競(jìng)賽的反響數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12IBM中國(guó)研究中心-招聘條件Positiontitle:BusinessOptimization(BJ)

1．Backgroundinindustrialengineering,operationsresearch,mathematics,ArtificialIntelligence,managementscienceetc.

2.Knowledgeinnetworkdesign,jobscheduling,dataanalysis,simulationandoptimization

3.Awardinmathematicalcontestinmodelingisaplus

4.Experienceinindustryisaplus

5.Experienceineclipseorprogrammingmodel/architecturedesignisaplus

--Feb.18,2006,/cn/ibm/crl/careers/condition.shtml競(jìng)賽的反響（一例）數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12CUMCM評(píng)閱標(biāo)準(zhǔn)：清晰性：摘要應(yīng)理解為詳細(xì)摘要，提綱挈領(lǐng)

表達(dá)嚴(yán)謹(jǐn)、簡(jiǎn)捷，思路清新

格式符合規(guī)范，嚴(yán)禁暴露身份創(chuàng)造性：特別欣賞獨(dú)樹一幟、標(biāo)新立異，但要合理假設(shè)的合理性，建模的創(chuàng)造性，結(jié)果的正確性，表述的清晰性。正確性：不強(qiáng)調(diào)與“參考答案”的一致性和結(jié)果的精度；好方法的結(jié)果一般比較好；但不一定是最好的合理性：關(guān)鍵假設(shè)；不欣賞羅列大量無關(guān)緊要的假設(shè)競(jìng)賽評(píng)閱一般原則及主要問題數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12CUMCM評(píng)閱標(biāo)準(zhǔn):一些常見問題有的論文過于簡(jiǎn)單，該交代的內(nèi)容省略了，難以看懂有的隊(duì)羅列一系列假設(shè)或模型，又不作比較、評(píng)價(jià)，希望碰上“參考答案”或“評(píng)閱思路”，弄巧成拙數(shù)學(xué)模型最好明確、合理、簡(jiǎn)潔：有些論文不給出明確的模型，只是根據(jù)賽題的情況，實(shí)際上是用“湊”的方法給出結(jié)果，雖然結(jié)果大致是對(duì)的，沒有一般性，不是數(shù)學(xué)建模的正確思路。有的論文參考文獻(xiàn)不全，或引用他人結(jié)果不作交代數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12從論文評(píng)閱看學(xué)生參加競(jìng)賽中的問題

吃透題意方面不足，沒有抓住和解決主要問題；

就事論事，形成數(shù)學(xué)模型的意識(shí)和能力欠缺；

對(duì)所用方法一知半解，不管具體條件，套用現(xiàn)成的方法，導(dǎo)致錯(cuò)誤；

對(duì)結(jié)果的分析不夠，怎樣符合實(shí)際考慮不周；

寫作方面的問題(摘要、簡(jiǎn)明、優(yōu)缺點(diǎn)、參考文獻(xiàn));

隊(duì)員之間合作精神差，孤軍奮戰(zhàn)；依賴心理重，甚至違紀(jì)（指導(dǎo)教師、網(wǎng)絡(luò)）。數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12參加競(jìng)賽前的準(zhǔn)備

了解競(jìng)賽章程等相關(guān)信息；

掌握數(shù)學(xué)建模的基本方法（學(xué)過“數(shù)學(xué)模型”或“數(shù)學(xué)實(shí)驗(yàn)”課最好，自學(xué)一些基本內(nèi)容也可以）；

掌握基本的數(shù)學(xué)軟件（Matlab/Mathematica；LINGO；如能掌握SAS統(tǒng)計(jì)軟件更好）；

訓(xùn)練規(guī)范的科技論文寫作/表達(dá)能力(摘要、正文、優(yōu)缺點(diǎn)、參考文獻(xiàn)及引用等);

試做幾道以前的賽題；培養(yǎng)合作精神。數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12

優(yōu)化問題三要素：決策變量；目標(biāo)函數(shù)；約束條件約束條件決策變量?jī)?yōu)化問題的一般形式目標(biāo)函數(shù)有人統(tǒng)計(jì)：

優(yōu)化問題占CUMCM賽題的一半以上（1/3~2/3）創(chuàng)新能力培養(yǎng)-----2007B分析數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12建模時(shí)需要注意的幾個(gè)基本問題

1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個(gè)數(shù)如：盡量少使用絕對(duì)值、符號(hào)函數(shù)、多個(gè)變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個(gè)數(shù)（如x/y<5改為x<5y）4、合理設(shè)定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級(jí)要適當(dāng)(如小于103)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12優(yōu)化建模如何創(chuàng)新？

方法1：大膽創(chuàng)新，別出心裁----采用有特色的目標(biāo)函數(shù)、約束條件等----你用非線性規(guī)劃，我用線性規(guī)劃----你用整數(shù)/離散規(guī)劃，我用連續(xù)規(guī)劃/網(wǎng)絡(luò)優(yōu)化----……

方法2：細(xì)致入微，滴水不漏----對(duì)目標(biāo)函數(shù)、約束條件處理特別細(xì)致----有算法設(shè)計(jì)和分析，不僅僅是簡(jiǎn)單套用軟件----敏感性分析詳細(xì)/全面----……數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/122007B命題背景奧運(yùn)相關(guān)的題目：(時(shí)代特性,社會(huì)關(guān)注）讓運(yùn)動(dòng)員及時(shí)到達(dá)場(chǎng)館（車輛調(diào)度，路徑安排等）應(yīng)急管理（緊急疏散，應(yīng)急調(diào)度等）賽程安排（單一項(xiàng)目，多個(gè)項(xiàng)目）成績(jī)排名（如循環(huán)賽，體操或跳水等）技術(shù)類，如“劉翔的運(yùn)動(dòng)鞋”乘公交，看奧運(yùn)：原名“自動(dòng)問路機(jī)”方沛辰（吉大），吳孟達(dá)（國(guó)防科大）提出原擬作乙組題，似乎難度太大數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12命題背景定位：公交路線選擇（查詢）模型與算法如何給數(shù)據(jù)？抽象數(shù)據(jù)／實(shí)際數(shù)據(jù)？（減小規(guī)模，不給地理信息）貌似簡(jiǎn)單，實(shí)則不然數(shù)據(jù)處理（轉(zhuǎn)換）方面有一定難度換乘次數(shù)多時(shí)簡(jiǎn)單搜索不易（計(jì)算復(fù)雜度高）換乘時(shí)間／步行時(shí)間等需要考慮周全標(biāo)準(zhǔn)的最短路算法（如Dijkstra算法）并不適用數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12乘公交，看奧運(yùn)公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)：核心是線路選擇的模型與算法應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求1:僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法2:同時(shí)考慮公汽與地鐵線路，解決以上問題3:假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12

【附錄1】基本參數(shù)設(shè)定相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)：3分鐘相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)：2.5分鐘公汽換乘公汽平均耗時(shí)：5分鐘(其中步行時(shí)間2分鐘)地鐵換乘地鐵平均耗時(shí)：4分鐘(其中步行時(shí)間2分鐘)地鐵換乘公汽平均耗時(shí)：7分鐘(其中步行時(shí)間4分鐘)公汽換乘地鐵平均耗時(shí)：6分鐘(其中步行時(shí)間4分鐘)公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種，標(biāo)記于線路后；其中分段計(jì)價(jià)的票價(jià)為：0～20站：1元；21～40站：2元；40站以上：3元地鐵票價(jià)：3元（無論地鐵線路間是否換乘）推論：換乘公汽等待３分鐘，換乘地鐵等待２分鐘

【附錄2】公交線路及相關(guān)信息（見數(shù)據(jù)文件）數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12線路數(shù)據(jù)中的問題線路數(shù)據(jù)中的異?；虿幻鞔_之處，同學(xué)可根據(jù)自己的理解作出假設(shè)和處理，一般不會(huì)影響實(shí)例的計(jì)算結(jié)果個(gè)別線路相鄰站點(diǎn)名相同，可去掉其中一點(diǎn)或不作處理等L406未標(biāo)明是環(huán)線，是否將其當(dāng)作環(huán)線處理均可L290標(biāo)明是環(huán)線，但首尾站點(diǎn)分別為1477與1479，可將所有線路中1477與1479統(tǒng)一為1477后計(jì)算。同學(xué)也可以按照各自認(rèn)為合理的方式處理，包括不當(dāng)作環(huán)線，或?qū)?479改為1477，或在1479后增加1477，等等如果在假設(shè)中有明確約定，則環(huán)線單向或雙向發(fā)車均應(yīng)認(rèn)可（按單向發(fā)車作假設(shè)，計(jì)算結(jié)果可能差些）

數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12對(duì)通過地鐵換乘的理解“假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過地鐵站換乘(無需支付地鐵費(fèi))”

步行：公汽站地鐵站（通道）公汽站換乘耗時(shí)11min：步行4+4=8min;等車3min第１問（只考慮公汽）：可不考慮以上換乘有同學(xué)也考慮了如上換乘，只是不坐地鐵，應(yīng)該也可以此樣處理時(shí)，第１問和第２問的難度相近數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12模型的目標(biāo)多目標(biāo)優(yōu)化問題（至少考慮三方面）換乘次數(shù)最少(N)、費(fèi)用最省(M)、時(shí)間最短(T)從該問題的實(shí)際背景來看，加權(quán)不太合適不少同學(xué)用層次分析法確定權(quán)不少同學(xué)計(jì)算時(shí)間的價(jià)值（平均收入／工作時(shí)間）不同目標(biāo)組合的模型三個(gè)目標(biāo)按優(yōu)先級(jí)排序，組合成六個(gè)模型也可將某些目標(biāo)作為約束數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12多數(shù)隊(duì)僅采用搜索法（70-80%?）直達(dá)；一次換乘；二次換乘；…ststst求出所有線路；評(píng)價(jià)其目標(biāo)(容易計(jì)算)；選優(yōu)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12多數(shù)隊(duì)僅采用搜索法總體來看，技術(shù)含量較低（基本上是枚舉）幾乎沒有建模，完全只有算法實(shí)現(xiàn)，算法也沒什么創(chuàng)新一般只考慮不超過兩次換乘不少文章引用參考文獻(xiàn)作為依據(jù)，實(shí)用中似乎夠用

題目難度大大降低，模型不夠一般換乘作為了第一目標(biāo)，或作為一個(gè)最重要的約束任意次換乘時(shí)算法復(fù)雜度提高，難以處理結(jié)果不佳（如：從省時(shí)考慮，有些需３－４次換乘）數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12圖論模型與最短路算法用圖論做的隊(duì)也不少，但往往考慮不周弧上賦權(quán)方式交代不清套用Dijkstra或Floyd-Warshall算法，卻不清楚其原理及適用的問題需要建立一個(gè)帶權(quán)有向圖，節(jié)點(diǎn)表示站點(diǎn)，有向弧表示前一站點(diǎn)能夠直達(dá)后一站點(diǎn)，弧上的權(quán)表示前一站點(diǎn)直達(dá)后一站點(diǎn)所需付出的代價(jià)(時(shí)間或費(fèi)用)圖（網(wǎng)絡(luò)）如何描述和表示？基本要素：節(jié)點(diǎn)，有向弧（邊），弧上賦權(quán)鄰接矩陣；關(guān)聯(lián)矩陣（數(shù)學(xué)上處理方便，存儲(chǔ)量較大）鏈表（存儲(chǔ)量較小，計(jì)算機(jī)上處理方便）數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12關(guān)聯(lián)矩陣(IncidenceMatrix)表示法在線路選擇問題中，當(dāng)從i可直達(dá)j時(shí)，定義弧(i,j)；其上的權(quán)可為１或成本(時(shí)間或費(fèi)用)；多重弧可只保留一條（弧上的權(quán)可取最小的成本，如時(shí)間或費(fèi)用）G=(V，A)是一個(gè)簡(jiǎn)單有向圖；|V|=n，|A|=m

重要數(shù)學(xué)性質(zhì)：關(guān)聯(lián)矩陣是全幺模矩陣圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個(gè)的矩陣，即數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12鄰接矩陣(AdjacencyMatrix)表示法圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個(gè)的0-1矩陣，即在線路選擇問題中，當(dāng)從i可直達(dá)j時(shí)，定義弧(i,j)；其上的權(quán)可為１或成本(時(shí)間或費(fèi)用)G=(V，A)是一個(gè)簡(jiǎn)單有向圖；|V|=n，|A|=m

有向圖的“傳遞閉包算法”(可用于一般二元關(guān)系)權(quán)取0-1時(shí)，C(0)=C可稱為直達(dá)矩陣

；C(1)=C*C

為１次可達(dá)矩陣；C(2)=C(1)*C

為2次可達(dá)矩陣；……數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12鏈表（鄰接表）表示法

122345283904602403053036470單向鏈表(指針數(shù)組)

A(1)={2,3}A(2)={4}A(3)={2}A(4)={3,5}A(5)={3,4}12345數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12Dijkstra算法（標(biāo)號(hào)算法，1959）STEP1.如果S=V,則uj為節(jié)點(diǎn)s到節(jié)點(diǎn)j的最短路路長(zhǎng)(最短路可以通過數(shù)組pred所記錄的信息反向追蹤獲得),結(jié)束.否則繼續(xù).STEP0.(初始化)令S=，=V，；對(duì)V中的頂點(diǎn)j(js)令初始距離標(biāo)號(hào).

STEP2.從中找到距離標(biāo)號(hào)最小的節(jié)點(diǎn)i，把它從刪除，加入S.對(duì)于所有從i出發(fā)的弧,若，則令

轉(zhuǎn)STEP1.特點(diǎn)：1.算法求出從源點(diǎn)s到所有點(diǎn)的最短路長(zhǎng)2.每點(diǎn)給一對(duì)標(biāo)號(hào)(uj,predj)，uj是從s到j(luò)的最短路長(zhǎng)；predj是從s到j(luò)的最短路中j點(diǎn)的前一點(diǎn)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12Example數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12Dijkstra算法（標(biāo)號(hào)設(shè)定算法）適用于正費(fèi)用網(wǎng)絡(luò)：“分層”設(shè)定標(biāo)號(hào)永久標(biāo)號(hào)：S中的點(diǎn)，uj是最短路長(zhǎng)臨時(shí)標(biāo)號(hào)；其他點(diǎn)，uj是只通過S中的點(diǎn)的最短路長(zhǎng)對(duì)于稠密網(wǎng)絡(luò)，這是求解最短路問題可能達(dá)到的最小的復(fù)雜度,因?yàn)槿魏嗡惴ǘ贾辽俦仨殞?duì)每條弧考慮一次.對(duì)于稀疏網(wǎng)絡(luò)，利用各種形式的堆（Heap），其復(fù)雜度可降為或等算法復(fù)雜度O(n2+m)：如鏈表或鄰接矩陣實(shí)現(xiàn)找最小標(biāo)號(hào)點(diǎn)修改標(biāo)號(hào)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12特點(diǎn)：求所有點(diǎn)對(duì)間最短路基本思想：逐步逼近，迭代求解最短路方程:O(n3)Floyd-Warshall算法

（標(biāo)號(hào)修正算法，1962)臨時(shí)標(biāo)號(hào)是不通過k，k+1，…,n節(jié)點(diǎn)(i,j除外)時(shí)從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路路長(zhǎng).數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12Floyd-Warshall算法的具體實(shí)現(xiàn):O(n3)由于要記錄所有節(jié)點(diǎn)之間最短路的信息,所以這里我們要用一個(gè)二維數(shù)組P；

可依據(jù)P,采用“正向追蹤”的方式得到最短路.STEP2：如果k=n,結(jié)束;否則轉(zhuǎn)STEP1.STEP0:k=0.對(duì)于所有節(jié)點(diǎn)i和j:令，,(，若節(jié)點(diǎn)i和j之間沒有弧,認(rèn)為).

STEP1:k=k+1.對(duì)于所有節(jié)點(diǎn)i和j:若,令,;否則令,.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12Floyd-Warshall算法的

矩陣迭代法實(shí)現(xiàn)：O(n4)令D為權(quán)矩陣(直達(dá)最短路長(zhǎng))Dm為正好經(jīng)過m條弧從i到j(luò)的最短路長(zhǎng)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12問題1和2的一種具體建模方法(賦權(quán))在線路選擇問題中，當(dāng)從i可直達(dá)j時(shí)（同為公汽或地鐵站點(diǎn)），定義弧(i,j)；其上的權(quán)為lij表示由i直達(dá)j付出的代價(jià)，可以為時(shí)間或費(fèi)用(不包括換乘代價(jià)；多條線路可達(dá)時(shí)只保留最小代價(jià))初始等車時(shí)間2(3)min也不包括在內(nèi)，最后結(jié)果可加上注意：D=D(0)不是對(duì)稱矩陣(“直達(dá)矩陣”)dij(0)=dij數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12問題１－２的一種具體建模方法i站點(diǎn)是公汽站點(diǎn)，j站點(diǎn)為地鐵站點(diǎn)：（1）若j站點(diǎn)對(duì)應(yīng)的所有換乘(公汽)站點(diǎn)k，均不能從i直達(dá)(不在i站點(diǎn)所在公汽線路L上)，則dij(0)

=∞.

（2）若j站點(diǎn)對(duì)應(yīng)的換乘站點(diǎn)(k),可從i站點(diǎn)直達(dá)k，則費(fèi)用為dij(0)

=dik(0)；對(duì)于時(shí)間則需要加上k到j(luò)的步行時(shí)間.(若有多種選擇，取最小成本者即可)ikj數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12問題１－２的一種具體建模方法j站點(diǎn)是公汽站點(diǎn)，i站點(diǎn)為地鐵站點(diǎn)：（1）若從i站點(diǎn)對(duì)應(yīng)的任何換乘(公汽)站點(diǎn)k，均不能直達(dá)j站點(diǎn)，則dij(0)

=∞.

（2）若從i站點(diǎn)對(duì)應(yīng)的換乘(公汽)站點(diǎn)k，能直達(dá)j站點(diǎn)，則費(fèi)用為dij(0)

=dkj(0)；對(duì)于時(shí)間則需要加上i到k的步行時(shí)間.

ikj數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12問題１－２：最小費(fèi)用或時(shí)間

定義矩陣算子“⊙”如下：設(shè)A、B均為n階方陣，C=A⊙B(考慮換乘代價(jià))當(dāng)考慮費(fèi)用矩陣之間的運(yùn)算時(shí)，表示在k的換乘時(shí)間當(dāng)考慮時(shí)間矩陣之間的運(yùn)算時(shí)，＝０D(k)=D(k-1)⊙D表示k次換乘的最低代價(jià)(費(fèi)用或時(shí)間)

該算法大體相當(dāng)于求最短路的Floyd-Warshall算法，但考慮了換乘因素，可稱為改進(jìn)Floyd-Warshall算法

類似地,通過修改Dijkstra算法求解也可數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12問題１－２：最小費(fèi)用或時(shí)間δi,j,k表示換乘時(shí)間i=j或k=i，j時(shí)，δi,j,k=0其他情形：若不可換乘(當(dāng)i，j為公汽站點(diǎn)而k為地鐵站點(diǎn)，或者i，j為地鐵站點(diǎn)而k為公汽站點(diǎn)時(shí))，則δi,j,k=0若可換乘，則k這只是等待時(shí)間，因?yàn)椴叫袝r(shí)間已在D中考慮了ij數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12第３問：已知所有站點(diǎn)間步行時(shí)間多數(shù)隊(duì)沒有給出一般模型,而只考慮最多一次換乘多數(shù)隊(duì)的想法：假設(shè)“起點(diǎn)步行”，“換乘步行”，“終點(diǎn)步行”三種模式，限定步行最大時(shí)間后搜索ikj數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12其他：最短路問題的線性規(guī)劃模型xij表示?。╥，j）是否位于s-t路上：當(dāng)xij=1時(shí)，表示?。╥，j）位于s-t路上，當(dāng)xij=0時(shí)，表示?。╥，j）不在s-t路上.

關(guān)聯(lián)矩陣是全么模矩陣，因此0-1變量可以松弛為區(qū)間[0,1]中的實(shí)數(shù)不含負(fù)圈，變量直接松弛為所有非負(fù)實(shí)數(shù)思考：為什么xij可以不限定為{0，1}(0-1規(guī)劃)?數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12最短路問題的線性規(guī)劃模型線性規(guī)劃模型，應(yīng)該可以計(jì)算到比較大規(guī)模的問題有些隊(duì)寫出了上述模型，但并未用該模型求解可能需要強(qiáng)大的優(yōu)化軟件，數(shù)據(jù)輸入工作量也較大換乘代價(jià)不易考慮（網(wǎng)絡(luò)上的權(quán)不易定義，或不具可加性）有些同學(xué)提到動(dòng)態(tài)規(guī)劃,但要么與這里介紹的最短路算法等價(jià),要么處理有誤,或只是搜索法的變種數(shù)學(xué)與統(tǒng)計(jì)學(xué)院費(fèi)文龍feiwl@126.com2023/1/12有些隊(duì)討論“交通阻