數(shù)學(xué)建模之運(yùn)籌學(xué).ppt

第一講 數(shù)學(xué)建模簡(jiǎn)介及數(shù)學(xué)規(guī)劃模型 Introduction of MM and Mathematical Programming Model,Network Programming,數(shù)學(xué)建模 Mathematical Modeling,數(shù)學(xué)建模簡(jiǎn)介,一般地，數(shù)學(xué)模型可以描述為，對(duì)于現(xiàn)實(shí)世界的一個(gè)特定對(duì)象，為了一個(gè)特定目的，根據(jù)特有的內(nèi)在規(guī)律，作出一些必要的簡(jiǎn)化假設(shè)，運(yùn)用適當(dāng)?shù)臄?shù)學(xué)工具，得到的一個(gè)數(shù)學(xué)結(jié)構(gòu)。 把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題加以提煉，抽象為數(shù)學(xué)模型，求出模型的解，驗(yàn)證模型的合理性，并用該數(shù)學(xué)模型所提供的解答來(lái)解釋現(xiàn)實(shí)問(wèn)題，我們把數(shù)學(xué)知識(shí)的這一應(yīng)用過(guò)程稱為數(shù)學(xué)建模。 數(shù)學(xué)模型或者能解釋特定現(xiàn)象的現(xiàn)實(shí)狀態(tài)，或者能預(yù)測(cè)到對(duì)象的未來(lái)狀況，或者能提供處理對(duì)象的最優(yōu)決策或控制。,數(shù)學(xué)模型的分類,1、按模型的應(yīng)用領(lǐng)域分類： 生物數(shù)學(xué)模型 醫(yī)學(xué)數(shù)學(xué)模型 地質(zhì)數(shù)學(xué)模型 數(shù)量經(jīng)濟(jì)學(xué)模型 數(shù)學(xué)社會(huì)學(xué)模型 2、按是否考慮隨機(jī)因素分類： 確定性模型 隨機(jī)性模型 3、按是否考慮模型的變化分類： 靜態(tài)模型 動(dòng)態(tài)模型,4、按應(yīng)用離散方法或連續(xù)方法分類： 離散模型 連續(xù)模型 5、按建立模型的數(shù)學(xué)方法分類： 幾何模型 微分方程模型 圖論模型 規(guī)劃論模型 馬氏鏈模型,6、按人們對(duì)是物發(fā)展過(guò)程的了解程度分類： （1）白箱模型：指那些內(nèi)部規(guī)律比較清楚的模 型。如力學(xué)、 熱學(xué)、電學(xué)以及相關(guān)的工程技 術(shù)問(wèn)題。 （2）灰箱模型：指那些內(nèi)部規(guī)律尚不十分清楚， 在建立和改 善模型方面都還不同程度地有許多 工作要做的問(wèn)題。如 氣象學(xué)、生態(tài)學(xué)經(jīng)濟(jì)學(xué)等領(lǐng)域的模型。 （3）黑箱模型：指一些其內(nèi)部規(guī)律還很少為人們 所知的現(xiàn)象。 如生命科學(xué)、社會(huì)科學(xué)等方面的問(wèn)題。但由于因素眾多、 關(guān)系復(fù)雜，也可簡(jiǎn)化為灰箱模型來(lái)研究。,數(shù)學(xué)建模的幾個(gè)過(guò)程,1、模型準(zhǔn)備 2、模型假設(shè) 3、模型建立 4、模型構(gòu)成 5、模型求解 6、模型分析 7、模型檢驗(yàn) 8、模型應(yīng)用,模型準(zhǔn)備,了解實(shí)際背景,明確建模目的,搜集有關(guān)信息,掌握對(duì)象特征,形成一個(gè) 比較清晰 的問(wèn)題,模型假設(shè) 針對(duì)問(wèn)題特點(diǎn)和建模目的 作出合理的、簡(jiǎn)化的假設(shè) 在合理與簡(jiǎn)化之間作出折中,模型建立,用數(shù)學(xué)的語(yǔ)言、符號(hào)描述問(wèn)題 發(fā)揮想像力使用類比法 盡量采用簡(jiǎn)單的數(shù)學(xué)工具,各種數(shù)學(xué)方法、軟件和計(jì)算機(jī)技術(shù),如結(jié)果的誤差分析、統(tǒng)計(jì)分析、模型對(duì)數(shù)據(jù)的穩(wěn)定性分析,模型求解,模型分析,模型檢驗(yàn) 與實(shí)際現(xiàn)象、數(shù)據(jù)比較，檢驗(yàn)?zāi)Ｐ偷暮侠硇浴⑦m用性,模型應(yīng)用,數(shù)學(xué)建模有助于培養(yǎng)以下幾個(gè)方面的素質(zhì)和能力：,數(shù)學(xué)素質(zhì)和能力 計(jì)算機(jī)應(yīng)用能力 論文寫(xiě)作能力 團(tuán)隊(duì)合作精神和進(jìn)行協(xié)調(diào)的組織能力 培養(yǎng)想象能力 發(fā)展觀察力，形成洞察力 勇于參與的競(jìng)爭(zhēng)意識(shí)和不怕困難、奮力攻關(guān)的頑強(qiáng)意志,為培養(yǎng)和選拔優(yōu)秀的數(shù)學(xué)人才，世界各國(guó)有各種不同形式不同層次的數(shù)學(xué)競(jìng)賽. 傳統(tǒng)的數(shù)學(xué)競(jìng)賽只局限于演繹、推理等純數(shù)學(xué)形式，它不能培養(yǎng)和發(fā)展學(xué)生運(yùn)用數(shù)學(xué)知識(shí)解決實(shí)際問(wèn)題的能力，不能滿足科學(xué)技術(shù)飛速發(fā)展的時(shí)代需要. 從1983年起，在美國(guó)就有一些有識(shí)之士開(kāi)始探討組織一項(xiàng)應(yīng)用數(shù)學(xué)方面的競(jìng)賽的可能性.,1985年美國(guó)第一屆大學(xué)生數(shù)學(xué)建模競(jìng)賽（mathematical competition in modeling） 1988年改為mathematical contest in modeling 簡(jiǎn)稱MCM. 由美國(guó)工業(yè)與應(yīng)用數(shù)學(xué)會(huì)和美國(guó)運(yùn)籌學(xué)會(huì)聯(lián)合舉辦. 1985年起每年舉行一屆，一般在每年的二月下旬或三月初的某個(gè)星期五或星期日舉行. 美國(guó)競(jìng)賽評(píng)出Outstanding, Meritorious, Honorable Mention及Successful Participation等級(jí)別.,1989年北京的三所大學(xué)組隊(duì)參加美國(guó)的MCM競(jìng)賽,此后我國(guó)的參賽隊(duì)伍越來(lái)越多. 19921993年中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)（CSIAM）舉辦了兩次中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽. 1994年起，由國(guó)家教委（教育部）高教司和中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)共同于每年9月舉辦，1999年開(kāi)始設(shè)立大專組的競(jìng)賽.,無(wú)論是美國(guó)還是我國(guó)大學(xué)本科組數(shù)學(xué)建模競(jìng)賽題每年都是兩道，參賽隊(duì)從中任選一道題目. 一般來(lái)說(shuō)其中一道是連續(xù)型，另一道是離散型；或者一道是開(kāi)放型的，另一道是嚴(yán)謹(jǐn)型的. 競(jìng)賽內(nèi)容或題目是由工程技術(shù)、管理科學(xué)中的實(shí)際問(wèn)題簡(jiǎn)化而成，留有充分余地供參賽者發(fā)揮其聰明才智和創(chuàng)造精神. 競(jìng)賽形式為三名學(xué)生組成一隊(duì)，可以自由地收集資料、調(diào)查研究，使用計(jì)算機(jī)、因特網(wǎng)和任何軟件，在三天時(shí)間內(nèi)分工合作完成一篇論文.評(píng)獎(jiǎng)標(biāo)準(zhǔn)為模型假設(shè)的合理性、建模的創(chuàng)造性、結(jié)果的準(zhǔn)確性和文字表述的清晰程度.,初等模型,一輛汽車(chē)在拐彎時(shí)急剎車(chē)，結(jié)果沖到路邊的溝里（見(jiàn)下圖），交通警察立即趕到了事故現(xiàn)場(chǎng)。司機(jī)申辯說(shuō)，當(dāng)他進(jìn)入彎道時(shí)剎車(chē)失靈，他還一口咬定，進(jìn)入彎道其車(chē)速為每小時(shí)英里（這是該路的速度上限，約合每秒.米）。警察驗(yàn)車(chē)時(shí)證實(shí)該車(chē)的制動(dòng)器在事故發(fā)生時(shí)確實(shí)失靈，然而，司機(jī)所說(shuō)的車(chē)速是否真實(shí)可信呢？,現(xiàn)在，讓我們幫警察計(jì)算一下司機(jī)所報(bào)速度的真實(shí)性。 連接剎車(chē)痕跡的初始點(diǎn)和終點(diǎn)，用x表示沿連線汽車(chē)橫向所走出的距離，用y表示豎直的距離，如下圖,上面的表中，我們給出了外側(cè)剎車(chē)痕跡的有關(guān)值，而且，經(jīng)過(guò)測(cè)量還 發(fā)現(xiàn)，該車(chē)并沒(méi)有偏離它所行駛的轉(zhuǎn)彎路線，也就是說(shuō)，它的車(chē)頭一直指 向切線方向?？梢约僭O(shè)，該車(chē)的重心是沿一個(gè)半徑為r的圓做圓周運(yùn)動(dòng)。 假設(shè)磨擦力作用在該車(chē)速度的法線方向上，并設(shè)汽車(chē)的速度v是一個(gè)常 數(shù)。顯然，磨擦力提供了向心力，設(shè)磨擦系數(shù)為, 則,其中m為汽車(chē)質(zhì)量.由上式易得,如何計(jì)算圓周半徑r？假設(shè)已知弦的長(zhǎng)度為c，弓形的高度為h，其圖如 下所示，由勾股定理知,由前面的表中代入近似數(shù)據(jù)c=33.27, h=3.55后，得 r=40.75米 根據(jù)實(shí)際路面與汽車(chē)輪胎的情況，可以測(cè)量出磨擦系數(shù)，經(jīng)過(guò)實(shí)際測(cè)試得到 g=8.175米秒 將此結(jié)果代入我們上面利用第二定律所得到的式子中，得 v18.25米秒 此結(jié)果比司機(jī)所報(bào)速度（17.92米秒）略大。但是，我們不得不考慮計(jì)算半徑r及測(cè)試時(shí)的誤差。如果誤差允許在以內(nèi)，無(wú)疑，此計(jì)算結(jié)果對(duì)司機(jī)是相當(dāng)有利的。,椅子能在不平的地面上放穩(wěn)嗎？,把四只腳的椅子往不平的地面上一放，通常只有三只腳著地，放不穩(wěn)，然而有人認(rèn)為只要稍挪動(dòng)幾次，就可以四腳著地，放穩(wěn)了，對(duì)嗎？,問(wèn)題分析 通常三只腳著地 放穩(wěn)的標(biāo)準(zhǔn): 四只腳著地 四條腿一樣長(zhǎng)，椅腳與地面點(diǎn)接觸， 四腳連線呈正方形; 地面高度連續(xù)變化，可視為數(shù)學(xué)上的連 續(xù)曲面; 地面相對(duì)平坦，使椅子在任意位置至少三只腳 同時(shí)著地。,模型假設(shè),建立模型,用數(shù)學(xué)語(yǔ)言把椅子位置和四只腳著地的關(guān)系表示出來(lái).,椅子位置,利用正方形(椅腳連線)的對(duì)稱性,用(對(duì)角線與x軸的夾角)表示椅子位置,四只腳著地,椅腳與地面距離為零,距離是的函數(shù),四個(gè)距離(四只腳),兩個(gè)距離,正方形ABCD 繞O點(diǎn)旋轉(zhuǎn),A,C 兩腳與地面距離之和記為f(),B,D 兩腳與地面距離之和記為g(),用數(shù)學(xué)語(yǔ)言把椅子位置和四只腳著地的關(guān)系表示出來(lái).,f() , g()是連續(xù)函數(shù),對(duì)任意, f(), g()至少一個(gè)為0,數(shù)學(xué)問(wèn)題,已知： f() , g()是連續(xù)函數(shù) ; 對(duì)任意， f() g()=0 ; 且 g(0)=0， f(0) 0. 證明：存在0，使f(0) = g(0) = 0.,地面為連續(xù)曲面,椅子在任意位置至少三只腳著地,模型求解,將椅子旋轉(zhuǎn)900，對(duì)角線AC和BD互換. 由g(0)=0， f(0) 0 ，知f(/2)=0 , g(/2)0. 令h()= f()g(), 則h(0)0和h(/2)0. 由 f, g的連續(xù)性知 h為連續(xù)函數(shù), 據(jù)連續(xù)函數(shù)的基本性質(zhì), 必存在0 , 使h(0)=0, 即f(0) = g(0) .因?yàn)閒() g()=0, 所以f(0) = g(0) = 0.,評(píng)注和思考,建模的關(guān)鍵 :,和 f(), g()的確定.,模型假設(shè)中四腳呈正方形不是本質(zhì)的,讀者可考慮長(zhǎng)方形的情形.,數(shù)學(xué)規(guī)劃模型,實(shí)際問(wèn)題中 的優(yōu)化模型,x決策變量,f(x)目標(biāo)函數(shù),gi(x)0約束條件,多元函數(shù)條件極值,決策變量個(gè)數(shù)n和 約束條件個(gè)數(shù)m較大,最優(yōu)解在可行域 的邊界上取得,重點(diǎn)在模型的建立和結(jié)果的分析,無(wú)約束優(yōu)化 線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃 多目標(biāo)規(guī)劃 動(dòng)態(tài)規(guī)劃等等,線性規(guī)劃,設(shè)每月生產(chǎn)小、中、大型汽車(chē)的數(shù)量分別為x1, x2, x3,汽車(chē)廠生產(chǎn)計(jì)劃,模型建立,線性規(guī)劃模型(LP),模型求解,3） 模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。,OBJECTIVE FUNCTION VALUE 1) 632.2581 VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.003226,1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值632.2581相差不大。,2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過(guò)比較可能得到更優(yōu)的解。,但必須檢驗(yàn)它們是否滿足約束條件。為什么？,結(jié)果為小數(shù)，怎么辦？,IP可用LINDO直接求解,整數(shù)規(guī)劃(Integer Programming,簡(jiǎn)記IP),“gin 3”表示“前3個(gè)變量為整數(shù)”，等價(jià)于： gin x1 gin x2 gin x3,IP 的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632,max 2x1+3x2+4x3 st 1.5x1+3x2+5x3600 280x1+250x2+400x360000 end gin 3,OBJECTIVE FUNCTION VALUE 1) 632.0000 VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000,模型求解,IP 結(jié)果輸出,其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：,方法1：分解為8個(gè)LP子模型,汽車(chē)廠生產(chǎn)計(jì)劃,若生產(chǎn)某類汽車(chē)，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。,x1,x2, x3=0 或 80,x1=80，x2= 150，x3=0，最優(yōu)值z(mì)=610,LINDO中對(duì)0-1變量的限定： int y1 int y2 int y3,方法2：引入0-1變量，化為整數(shù)規(guī)劃,M為大的正數(shù)，可取1000,OBJECTIVE FUNCTION VALUE 1) 610.0000 VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生產(chǎn)某類汽車(chē)，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。,x1=0 或 80,最優(yōu)解同前,NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO, MATLAB)，但是其結(jié)果常依賴于初值的選擇。,方法3：化為非線性規(guī)劃,非線性規(guī)劃（Non- Linear Programming，簡(jiǎn)記NLP）,實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。,若生產(chǎn)某類汽車(chē)，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。,x1=0 或 80,非線性規(guī)劃,某公司有6個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系a, b表示，距離單位：千米）及水泥用量d（噸）如下：,為保障供應(yīng)，需建兩個(gè)料場(chǎng)，日儲(chǔ)量各為20噸，問(wèn)應(yīng)建在何處，使總的噸千米數(shù)最小，并試制定每天的供應(yīng)計(jì)劃.,一個(gè)有約束條件的非線性規(guī)劃問(wèn)題的解法大致分為： 用線性規(guī)劃、二次規(guī)劃來(lái)逐步逼近非線性規(guī)劃的方法； 對(duì)約束非線性規(guī)劃問(wèn)題不預(yù)先作轉(zhuǎn)換的直接求解方法，如隨機(jī)試驗(yàn)法等； 對(duì)約束非線性規(guī)劃問(wèn)題不預(yù)先作轉(zhuǎn)換，直接進(jìn)行處理的分析方法，如可行方向法、凸單純形法等； 把約束非線性規(guī)劃問(wèn)題轉(zhuǎn)換為無(wú)約束非線性規(guī)劃來(lái)求解的方法，如SUMT外點(diǎn)法、SUMT內(nèi)點(diǎn)法、乘子法等。,整數(shù)規(guī)劃,為了選修課程門(mén)數(shù)最少，應(yīng)學(xué)習(xí)哪些課程 ？,選課策略,選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程 ？,0-1規(guī)劃模型,決策變量,目標(biāo)函數(shù),xi=1 選修課號(hào)i 的課程（xi=0 不選）,選修課程總數(shù)最少,約束條件,最少2門(mén)數(shù)學(xué)課，3門(mén)運(yùn)籌學(xué)課， 2門(mén)計(jì)算機(jī)課。,先修課程要求,最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為0；6門(mén)課程，總學(xué)分21,0-1規(guī)劃模型,約束條件,x3=1必有x1 = x2 =1,模型求解（LINDO）,學(xué)分最多,多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。,兩目標(biāo)(多目標(biāo))規(guī)劃,討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？,課程最少,以學(xué)分最多為目標(biāo)，不管課程多少。,以課程最少