1、關于數學建模賽題分析(建模方法)第一張，PPT共六十頁，創作于2022年6月簡要提綱 應用數學與數學建模 - 建模及建模競賽的意義 競賽評閱標準 - 一般原則及主要問題 優化模型的創新 - 2007B題分析第二張，PPT共六十頁，創作于2022年6月數學知識數學技巧數學應用數學發現應用數學數學技術數學實驗隨機數學代數與幾何微積分數學美學數學哲學數學精神數學素質數學文化數學：幾個層次的理解第三張，PPT共六十頁，創作于2022年6月數學建模：實際與數學之間的橋梁實際問題數學Mathematical Modeling 現實對象的信息數學模型現實對象的解答數學模型的解答表述求解解釋驗證(歸納)(演繹

2、)數學建模的全過程第四張，PPT共六十頁，創作于2022年6月美國MCM+ICM競賽規模第五張，PPT共六十頁，創作于2022年6月我國CUMCM競賽規模第六張，PPT共六十頁，創作于2022年6月學生歡迎：“一次參賽，終身受益”研究生導師們的認同企業界的認同贊助教育改革同行的認同：“成功范例”國際同行的認同競賽的反響第七張，PPT共六十頁，創作于2022年6月IBM 中國研究中心- 招聘條件Position title: Business Optimization(BJ)1Background in industrial engineering, operations research, m

3、athematics, Artificial Intelligence, management science etc. 2. Knowledge in network design, job scheduling, data analysis, simulation and optimization 3. Award in mathematical contest in modeling is a plus 4. Experience in industry is a plus 5. Experience in eclipse or programming model / architect

4、ure design is a plus -Feb. 18, 2006, /cn/ibm/crl/careers/condition.shtml競賽的反響（一例）第八張，PPT共六十頁，創作于2022年6月簡要提綱 應用數學與數學建模 - 建模及建模競賽的意義 競賽評閱標準 - 一般原則及主要問題 創新能力培養 -幾個例子（結合優化模型）第九張，PPT共六十頁，創作于2022年6月CUMCM評閱標準清晰性：摘要應理解為詳細摘要，提綱挈領 表達嚴謹、簡捷，思路清新 格式符合規范，嚴禁暴露身份創造性：特別欣賞獨樹一幟、標新立異，但要合理假設的合理性，建模的創造性，結果的正確性，表述的清晰性。正確性

5、：不強調與“參考答案”的一致性和結果的精度； 好方法的結果一般比較好；但不一定是最好的合理性：關鍵假設；不欣賞羅列大量無關緊要的假設 第十張，PPT共六十頁，創作于2022年6月CUMCM評閱標準: 一些常見問題有的論文過于簡單，該交代的內容省略了，難以看懂有的隊羅列一系列假設或模型，又不作比較、評價，希望碰上“參考答案”或“評閱思路”，弄巧成拙數學模型最好明確、合理、簡潔：有些論文不給出明確的模型，只是根據賽題的情況，實際上是用“湊”的方法給出結果，雖然結果大致是對的，沒有一般性，不是數學建模的正確思路。有的論文參考文獻不全，或引用他人結果不作交代第十一張，PPT共六十頁，創作于2022年6

6、月從論文評閱看學生參加競賽中的問題 吃透題意方面不足，沒有抓住和解決主要問題； 就事論事，形成數學模型的意識和能力欠缺； 對所用方法一知半解，不管具體條件，套用現成的方法，導致錯誤； 對結果的分析不夠，怎樣符合實際考慮不周； 寫作方面的問題(摘要、簡明、優缺點、參考文獻); 隊員之間合作精神差，孤軍奮戰； 依賴心理重，甚至違紀（指導教師、 網絡）。第十二張，PPT共六十頁，創作于2022年6月簡要提綱 應用數學與數學建模 - 建模及建模競賽的意義 競賽評閱標準 - 一般原則及主要問題 創新能力培養 - 2007B分析第十三張，PPT共六十頁，創作于2022年6月14 優化問題三要素：決策變量；

7、目標函數；約束條件約束條件決策變量優化問題的一般形式目標函數有人統計： 優化問題占CUMCM賽題的一半以上（1/32/3）第十四張，PPT共六十頁，創作于2022年6月 建模時需要注意的幾個基本問題 1、盡量使用實數優化，減少整數約束和整數變量2、盡量使用光滑優化，減少非光滑約束的個數 如：盡量少使用絕對值、符號函數、多個變量求最大/最小值、四舍五入、取整函數等3、盡量使用線性模型，減少非線性約束和非線性變量的個數 （如x/y 5 改為x5y）4、合理設定變量上下界，盡可能給出變量初始值 5、模型中使用的參數數量級要適當 (如小于103)第十五張，PPT共六十頁，創作于2022年6月優化建模如

8、何創新？ 方法1：大膽創新，別出心裁 - 采用有特色的目標函數、約束條件等 - 你用非線性規劃，我用線性規劃 - 你用整數/離散規劃，我用連續規劃/網絡優化 - 方法2：細致入微，滴水不漏 - 對目標函數、約束條件處理特別細致 - 有算法設計和分析，不僅僅是簡單套用軟件 - 敏感性分析詳細 / 全面 - 第十六張，PPT共六十頁，創作于2022年6月2007B命題背景 奧運相關的題目：(時代特性, 社會關注）讓運動員及時到達場館（車輛調度，路徑安排等） 應急管理（緊急疏散，應急調度等）賽程安排（單一項目，多個項目）成績排名（如循環賽，體操或跳水等）技術類，如“劉翔的運動鞋”乘公交，看奧運：原名

9、“自動問路機”方沛辰（吉大），吳孟達（國防科大）提出原擬作乙組題，似乎難度太大第十七張，PPT共六十頁，創作于2022年6月命題背景 定位：公交路線選擇（查詢）模型與算法如何給數據？抽象數據實際數據？（減小規模，不給地理信息）貌似簡單，實則不然數據處理（轉換）方面有一定難度換乘次數多時簡單搜索不易（計算復雜度高）換乘時間步行時間等需要考慮周全標準的最短路算法（如Dijkstra算法）并不適用第十八張，PPT共六十頁，創作于2022年6月 B題：乘公交，看奧運 第29屆奧運會08年8月將在北京舉行，屆時有大量觀眾到現場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出

10、行。北京市的公交線路已達800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，某公司準備研制開發一個解決公交線路選擇問題的自主查詢計算機系統。 應該從實際情況出發考慮，滿足查詢者的各種不同需求。07-B 題 解 題 分 析 為了設計這樣一個系統，其核心是線路選擇的模型與算法。第十九張，PPT共六十頁，創作于2022年6月07-B 題 解 題 分 析請解決如下問題： 1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數學模型與算法。并根據附錄數據，利用你們的模型與算法，求出以下6對起始站終到站之間的最佳路線（要有清晰的評價說明）。 (1)、S3359

11、S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設又知道所有站點之間的步行時間,請你給出任意兩站點之間線路選擇問題的數學模型。第二十張，PPT共六十頁，創作于2022年6月07-B 題 解 題 分 析【附錄1】基本參數設定相鄰公汽站平均行駛時間(包括停站時間)： 3分鐘相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鐘公汽換乘公汽平均耗時： 5分鐘(其中步行時間2分鐘)地鐵換乘地鐵平均耗時： 4分鐘(其中步行時間2分鐘)地鐵換乘公汽平

12、均耗時： 7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時： 6分鐘(其中步行時間4分鐘)公汽票價：分為單一票價與分段計價兩種，標記于線路后；其中分段計價的票價為：020站：1元；2140站：2元； 40站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘）【附錄2】公交線路及相關信息 （見數據文件B2007data.rar） 第二十一張，PPT共六十頁，創作于2022年6月線路數據中的問題線路數據中的異?；虿幻鞔_之處，同學可根據自己的理解作出假設和處理，一般不會影響實例的計算結果個別線路相鄰站點名相同，可去掉其中一點或不作處理等L406未標明是環線，是否將其當作環線處理均可L290標明是環線，

13、但首尾站點分別為1477與1479，可將所有線路中1477與1479統一為1477后計算。同學也可以按照各自認為合理的方式處理，包括不當作環線，或將1479改為1477，或在1479后增加1477，等等如果在假設中有明確約定，則環線單向或雙向發車均應認可（按單向發車作假設，計算結果可能差些） 第二十二張，PPT共六十頁，創作于2022年6月對通過地鐵換乘的理解“假設同一地鐵站對應的任意兩個公汽站之間可以通過地鐵站換乘(無需支付地鐵費)”步行：公汽站地鐵站（通道）公汽站換乘耗時11min：步行4+4=8min; 等車3min第問（只考慮公汽）：可不考慮以上換乘有同學也考慮了如上換乘，只是不坐地鐵

14、，應該也可以此樣處理時，第問和第問的難度相近第二十三張，PPT共六十頁，創作于2022年6月07-B 題 解 題 分 析 題目特點 1、本題根據公交線路查詢系統研制的實際需求簡 化改編而成； 2、問題容易理解，相關參考文獻較多； 3、相關知識點： （1）圖論（最短路徑）； （2）多目標規劃。 4、題目開放度不夠，可發揮余地不多。 第二十四張，PPT共六十頁，創作于2022年6月關于數據的預處理：1、對于原始數據中出現的一些異常數據，可根據自己的理解作出假設和處理。如：（1）對于個別線路相鄰點名相同，可以采取去掉其中1點或不作處理等方式，一般不會影響實例計算中線路選擇的結果。（2）對于L406未

15、標明是環行線的問題，無論學生是否將其當作環線處理，一般不會影響到實例的計算結果。（3）對于L290標明是環線，但首尾站點分別為1477與1479的問題，可將所有線路中1477與1479統一為1477后計算。也可以按照各自認為合理的方式處理，包括不當作環線，實例計算用到的是該線路中部的幾個站點，一般不會影響實例計算結果。07-B 題 解 題 分 析2、關于環行線路，可以假設為單向或雙向。3、線路數據格式需編程進行轉換。第二十五張，PPT共六十頁，創作于2022年6月 模型的目標多目標優化問題（至少考慮三方面）換乘次數最少(N)、費用最省(M)、時間最短(T)從該問題的實際背景來看，加權不太合適

16、不少同學用層次分析法確定權不少同學計算時間的價值（平均收入工作時間）不同目標組合的模型三個目標按優先級排序，組合成六個模型也可將某些目標作為約束第二十六張，PPT共六十頁，創作于2022年6月 多數隊僅采用搜索法（70-80%?）直達； 一次換乘； 二次換乘；ststs t求出所有線路；評價其目標(容易計算)；選優第二十七張，PPT共六十頁，創作于2022年6月 多數隊僅采用搜索法總體來看，技術含量較低（基本上是枚舉）幾乎沒有建模，完全只有算法實現，算法也沒什么創新一般只考慮不超過兩次換乘不少文章引用參考文獻作為依據，實用中似乎夠用 題目難度大大降低，模型不夠一般換乘作為了第一目標，或作為一個

17、最重要的約束任意次換乘時算法復雜度提高，難以處理結果不佳（如：從省時考慮，有些需次換乘）第二十八張，PPT共六十頁，創作于2022年6月 圖論模型與最短路算法用圖論做的隊也不少，但往往考慮不周弧上賦權方式交代不清套用Dijkstra或Floyd-Warshall算法，卻不清楚其原理及適用的問題需要建立一個帶權有向圖，節點表示站點，有向弧表示前一站點能夠直達后一站點，弧上的權表示前一站點直達后一站點所需付出的代價(時間或費用)圖（網絡）如何描述和表示？基本要素：節點，有向?。ㄟ叄?，弧上賦權鄰接矩陣；關聯矩陣（數學上處理方便，存儲量較大）鏈表（存儲量較小，計算機上處理方便）第二十九張，PPT共六十

18、頁，創作于2022年6月 關聯矩陣(Incidence Matrix)表示法在線路選擇問題中，當從i可直達j時，定義弧(i,j)；其上的權可為或成本(時間或費用)；多重弧可只保留一條（弧上的權可取最小的成本，如時間或費用）G=(V，A)是一個簡單有向圖；|V|=n，|A|=m 重要數學性質：關聯矩陣是全幺模矩陣圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個 的矩陣，即第三十張，PPT共六十頁，創作于2022年6月 鄰接矩陣(Adjacency Matrix)表示法圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個 的0-1矩陣，即在線路選擇問題中，當從i可直達j時，定義弧(i,j)；其上的

19、權可為或成本(時間或費用)G=(V，A)是一個簡單有向圖；|V|=n，|A|=m 有向圖的“傳遞閉包算法”(可用于一般二元關系)權取0-1時，C(0)=C可稱為直達矩陣 ；C(1)=C*C 為次可達矩陣；C(2)=C(1)*C 為2次可達矩陣；第三十一張，PPT共六十頁，創作于2022年6月鏈表（鄰接表）表示法 122345283904602403053036470單向鏈表(指針數組) A(1)=2,3A(2)=4A(3)=2A(4)=3,5A(5)=3,412345第三十二張，PPT共六十頁，創作于2022年6月 Dijkstra算法（標號算法，1959）STEP1. 如果S=V, 則uj為

20、節點s到節點j的最短路路長(最短路可以通過數組pred所記錄的信息反向追蹤獲得), 結束.否則繼續. STEP0. (初始化) 令S= ，=V， ；對V 中的頂點j(j s)令初始距離標號 . STEP2. 從 中找到距離標號最小的節點i，把它從 刪除，加入S. 對于所有從i出發的弧 , 若 ，則令 轉STEP1. 特點：1. 算法求出從源點s到所有點的最短路長 2. 每點給一對標號 (uj, predj)，uj是從s到j的最短路長；predj是從s到j的最短路中j點的前一點第三十三張，PPT共六十頁，創作于2022年6月Example第三十四張，PPT共六十頁，創作于2022年6月Dijks

21、tra算法（標號設定算法）適用于正費用網絡：“分層”設定標號永久標號：S中的點，uj是最短路長臨時標號；其他點， uj是只通過S中的點的最短路長對于稠密網絡，這是求解最短路問題可能達到的最小的復雜度,因為任何算法都至少必須對每條弧考慮一次.對于稀疏網絡，利用各種形式的堆（Heap），其復雜度可降為 或 等算法復雜度O( n2+m)：如鏈表或鄰接矩陣實現找最小標號點修改標號第三十五張，PPT共六十頁，創作于2022年6月特點：求所有點對間最短路基本思想：逐步逼近，迭代求解最短路方程: O(n3) Floyd-Warshall算法（標號修正算法1962)臨時標號 是不通過k，k+1，,n 節點(i

22、,j 除外)時從節點i到節點j的最短路路長. 第三十六張，PPT共六十頁，創作于2022年6月 Floyd-Warshall算法的具體實現: O(n3)由于要記錄所有節點之間最短路的信息, 所以這里我們要用一個二維數組P； 可依據P, 采用“正向追蹤”的方式得到最短路. STEP2：如果k=n, 結束; 否則轉STEP1. STEP0: k=0. 對于所有節點i和j: 令 ， , ( ，若節點i和j之間沒有弧, 認為 ) . STEP1: k=k+1. 對于所有節點i和j: 若 , 令 , ; 否則令 , . 第三十七張，PPT共六十頁，創作于2022年6月Floyd-Warshall算法的矩

23、陣迭代法實現：O(n4)令D為權矩陣(直達最短路長)Dm為正好經過m條弧從i到j的最短路長第三十八張，PPT共六十頁，創作于2022年6月 問題1和2的一種具體建模方法(賦權)在線路選擇問題中，當從i可直達j時（同為公汽或地鐵站點），定義弧(i,j)；其上的權為lij表示由i直達j付出的代價，可以為時間或費用 (不包括換乘代價；多條線路可達時只保留最小代價)初始等車時間2(3)min也不包括在內，最后結果可加上注意：D=D(0)不是對稱矩陣(“直達矩陣”)dij(0)=dij第三十九張，PPT共六十頁，創作于2022年6月 問題的一種具體建模方法i站點是公汽站點，j站點為地鐵站點：（1）若j站

24、點對應的所有換乘(公汽)站點k，均不能從i直達(不在i站點所在公汽線路L上)，則dij(0) =. （2）若j站點對應的換乘站點(k), 可從i站點直達k，則費用為dij(0) = dik(0)；對于時間則需要加上k到j的步行時間. (若有多種選擇，取最小成本者即可)ikj第四十張，PPT共六十頁，創作于2022年6月 問題的一種具體建模方法j站點是公汽站點，i站點為地鐵站點：（1）若從i站點對應的任何換乘(公汽)站點k，均不能直達j站點，則dij(0) =. （2）若從i站點對應的換乘(公汽)站點k，能直達j站點， 則費用為dij(0) = dkj(0)；對于時間則需要加上i到k的步行時間.

25、 ikj第四十一張，PPT共六十頁，創作于2022年6月 問題：最小費用或時間 定義矩陣算子“”如下：設A、B均為n階方陣， C = A B (考慮換乘代價)當考慮費用矩陣之間的運算時，表示在k的換乘時間 當考慮時間矩陣之間的運算時， D(k)= D(k-1) D 表示k次換乘的最低代價(費用或時間) 該算法大體相當于求最短路的Floyd-Warshall算法，但考慮了換乘因素，可稱為改進Floyd-Warshall算法 類似地,通過修改Dijkstra算法求解也可第四十二張，PPT共六十頁，創作于2022年6月 問題：最小費用或時間i,j,k表示換乘時間 i = j 或k = i，j時，i,

26、j,k = 0其他情形：若不可換乘(當i ，j為公汽站點而k為地鐵站點，或者i ，j為地鐵站點而k為公汽站點時)，則 i,j,k = 0若可換乘，則k這只是等待時間，因為步行時間已在D中考慮了ij第四十三張，PPT共六十頁，創作于2022年6月 第問：已知所有站點間步行時間多數隊沒有給出一般模型, 而只考慮最多一次換乘多數隊的想法：假設“起點步行”，“換乘步行”，“終點步行”三種模式，限定步行最大時間后搜索ikj第四十四張，PPT共六十頁，創作于2022年6月 其他：最短路問題的線性規劃模型xij表示?。╥，j）是否位于s-t路上：當xij =1時，表示?。╥，j）位于s-t路上，當xij =

27、0時，表示?。╥，j）不在s-t路上. 關聯矩陣是全么模矩陣，因此0-1變量可以松弛為區間0,1中的實數 不含負圈，變量直接松弛為所有非負實數思考：為什么xij 可以不限定為0，1 (0-1規劃) ?第四十五張，PPT共六十頁，創作于2022年6月 最短路問題的線性規劃模型線性規劃模型，應該可以計算到比較大規模的問題有些隊寫出了上述模型，但并未用該模型求解可能需要強大的優化軟件，數據輸入工作量也較大換乘代價不易考慮（網絡上的權不易定義，或不具可加性） 有些同學提到動態規劃, 但要么與這里介紹的最短路算法等價, 要么處理有誤, 或只是搜索法的變種第四十六張，PPT共六十頁，創作于2022年6月

28、有些隊討論“交通阻抗”:“文不對題”道路阻抗在交通流分配中可以通過路阻函數來描述所謂路阻函數是指路段行駛時間與路段交通負荷，交叉口延誤與交叉口負荷之間的關系在具體分配過程中，由路段行駛時間及交叉口延誤共同組成出行交通阻抗交通網絡上的路阻，應包含反映交通時間、交通安全、交通成本、舒適程度、便捷性和準時性等等許多因素第四十七張，PPT共六十頁，創作于2022年6月 同學論文中存在的主要問題2. 目標不當，或不完整 3. 換乘時間處理不當 尤其地鐵站與公汽站之間，以及 通過地鐵通道換乘的公汽站之間1. 幾乎沒有模型，只有算法（一般是搜索法）4. 算法使用不當，或濫用5. 對第問，很少認真進行討論和建

29、模6. 全文表達不清，思路混亂第四十八張，PPT共六十頁，創作于2022年6月關于目標的考慮：問題1、2：換乘次數最少、費用最省、時間最短。 07-B 題 解 題 分 析問題3：換乘次數最少、乘車的總站數最少、步行的總時間最少、總車費最少等 。 第四十九張，PPT共六十頁，創作于2022年6月關于目標的處理： 從該問題的實際背景來看，采取加權合成將問題轉化為單目標優化問題的解題思路不太合適。比較適當的方法是對每個目標尋求最佳線路，然后讓乘客按照自己的需要進行選擇。 07-B 題 解 題 分 析第五十張，PPT共六十頁，創作于2022年6月換乘次數與可達矩陣：對于本問題，經計算可知，任何兩站點最多經5次換乘可達。經三次換乘可達率大于99%。07-B 題 解 題 分 析第五十一張，PPT共六十頁，創作于2022年6月 問題1 不考慮地鐵線路時的公交線路選擇 圖論模型：這可能是最常使用的方法，首先要考慮如何根據不同目標建立有向賦權圖（如利用不同的矩陣表示），然后再求給定點對之間的最小換乘次數或最短路。求兩點間最短路有Dijkstra算法與Floyd算法等，但并不能將這兩種算法直接套用于本問題，還需要處理好換乘次數 和換乘時間問題。07-B 題 解 題 分 析第五十二張，PPT共六十頁，創作于2022年6月其它方法規劃模型，包括0