數(shù)學建模之運籌學.ppt

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