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

關于數(shù)學建模賽題分析(建模方法)第1頁，共60頁，2023年，2月20日，星期四簡要提綱

應用數(shù)學與數(shù)學建模

-----建模及建模競賽的意義競賽評閱標準

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

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

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

應用數(shù)學與數(shù)學建模

-----建模及建模競賽的意義競賽評閱標準

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

-----幾個例子（結合優(yōu)化模型）第9頁，共60頁，2023年，2月20日，星期四CUMCM評閱標準清晰性：摘要應理解為詳細摘要，提綱挈領

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

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

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

應用數(shù)學與數(shù)學建模

-----建模及建模競賽的意義競賽評閱標準

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

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

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

建模時需要注意的幾個基本問題

1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù)如：盡量少使用絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)（如x/y<5改為x<5y）4、合理設定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級要適當(如小于103)第15頁，共60頁，2023年，2月20日，星期四優(yōu)化建模如何創(chuàng)新？

方法1：大膽創(chuàng)新，別出心裁

----采用有特色的目標函數(shù)、約束條件等

----你用非線性規(guī)劃，我用線性規(guī)劃

----你用整數(shù)/離散規(guī)劃，我用連續(xù)規(guī)劃/網(wǎng)絡優(yōu)化

----……

方法2：細致入微，滴水不漏

----對目標函數(shù)、約束條件處理特別細致

----有算法設計和分析，不僅僅是簡單套用軟件

----敏感性分析詳細/全面

----……第16頁，共60頁，2023年，2月20日，星期四2007B命題背景奧運相關的題目：(時代特性,社會關注）讓運動員及時到達場館（車輛調(diào)度，路徑安排等）應急管理（緊急疏散，應急調(diào)度等）賽程安排（單一項目，多個項目）成績排名（如循環(huán)賽，體操或跳水等）技術類，如“劉翔的運動鞋”乘公交，看奧運：原名“自動問路機”方沛辰（吉大），吳孟達（國防科大）提出原擬作乙組題，似乎難度太大第17頁，共60頁，2023年，2月20日，星期四命題背景定位：公交路線選擇（查詢）模型與算法如何給數(shù)據(jù)？抽象數(shù)據(jù)／實際數(shù)據(jù)？（減小規(guī)模，不給地理信息）貌似簡單，實則不然數(shù)據(jù)處理（轉(zhuǎn)換）方面有一定難度換乘次數(shù)多時簡單搜索不易（計算復雜度高）換乘時間／步行時間等需要考慮周全標準的最短路算法（如Dijkstra算法）并不適用第18頁，共60頁，2023年，2月20日，星期四B題：乘公交，看奧運

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

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

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

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

(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設又知道所有站點之間的步行時間,請你給出任意兩站點之間線路選擇問題的數(shù)學模型。第20頁，共60頁，2023年，2月20日，星期四07-B題解題分析【附錄1】基本參數(shù)設定相鄰公汽站平均行駛時間(包括停站時間)：3分鐘相鄰地鐵站平均行駛時間(包括停站時間)：2.5分鐘公汽換乘公汽平均耗時：5分鐘(其中步行時間2分鐘)地鐵換乘地鐵平均耗時：4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時：7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時：6分鐘(其中步行時間4分鐘)公汽票價：分為單一票價與分段計價兩種，標記于線路后；其中分段計價的票價為：0～20站：1元；21～40站：2元；

40站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘）【附錄2】公交線路及相關信息（見數(shù)據(jù)文件B2007data.rar）第21頁，共60頁，2023年，2月20日，星期四線路數(shù)據(jù)中的問題

線路數(shù)據(jù)中的異常或不明確之處，同學可根據(jù)自己的理解作出假設和處理，一般不會影響實例的計算結果個別線路相鄰站點名相同，可去掉其中一點或不作處理等L406未標明是環(huán)線，是否將其當作環(huán)線處理均可L290標明是環(huán)線，但首尾站點分別為1477與1479，可將所有線路中1477與1479統(tǒng)一為1477后計算。同學也可以按照各自認為合理的方式處理，包括不當作環(huán)線，或?qū)?479改為1477，或在1479后增加1477，等等如果在假設中有明確約定，則環(huán)線單向或雙向發(fā)車均應認可（按單向發(fā)車作假設，計算結果可能差些）

第22頁，共60頁，2023年，2月20日，星期四對通過地鐵換乘的理解“假設同一地鐵站對應的任意兩個公汽站之間可以通過地鐵站換乘(無需支付地鐵費)”

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

題目特點

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

2、問題容易理解，相關參考文獻較多；

3、相關知識點：

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

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

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

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

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

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

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

圖論模型與最短路算法用圖論做的隊也不少，但往往考慮不周弧上賦權方式交代不清套用Dijkstra或Floyd-Warshall算法，卻不清楚其原理及適用的問題需要建立一個帶權有向圖，節(jié)點表示站點，有向弧表示前一站點能夠直達后一站點，弧上的權表示前一站點直達后一站點所需付出的代價(時間或費用)圖（網(wǎng)絡）如何描述和表示？基本要素：節(jié)點，有向弧（邊），弧上賦權鄰接矩陣；關聯(lián)矩陣（數(shù)學上處理方便，存儲量較大）鏈表（存儲量較小，計算機上處理方便）第29頁，共60頁，2023年，2月20日，星期四

關聯(lián)矩陣(IncidenceMatrix)表示法在線路選擇問題中，當從i可直達j時，定義弧(i,j)；其上的權可為１或成本(時間或費用)；多重弧可只保留一條（弧上的權可取最小的成本，如時間或費用）G=(V，A)是一個簡單有向圖；|V|=n，|A|=m

重要數(shù)學性質(zhì)：關聯(lián)矩陣是全幺模矩陣圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個的矩陣，即第30頁，共60頁，2023年，2月20日，星期四

鄰接矩陣(AdjacencyMatrix)表示法圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個的0-1矩陣，即在線路選擇問題中，當從i可直達j時，定義弧(i,j)；其上的權可為１或成本(時間或費用)G=(V，A)是一個簡單有向圖；|V|=n，|A|=m

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

；C(1)=C*C

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

為2次可達矩陣；……第31頁，共60頁，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頁，共60頁，2023年，2月20日，星期四Dijkstra算法（標號算法，1959）STEP1.如果S=V,則uj為節(jié)點s到節(jié)點j的最短路路長(最短路可以通過數(shù)組pred所記錄的信息反向追蹤獲得),結束.否則繼續(xù).STEP0.(初始化)令S=，=V，；對V中的頂點j(js)令初始距離標號.

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

轉(zhuǎn)STEP1.特點：1.算法求出從源點s到所有點的最短路長

2.每點給一對標號(uj,predj)，uj是從s到j的最短路長；predj是從s到j的最短路中j點的前一點第33頁，共60頁，2023年，2月20日，星期四Example第34頁，共60頁，2023年，2月20日，星期四Dijkstra算法（標號設定算法）適用于正費用網(wǎng)絡：“分層”設定標號永久標號：S中的點，uj是最短路長臨時標號；其他點，uj是只通過S中的點的最短路長對于稠密網(wǎng)絡，這是求解最短路問題可能達到的最小的復雜度,因為任何算法都至少必須對每條弧考慮一次.對于稀疏網(wǎng)絡，利用各種形式的堆（Heap），其復雜度可降為或等算法復雜度O(n2+m)：如鏈表或鄰接矩陣實現(xiàn)找最小標號點修改標號第35頁，共60頁，2023年，2月20日，星期四特點：求所有點對間最短路基本思想：逐步逼近，迭代求解最短路方程:O(n3)Floyd-Warshall算法（標號修正算法1962)臨時標號是不通過k，k+1，…,n節(jié)點(i,j除外)時從節(jié)點i到節(jié)點j的最短路路長.第36頁，共60頁，2023年，2月20日，星期四Floyd-Warshall算法的具體實現(xiàn):O(n3)由于要記錄所有節(jié)點之間最短路的信息,所以這里我們要用一個二維數(shù)組P；

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

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

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

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

問題1和2的一種具體建模方法(賦權)在線路選擇問題中，當從i可直達j時（同為公汽或地鐵站點），定義弧(i,j)；其上的權為lij表示由i直達j付出的代價，可以為時間或費用(不包括換乘代價；多條線路可達時只保留最小代價)初始等車時間2(3)min也不包括在內(nèi)，最后結果可加上注意：D=D(0)不是對稱矩陣(“直達矩陣”)dij(0)=dij第39頁，共60頁，2023年，2月20日，星期四

問題１－２的一種具體建模方法i站點是公汽站點，j站點為地鐵站點：（1）若j站點對應的所有換乘(公汽)站點k，均不能從i直達(不在i站點所在公汽線路L上)，則dij(0)

=∞.

（2）若j站點對應的換乘站點(k),可從i站點直達k，則費用為dij(0)

=dik(0)；對于時間則需要加上k到j的步行時間.(若有多種選擇，取最小成本者即可)ikj第40頁，共60頁，2023年，2月20日，星期四

問題１－２的一種具體建模方法j站點是公汽站點，i站點為地鐵站點：（1）若從i站點對應的任何換乘(公汽)站點k，均不能直達j站點，則dij(0)

=∞.

（2）若從i站點對應的換乘(公汽)站點k，能直達j站點，則費用為dij(0)

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

ikj第41頁，共60頁，2023年，2月20日，星期四

問題１－２：最小費用或時間

定義矩陣算子“⊙”如下：設A、B均為n階方陣，

C=A⊙B(考慮換乘代價)當考慮費用矩陣之間的運算時，表示在k的換乘時間當考慮時間矩陣之間的運算時，＝０D(k)=D(k-1)⊙D表示k次換乘的最低代價(費用或時間)

該算法大體相當于求最短路的Floyd-Warshall算法，但考慮了換乘因素，可稱為改進Floyd-Warshall算法類似地,通過修改Dijkstra算法求解也可第42頁，共60頁，2023年，2月20日，星期四

問題１－２：最小費用或時間δi,j,k表示換乘時間i=j

或k=i，j時，δi,j,k=0其他情形：若不可換乘(當i，j為公汽站點而k為地鐵站點，或者i，j為地鐵站點而k為公汽站點時)，則δi,j,k=0若可換乘，則k這只是等待時間，因為步行時間已在D中考慮了ij第43頁，共60頁，2023年，2月20日，星期四

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

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

關聯(lián)矩陣是全么模矩陣，因此0-1變量可以松弛為區(qū)間[0,1]中的實數(shù)不含負圈，變量直接松弛為所有非負實數(shù)思考：為什么xij可以不限定為{0，1}(0-1規(guī)劃)?第45頁，共60頁，2023年，2月20日，星期四

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

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

同學論文中存在的主要問題2.目標不當，或不完整3.換乘時間處理不當尤其地鐵站與公汽站之間，以及通過地鐵通道換乘的公汽站之間1.幾乎沒有模型，只有算法（一般是搜索法）4.算法使用不當，或濫用5.對第３問，很少認真進行討論和建模6.全文表達不清，思路混亂第48頁，共60頁，2023年，2月20日，星期四關于目標的考慮：問題1、2：換乘次數(shù)最少、費用最省、時間最短。07-B題解題分析問題3：換乘次數(shù)最少、乘車的總站數(shù)最少、步行的總時間最少、總車費最少等。第49頁，共60頁，2023年，2月20日，星期四關于目標的處理：

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

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

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