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

關(guān)于數(shù)學(xué)建模賽題分析(建模方法)第一頁(yè)，共六十頁(yè)，2022年，8月28日簡(jiǎn)要提綱

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

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

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

-----2007B題分析第二頁(yè)，共六十頁(yè)，2022年，8月28日數(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è)層次的理解第三頁(yè)，共六十頁(yè)，2022年，8月28日數(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é)建模的全過程第四頁(yè)，共六十頁(yè)，2022年，8月28日美國(guó)MCM+ICM競(jìng)賽規(guī)模第五頁(yè)，共六十頁(yè)，2022年，8月28日我國(guó)CUMCM競(jìng)賽規(guī)模第六頁(yè)，共六十頁(yè)，2022年，8月28日學(xué)生歡迎：“一次參賽，終身受益”研究生導(dǎo)師們的認(rèn)同企業(yè)界的認(rèn)同／贊助教育改革同行的認(rèn)同：“成功范例”國(guó)際同行的認(rèn)同競(jìng)賽的反響第七頁(yè)，共六十頁(yè)，2022年，8月28日IBM中國(guó)研究中心-招聘條件Positiontitle:BusinessOptimization(BJ)

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

2.Knowledgeinnetworkdesign,jobscheduling,dataanalysis,simulationandoptimization

3.Awardinmathematicalcontestinmodelingisaplus

4.Experienceinindustryisaplus

5.Experienceineclipseorprogrammingmodel/architecturedesignisaplus

--競(jìng)賽的反響（一例）第八頁(yè)，共六十頁(yè)，2022年，8月28日簡(jiǎn)要提綱

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

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

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

-----幾個(gè)例子（結(jié)合優(yōu)化模型）第九頁(yè)，共六十頁(yè)，2022年，8月28日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ú)樹一幟、標(biāo)新立異，但要合理假設(shè)的合理性，建模的創(chuàng)造性，結(jié)果的正確性，表述的清晰性。正確性：不強(qiáng)調(diào)與“參考答案”的一致性和結(jié)果的精度；好方法的結(jié)果一般比較好；但不一定是最好的合理性：關(guān)鍵假設(shè)；不欣賞羅列大量無關(guān)緊要的假設(shè)第十頁(yè)，共六十頁(yè)，2022年，8月28日CUMCM評(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é)果不作交代第十一頁(yè)，共六十頁(yè)，2022年，8月28日從論文評(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ò)）。第十二頁(yè)，共六十頁(yè)，2022年，8月28日簡(jiǎn)要提綱

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

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

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

-----2007B分析第十三頁(yè)，共六十頁(yè)，2022年，8月28日

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

建模時(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)第十五頁(yè)，共六十頁(yè)，2022年，8月28日優(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ì)/全面

----……第十六頁(yè)，共六十頁(yè)，2022年，8月28日2007B命題背景奧運(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ó)防科大）提出原擬作乙組題，似乎難度太大第十七頁(yè)，共六十頁(yè)，2022年，8月28日命題背景定位：公交路線選擇（查詢）模型與算法如何給數(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算法）并不適用第十八頁(yè)，共六十頁(yè)，2022年，8月28日B題：乘公交，看奧運(yùn)

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

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

為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法。第十九頁(yè)，共六十頁(yè)，2022年，8月28日07-B題解題分析請(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é)模型。第二十頁(yè)，共六十頁(yè)，2022年，8月28日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元（無論地鐵線路間是否換乘）【附錄2】公交線路及相關(guān)信息（見數(shù)據(jù)文件B2007data.rar）第二十一頁(yè)，共六十頁(yè)，2022年，8月28日線路數(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é)果可能差些）

第二十二頁(yè)，共六十頁(yè)，2022年，8月28日對(duì)通過地鐵換乘的理解“假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過地鐵站換乘(無需支付地鐵費(fèi))”

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

題目特點(diǎn)

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

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

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

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

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

第二十四頁(yè)，共六十頁(yè)，2022年，8月28日關(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)行線的問題，無論學(xué)生是否將其當(dāng)作環(huán)線處理，一般不會(huì)影響到實(shí)例的計(jì)算結(jié)果。（3）對(duì)于L290標(biāo)明是環(huán)線，但首尾站點(diǎn)分別為1477與1479的問題，可將所有線路中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)換。第二十五頁(yè)，共六十頁(yè)，2022年，8月28日

模型的目標(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)作為約束第二十六頁(yè)，共六十頁(yè)，2022年，8月28日

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

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

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

圖論模型與最短路算法用圖論做的隊(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ī)上處理方便）第二十九頁(yè)，共六十頁(yè)，2022年，8月28日

關(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è)的矩陣，即第三十頁(yè)，共六十頁(yè)，2022年，8月28日

鄰接矩陣(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á)矩陣；……第三十一頁(yè)，共六十頁(yè)，2022年，8月28日鏈表（鄰接表）表示法

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

A(1)={2,3}A(2)={4}A(3)={2}A(4)={3,5}A(5)={3,4}12345第三十二頁(yè)，共六十頁(yè)，2022年，8月28日Dijkstra算法（標(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)第三十三頁(yè)，共六十頁(yè)，2022年，8月28日Example第三十四頁(yè)，共六十頁(yè)，2022年，8月28日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是只通過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)第三十五頁(yè)，共六十頁(yè)，2022年，8月28日特點(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).第三十六頁(yè)，共六十頁(yè)，2022年，8月28日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之間沒有弧,認(rèn)為).

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

,;否則令,.第三十七頁(yè)，共六十頁(yè)，2022年，8月28日Floyd-Warshall算法的

矩陣迭代法實(shí)現(xiàn)：O(n4)令D為權(quán)矩陣(直達(dá)最短路長(zhǎng))Dm為正好經(jīng)過m條弧從i到j(luò)的最短路長(zhǎng)第三十八頁(yè)，共六十頁(yè)，2022年，8月28日

問題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第三十九頁(yè)，共六十頁(yè)，2022年，8月28日

問題１－２的一種具體建模方法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第四十頁(yè)，共六十頁(yè)，2022年，8月28日

問題１－２的一種具體建模方法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第四十一頁(yè)，共六十頁(yè)，2022年，8月28日

問題１－２：最小費(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算法求解也可第四十二頁(yè)，共六十頁(yè)，2022年，8月28日

問題１－２：最小費(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第四十三頁(yè)，共六十頁(yè)，2022年，8月28日

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

其他：最短路問題的線性規(guī)劃模型xij表示?。╥，j）是否位于s-t路上：當(dāng)xij=1時(shí)，表示弧（i，j）位于s-t路上，當(dāng)xij=0時(shí)，表示弧（i，j）不在s-t路上.

關(guān)聯(lián)矩陣是全么模矩陣，因此0-1變量可以松弛為區(qū)間[0,1]中的實(shí)數(shù)不含負(fù)圈，變量直接松弛為所有非負(fù)實(shí)數(shù)思考：為什么xij可以不限定為{0，1}(0-1規(guī)劃)?第四十五頁(yè)，共六十頁(yè)，2022年，8月28日

最短路問題的線性規(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à),要么處理有誤,或只是搜索法的變種第四十六頁(yè)，共六十頁(yè)，2022年，8月28日

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

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

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

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

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