1、,1985年由美國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)和美國(guó)運(yùn)籌 學(xué)會(huì)聯(lián)合主辦大學(xué)生數(shù)學(xué)建模競(jìng)賽（ MCM ),1.1 數(shù)學(xué)建模由來(lái), 在上世紀(jì)70年代末和80年代初，英國(guó)著名的劍 橋大學(xué)專門為研究生開設(shè)了數(shù)學(xué)建模課程, 數(shù)學(xué)建模作為一門嶄新的課程在20世紀(jì)80年代 進(jìn)入我國(guó)高校，蕭樹鐵先生1983年在清華大學(xué)首次為本科生講授數(shù)學(xué)模型課程，他是我國(guó)高校開設(shè)數(shù)學(xué)模型課程的創(chuàng)始人,玩具、照片、飛機(jī)、火箭模型 , 實(shí)物模型,地圖、電路圖、分子結(jié)構(gòu)圖 , 符號(hào)模型,模型是為了一定目的，對(duì)客觀事物的一部分 進(jìn)行簡(jiǎn)縮、抽象、提煉出來(lái)的原型的替代物,模型集中反映了原型中人們需要的那一部分特征,1.2 從現(xiàn)實(shí)對(duì)象到數(shù)學(xué)模型,我

2、們常見的模型,你碰到過(guò)的數(shù)學(xué)模型“航行問(wèn)題”,用 x 表示船速，y 表示水速，列出方程：,答：船速每小時(shí)20千米/小時(shí).,甲乙兩地相距750千米，船從甲到乙順?biāo)叫行?0小時(shí)， 從乙到甲逆水航行需50小時(shí)，問(wèn)船的速度是多少?,x =20 y =5,航行問(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í)）。,數(shù)學(xué)模型 (Mathematical Model) 和 數(shù)學(xué)建模（Mathe

3、matical Modeling),對(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é)建模,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é)建模開辟了許多處女地。,數(shù)學(xué)建模的具體應(yīng)用,分析與設(shè)計(jì),預(yù)報(bào)與決策,控制與優(yōu)化,規(guī)劃

4、與管理,數(shù)學(xué)建模,計(jì)算機(jī)技術(shù),知識(shí)經(jīng)濟(jì),數(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í)例研究 (Case Studies)來(lái)學(xué)習(xí)。以下建模主要指機(jī)理分析。,二者結(jié)合,用機(jī)理分析建立模型結(jié)構(gòu), 用測(cè)試分析確定模型參數(shù),1.4 數(shù)學(xué)建模的方法和步驟,數(shù)學(xué)建模的一般步驟,模 型 準(zhǔn) 備,了解實(shí)際背景,明確建模目的,搜集有關(guān)信息,掌握對(duì)象特征,形成一個(gè) 比較清晰 的問(wèn)題,模 型 假 設(shè),針對(duì)問(wèn)題特點(diǎn)和建模目的,作出合理的、簡(jiǎn)化的假設(shè),在合理與簡(jiǎn)化

5、之間作出折中,模 型 構(gòu) 成,用數(shù)學(xué)的語(yǔ)言、符號(hào)描述問(wèn)題,發(fā)揮想像力,使用類比法,盡量采用簡(jiǎn)單的數(shù)學(xué)工具,數(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)Ｐ偷暮侠硇?、適用性,模型應(yīng)用,數(shù)學(xué)建模的一般步驟,數(shù)學(xué)建模的全過(guò)程,現(xiàn)實(shí)對(duì)象的信息,數(shù)學(xué)模型,現(xiàn)實(shí)對(duì)象的解答,數(shù)學(xué)模型的解答,(歸納),(演繹),表述,求解,解釋,驗(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)得到的

6、解答,實(shí)踐,現(xiàn)實(shí)世界,數(shù)學(xué)世界,近幾年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題,真是月亮惹的禍嗎?,三國(guó)人物：誰(shuí)是天下第一？,圖論與網(wǎng)絡(luò)優(yōu)化,一、最小生成樹問(wèn)題,二、最短路問(wèn)題,哥尼斯堡七橋問(wèn)題,C,A,D,B,抽象為圖的問(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),例：中國(guó)郵遞員問(wèn)題(CPP-Chinese Postman Problem) 一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件.如何設(shè)計(jì)一條最短的投遞路線(從郵局出發(fā)，經(jīng)

7、過(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算法給出好算法,圖與網(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

8、又稱加權(quán)圖(Weighted graph),所有邊都沒(méi)有方向的圖稱為無(wú)向圖 在無(wú)向圖中 eij=eji，或 (vi, vj)=(vj, vi) 當(dāng)所有邊都有方向時(shí)，稱為有向圖，用G(V,A)表示 在有向圖中，有向邊又稱為弧，用 aij表示，i, j 的順序是不能顛倒的，圖中弧的方向用箭頭標(biāo)識(shí) 圖中既有邊又有弧，稱為混合圖,無(wú)向圖與有向圖,返回,完備圖,二元圖,完備二元圖,頂點(diǎn)的次數(shù),例 在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。,返回,子圖,返回,關(guān)聯(lián)矩陣,注：假設(shè)圖為簡(jiǎn)單圖,返回,鄰接矩陣,注：假設(shè)圖為簡(jiǎn)單圖,返回,例 甲、乙、丙、丁、戊五個(gè)球隊(duì)比賽情況。,v5,v1,v3,v4,v2,v

9、1,v2,v3,v4,v5,v5,v1,v3,v4,v2,某單位儲(chǔ)存八種化學(xué)藥品，其中某些藥品不能存放在同一個(gè)倉(cāng)庫(kù)，考慮所需最少倉(cāng)庫(kù)數(shù),v5,v1,v2,v3,v4,v6,v7,v8,至少四個(gè)庫(kù)房：1，2，5，8任意兩個(gè)不能同存,1，3，4，7,2,5,8，6,邊與頂點(diǎn)均不重復(fù)的通路稱為路徑,路：,vi1,vi2,vin-2,vin-1,vin,vi3,vijvik, jk,路徑,返回,無(wú)圈連通圖,v1,v2,v3,v4,v5,v6,v7,v8,v1,v2,v3,v4,v5,v6,v7,v8,v1,v2,v3,v4,v5,v6,v7,v8,樹：,G的生成樹(spanning tree): T(

10、V,E)是圖 G(V,E)的子圖,且是一棵樹,最小生成樹: T(V,E)是圖G(V,E)所有生成樹中權(quán)重最小的一棵,樹圖與最小生成樹,一般研究無(wú)向圖 樹圖：倒置的樹，根(root)在上，樹葉(leaf)在下 多級(jí)輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分類學(xué)、組織結(jié)構(gòu)等都是典型的樹圖,例 在五個(gè)村莊之間修路，使任一村莊可到其余各村莊。已知各村莊間修路所需費(fèi)用如下圖，考慮費(fèi)用最省方案。,v5,v1,v2,v3,v4,50,15,30,10,30,10,25,20,40,50,問(wèn)題即為求對(duì)應(yīng)圖的最小生成樹,最小生成樹求解方法：避圈法；破圈法,避圈法,v2,v3,v4,50,15,30,10,30,

11、10,25,20,40,50,1,2,3,4,v1,v5,v1,v2,v3,v4,15,10,10,25,權(quán)重為60,最小生成樹為：,v5,Kruskal算法,v2,v3,v4,50,15,30,10,30,10,25,20,40,50,v1,v5,6,3,5,4,2,1,權(quán)重為60,最小生成樹為：,破圈法,v5,v1,v2,v3,v4,15,10,10,25,權(quán)矩陣,(wij)=,第1列叉,第1行最小圈.圈列叉,第1，5行最小圈.圈列叉,第1,4,5行最小圈.圈列叉,v5,25,v1,v5,25,v1,v3,10,權(quán)矩陣,(wij)=,第1列叉,第1行最小圈.圈列叉,第1，5行最小圈.圈列叉

12、,第1,4,5行最小圈.圈列叉,第1,3,4,5行最小圈.圈列叉,v5,v1,v2,v3,v4,15,10,10,25,v5,25,v1,v5,25,v1,v3,10,v5,v1,v4,10,10,25,v3,一、問(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)),二、最短路算法：,1 D氏標(biāo)號(hào)法（Dijkstra） （1）求解思路從始點(diǎn)出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。,（2）使用條件網(wǎng)絡(luò)中所有的弧權(quán)均 非負(fù)，即 。,最短路問(wèn)題(非負(fù)

13、權(quán)),例 有五個(gè)位置，其間的路都是單行道。具體方向及距離見下圖。求由位置1到其他各個(gè)位置怎么走路途最短。,v5,v1,v2,v3,v4,2,4,4,3,10,1,2,1,轉(zhuǎn)化為求v1到其他所有頂點(diǎn)的最短路,權(quán)矩陣,(wij)=,5,(wij)=,第1列叉,第1行最小圈.圈列叉,1,1,對(duì)應(yīng)行加1,第1,2行最小圈,圈列叉,4,對(duì)應(yīng)行加4,第1,2,5行最小圈,圈列叉,1,4,5,對(duì)應(yīng)行加5,第1,2,4,5行最小圈,圈列叉,1,4,5,7,可化為最短路問(wèn)題的多階段決策問(wèn)題,返回,選址問(wèn)題-中心問(wèn)題,S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7,

14、S(v6)=7, S(v7)=8.5,S(v3)=6,故應(yīng)將消防站設(shè)在v3處。,返回,選址問(wèn)題-重心問(wèn)題,返回,歐 拉 圖,環(huán)游 ：v1e1v2e2v3e5v1e4v4e3v3e5v1,歐拉道路：v1e1v2e2v3e5v1e4v4e3v3,歐拉環(huán)游 ：v1e1v2e2v3e5v1e4v4e3v3e6v1,圖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連通，e E(G),若從G中刪除邊e后，圖G-e不連通，則稱邊e為圖G的割邊,G的邊e是割邊的充要條件是e不含在G的圈中,中國(guó)郵遞員問(wèn)題-算法,若G不是歐拉圖，則G的任何一個(gè)巡回經(jīng)過(guò)某些邊必定多于一次,解決這類問(wèn)題的一般方法是，在一些點(diǎn)對(duì)之間 引入重復(fù)邊（重復(fù)邊與它平行的邊具有相同的權(quán)）， 使原圖成為歐拉圖，但希望所有添加的重復(fù)邊的 權(quán)的總和為最小,（）求出G1的最小權(quán)理想匹配M，得到奇次頂點(diǎn)的最佳配對(duì),返回,哈 密 爾 頓 圖,返回,推銷員問(wèn)題-定義,流動(dòng)推銷員需要訪問(wèn)某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點(diǎn)問(wèn)如何安排旅行路線使總行程