數(shù)學(xué)建模講座cumcm-20xxb賽題分析(編輯修改稿)
2024-08-15 17:42 本頁面
【文章內(nèi)容簡介】 【 附錄 2】 公交線路及相關(guān)信息 （見數(shù)據(jù)文件） 169。 謝金星 , 清華大學(xué)數(shù)學(xué)科學(xué)系 , 20222022. 線路數(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ū)?1479改為1477，或在 1479后增加 1477，等等 – 如果在假設(shè)中有明確約定，則環(huán)線單向或雙向發(fā)車均應(yīng)認(rèn)可（按單向發(fā)車作假設(shè)，計(jì)算結(jié)果可能差些） 169。 謝金星 , 清華大學(xué)數(shù)學(xué)科學(xué)系 , 20222022. 對(duì)通過地鐵換乘的理解 ? “假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過地鐵站換乘 (無需支付地鐵費(fèi) )” ? 步行：公汽站 ?地鐵站（通道） ?公汽站 ? 換乘耗時(shí) 11min：步行 4+4=8min。 等車 3min ? 第１問（只考慮公汽）：可不考慮以上換乘 – 有同學(xué)也考慮了如上換乘，只是不坐地鐵，應(yīng)該也可以 – 此樣處理時(shí)，第１問和第２問的難度相近 169。 謝金星 , 清華大學(xué)數(shù)學(xué)科學(xué)系 , 20222022. 模型的目標(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)作為約束 169。 謝金星 , 清華大學(xué)數(shù)學(xué)科學(xué)系 , 20222022. 多數(shù)隊(duì) 僅 采用搜索法（ 7080%?） ? 直達(dá)； 一次換乘； 二次換乘； … s t s t s t ? 求出所有線路；評(píng)價(jià)其目標(biāo) (容易計(jì)算 )；選優(yōu) 169。 謝金星 , 清華大學(xué)數(shù)學(xué)科學(xué)系 , 20222022. 多數(shù)隊(duì) 僅 采用搜索法 ? 總體來看，技術(shù)含量較低（基本上是枚舉） – 幾乎沒有建模，完全只有算法實(shí)現(xiàn)，算法也沒什么創(chuàng)新 ? 一般只考慮不超過兩次換乘 – 不少文章引用參考文獻(xiàn)作為依據(jù)，實(shí)用中似乎夠用 – 題目難度大大降低，模型不夠 一般 ? 換乘作為了 第一目標(biāo) ，或作為一個(gè) 最重要的約束 ? 任意次換乘時(shí)算法復(fù)雜度提高，難以處理 – 結(jié)果不佳（如：從省時(shí)考慮，有些需３－４次換乘） 169。 謝金星 , 清華大學(xué)數(shù)學(xué)科學(xué)系 , 20222022. 圖論模型與最短路算法 ? 用圖論做的隊(duì)也不少，但往往考慮不周 – 弧上賦權(quán)方式交代不清 – 套用 Dijkstra或 FloydWarshall算法，卻不清楚其原理及適用的問題 ? 需要建立一個(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ī)上處理方便） 169。 謝金星 , 清華大學(xué)數(shù)學(xué)科學(xué)系 , 20222022. 關(guān)聯(lián)矩陣 (Incidence Matrix)表示法 在線路選擇問題中，當(dāng)從 i可直達(dá) j時(shí)，定義弧(i,j)；其上的權(quán)可為１或成本 (時(shí)間或費(fèi)用 )；多重弧可只保留一條（弧上的權(quán)可取最小的成本，如時(shí)間或費(fèi)用） G=(V， A)是一個(gè)簡單有向圖； |V|=n， |A|=m 重要數(shù)學(xué)性質(zhì)： 關(guān)聯(lián)矩陣是全幺模矩陣 圖 G=(V， A)的鄰接矩陣 C是如下定義的： C是一個(gè) 的矩陣 ， 即 mn?,}1,0,1{)( mnmnikbB ?? ??????????????????其他。，,0),(,1,),(,1AijkVjAjikVjb ik169。 謝金星 , 清華大學(xué)數(shù)學(xué)科學(xué)系 , 20222022. 鄰接矩陣 (Adjacency Matrix)表示法 圖 G=(V， A)的鄰接矩陣 C是如下定義的： C是一個(gè) 的 01矩陣 ， 即 在線路選擇問題中，當(dāng)從 i可直達(dá) j時(shí)，定義弧(i,j)；其上的權(quán)可為１或成本 (時(shí)間或費(fèi)用 ) nn?G=(V， A)是一個(gè)簡單有向圖； |V|=n， |A|=m ,}1,0{)( nnnnijcC ?? ????????.),(,1,),(,0AjiAjicij有向圖的“傳遞閉包算法” (可用于一般二元關(guān)系 ) 權(quán)取 01時(shí)， C(0)=C可稱為 直達(dá)矩陣 ； C(1)=C*C 為１次可達(dá)矩陣 ； C(2)=C(1)*C 為 2次可達(dá)矩陣 ； …… 169。 謝金星 , 清華大學(xué)數(shù)學(xué)科學(xué)系 , 20222022. 鏈表（鄰接表）表示法 1 2 2 3 4 5 2 8 3 9 0 4 6 0 2 4 0 3 0 5 3 0 3 6 4 7 0 單向鏈表(指針數(shù)組) A(1)={2,3
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1