數(shù)學(xué)建模講座2007B題tsinghua資料

1、數(shù)學(xué)建模講座(jingzu)CUMCM-2007B 賽題分析謝金星(jnxng)100084北京清華大學(xué)數(shù)學(xué)科學(xué)系Tel:Fax:mail:jxie /jxie共四十八頁簡要(jinyo)提綱 應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模 - 建模及建模競賽(jngsi)的意義 競賽評閱標(biāo)準(zhǔn) - 一般原則及主要問題 優(yōu)化模型的創(chuàng)新 - 2007B題分析共四十八頁數(shù)學(xué)知識數(shù)學(xué)(shxu)技巧數(shù)學(xué)應(yīng)用數(shù)學(xué)發(fā)現(xiàn)應(yīng)用數(shù)學(xué)數(shù)學(xué)技術(shù)數(shù)學(xué)實驗隨機數(shù)學(xué)(shxu)代數(shù)與幾何微積分?jǐn)?shù)學(xué)美學(xué)數(shù)學(xué)哲學(xué)數(shù)學(xué)精神數(shù)學(xué)素質(zhì)數(shù)學(xué)文化數(shù)學(xué)：幾個層次的理解共四十八頁數(shù)學(xué)(shxu)建模：實際與數(shù)學(xué)

2、(shxu)之間的橋梁實際(shj)問題數(shù)學(xué)Mathematical Modeling 現(xiàn)實對象的信息數(shù)學(xué)模型現(xiàn)實對象的解答數(shù)學(xué)模型的解答表述求解解釋驗證(歸納)(演繹)數(shù)學(xué)建模的全過程共四十八頁美國MCM+ICM競賽(jngsi)規(guī)模共四十八頁我國CUMCM競賽(jngsi)規(guī)模共四十八頁學(xué)生歡迎：“一次參賽，終身受益”研究生導(dǎo)師(dosh)們的認(rèn)同企業(yè)界的認(rèn)同贊助教育改革同行的認(rèn)同：“成功范例”國際同行的認(rèn)同競賽(jngsi)的反響共四十八頁IBM 中國研究中心- 招聘(zhopn)條件Position title: Business Optimization(BJ)1Background

3、 in industrial engineering, operations research, mathematics, 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. Expe

4、rience in eclipse or programming model / architecture design is a plus -Feb. 18, 2006, /cn/ibm/crl/careers/condition.shtml競賽(jngsi)的反響（一例）共四十八頁簡要(jinyo)提綱 應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模 - 建模及建模競賽的意義 競賽評閱標(biāo)準(zhǔn) - 一般(ybn)原則及主要問題 創(chuàng)新能力培養(yǎng) -幾個例子（結(jié)合優(yōu)化模型）共四十八頁CUMCM評閱(pngyu)標(biāo)準(zhǔn)清晰性：摘要(zhiyo)應(yīng)理解為詳細(xì)摘要(zhiyo)，提綱挈領(lǐng) 表達(dá)嚴(yán)謹(jǐn)、簡捷，思路清新 格式符合規(guī)范，嚴(yán)禁暴

5、露身份創(chuàng)造性：特別欣賞獨樹一幟、標(biāo)新立異，但要合理假設(shè)的合理性，建模的創(chuàng)造性，結(jié)果的正確性，表述的清晰性。正確性：不強調(diào)與“參考答案”的一致性和結(jié)果的精度； 好方法的結(jié)果一般比較好；但不一定是最好的合理性：關(guān)鍵假設(shè)；不欣賞羅列大量無關(guān)緊要的假設(shè) 共四十八頁CUMCM評閱標(biāo)準(zhǔn)(biozhn): 一些常見問題有的論文(lnwn)過于簡單，該交代的內(nèi)容省略了，難以看懂有的隊羅列一系列假設(shè)或模型，又不作比較、評價，希望碰上“參考答案”或“評閱思路”，弄巧成拙數(shù)學(xué)模型最好明確、合理、簡潔：有些論文不給出明確的模型，只是根據(jù)賽題的情況，實際上是用“湊”的方法給出結(jié)果，雖然結(jié)果大致是對的，沒有一般性，不是數(shù)

6、學(xué)建模的正確思路。有的論文參考文獻(xiàn)不全，或引用他人結(jié)果不作交代共四十八頁從論文評閱看學(xué)生參加(cnji)競賽中的問題 吃透題意方面不足，沒有抓住和解決主要問題； 就事論事，形成數(shù)學(xué)模型的意識和能力欠缺； 對所用方法一知半解，不管具體條件，套用現(xiàn)成的方法，導(dǎo)致錯誤； 對結(jié)果(ji gu)的分析不夠，怎樣符合實際考慮不周； 寫作方面的問題(摘要、簡明、優(yōu)缺點、參考文獻(xiàn)); 隊員之間合作精神差，孤軍奮戰(zhàn)； 依賴心理重，甚至違紀(jì)（指導(dǎo)教師、 網(wǎng)絡(luò)）。共四十八頁參加競賽(jngsi)前的準(zhǔn)備 了解競賽章程等相關(guān)信息； 掌握數(shù)學(xué)建模的基本方法（學(xué)過“數(shù)學(xué)模型”或“數(shù)學(xué)實驗”課最好，自學(xué)一些基本內(nèi)容也可以）

7、； 掌握基本的數(shù)學(xué)軟件（Matlab/Mathematica；LINGO；如能掌握SAS/JMP統(tǒng)計軟件更好）； 訓(xùn)練規(guī)范的科技論文寫作/表達(dá)能力 (摘要、正文、優(yōu)缺點、參考文獻(xiàn)及引用等); 試做幾道以前的賽題； 培養(yǎng)合作(hzu)精神。共四十八頁簡要(jinyo)提綱 應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模 - 建模及建模競賽的意義 競賽評閱標(biāo)準(zhǔn) - 一般原則(yunz)及主要問題 創(chuàng)新能力培養(yǎng) - 2007B分析共四十八頁 優(yōu)化問題三要素：決策變量(binling)；目標(biāo)函數(shù)；約束條件約束條件決策變量優(yōu)化問題(wnt)的一般形式目標(biāo)函數(shù)有人統(tǒng)計： 優(yōu)化問題占CUMCM賽題的一半以上（1/32/3）共四十八頁建

8、模時需要注意的幾個(j )基本問題 1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù) 如：盡量少使用絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù) （如x/y 5 改為x5y）4、合理設(shè)定變量上下界(xi ji)，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級要適當(dāng) (如小于103)共四十八頁優(yōu)化建模如何(rh)創(chuàng)新？ 方法1：大膽創(chuàng)新，別出心裁 - 采用有特色的目標(biāo)(mbio)函數(shù)、約束條件等 - 你用非線性規(guī)劃，我用線性規(guī)劃 - 你用整數(shù)/離散規(guī)劃，我用連續(xù)規(guī)劃/網(wǎng)絡(luò)優(yōu)化 - 方法

9、2：細(xì)致入微，滴水不漏 - 對目標(biāo)函數(shù)、約束條件處理特別細(xì)致 - 有算法設(shè)計和分析，不僅僅是簡單套用軟件 - 敏感性分析詳細(xì) / 全面 - 共四十八頁2007B命題(mng t)背景 奧運相關(guān)的題目：(時代特性, 社會關(guān)注）讓運動員及時到達(dá)場館（車輛調(diào)度，路徑安排等） 應(yīng)急管理(gunl)（緊急疏散，應(yīng)急調(diào)度等）賽程安排（單一項目，多個項目）成績排名（如循環(huán)賽，體操或跳水等）技術(shù)類，如“劉翔的運動鞋”乘公交，看奧運：原名“自動問路機”方沛辰（吉大），吳孟達(dá)（國防科大）提出原擬作乙組題，似乎難度太大共四十八頁命題(mng t)背景 定位：公交路線選擇（查詢）模型與算法如何給數(shù)據(jù)？抽象數(shù)據(jù)實際數(shù)據(jù)

10、？（減小規(guī)模，不給地理信息）貌似簡單，實則不然數(shù)據(jù)處理（轉(zhuǎn)換）方面有一定難度換乘次數(shù)多時簡單搜索(su su)不易（計算復(fù)雜度高）換乘時間步行時間等需要考慮周全標(biāo)準(zhǔn)的最短路算法（如Dijkstra算法）并不適用共四十八頁乘公交(n jio)，看奧運公交線路選擇問題的自主查詢計算機系統(tǒng)：核心是線路選擇的模型與算法應(yīng)該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求1: 僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法 2: 同時考慮公汽與地鐵線路，解決以上問題3: 假設(shè)又知道(zh do)所有站點之間的步行時間，給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型 共四十八頁【附錄1】基本

11、參數(shù)設(shè)定相鄰公汽站平均行駛時間(包括停站時間)： 3分鐘相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鐘公汽換乘公汽平均耗時： 5分鐘(其中步行時間2分鐘)地鐵換乘地鐵平均耗時： 4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時： 7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時： 6分鐘(其中步行時間4分鐘)公汽票價：分為單一(dny)票價與分段計價兩種，標(biāo)記于線路后；其中分段計價的票價為：020站：1元；2140站：2元；40站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘）推論：換乘公汽等待分鐘，換乘地鐵等待分鐘【附錄2】公交線路及相關(guān)信息 （見數(shù)據(jù)文件）共四十八頁線路數(shù)據(jù)(shj

12、)中的問題線路數(shù)據(jù)中的異常或不明確(mngqu)之處，同學(xué)可根據(jù)自己的理解作出假設(shè)和處理，一般不會影響實例的計算結(jié)果個別線路相鄰站點名相同，可去掉其中一點或不作處理等L406未標(biāo)明是環(huán)線，是否將其當(dāng)作環(huán)線處理均可L290標(biāo)明是環(huán)線，但首尾站點分別為1477與1479，可將所有線路中1477與1479統(tǒng)一為1477后計算。同學(xué)也可以按照各自認(rèn)為合理的方式處理，包括不當(dāng)作環(huán)線，或?qū)?479改為1477，或在1479后增加1477，等等如果在假設(shè)中有明確約定，則環(huán)線單向或雙向發(fā)車均應(yīng)認(rèn)可（按單向發(fā)車作假設(shè)，計算結(jié)果可能差些） 共四十八頁對通過(tnggu)地鐵換乘的理解“假設(shè)同一地鐵站對應(yīng)的任意兩個

13、公汽站之間可以通過(tnggu)地鐵站換乘(無需支付地鐵費)”步行：公汽站地鐵站（通道）公汽站換乘耗時11min：步行4+4=8min; 等車3min第問（只考慮公汽）：可不考慮以上換乘有同學(xué)也考慮了如上換乘，只是不坐地鐵，應(yīng)該也可以此樣處理時，第問和第問的難度相近共四十八頁模型(mxng)的目標(biāo)多目標(biāo)優(yōu)化問題（至少考慮三方面）換乘次數(shù)最少(N)、費用最省(M)、時間最短(T)從該問題的實際背景來看，加權(quán)太合適 不少同學(xué)用層次分析法確定權(quán)不少同學(xué)計算時間的價值（平均收入工作時間）不同目標(biāo)組合(zh)的模型三個目標(biāo)按優(yōu)先級排序，組合成六個模型也可將某些目標(biāo)作為約束共四十八頁多數(shù)隊僅采用(ciyn

14、g)搜索法（70-80%?）直達(dá)(zhd)； 一次換乘； 二次換乘；ststs t求出所有線路；評價其目標(biāo)(容易計算)；選優(yōu)共四十八頁多數(shù)隊僅采用(ciyng)搜索法總體來看，技術(shù)含量較低（基本上是枚舉）幾乎沒有建模，完全只有算法實現(xiàn)，算法也沒什么創(chuàng)新一般只考慮不超過兩次換乘不少文章引用參考文獻(xiàn)作為依據(jù)，實用中似乎夠用 題目難度大大降低，模型不夠一般換乘作為了第一目標(biāo)，或作為一個最重要的約束任意次換乘時算法復(fù)雜度提高，難以處理(chl)結(jié)果不佳（如：從省時考慮，有些需次換乘）共四十八頁圖論模型(mxng)與最短路算法用圖論做的隊也不少，但往往考慮不周弧上賦權(quán)方式交代不清套用Dijkstra或F

15、loyd-Warshall算法，卻不清楚其原理及適用的問題需要建立一個帶權(quán)有向圖，節(jié)點(ji din)表示站點，有向弧表示前一站點能夠直達(dá)后一站點，弧上的權(quán)表示前一站點直達(dá)后一站點所需付出的代價(時間或費用)圖（網(wǎng)絡(luò)）如何描述和表示？基本要素：節(jié)點，有向弧（邊），弧上賦權(quán)鄰接矩陣；關(guān)聯(lián)矩陣（數(shù)學(xué)上處理方便，存儲量較大）鏈表（存儲量較小，計算機上處理方便）共四十八頁關(guān)聯(lián)矩陣(Incidence Matrix)表示法在線路(xinl)選擇問題中，當(dāng)從i可直達(dá)j時，定義弧(i,j)；其上的權(quán)可為或成本(時間或費用)；多重弧可只保留一條（弧上的權(quán)可取最小的成本，如時間或費用）G=(V，A)是一個(y

16、)簡單有向圖；|V|=n，|A|=m 重要數(shù)學(xué)性質(zhì)：關(guān)聯(lián)矩陣是全幺模矩陣圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個 的矩陣，即共四十八頁鄰接矩陣(Adjacency Matrix)表示法圖G=(V，A)的鄰接矩陣C是如下(rxi)定義的：C是一個 的0-1矩陣，即在線路選擇問題(wnt)中，當(dāng)從i可直達(dá)j時，定義弧(i,j)；其上的權(quán)可為或成本(時間或費用)G=(V，A)是一個簡單有向圖；|V|=n，|A|=m 有向圖的“傳遞閉包算法”(可用于一般二元關(guān)系)權(quán)取0-1時，C(0)=C可稱為直達(dá)矩陣 ；C(1)=C*C 為次可達(dá)矩陣；C(2)=C(1)*C 為2次可達(dá)矩陣；共四十八頁鏈表

17、（鄰接(ln ji)表）表示法 122345283904602403053036470單向(dn xin)鏈表(指針數(shù)組) A(1)=2,3A(2)=4A(3)=2A(4)=3,5A(5)=3,412345共四十八頁Dijkstra算法(sun f)（標(biāo)號算法(sun f)，1959）STEP1. 如果S=V, 則uj為節(jié)點s到節(jié)點j的最短路路長(最短路可以通過數(shù)組pred所記錄的信息反向(fn xin)追蹤獲得), 結(jié)束.否則繼續(xù). STEP0. (初始化) 令S= ，=V， ；對V 中的頂點j(j s)令初始距離標(biāo)號 . STEP2. 從 中找到距離標(biāo)號最小的節(jié)點i，把它從 刪除，加入S.

18、 對于所有從i出發(fā)的弧 , 若 ，則令 轉(zhuǎn)STEP1. 特點：1. 算法求出從源點s到所有點的最短路長 2. 每點給一對標(biāo)號 (uj, predj)，uj是從s到j(luò)的最短路長；predj是從s到j(luò)的最短路中j點的前一點共四十八頁Example共四十八頁Dijkstra算法（標(biāo)號(bioho)設(shè)定算法）適用于正費用網(wǎng)絡(luò)：“分層”設(shè)定標(biāo)號永久標(biāo)號：S中的點，uj是最短路(dunl)長臨時標(biāo)號；其他點， uj是只通過S中的點的最短路長對于稠密網(wǎng)絡(luò)，這是求解最短路問題可能達(dá)到的最小的復(fù)雜度,因為任何算法都至少必須對每條弧考慮一次.對于稀疏網(wǎng)絡(luò)，利用各種形式的堆（Heap），其復(fù)雜度可降為 或 等算法復(fù)

19、雜度O( n2+m)：如鏈表或鄰接矩陣實現(xiàn)找最小標(biāo)號點修改標(biāo)號共四十八頁特點：求所有點對間最短路基本思想：逐步逼近，迭代(di di)求解最短路方程: O(n3)Floyd-Warshall算法 （標(biāo)號(bioho)修正算法，1962)臨時標(biāo)號 是不通過k，k+1，,n 節(jié)點(i,j 除外)時從節(jié)點i到節(jié)點j的最短路路長. 共四十八頁Floyd-Warshall算法的具體(jt)實現(xiàn): O(n3)由于要記錄所有節(jié)點之間最短路的信息(xnx), 所以這里我們要用一個二維數(shù)組P； 可依據(jù)P, 采用“正向追蹤”的方式得到最短路. STEP2：如果k=n, 結(jié)束; 否則轉(zhuǎn)STEP1. STEP0: k

20、=0. 對于所有節(jié)點i和j: 令 ， , ( ，若節(jié)點i和j之間沒有弧, 認(rèn)為 ) . STEP1: k=k+1. 對于所有節(jié)點i和j: 若 , 令 , ; 否則令 , . 共四十八頁Floyd-Warshall算法(sun f)的矩陣迭代法實現(xiàn)：O(n4)令D為權(quán)矩陣(直達(dá)(zhd)最短路長)Dm為正好經(jīng)過m條弧從i到j(luò)的最短路長共四十八頁問題(wnt)1和2的一種具體建模方法(賦權(quán))在線路選擇(xunz)問題中，當(dāng)從i可直達(dá)j時（同為公汽或地鐵站點），定義弧(i,j)；其上的權(quán)為lij表示由i直達(dá)j付出的代價，可以為時間或費用 (不包括換乘代價；多條線路可達(dá)時只保留最小代價)初始等車時間2

21、(3)min也不包括在內(nèi)，最后結(jié)果可加上注意：D=D(0)不是對稱矩陣(“直達(dá)矩陣”)dij(0)=dij共四十八頁問題的一種(y zhn)具體建模方法i站點是公汽站點，j站點為地鐵站點：（1）若j站點對應(yīng)(duyng)的所有換乘(公汽)站點k，均不能從i直達(dá)(不在i站點所在公汽線路L上)，則dij(0) =. （2）若j站點對應(yīng)的換乘站點(k), 可從i站點直達(dá)k，則費用為dij(0) = dik(0)；對于時間則需要加上k到j(luò)的步行時間. (若有多種選擇，取最小成本者即可)ikj共四十八頁問題(wnt)的一種具體建模方法j站點是公汽站點，i站點為地鐵站點：（1）若從i站點對應(yīng)的任何(rnh

22、)換乘(公汽)站點k，均不能直達(dá)j站點，則dij(0) =. （2）若從i站點對應(yīng)的換乘(公汽)站點k，能直達(dá)j站點， 則費用為dij(0) = dkj(0)；對于時間則需要加上i到k的步行時間. ikj共四十八頁問題(wnt)：最小費用或時間 定義(dngy)矩陣算子“”如下：設(shè)A、B均為n階方陣， C = A B (考慮換乘代價)當(dāng)考慮費用矩陣之間的運算時，表示在k的換乘時間 當(dāng)考慮時間矩陣之間的運算時， D(k)= D(k-1) D 表示k次換乘的最低代價(費用或時間) 該算法大體相當(dāng)于求最短路的Floyd-Warshall算法，但考慮了換乘因素，可稱為改進(jìn)Floyd-Warshall算

23、法 類似地,通過修改Dijkstra算法求解也可共四十八頁問題：最小費用(fi yong)或時間i,j,k表示(biosh)換乘時間 i = j 或k = i，j時，i,j,k = 0其他情形：若不可換乘(當(dāng)i ，j為公汽站點而k為地鐵站點，或者i ，j為地鐵站點而k為公汽站點時)，則 i,j,k = 0若可換乘，則k這只是等待時間，因為步行時間已在D中考慮了ij共四十八頁第問：已知所有(suyu)站點間步行時間多數(shù)隊沒有給出一般(ybn)模型, 而只考慮最多一次換乘多數(shù)隊的想法：假設(shè)“起點步行”，“換乘步行”，“終點步行”三種模式，限定步行最大時間后搜索ikj共四十八頁其他：最短路問題(wn

24、t)的線性規(guī)劃模型xij表示(biosh)?。╥，j）是否位于s-t路上：當(dāng)xij =1時，表示?。╥，j）位于s-t路上，當(dāng)xij =0時，表示?。╥，j）不在s-t路上. 關(guān)聯(lián)矩陣是全么模矩陣，因此0-1變量可以松弛為區(qū)間0,1中的實數(shù) 不含負(fù)圈，變量直接松弛為所有非負(fù)實數(shù)思考：為什么xij 可以不限定為0，1 (0-1規(guī)劃) ?共四十八頁最短路問題的線性規(guī)劃(xin xn u hu)模型線性規(guī)劃模型，應(yīng)該可以計算到比較大規(guī)模的問題有些隊寫出了上述模型，但并未用該模型求解可能需要強大的優(yōu)化軟件，數(shù)據(jù)(shj)輸入工作量也較大換乘代價不易考慮（網(wǎng)絡(luò)上的權(quán)不易定義，或不具可加性） 有些同學(xué)提到動態(tài)規(guī)劃, 但要么與這