數(shù)學(xué)建模賽題分析(建模方法)

關(guān)于數(shù)學(xué)建模賽題分析(建模方法)第1頁(yè)，共60頁(yè)，2023年，2月20日，星期四簡(jiǎn)要提綱

應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模

-----建模及建模競(jìng)賽的意義競(jìng)賽評(píng)閱標(biāo)準(zhǔn)

-----一般原則及主要問(wèn)題優(yōu)化模型的創(chuàng)新

-----2007B題分析第2頁(yè)，共60頁(yè)，2023年，2月20日，星期四數(shù)學(xué)知識(shí)數(shù)學(xué)技巧數(shù)學(xué)應(yīng)用數(shù)學(xué)發(fā)現(xiàn)……應(yīng)用數(shù)學(xué)數(shù)學(xué)技術(shù)數(shù)學(xué)實(shí)驗(yàn)……隨機(jī)數(shù)學(xué)代數(shù)與幾何微積分……數(shù)學(xué)美學(xué)數(shù)學(xué)哲學(xué)數(shù)學(xué)精神數(shù)學(xué)素質(zhì)數(shù)學(xué)文化數(shù)學(xué)：幾個(gè)層次的理解第3頁(yè)，共60頁(yè)，2023年，2月20日，星期四數(shù)學(xué)建模：實(shí)際與數(shù)學(xué)之間的橋梁實(shí)際問(wèn)題數(shù)學(xué)MathematicalModeling

現(xiàn)實(shí)對(duì)象的信息數(shù)學(xué)模型現(xiàn)實(shí)對(duì)象的解答數(shù)學(xué)模型的解答表述求解解釋驗(yàn)證(歸納)(演繹)數(shù)學(xué)建模的全過(guò)程第4頁(yè)，共60頁(yè)，2023年，2月20日，星期四美國(guó)MCM+ICM競(jìng)賽規(guī)模第5頁(yè)，共60頁(yè)，2023年，2月20日，星期四我國(guó)CUMCM競(jìng)賽規(guī)模第6頁(yè)，共60頁(yè)，2023年，2月20日，星期四學(xué)生歡迎：“一次參賽，終身受益”研究生導(dǎo)師們的認(rèn)同企業(yè)界的認(rèn)同／贊助教育改革同行的認(rèn)同：“成功范例”國(guó)際同行的認(rèn)同競(jìng)賽的反響第7頁(yè)，共60頁(yè)，2023年，2月20日，星期四IBM中國(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)賽的反響（一例）第8頁(yè)，共60頁(yè)，2023年，2月20日，星期四簡(jiǎn)要提綱

應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模

-----建模及建模競(jìng)賽的意義競(jìng)賽評(píng)閱標(biāo)準(zhǔn)

-----一般原則及主要問(wèn)題創(chuàng)新能力培養(yǎng)

-----幾個(gè)例子（結(jié)合優(yōu)化模型）第9頁(yè)，共60頁(yè)，2023年，2月20日，星期四CUMCM評(píng)閱標(biāo)準(zhǔn)清晰性：摘要應(yīng)理解為詳細(xì)摘要，提綱挈領(lǐng)

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

吃透題意方面不足，沒(méi)有抓住和解決主要問(wèn)題；就事論事，形成數(shù)學(xué)模型的意識(shí)和能力欠缺；對(duì)所用方法一知半解，不管具體條件，套用現(xiàn)成的方法，導(dǎo)致錯(cuò)誤；對(duì)結(jié)果的分析不夠，怎樣符合實(shí)際考慮不周；寫(xiě)作方面的問(wèn)題(摘要、簡(jiǎn)明、優(yōu)缺點(diǎn)、參考文獻(xiàn));

隊(duì)員之間合作精神差，孤軍奮戰(zhàn)；依賴心理重，甚至違紀(jì)（指導(dǎo)教師、網(wǎng)絡(luò)）。第12頁(yè)，共60頁(yè)，2023年，2月20日，星期四簡(jiǎn)要提綱

應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模

-----建模及建模競(jìng)賽的意義競(jìng)賽評(píng)閱標(biāo)準(zhǔn)

-----一般原則及主要問(wèn)題創(chuàng)新能力培養(yǎng)

-----2007B分析第13頁(yè)，共60頁(yè)，2023年，2月20日，星期四14

優(yōu)化問(wèn)題三要素：決策變量；目標(biāo)函數(shù)；約束條件約束條件決策變量?jī)?yōu)化問(wèn)題的一般形式目標(biāo)函數(shù)有人統(tǒng)計(jì)：優(yōu)化問(wèn)題占CUMCM賽題的一半以上（1/3~2/3）第14頁(yè)，共60頁(yè)，2023年，2月20日，星期四

建模時(shí)需要注意的幾個(gè)基本問(wèn)題

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)第15頁(yè)，共60頁(yè)，2023年，2月20日，星期四優(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ì)/全面

----……第16頁(yè)，共60頁(yè)，2023年，2月20日，星期四2007B命題背景奧運(yùn)相關(guān)的題目：(時(shí)代特性,社會(huì)關(guān)注）讓運(yùn)動(dòng)員及時(shí)到達(dá)場(chǎng)館（車(chē)輛調(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)問(wèn)路機(jī)”方沛辰（吉大），吳孟達(dá)（國(guó)防科大）提出原擬作乙組題，似乎難度太大第17頁(yè)，共60頁(yè)，2023年，2月20日，星期四命題背景定位：公交路線選擇（查詢）模型與算法如何給數(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算法）并不適用第18頁(yè)，共60頁(yè)，2023年，2月20日，星期四B題：乘公交，看奧運(yùn)

第29屆奧運(yùn)會(huì)08年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行。北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問(wèn)題。針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)。

應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。07-B題解題分析

為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法。第19頁(yè)，共60頁(yè)，2023年，2月20日，星期四07-B題解題分析請(qǐng)解決如下問(wèn)題：

1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站→終到站之間的最佳路線（要有清晰的評(píng)價(jià)說(shuō)明）。

(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同時(shí)考慮公汽與地鐵線路，解決以上問(wèn)題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間,請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型。第20頁(yè)，共60頁(yè)，2023年，2月20日，星期四07-B題解題分析【附錄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元（無(wú)論地鐵線路間是否換乘）【附錄2】公交線路及相關(guān)信息（見(jiàn)數(shù)據(jù)文件B2007data.rar）第21頁(yè)，共60頁(yè)，2023年，2月20日，星期四線路數(shù)據(jù)中的問(wèn)題

線路數(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ā)車(chē)均應(yīng)認(rèn)可（按單向發(fā)車(chē)作假設(shè)，計(jì)算結(jié)果可能差些）

第22頁(yè)，共60頁(yè)，2023年，2月20日，星期四對(duì)通過(guò)地鐵換乘的理解“假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過(guò)地鐵站換乘(無(wú)需支付地鐵費(fèi))”

步行：公汽站地鐵站（通道）公汽站換乘耗時(shí)11min：步行4+4=8min;等車(chē)3min第１問(wèn)（只考慮公汽）：可不考慮以上換乘有同學(xué)也考慮了如上換乘，只是不坐地鐵，應(yīng)該也可以此樣處理時(shí)，第１問(wèn)和第２問(wèn)的難度相近第23頁(yè)，共60頁(yè)，2023年，2月20日，星期四07-B題解題分析

題目特點(diǎn)

1、本題根據(jù)公交線路查詢系統(tǒng)研制的實(shí)際需求簡(jiǎn)化改編而成；

2、問(wèn)題容易理解，相關(guān)參考文獻(xiàn)較多；

3、相關(guān)知識(shí)點(diǎn)：

（1）圖論（最短路徑）；（2）多目標(biāo)規(guī)劃。

4、題目開(kāi)放度不夠，可發(fā)揮余地不多。

第24頁(yè)，共60頁(yè)，2023年，2月20日，星期四關(guān)于數(shù)據(jù)的預(yù)處理：1、對(duì)于原始數(shù)據(jù)中出現(xiàn)的一些異常數(shù)據(jù)，可根據(jù)自己的理解作出假設(shè)和處理。如：（1）對(duì)于個(gè)別線路相鄰點(diǎn)名相同，可以采取去掉其中1點(diǎn)或不作處理等方式，一般不會(huì)影響實(shí)例計(jì)算中線路選擇的結(jié)果。（2）對(duì)于L406未標(biāo)明是環(huán)行線的問(wèn)題，無(wú)論學(xué)生是否將其當(dāng)作環(huán)線處理，一般不會(huì)影響到實(shí)例的計(jì)算結(jié)果。（3）對(duì)于L290標(biāo)明是環(huán)線，但首尾站點(diǎn)分別為1477與1479的問(wèn)題，可將所有線路中1477與1479統(tǒng)一為1477后計(jì)算。也可以按照各自認(rèn)為合理的方式處理，包括不當(dāng)作環(huán)線，實(shí)例計(jì)算用到的是該線路中部的幾個(gè)站點(diǎn)，一般不會(huì)影響實(shí)例計(jì)算結(jié)果。07-B題解題分析2、關(guān)于環(huán)行線路，可以假設(shè)為單向或雙向。3、線路數(shù)據(jù)格式需編程進(jìn)行轉(zhuǎn)換。第25頁(yè)，共60頁(yè)，2023年，2月20日，星期四

模型的目標(biāo)多目標(biāo)優(yōu)化問(wèn)題（至少考慮三方面）換乘次數(shù)最少(N)、費(fèi)用最省(M)、時(shí)間最短(T)從該問(wèn)題的實(shí)際背景來(lái)看，加權(quán)不太合適不少同學(xué)用層次分析法確定權(quán)不少同學(xué)計(jì)算時(shí)間的價(jià)值（平均收入／工作時(shí)間）不同目標(biāo)組合的模型三個(gè)目標(biāo)按優(yōu)先級(jí)排序，組合成六個(gè)模型也可將某些目標(biāo)作為約束第26頁(yè)，共60頁(yè)，2023年，2月20日，星期四

多數(shù)隊(duì)僅采用搜索法（70-80%?）直達(dá)；一次換乘；二次換乘；…ststst求出所有線路；評(píng)價(jià)其目標(biāo)(容易計(jì)算)；選優(yōu)第27頁(yè)，共60頁(yè)，2023年，2月20日，星期四

多數(shù)隊(duì)僅采用搜索法總體來(lái)看，技術(shù)含量較低（基本上是枚舉）幾乎沒(méi)有建模，完全只有算法實(shí)現(xiàn)，算法也沒(méi)什么創(chuàng)新一般只考慮不超過(guò)兩次換乘不少文章引用參考文獻(xiàn)作為依據(jù)，實(shí)用中似乎夠用

題目難度大大降低，模型不夠一般換乘作為了第一目標(biāo)，或作為一個(gè)最重要的約束任意次換乘時(shí)算法復(fù)雜度提高，難以處理結(jié)果不佳（如：從省時(shí)考慮，有些需３－４次換乘）第28頁(yè)，共60頁(yè)，2023年，2月20日，星期四

圖論模型與最短路算法用圖論做的隊(duì)也不少，但往往考慮不周弧上賦權(quán)方式交代不清套用Dijkstra或Floyd-Warshall算法，卻不清楚其原理及適用的問(wèn)題需要建立一個(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ī)上處理方便）第29頁(yè)，共60頁(yè)，2023年，2月20日，星期四

關(guān)聯(lián)矩陣(IncidenceMatrix)表示法在線路選擇問(wèn)題中，當(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è)的矩陣，即第30頁(yè)，共60頁(yè)，2023年，2月20日，星期四

鄰接矩陣(AdjacencyMatrix)表示法圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個(gè)的0-1矩陣，即在線路選擇問(wèn)題中，當(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á)矩陣；……第31頁(yè)，共60頁(yè)，2023年，2月20日，星期四鏈表（鄰接表）表示法

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

A(1)={2,3}A(2)={4}A(3)={2}A(4)={3,5}A(5)={3,4}12345第32頁(yè)，共60頁(yè)，2023年，2月20日，星期四Dijkstra算法（標(biāo)號(hào)算法，1959）STEP1.如果S=V,則uj為節(jié)點(diǎn)s到節(jié)點(diǎn)j的最短路路長(zhǎng)(最短路可以通過(guò)數(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)第33頁(yè)，共60頁(yè)，2023年，2月20日，星期四Example第34頁(yè)，共60頁(yè)，2023年，2月20日，星期四Dijkstra算法（標(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是只通過(guò)S中的點(diǎn)的最短路長(zhǎng)對(duì)于稠密網(wǎng)絡(luò)，這是求解最短路問(wèn)題可能達(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)第35頁(yè)，共60頁(yè)，2023年，2月20日，星期四特點(diǎn)：求所有點(diǎn)對(duì)間最短路基本思想：逐步逼近，迭代求解最短路方程:O(n3)Floyd-Warshall算法（標(biāo)號(hào)修正算法1962)臨時(shí)標(biāo)號(hào)是不通過(guò)k，k+1，…,n節(jié)點(diǎn)(i,j除外)時(shí)從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路路長(zhǎng).第36頁(yè)，共60頁(yè)，2023年，2月20日，星期四Floyd-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之間沒(méi)有弧,認(rèn)為).

STEP1:k=k+1.對(duì)于所有節(jié)點(diǎn)i和j:若,令

,;否則令,.第37頁(yè)，共60頁(yè)，2023年，2月20日，星期四Floyd-Warshall算法的

矩陣迭代法實(shí)現(xiàn)：O(n4)令D為權(quán)矩陣(直達(dá)最短路長(zhǎng))Dm為正好經(jīng)過(guò)m條弧從i到j(luò)的最短路長(zhǎng)第38頁(yè)，共60頁(yè)，2023年，2月20日，星期四

問(wèn)題1和2的一種具體建模方法(賦權(quán))在線路選擇問(wè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à))初始等車(chē)時(shí)間2(3)min也不包括在內(nèi)，最后結(jié)果可加上注意：D=D(0)不是對(duì)稱矩陣(“直達(dá)矩陣”)dij(0)=dij第39頁(yè)，共60頁(yè)，2023年，2月20日，星期四

問(wèn)題１－２的一種具體建模方法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第40頁(yè)，共60頁(yè)，2023年，2月20日，星期四

問(wèn)題１－２的一種具體建模方法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第41頁(yè)，共60頁(yè)，2023年，2月20日，星期四

問(wèn)題１－２：最小費(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算法類似地,通過(guò)修改Dijkstra算法求解也可第42頁(yè)，共60頁(yè)，2023年，2月20日，星期四

問(wèn)題１－２：最小費(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第43頁(yè)，共60頁(yè)，2023年，2月20日，星期四

第３問(wèn)：已知所有站點(diǎn)間步行時(shí)間多數(shù)隊(duì)沒(méi)有給出一般模型,而只考慮最多一次換乘多數(shù)隊(duì)的想法：假設(shè)“起點(diǎn)步行”，“換乘步行”，“終點(diǎn)步行”三種模式，限定步行最大時(shí)間后搜索ikj第44頁(yè)，共60頁(yè)，2023年，2月20日，星期四

其他：最短路問(wèn)題的線性規(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ī)劃)?第45頁(yè)，共60頁(yè)，2023年，2月20日，星期四

最短路問(wèn)題的線性規(guī)劃模型線性規(guī)劃模型，應(yīng)該可以計(jì)算到比較大規(guī)模的問(wèn)題有些隊(duì)寫(xiě)出了上述模型，但并未用該模型求解可能需要強(qiáng)大的優(yōu)化軟件，數(shù)據(jù)輸入工作量也較大換乘代價(jià)不易考慮（網(wǎng)絡(luò)上的權(quán)不易定義，或不具可加性）有些同學(xué)提到動(dòng)態(tài)規(guī)劃,但要么與這里介紹的最短路算法等價(jià),要么處理有誤,或只是搜索法的變種第46頁(yè)，共60頁(yè)，2023年，2月20日，星期四

有些隊(duì)討論“交通阻抗”:“文不對(duì)題”道路阻抗在交通流分配中可以通過(guò)路阻函數(shù)來(lái)描述所謂路阻函數(shù)是指路段行駛時(shí)間與路段交通負(fù)荷，交叉口延誤與交叉口負(fù)荷之間的關(guān)系在具體分配過(guò)程中，由路段行駛時(shí)間及交叉口延誤共同組成出行交通阻抗交通網(wǎng)絡(luò)上的路阻，應(yīng)包含反映交通時(shí)間、交通安全、交通成本、舒適程度、便捷性和準(zhǔn)時(shí)性等等許多因素第47頁(yè)，共60頁(yè)，2023年，2月20日，星期四

同學(xué)論文中存在的主要問(wèn)題2.目標(biāo)不當(dāng)，或不完整3.換乘時(shí)間處理不當(dāng)尤其地鐵站與公汽站之間，以及通過(guò)地鐵通道換乘的公汽站之間1.幾乎沒(méi)有模型，只有算法（一般是搜索法）4.算法使用不當(dāng)，或?yàn)E用5.對(duì)第３問(wèn)，很少認(rèn)真進(jìn)行討論和建模6.全文表達(dá)不清，思路混亂第48頁(yè)，共60頁(yè)，2023年，2月20日，星期四關(guān)于目標(biāo)的考慮：?jiǎn)栴}1、2：換乘次數(shù)最少、費(fèi)用最省、時(shí)間最短。07-B題解題分析問(wèn)題3：換乘次數(shù)最少、乘車(chē)的總站數(shù)最少、步行的總時(shí)間最少、總車(chē)費(fèi)最少等。第49頁(yè)，共60頁(yè)，2023年，2月20日，星期四關(guān)于目標(biāo)的處理：

從該問(wèn)題的實(shí)際背景來(lái)看，采取加權(quán)合成將問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題的解題思路不太合適。比較適當(dāng)?shù)姆椒ㄊ菍?duì)每個(gè)目標(biāo)尋求最佳線路，然后讓乘客按照自己的需要進(jìn)行選擇。07-B題解題分析第50頁(yè)，共60頁(yè)，2023年，2月20日，星期四換乘次數(shù)與可達(dá)矩陣：對(duì)于本問(wèn)題，經(jīng)計(jì)算可知，任何兩站點(diǎn)最多經(jīng)5次換乘可達(dá)。經(jīng)三次換乘可達(dá)率大于99%。07-B題解題分析第51頁(yè)，共60頁(yè)，2023年，2月20日，星期四

問(wèn)題1不考慮地鐵線路時(shí)的公交線路選擇

圖論模型：這可能是最常使用的方法，首先要考慮如何根據(jù)不同目標(biāo)建立有向賦權(quán)圖（如利用不同的矩陣表示），然后再求給定點(diǎn)對(duì)之間的最小換乘次數(shù)或最短路。求兩點(diǎn)間最短路有Dijkstra算法與Floyd算法等，但并不能將這兩種算法直接套用于本問(wèn)題