數(shù)學建模題目

你碰到過的數(shù)學模型——“航行問題”用x

表示船速，y表示水速，列出方程：答：船速每小時20千米/小時.甲乙兩地相距750千米，船從甲到乙順水航行需30小時，從乙到甲逆水航行需50小時，問船的速度是多少?x=20y=5求解第一頁第二頁，共67頁。航行問題建立數(shù)學模型的基本步驟作出簡化假設(shè)（船速、水速為常數(shù)）；用符號表示有關(guān)量（x,y表示船速和水速）；用物理定律（勻速運動的距離等于速度乘以時間）列出數(shù)學式子（二元一次方程）；求解得到數(shù)學解答（x=20,y=5）；回答原問題（船速每小時20千米/小時）。第二頁第三頁，共67頁。數(shù)學模型(MathematicalModel)和數(shù)學建模（MathematicalModeling)對于一個現(xiàn)實對象，為了一個特定目的，根據(jù)其內(nèi)在規(guī)律，作出必要的簡化假設(shè)，運用適當?shù)臄?shù)學工具，得到的一個數(shù)學結(jié)構(gòu)。建立數(shù)學模型的全過程（包括表述、求解、解釋、檢驗等）數(shù)學模型數(shù)學建模第三頁第四頁，共67頁。1.3

數(shù)學建模的重要意義電子計算機的出現(xiàn)及飛速發(fā)展；數(shù)學以空前的廣度和深度向一切領(lǐng)域滲透。數(shù)學建模作為用數(shù)學方法解決實際問題的第一步，越來越受到人們的重視。

在一般工程技術(shù)領(lǐng)域數(shù)學建模仍然大有用武之地；

在高新技術(shù)領(lǐng)域數(shù)學建模幾乎是必不可少的工具；

數(shù)學進入一些新領(lǐng)域，為數(shù)學建模開辟了許多處女地。第四頁第五頁，共67頁。數(shù)學建模的具體應用

分析與設(shè)計

預報與決策

控制與優(yōu)化

規(guī)劃與管理數(shù)學建模計算機技術(shù)知識經(jīng)濟如虎添翼第五頁第六頁，共67頁。數(shù)學建模的基本方法機理分析測試分析根據(jù)對客觀事物特性的認識，找出反映內(nèi)部機理的數(shù)量規(guī)律將對象看作“黑箱”,通過對量測數(shù)據(jù)的統(tǒng)計分析，找出與數(shù)據(jù)擬合最好的模型機理分析沒有統(tǒng)一的方法，主要通過實例研究(CaseStudies)來學習。以下建模主要指機理分析。二者結(jié)合用機理分析建立模型結(jié)構(gòu),用測試分析確定模型參數(shù)1.4

數(shù)學建模的方法和步驟第六頁第七頁，共67頁。數(shù)學建模的一般步驟模型準備模型假設(shè)模型構(gòu)成模型求解模型分析模型檢驗模型應用模型準備了解實際背景明確建模目的搜集有關(guān)信息掌握對象特征形成一個比較清晰的‘問題’第七頁第八頁，共67頁。模型假設(shè)針對問題特點和建模目的作出合理的、簡化的假設(shè)在合理與簡化之間作出折中模型構(gòu)成用數(shù)學的語言、符號描述問題發(fā)揮想像力使用類比法盡量采用簡單的數(shù)學工具數(shù)學建模的一般步驟第八頁第九頁，共67頁。模型求解各種數(shù)學方法、軟件和計算機技術(shù)如結(jié)果的誤差分析、統(tǒng)計分析、模型對數(shù)據(jù)的穩(wěn)定性分析模型分析模型檢驗與實際現(xiàn)象、數(shù)據(jù)比較，檢驗模型的合理性、適用性模型應用數(shù)學建模的一般步驟第九頁第十頁，共67頁。數(shù)學建模的全過程現(xiàn)實對象的信息數(shù)學模型現(xiàn)實對象的解答數(shù)學模型的解答表述求解解釋驗證(歸納)(演繹)表述求解解釋驗證根據(jù)建模目的和信息將實際問題“翻譯”成數(shù)學問題選擇適當?shù)臄?shù)學方法求得數(shù)學模型的解答將數(shù)學語言表述的解答“翻譯”回實際對象用現(xiàn)實對象的信息檢驗得到的解答實踐現(xiàn)實世界數(shù)學世界理論實踐第十頁第十一頁，共67頁。

近幾年全國大學生數(shù)學建模競賽題第十一頁第十二頁，共67頁。第十二頁第十三頁，共67頁。第十三頁第十四頁，共67頁。第十四頁第十五頁，共67頁。第十五頁第十六頁，共67頁。第十六頁第十七頁，共67頁。真是月亮惹的禍嗎?第十七頁第十八頁，共67頁。三國人物：誰是天下第一？第十八頁第十九頁，共67頁。圖論與網(wǎng)絡(luò)優(yōu)化一、最小生成樹問題二、最短路問題第十九頁第二十頁，共67頁。哥尼斯堡七橋問題CADB抽象為圖的問題：圖G(V,E)能經(jīng)過每條邊恰好一次回到原點每個頂點與偶數(shù)條邊相關(guān)聯(lián)圖G(V,E)Fleury算法網(wǎng)絡(luò)優(yōu)化及實例從某點出發(fā)，經(jīng)過圖上每條邊恰好一次回到原點—Euler環(huán)游圖G(V,E)有Euler環(huán)游圖G(V,E)無奇點第二十頁第二十一頁，共67頁。例：中國郵遞員問題(CPP-ChinesePostmanProblem)一名郵遞員負責投遞某個街區(qū)的郵件.如何設(shè)計一條最短的投遞路線(從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局)？由于這一問題是我國學者管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題.給定一個圖，問是否存在點不重的環(huán)游？例：1973年，John和Edmonds結(jié)合Fleury算法給出好算法第二十一頁第二十二頁，共67頁。圖與網(wǎng)路的基本概念6.1.1圖與網(wǎng)路頂點(Vertex)物理實體、事物、概念一般用vi

表示邊(Edge)頂點間的連線，表示有關(guān)聯(lián)一般用eij

表示圖(Graph)頂點和邊的集合一般用G(V,E)表示頂點集V={v1,v2,…,vn}邊集E={eij}網(wǎng)路(Network)邊上具有表示連接強度的權(quán)值，如wij又稱加權(quán)圖(Weightedgraph)第二十二頁第二十三頁，共67頁。所有邊都沒有方向的圖稱為無向圖在無向圖中eij=eji，或(vi,vj)=(vj,vi)當所有邊都有方向時，稱為有向圖，用G(V,A)表示在有向圖中，有向邊又稱為弧，用aij表示，i,j的順序是不能顛倒的，圖中弧的方向用箭頭標識圖中既有邊又有弧，稱為混合圖無向圖與有向圖第二十三頁第二十四頁，共67頁。第二十四頁第二十五頁，共67頁。返回完備圖

二元圖

完備二元圖

第二十五頁第二十六頁，共67頁。頂點的次數(shù)第二十六頁第二十七頁，共67頁。例在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù)。返回第二十七頁第二十八頁，共67頁。子圖返回第二十八頁第二十九頁，共67頁。關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回第二十九頁第三十頁，共67頁。鄰接矩陣注：假設(shè)圖為簡單圖第三十頁第三十一頁，共67頁。返回第三十一頁第三十二頁，共67頁。例甲、乙、丙、丁、戊五個球隊比賽情況。v5v1v3v4v2v1v2v3v4v5v5v1v3v4v2第三十二頁第三十三頁，共67頁。某單位儲存八種化學藥品，其中某些藥品不能存放在同一個倉庫，考慮所需最少倉庫數(shù)v5v1v2v3v4v6v7v8至少四個庫房：1，2，5，8任意兩個不能同存1，3，4，7258，6第三十三頁第三十四頁，共67頁。邊與頂點均不重復的通路稱為路徑路：vi1vi2vin-2……vin-1vinvi3vij≠vik,j≠k……路徑第三十四頁第三十五頁，共67頁。返回第三十五頁第三十六頁，共67頁。無圈連通圖v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8樹：G的生成樹(spanningtree):T(V,E’)是圖G(V,E)的子圖,且是一棵樹最小生成樹:T(V,E’)是圖G(V,E)所有生成樹中權(quán)重最小的一棵第三十六頁第三十七頁，共67頁。樹圖與最小生成樹一般研究無向圖樹圖：倒置的樹，根(root)在上，樹葉(leaf)在下多級輻射制的電信網(wǎng)絡(luò)、管理的指標體系、家譜、分類學、組織結(jié)構(gòu)等都是典型的樹圖第三十七頁第三十八頁，共67頁。例在五個村莊之間修路，使任一村莊可到其余各村莊。已知各村莊間修路所需費用如下圖，考慮費用最省方案。v5v1v2v3v450153010301025204050(萬元)123451∞5030402525010104403010∞20525501020∞問題即為求對應圖的最小生成樹第三十八頁第三十九頁，共67頁。最小生成樹求解方法：避圈法；破圈法避圈法v2v3v4501530103010252040501234v1v5v1v2v3v415101025權(quán)重為60最小生成樹為：v5Kruskal算法第三十九頁第四十頁，共67頁。v2v3v450153010301025204050v1v5635421權(quán)重為60最小生成樹為：破圈法v5v1v2v3v415101025第四十頁第四十一頁，共67頁。權(quán)矩陣v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞(wij)=第1列叉,第1行最小圈.圈列叉第1，5行最小圈.圈列叉v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞第1,4,5行最小圈.圈列叉v525v1v525v1v310第四十一頁第四十二頁，共67頁。權(quán)矩陣v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞(wij)=第1列叉,第1行最小圈.圈列叉第1，5行最小圈.圈列叉v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞第1,4,5行最小圈.圈列叉v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞第1,3,4,5行最小圈.圈列叉v1v2

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞v5v1v2v3v415101025v525v1v525v1v310v5v1v4101025v3第四十二頁第四十三頁，共67頁。一、問題的提法及應用背景

（1）問題的提法——尋求網(wǎng)絡(luò)中兩點間的最短路就是尋求連接這兩個點的邊的總權(quán)數(shù)為最小的通路。（2）應用背景——管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等。最短路問題(非負權(quán))第四十三頁第四十四頁，共67頁。二、最短路算法：

1．D氏標號法（Dijkstra）（1）求解思路——從始點出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。

（2）使用條件——網(wǎng)絡(luò)中所有的弧權(quán)均

非負，即。第四十四頁第四十五頁，共67頁。最短路問題(非負權(quán))例有五個位置，其間的路都是單行道。具體方向及距離見下圖。求由位置1到其他各個位置怎么走路途最短。v5v1v2v3v4244310121轉(zhuǎn)化為求v1到其他所有頂點的最短路權(quán)矩陣v1v2

v3v4v5v1

∞11054v2∞∞∞∞4v3∞3∞∞2v4∞∞2∞∞v5∞∞∞1∞(wij)=5第四十五頁第四十六頁，共67頁。v1v2

v3v4v5v1

∞11054v2∞∞∞∞4v3∞3∞∞2v4∞∞2∞∞v5∞∞∞1∞(wij)=第1列叉,第1行最小圈.圈列叉1v1v2

v3v4v5v1

∞11054v2∞∞∞∞5v3∞3∞∞2v4∞∞2∞∞v5∞∞∞1∞1對應行加1,第1,2行最小圈,圈列叉4對應行加4,第1,2,5行最小圈,圈列叉v1v2

v3v4v5v1

∞11054v2∞∞∞∞5v3∞3∞∞2v4∞∞2∞∞v5∞∞∞5∞145對應行加5,第1,2,4,5行最小圈,圈列叉v1v2

v3v4v5v1

∞11054v2∞∞∞∞5v3∞3∞∞2v4∞∞7∞∞v5∞∞∞5∞1457第四十六頁第四十七頁，共67頁?？苫癁樽疃搪穯栴}的多階段決策問題第四十七頁第四十八頁，共67頁。返回第四十八頁第四十九頁，共67頁。

選址問題--中心問題第四十九頁第五十頁，共67頁。S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應將消防站設(shè)在v3處。返回第五十頁第五十一頁，共67頁。

選址問題--重心問題返回第五十一頁第五十二頁，共67頁。e3v1v2v3v4e1e2e4e5e6歐拉圖e3v1v2v3v4e1e2e4e5環(huán)游

：v1e1v2e2v3e5v1e4v4e3v3e5v1歐拉道路：v1e1v2e2v3e5v1e4v4e3v3歐拉環(huán)游：v1e1v2e2v3e5v1e4v4e3v3e6v1第五十二頁第五十三頁，共67頁。圖G(V,E)有Euler環(huán)游充要條件是圖G(V,E)無奇點

Fleury算法-基本思想：從任一點出發(fā)，每當訪問一條邊時，先要進行檢查．如果可供訪問的邊不只一條，則應選一條不是未訪問的邊集的導出子圖的割邊作為訪問邊，直到?jīng)]有邊可選擇為止.割邊的定義：設(shè)G連通，eE(G),若從G中刪除邊e后，圖G-{e}不連通，則稱邊e為圖G的割邊．V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割邊G的邊e是割邊的充要條件是e不含在G的圈中．第五十三頁第五十四頁，共67頁。V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10第五十四頁第五十五頁，共67頁。中國郵遞員問題