數(shù)學(xué)建模講座CUMCM2007B賽題分析.ppt

數(shù)學(xué)建模講座 CUMCM-2007B 賽題分析,謝金星 100084北京清華大學(xué)數(shù)學(xué)科學(xué)系 Tel:Fax:Email: /jxie,簡(jiǎn)要提綱,應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模 - 建模及建模競(jìng)賽的意義 競(jìng)賽評(píng)閱標(biāo)準(zhǔn) - 一般原則及主要問(wèn)題 優(yōu)化模型的創(chuàng)新 - 2007B題分析,數(shù)學(xué)知識(shí) 數(shù)學(xué)技巧, 隨機(jī)數(shù)學(xué) 代數(shù)與幾何 微積分,數(shù)學(xué)：幾個(gè)層次的理解,數(shù)學(xué)建模：實(shí)際與數(shù)學(xué)之間的橋梁,實(shí)際問(wèn)題,數(shù)學(xué),Mathematical Modeling,現(xiàn)實(shí)對(duì)象的信息,數(shù)學(xué)模型,現(xiàn)實(shí)對(duì)象的解答,數(shù)學(xué)模型的解答,(歸納),(演繹),數(shù)學(xué)建模的全過(guò)程,美國(guó)MCM+ICM競(jìng)賽規(guī)模,我國(guó)CUMCM競(jìng)賽規(guī)模,學(xué)生歡迎：“一次參賽，終身受益” 研究生導(dǎo)師們的認(rèn)同 企業(yè)界的認(rèn)同贊助 教育改革同行的認(rèn)同：“成功范例” 國(guó)際同行的認(rèn)同,競(jìng)賽的反響,IBM 中國(guó)研究中心- 招聘條件 Position title: Business Optimization(BJ) 1Background 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. Experience in eclipse or programming model / architecture design is a plus -Feb. 18, 2006, /cn/ibm/crl/careers/condition.shtml,競(jìng)賽的反響（一例）,簡(jiǎn)要提綱,應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模 - 建模及建模競(jìng)賽的意義 競(jìng)賽評(píng)閱標(biāo)準(zhǔn) - 一般原則及主要問(wèn)題 創(chuàng)新能力培養(yǎng) -幾個(gè)例子（結(jié)合優(yōu)化模型）,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ú)樹(shù)一幟、標(biāo)新立異，但要合理,假設(shè)的合理性，建模的創(chuàng)造性， 結(jié)果的正確性，表述的清晰性。,正確性：不強(qiáng)調(diào)與“參考答案”的一致性和結(jié)果的精度； 好方法的結(jié)果一般比較好；但不一定是最好的,合理性：關(guān)鍵假設(shè)；不欣賞羅列大量無(wú)關(guān)緊要的假設(shè),CUMCM評(píng)閱標(biāo)準(zhǔn): 一些常見(jiàn)問(wèn)題,有的論文過(guò)于簡(jiǎn)單，該交代的內(nèi)容省略了，難以看懂,有的隊(duì)羅列一系列假設(shè)或模型，又不作比較、評(píng)價(jià)， 希望碰上“參考答案”或“評(píng)閱思路”，弄巧成拙,數(shù)學(xué)模型最好明確、合理、簡(jiǎn)潔： 有些論文不給出明確的模型，只是根據(jù)賽題的情況， 實(shí)際上是用“湊”的方法給出結(jié)果，雖然結(jié)果大致是對(duì) 的，沒(méi)有一般性，不是數(shù)學(xué)建模的正確思路。,有的論文參考文獻(xiàn)不全，或引用他人結(jié)果不作交代,從論文評(píng)閱看學(xué)生參加競(jìng)賽中的問(wèn)題,吃透題意方面不足，沒(méi)有抓住和解決主要問(wèn)題； 就事論事，形成數(shù)學(xué)模型的意識(shí)和能力欠缺； 對(duì)所用方法一知半解，不管具體條件，套用現(xiàn)成的方法，導(dǎo)致錯(cuò)誤； 對(duì)結(jié)果的分析不夠，怎樣符合實(shí)際考慮不周； 寫(xiě)作方面的問(wèn)題(摘要、簡(jiǎn)明、優(yōu)缺點(diǎn)、參考文獻(xiàn)); 隊(duì)員之間合作精神差，孤軍奮戰(zhàn)； 依賴心理重，甚至違紀(jì)（指導(dǎo)教師、 網(wǎng)絡(luò)）。,參加競(jìng)賽前的準(zhǔn)備,了解競(jìng)賽章程等相關(guān)信息； 掌握數(shù)學(xué)建模的基本方法（學(xué)過(guò)“數(shù)學(xué)模型”或“數(shù)學(xué)實(shí)驗(yàn)”課最好，自學(xué)一些基本內(nèi)容也可以）； 掌握基本的數(shù)學(xué)軟件（Matlab/Mathematica；LINGO；如能掌握SAS/JMP統(tǒng)計(jì)軟件更好）； 訓(xùn)練規(guī)范的科技論文寫(xiě)作/表達(dá)能力 (摘要、正文、優(yōu)缺點(diǎn)、參考文獻(xiàn)及引用等); 試做幾道以前的賽題； 培養(yǎng)合作精神。,簡(jiǎn)要提綱,應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模 - 建模及建模競(jìng)賽的意義 競(jìng)賽評(píng)閱標(biāo)準(zhǔn) - 一般原則及主要問(wèn)題 創(chuàng)新能力培養(yǎng) - 2007B分析,優(yōu)化問(wèn)題三要素：決策變量；目標(biāo)函數(shù)；約束條件,優(yōu)化問(wèn)題的一般形式,有人統(tǒng)計(jì)： 優(yōu)化問(wèn)題占CUMCM賽題的一半以上（1/32/3）,建模時(shí)需要注意的幾個(gè)基本問(wèn)題,1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量 2、盡量使用光滑優(yōu)化，減少非光滑約束的個(gè)數(shù) 如：盡量少使用絕對(duì)值、符號(hào)函數(shù)、多個(gè)變量求最大/最小值、四舍五入、取整函數(shù)等 3、盡量使用線性模型，減少非線性約束和非線性變量的個(gè)數(shù) （如x/y 5 改為x5y） 4、合理設(shè)定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級(jí)要適當(dāng) (如小于103),優(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ì) / 全面 - ,2007B命題背景,奧運(yùn)相關(guān)的題目：(時(shí)代特性, 社會(huì)關(guān)注） 讓運(yùn)動(dòng)員及時(shí)到達(dá)場(chǎng)館（車(chē)輛調(diào)度，路徑安排等） 應(yīng)急管理（緊急疏散，應(yīng)急調(diào)度等） 賽程安排（單一項(xiàng)目，多個(gè)項(xiàng)目） 成績(jī)排名（如循環(huán)賽，體操或跳水等） 技術(shù)類(lèi)，如“劉翔的運(yùn)動(dòng)鞋” 乘公交，看奧運(yùn)：原名“自動(dòng)問(wèn)路機(jī)” 方沛辰（吉大），吳孟達(dá)（國(guó)防科大）提出 原擬作乙組題，似乎難度太大,命題背景,定位：公交路線選擇（查詢）模型與算法 如何給數(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ùn),公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)：核心是線路選擇的模型與算法 應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求 1: 僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法 2: 同時(shí)考慮公汽與地鐵線路，解決以上問(wèn)題 3: 假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，給出任意兩站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型,【附錄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à)為：020站：1元；2140站：2元；40站以上：3元 地鐵票價(jià)：3元（無(wú)論地鐵線路間是否換乘） 推論：換乘公汽等待分鐘，換乘地鐵等待分鐘 【附錄2】公交線路及相關(guān)信息 （見(jiàn)數(shù)據(jù)文件）,線路數(shù)據(jù)中的問(wèn)題,線路數(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ā)車(chē)均應(yīng)認(rèn)可（按單向發(fā)車(chē)作假設(shè)，計(jì)算結(jié)果可能差些）,對(duì)通過(guò)地鐵換乘的理解,“假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過(guò)地鐵站換乘(無(wú)需支付地鐵費(fèi))” 步行：公汽站地鐵站（通道）公汽站 換乘耗時(shí)11min：步行4+4=8min; 等車(chē)3min 第問(wèn)（只考慮公汽）：可不考慮以上換乘 有同學(xué)也考慮了如上換乘，只是不坐地鐵，應(yīng)該也可以 此樣處理時(shí)，第問(wèn)和第問(wèn)的難度相近,模型的目標(biāo),多目標(biāo)優(yōu)化問(wèn)題（至少考慮三方面） 換乘次數(shù)最少(N)、費(fèi)用最省(M)、時(shí)間最短(T) 從該問(wèn)題的實(shí)際背景來(lái)看，加權(quán)太合適 不少同學(xué)用層次分析法確定權(quán) 不少同學(xué)計(jì)算時(shí)間的價(jià)值（平均收入工作時(shí)間） 不同目標(biāo)組合的模型 三個(gè)目標(biāo)按優(yōu)先級(jí)排序，組合成六個(gè)模型 也可將某些目標(biāo)作為約束,多數(shù)隊(duì)僅采用搜索法（70-80%?）,直達(dá)； 一次換乘； 二次換乘； ,s t,s t,s t,求出所有線路；評(píng)價(jià)其目標(biāo)(容易計(jì)算)；選優(yōu),多數(shù)隊(duì)僅采用搜索法,總體來(lái)看，技術(shù)含量較低（基本上是枚舉） 幾乎沒(méi)有建模，完全只有算法實(shí)現(xiàn)，算法也沒(méi)什么創(chuàng)新 一般只考慮不超過(guò)兩次換乘 不少文章引用參考文獻(xiàn)作為依據(jù)，實(shí)用中似乎夠用 題目難度大大降低，模型不夠一般 換乘作為了第一目標(biāo)，或作為一個(gè)最重要的約束 任意次換乘時(shí)算法復(fù)雜度提高，難以處理 結(jié)果不佳（如：從省時(shí)考慮，有些需次換乘）,圖論模型與最短路算法,用圖論做的隊(duì)也不少，但往往考慮不周 弧上賦權(quán)方式交代不清 套用Dijkstra或Floyd-Warshall算法，卻不清楚其原理及適用的問(wèn)題 需要建立一個(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ī)上處理方便）,關(guān)聯(lián)矩陣(Incidence Matrix)表示法,在線路選擇問(wèn)題中，當(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è) 的矩陣，即,鄰接矩陣(Adjacency Matrix)表示法,圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個(gè) 的0-1矩陣，即,在線路選擇問(wèn)題中，當(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á)矩陣；,鏈表（鄰接表）表示法,單向鏈表(指針數(shù)組),A(1)=2,3,A(2)=4,A(3)=2,A(4)=3,5,A(5)=3,4,Dijkstra算法（標(biāo)號(hào)算法，1959）,STEP1. 如果S=V, 則uj為節(jié)點(diǎn)s到節(jié)點(diǎn)j的最短路路長(zhǎng)(最短路可以通過(guò)數(shù)組pred所記錄的信息反向追蹤獲得), 結(jié)束.否則繼續(xù).,STEP0. (初始化) 令S= ，=V， ；對(duì)V 中的頂點(diǎn)j(j s)令初始距離標(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),Example,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是只通過(guò)S中的點(diǎn)的最短路長(zhǎng),對(duì)于稠密網(wǎng)絡(luò)，這是求解最短路問(wèn)題可能達(dá)到的最小的復(fù)雜度,因?yàn)槿魏嗡惴ǘ贾辽俦仨殞?duì)每條弧考慮一次. 對(duì)于稀疏網(wǎng)絡(luò)，利用各種形式的堆（Heap），其復(fù)雜度可降為 或 等,特點(diǎn)：求所有點(diǎn)對(duì)間最短路 基本思想：逐步逼近，迭代求解最短路方程: O(n3),Floyd-Warshall算法 （標(biāo)號(hào)修正算法，1962),臨時(shí)標(biāo)號(hào) 是不通過(guò)k，k+1，,n 節(jié)點(diǎn)(i,j 除外)時(shí)從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路路長(zhǎng).,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之間沒(méi)有弧, 認(rèn)為 ) .,STEP1: k=k+1. 對(duì)于所有節(jié)點(diǎn)i和j: 若 , 令 , ; 否則令 , .,Floyd-Warshall算法的 矩陣迭代法實(shí)現(xiàn)：O(n4),令D為權(quán)矩陣(直達(dá)最短路長(zhǎng)) Dm為正好經(jīng)過(guò)m條弧從i到j(luò)的最短路長(zhǎng),問(wèn)題1和2的一種具體建模方法(賦權(quán)),在線路選擇問(wè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à)) 初始等車(chē)時(shí)間2(3)min也不包括在內(nèi)，最后結(jié)果可加上 注意：D=D(0)不是對(duì)稱矩陣(“直達(dá)矩陣”),dij(0)=dij,問(wèn)題的一種具體建模方法,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í)間. (若有多種選擇，取最小成本者即可),i,k,j,問(wèn)題的一種具體建模方法,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í)間.,i,k,j,問(wèn)題：最小費(fèi)用或時(shí)間,定義矩陣算子“”如下：設(shè)A、B均為n階方陣， C = A B (考慮換乘代價(jià)),D(k)= D(k-1) D 表示k次換乘的最低代價(jià)(費(fèi)用或時(shí)間) 該算法大體相當(dāng)于求最短路的Floyd-Warshall算法，但考慮了換乘因素，可稱為改進(jìn)Floyd-Warshall算法 類(lèi)似地, 通過(guò)修改Dijkstra算法求解也可,問(wèn)題：最小費(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中考慮了,i,j,第問(wèn)：已知所有站點(diǎn)間步行時(shí)間,多數(shù)隊(duì)沒(méi)有給出一般模型, 而只考慮最多一次換乘 多數(shù)隊(duì)的想法：假設(shè)“起點(diǎn)步行”，“換乘步行”，“終點(diǎn)步行”三種模式，限定步行最大時(shí)間后搜索,i,k,j,其他：最短路問(wèn)題的線性規(guī)劃模型,xij表示?。╥，j）是否位于s-t