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

數(shù)學建模之運籌學第1頁，共68頁，2023年，2月20日，星期六數(shù)學建模簡介第2頁，共68頁，2023年，2月20日，星期六一般地，數(shù)學模型可以描述為，對于現(xiàn)實世界的一個特定對象，為了一個特定目的，根據(jù)特有的內(nèi)在規(guī)律，作出一些必要的簡化假設，運用適當?shù)臄?shù)學工具，得到的一個數(shù)學結構。把現(xiàn)實世界中的實際問題加以提煉，抽象為數(shù)學模型，求出模型的解，驗證模型的合理性，并用該數(shù)學模型所提供的解答來解釋現(xiàn)實問題，我們把數(shù)學知識的這一應用過程稱為數(shù)學建模。數(shù)學模型或者能解釋特定現(xiàn)象的現(xiàn)實狀態(tài)，或者能預測到對象的未來狀況，或者能提供處理對象的最優(yōu)決策或控制。

第3頁，共68頁，2023年，2月20日，星期六數(shù)學模型的分類1、按模型的應用領域分類：生物數(shù)學模型醫(yī)學數(shù)學模型地質(zhì)數(shù)學模型數(shù)量經(jīng)濟學模型數(shù)學社會學模型2、按是否考慮隨機因素分類：確定性模型隨機性模型3、按是否考慮模型的變化分類：靜態(tài)模型動態(tài)模型第4頁，共68頁，2023年，2月20日，星期六4、按應用離散方法或連續(xù)方法分類：離散模型連續(xù)模型5、按建立模型的數(shù)學方法分類：幾何模型微分方程模型圖論模型規(guī)劃論模型馬氏鏈模型第5頁，共68頁，2023年，2月20日，星期六6、按人們對是物發(fā)展過程的了解程度分類：（1）白箱模型：指那些內(nèi)部規(guī)律比較清楚的模型。如力學、熱學、電學以及相關的工程技術問題。（2）灰箱模型：指那些內(nèi)部規(guī)律尚不十分清楚，在建立和改善模型方面都還不同程度地有許多工作要做的問題。如氣象學、生態(tài)學經(jīng)濟學等領域的模型。（3）黑箱模型：指一些其內(nèi)部規(guī)律還很少為人們所知的現(xiàn)象。如生命科學、社會科學等方面的問題。但由于因素眾多、關系復雜，也可簡化為灰箱模型來研究。

第6頁，共68頁，2023年，2月20日，星期六數(shù)學建模的幾個過程

1、模型準備

2、模型假設

3、模型建立

4、模型構成

5、模型求解

6、模型分析

7、模型檢驗8、模型應用

第7頁，共68頁，2023年，2月20日，星期六模型準備了解實際背景明確建模目的搜集有關信息掌握對象特征形成一個比較清晰的‘問題’模型假設針對問題特點和建模目的作出合理的、簡化的假設在合理與簡化之間作出折中第8頁，共68頁，2023年，2月20日，星期六模型建立用數(shù)學的語言、符號描述問題發(fā)揮想像力使用類比法盡量采用簡單的數(shù)學工具各種數(shù)學方法、軟件和計算機技術如結果的誤差分析、統(tǒng)計分析、模型對數(shù)據(jù)的穩(wěn)定性分析模型求解模型分析第9頁，共68頁，2023年，2月20日，星期六模型檢驗

與實際現(xiàn)象、數(shù)據(jù)比較，檢驗模型的合理性、適用性模型應用第10頁，共68頁，2023年，2月20日，星期六數(shù)學建模有助于培養(yǎng)以下幾個方面的素質(zhì)和能力：數(shù)學素質(zhì)和能力計算機應用能力論文寫作能力團隊合作精神和進行協(xié)調(diào)的組織能力培養(yǎng)想象能力發(fā)展觀察力，形成洞察力勇于參與的競爭意識和不怕困難、奮力攻關的頑強意志第11頁，共68頁，2023年，2月20日，星期六為培養(yǎng)和選拔優(yōu)秀的數(shù)學人才，世界各國有各種不同形式不同層次的數(shù)學競賽.傳統(tǒng)的數(shù)學競賽只局限于演繹、推理等純數(shù)學形式，它不能培養(yǎng)和發(fā)展學生運用數(shù)學知識解決實際問題的能力，不能滿足科學技術飛速發(fā)展的時代需要.從1983年起，在美國就有一些有識之士開始探討組織一項應用數(shù)學方面的競賽的可能性.第12頁，共68頁，2023年，2月20日，星期六1985年美國第一屆大學生數(shù)學建模競賽（mathematicalcompetitioninmodeling）1988年改為mathematicalcontestinmodeling簡稱MCM.由美國工業(yè)與應用數(shù)學會和美國運籌學會聯(lián)合舉辦.1985年起每年舉行一屆，一般在每年的二月下旬或三月初的某個星期五或星期日舉行.美國競賽評出Outstanding,Meritorious,HonorableMention及SuccessfulParticipation等級別.第13頁，共68頁，2023年，2月20日，星期六1989年北京的三所大學組隊參加美國的MCM競賽,此后我國的參賽隊伍越來越多.1992－1993年中國工業(yè)與應用數(shù)學學會（CSIAM）舉辦了兩次中國大學生數(shù)學建模競賽.1994年起，由國家教委（教育部）高教司和中國工業(yè)與應用數(shù)學學會共同于每年9月舉辦，1999年開始設立大專組的競賽.第14頁，共68頁，2023年，2月20日，星期六無論是美國還是我國大學本科組數(shù)學建模競賽題每年都是兩道，參賽隊從中任選一道題目.一般來說其中一道是連續(xù)型，另一道是離散型；或者一道是開放型的，另一道是嚴謹型的.競賽內(nèi)容或題目是由工程技術、管理科學中的實際問題簡化而成，留有充分余地供參賽者發(fā)揮其聰明才智和創(chuàng)造精神.競賽形式為三名學生組成一隊，可以自由地收集資料、調(diào)查研究，使用計算機、因特網(wǎng)和任何軟件，在三天時間內(nèi)分工合作完成一篇論文.評獎標準為模型假設的合理性、建模的創(chuàng)造性、結果的準確性和文字表述的清晰程度.第15頁，共68頁，2023年，2月20日，星期六初等模型第16頁，共68頁，2023年，2月20日，星期六一輛汽車在拐彎時急剎車，結果沖到路邊的溝里（見下圖），交通警察立即趕到了事故現(xiàn)場。司機申辯說，當他進入彎道時剎車失靈，他還一口咬定，進入彎道其車速為每小時４０英里（這是該路的速度上限，約合每秒１７.９２米）。警察驗車時證實該車的制動器在事故發(fā)生時確實失靈，然而，司機所說的車速是否真實可信呢？第17頁，共68頁，2023年，2月20日，星期六

現(xiàn)在，讓我們幫警察計算一下司機所報速度的真實性。連接剎車痕跡的初始點和終點，用x表示沿連線汽車橫向所走出的距離，用y表示豎直的距離，如下圖第18頁，共68頁，2023年，2月20日，星期六

上面的表中，我們給出了外側剎車痕跡的有關值，而且，經(jīng)過測量還發(fā)現(xiàn)，該車并沒有偏離它所行駛的轉彎路線，也就是說，它的車頭一直指向切線方向。可以假設，該車的重心是沿一個半徑為r的圓做圓周運動。假設磨擦力作用在該車速度的法線方向上，并設汽車的速度v是一個常數(shù)。顯然，磨擦力提供了向心力，設磨擦系數(shù)為μ,則其中m為汽車質(zhì)量.由上式易得

如何計算圓周半徑r？假設已知弦的長度為c，弓形的高度為h，其圖如下所示，由勾股定理知第19頁，共68頁，2023年，2月20日，星期六

由前面的表中代入近似數(shù)據(jù)c=33.27,h=3.55后，得r=40.75米根據(jù)實際路面與汽車輪胎的情況，可以測量出磨擦系數(shù)，經(jīng)過實際測試得到g=8.175米／秒２

將此結果代入我們上面利用第二定律所得到的式子中，得v≈18.25米／秒此結果比司機所報速度（17.92米／秒）略大。但是，我們不得不考慮計算半徑r及測試時的誤差。如果誤差允許在１０％以內(nèi)，無疑，此計算結果對司機是相當有利的。

第20頁，共68頁，2023年，2月20日，星期六椅子能在不平的地面上放穩(wěn)嗎？

把四只腳的椅子往不平的地面上一放，通常只有三只腳著地，放不穩(wěn)，然而有人認為只要稍挪動幾次，就可以四腳著地，放穩(wěn)了，對嗎？第21頁，共68頁，2023年，2月20日，星期六問題分析

通常三只腳著地

放穩(wěn)的標準:四只腳著地

四條腿一樣長，椅腳與地面點接觸，四腳連線呈正方形;

地面高度連續(xù)變化，可視為數(shù)學上的連續(xù)曲面;

地面相對平坦，使椅子在任意位置至少三只腳同時著地。模型假設第22頁，共68頁，2023年，2月20日，星期六建立模型用數(shù)學語言把椅子位置和四只腳著地的關系表示出來.

椅子位置利用正方形(椅腳連線)的對稱性用(對角線與x軸的夾角)表示椅子位置

四只腳著地椅腳與地面距離為零距離是的函數(shù)xBADCOD′C′B′A′四個距離(四只腳)兩個距離正方形對稱性正方形ABCD繞O點旋轉A,C兩腳與地面距離之和記為f()B,D兩腳與地面距離之和記為g()第23頁，共68頁，2023年，2月20日，星期六用數(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ù)曲面

椅子在任意位置至少三只腳著地第24頁，共68頁，2023年，2月20日，星期六模型求解

將椅子旋轉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ù)的基本性質(zhì),必存在0,使h(0)=0,即f(0)=g(0).因為f()?g()=0,所以f(0)=g(0)=0.評注和思考建模的關鍵

:和f(),g()的確定.

模型假設中四腳呈正方形不是本質(zhì)的,讀者可考慮長方形的情形.第25頁，共68頁，2023年，2月20日，星期六數(shù)學規(guī)劃模型第26頁，共68頁，2023年，2月20日，星期六實際問題中的優(yōu)化模型x~決策變量f(x)~目標函數(shù)gi(x)0~約束條件多元函數(shù)條件極值

決策變量個數(shù)n和約束條件個數(shù)m較大

最優(yōu)解在可行域的邊界上取得

重點在模型的建立和結果的分析第27頁，共68頁，2023年，2月20日，星期六無約束優(yōu)化線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃多目標規(guī)劃動態(tài)規(guī)劃等等第28頁，共68頁，2023年，2月20日，星期六線性規(guī)劃第29頁，共68頁，2023年，2月20日，星期六設每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3汽車廠生產(chǎn)計劃

模型建立

小型中型大型現(xiàn)有量鋼材1.535600時間28025040060000利潤234線性規(guī)劃模型(LP)第30頁，共68頁，2023年，2月20日，星期六模型求解

3）

模型中增加條件：x1,x2,x3

均為整數(shù)，重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.516129

0.000000

X2167.741928

0.000000

X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.0032261）舍去小數(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ù)，怎么辦？第31頁，共68頁，2023年，2月20日，星期六IP可用LINDO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡記IP)“gin3”表示“前3個變量為整數(shù)”，等價于：ginx1ginx2ginx3IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=632

max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000

模型求解

IP結果輸出第32頁，共68頁，2023年，2月20日，星期六其中3個子模型應去掉，然后逐一求解，比較目標函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個LP子模型

汽車廠生產(chǎn)計劃若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z=610第33頁，共68頁，2023年，2月20日，星期六LINDO中對0-1變量的限定：inty1inty2inty3方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù)，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOST

X180.000000

-2.000000

X2150.000000-3.000000

X30.000000

-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

第34頁，共68頁，2023年，2月20日，星期六NLP雖然可用現(xiàn)成的數(shù)學軟件求解(如LINGO,MATLAB)，但是其結果常依賴于初值的選擇。

方法3：化為非線性規(guī)劃

非線性規(guī)劃（Non-LinearProgramming，簡記NLP）

實踐表明，本例僅當初值非常接近上面方法算出的最優(yōu)解時，才能得到正確的結果。

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。x1=0或

80x2=0或

80x3=0或

80第35頁，共68頁，2023年，2月20日，星期六非線性規(guī)劃第36頁，共68頁，2023年，2月20日，星期六

某公司有6個建筑工地要開工，每個工地的位置（用平面坐標系a,b表示，距離單位：千米）及水泥用量d（噸）如下：123456abd1.251.2538.750.7550.54.7545.755736.567.257.2511

為保障供應，需建兩個料場，日儲量各為20噸，問應建在何處，使總的噸千米數(shù)最小，并試制定每天的供應計劃.第37頁，共68頁，2023年，2月20日，星期六一個有約束條件的非線性規(guī)劃問題的解法大致分為：①

用線性規(guī)劃、二次規(guī)劃來逐步逼近非線性規(guī)劃的方法；②

對約束非線性規(guī)劃問題不預先作轉換的直接求解方法，如隨機試驗法等；③

對約束非線性規(guī)劃問題不預先作轉換，直接進行處理的分析方法，如可行方向法、凸單純形法等；④

把約束非線性規(guī)劃問題轉換為無約束非線性規(guī)劃來求解的方法，如SUMT外點法、SUMT內(nèi)點法、乘子法等。第38頁，共68頁，2023年，2月20日，星期六整數(shù)規(guī)劃第39頁，共68頁，2023年，2月20日，星期六為了選修課程門數(shù)最少，應學習哪些課程？

選課策略選修課程最少，且學分盡量多，應學習哪些課程？

課號課名學分所屬類別先修課要求1微積分5數(shù)學

2線性代數(shù)4數(shù)學

3最優(yōu)化方法4數(shù)學；運籌學微積分；線性代數(shù)4數(shù)據(jù)結構3數(shù)學；計算機計算機編程5應用統(tǒng)計4數(shù)學；運籌學微積分；線性代數(shù)6計算機模擬3計算機；運籌學計算機編程7計算機編程2計算機

8預測理論2運籌學應用統(tǒng)計9數(shù)學實驗3運籌學；計算機微積分；線性代數(shù)第40頁，共68頁，2023年，2月20日，星期六0-1規(guī)劃模型

決策變量

目標函數(shù)

xi=1~選修課號i的課程（xi=0~不選）

選修課程總數(shù)最少

約束條件課號課名所屬類別1微積分數(shù)學2線性代數(shù)數(shù)學3最優(yōu)化方法數(shù)學；運籌學4數(shù)據(jù)結構數(shù)學；計算機5應用統(tǒng)計數(shù)學；運籌學6計算機模擬計算機；運籌學7計算機編程計算機8預測理論運籌學9數(shù)學實驗運籌學；計算機最少2門數(shù)學課，3門運籌學課，2門計算機課。

第41頁，共68頁，2023年，2月20日，星期六先修課程要求最優(yōu)解：

x1=x2=x3=x6=x7=x9=1,其它為0；6門課程，總學分210-1規(guī)劃模型

約束條件x3=1必有x1=x2=1模型求解（LINDO）課號課名先修課要求1微積分

2線性代數(shù)

3最優(yōu)化方法微積分；線性代數(shù)4數(shù)據(jù)結構計算機編程5應用統(tǒng)計微積分；線性代數(shù)6計算機模擬計算機編程7計算機編程

8預測理論應用統(tǒng)計9數(shù)學實驗微積分；線性代數(shù)第42頁，共68頁，2023年，2月20日，星期六學分最多多目標優(yōu)化的處理方法：化成單目標優(yōu)化。兩目標(多目標)規(guī)劃

討論：選修課程最少，學分盡量多，應學習哪些課程？

課程最少

以學分最多為目標，不管課程多少。

以課程最少為目標，不管學分多少。最優(yōu)解如上，6門課程，總學分21。最優(yōu)解顯然是選修所有9門課程。第43頁，共68頁，2023年，2月20日，星期六多目標規(guī)劃

在課程最少的前提下以學分最多為目標。注意：最優(yōu)解不唯一！課號課名學分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結構35應用統(tǒng)計46計算機模擬37計算機編程28預測理論29數(shù)學實驗3LINDO無法告訴優(yōu)化問題的解是否唯一?？蓪9=1易為x6=1增加約束，以學分最多為目標求解。最優(yōu)解：

x1=x2=x3=x5=x7=x9=1,

其它為0；總學分由21增至22。第44頁，共68頁，2023年，2月20日，星期六多目標規(guī)劃

對學分數(shù)和課程數(shù)加權形成一個目標，如三七開。課號課名學分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結構35應用統(tǒng)計46計算機模擬37計算機編程28預測理論29數(shù)學實驗3最優(yōu)解：

x1=x2=x3=x4=x5=x6=x7=x9=1，其它為0