數(shù)學(xué)建模題目

你碰到過(guò)的數(shù)學(xué)模型——“航行問(wèn)題”用x

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

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

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

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

數(shù)學(xué)進(jìn)入一些新領(lǐng)域，為數(shù)學(xué)建模開(kāi)辟了許多處女地。第四頁(yè)第五頁(yè)，共67頁(yè)。數(shù)學(xué)建模的具體應(yīng)用

分析與設(shè)計(jì)

預(yù)報(bào)與決策

控制與優(yōu)化

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

數(shù)學(xué)建模的方法和步驟第六頁(yè)第七頁(yè)，共67頁(yè)。數(shù)學(xué)建模的一般步驟模型準(zhǔn)備模型假設(shè)模型構(gòu)成模型求解模型分析模型檢驗(yàn)?zāi)Ｐ蛻?yīng)用模型準(zhǔn)備了解實(shí)際背景明確建模目的搜集有關(guān)信息掌握對(duì)象特征形成一個(gè)比較清晰的‘問(wèn)題’第七頁(yè)第八頁(yè)，共67頁(yè)。模型假設(shè)針對(duì)問(wèn)題特點(diǎn)和建模目的作出合理的、簡(jiǎn)化的假設(shè)在合理與簡(jiǎn)化之間作出折中模型構(gòu)成用數(shù)學(xué)的語(yǔ)言、符號(hào)描述問(wèn)題發(fā)揮想像力使用類比法盡量采用簡(jiǎn)單的數(shù)學(xué)工具數(shù)學(xué)建模的一般步驟第八頁(yè)第九頁(yè)，共67頁(yè)。模型求解各種數(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è)第十頁(yè)，共67頁(yè)。數(shù)學(xué)建模的全過(guò)程現(xiàn)實(shí)對(duì)象的信息數(shù)學(xué)模型現(xiàn)實(shí)對(duì)象的解答數(shù)學(xué)模型的解答表述求解解釋驗(yàn)證(歸納)(演繹)表述求解解釋驗(yàn)證根據(jù)建模目的和信息將實(shí)際問(wèn)題“翻譯”成數(shù)學(xué)問(wèn)題選擇適當(dāng)?shù)臄?shù)學(xué)方法求得數(shù)學(xué)模型的解答將數(shù)學(xué)語(yǔ)言表述的解答“翻譯”回實(shí)際對(duì)象用現(xiàn)實(shí)對(duì)象的信息檢驗(yàn)得到的解答實(shí)踐現(xiàn)實(shí)世界數(shù)學(xué)世界理論實(shí)踐第十頁(yè)第十一頁(yè)，共67頁(yè)。

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

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

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

二元圖

完備二元圖

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

v3v4v5v1

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

v3v4v5v1

∞50304025v250∞153050v33015∞1010v4403010∞20v525501020∞第1,4,5行最小圈.圈列叉v525v1v525v1v310第四十一頁(yè)第四十二頁(yè)，共67頁(yè)。權(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第四十二頁(yè)第四十三頁(yè)，共67頁(yè)。一、問(wèn)題的提法及應(yīng)用背景

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

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

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

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

v3v4v5v1

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

v3v4v5v1

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

v3v4v5v1

∞11054v2∞∞∞∞5v3∞3∞∞2v4∞∞2∞∞v5∞∞∞1∞1對(duì)應(yīng)行加1,第1,2行最小圈,圈列叉4對(duì)應(yīng)行加4,第1,2,5行最小圈,圈列叉v1v2

v3v4v5v1

∞11054v2∞∞∞∞5v3∞3∞∞2v4∞∞2∞∞v5∞∞∞5∞145對(duì)應(yīng)行加5,第1,2,4,5行最小圈,圈列叉v1v2

v3v4v5v1

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

選址問(wèn)題--中心問(wèn)題第四十九頁(yè)第五十頁(yè)，共67頁(yè)。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,故應(yīng)將消防站設(shè)在v3處。返回第五十頁(yè)第五十一頁(yè)，共67頁(yè)。

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

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

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