數(shù)模培訓(xùn)資料課件

全國數(shù)學(xué)建模競賽培訓(xùn)這是一場艱苦的戰(zhàn)役。需要不怕苦和不怕累的精神，要有堅(jiān)忍不拔的毅力。6/7/2023可能面臨酷暑、內(nèi)容多、強(qiáng)度大的困難。6/7/2023數(shù)學(xué)建模暑期培訓(xùn)紀(jì)律不允許缺課，遲到和早退的現(xiàn)象發(fā)生。每一個(gè)隊(duì)每一次培訓(xùn)或講評，必須是三人到齊。教練會對每一次活動(dòng)考勤，并與相關(guān)學(xué)院聯(lián)系，對缺課學(xué)生予以相應(yīng)處罰。6/7/2023圖論算法參考教材：數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)（趙靜、但琦編）數(shù)學(xué)建模導(dǎo)論（陳理榮編）圖論及其算法（殷劍宏、吳開亞編）集合論與圖論（耿素云編）6/7/2023圖論算法１.最短路問題２.中國郵遞員問題和ＴＳＰ問題３.匹配6/7/2023圖論算法（１）－最短路問題1．圖論的基本概念2．最短路問題及其算法3．最短路的應(yīng)用4．建模案例：最優(yōu)截?cái)嗲懈顔栴}5．實(shí)例應(yīng)用6/7/2023圖論的基本概念一、圖的概念1．圖的定義2．頂點(diǎn)的次數(shù)

3．子圖二、圖的矩陣表示1．關(guān)聯(lián)矩陣2．鄰接矩陣返回6/7/2023定義有序三元組G=(V,E,)稱為一個(gè)圖,如果：圖的定義6/7/2023定義定義6/7/20236/7/2023返回6/7/2023頂點(diǎn)的次數(shù)（度數(shù)）6/7/2023例

在一次聚會中，認(rèn)識奇數(shù)個(gè)人的人數(shù)一定是偶數(shù).返回6/7/2023子圖返回6/7/2023關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回6/7/2023鄰接矩陣注：假設(shè)圖為簡單圖6/7/2023返回6/7/2023最短路問題及其算法一、基本概念二、固定起點(diǎn)的最短路三、每對頂點(diǎn)之間的最短路返回6/7/2023基本概念6/7/2023返回6/7/2023固定起點(diǎn)的最短路-Dijkstra算法最短路是一條路徑，且最短路的任一段也是最短路．假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹．因此,可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路．6/7/2023Dijkstra算法思想Dijkstra算法:這是荷蘭計(jì)算機(jī)科學(xué)教授EdsgerW.Dijkstra(1930-)在1959年發(fā)現(xiàn)的一個(gè)算法.他在1972年獲得計(jì)算機(jī)協(xié)會授予的圖靈獎(jiǎng),這是計(jì)算機(jī)科學(xué)中最具聲望的獎(jiǎng)項(xiàng).Dijkstra算法是求出一個(gè)連通加權(quán)簡單圖中從結(jié)點(diǎn)a到結(jié)點(diǎn)z的最短路.邊{i,j}的權(quán)(i,j)>0,且結(jié)點(diǎn)x的標(biāo)號為L(x),結(jié)束時(shí),L(z)是從x到z的最短路的長度.6/7/20236/7/2023算法步驟：6/7/2023

TOMATLAB(road1)6/7/20236/7/2023

12

34

5

6

7

8返回6/7/2023每對頂點(diǎn)之間的最短路-Floyd算法1．求距離矩陣的方法2．求路徑矩陣的方法3．查找最短路路徑的方法（一）算法的基本思想（三）算法步驟返回6/7/2023算法的基本思想返回6/7/2023算法原理——求距離矩陣的方法返回6/7/2023算法原理——求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑矩陣R．即當(dāng)k被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求時(shí)求得，可由來查找任何點(diǎn)對之間最短路的路徑．返回)(nR6/7/2023i

j算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：返回6/7/2023算法步驟6/7/2023

TO

MATLAB

(road2(floyd))返回

6/7/2023一、可化為最短路問題的多階段決策問題二、選址問題1．中心問題2．重心問題返回6/7/2023可化為最短路問題的多階段決策問題6/7/20236/7/20236/7/2023返回6/7/2023

選址問題--中心問題

TOMATLAB

(road3(floyd))6/7/2023S(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處.返回6/7/2023

選址問題--重心問題返回6/7/2023圖論算法（２）－中國郵遞員問題和ＴＳＰ問題6/7/2023郵路問題及ＴＳＰ問題一、中國郵遞員問題二、推銷員問題三、建模案例：最佳災(zāi)情巡視路線（一）歐拉圖（二）中國郵遞員問題（一）哈密爾頓圖（二）推銷員問題6/7/2023

7

3

1

2

3

4

1

2

4

5

5

6

6

7

8

9割邊G的邊是割邊的充要條件是不含在G的圈中．

割邊的定義：設(shè)G連通，

E(G),若從G中刪除邊后，圖G-{}不連通，則稱邊為圖G的割邊．6/7/2023

e3

v1

v2

v3

v4e1e2e4

e5e6歐拉圖

e3

v1

v2

v3

v4

e1e

2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1歐拉道路：v1e1v2e2v3e5v1e4v4e3v3歐拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v16/7/2023e3

v1

v2

v3v4e1e2e4

e5e3

v1

v2

v3v

4

e1

e2e4

e5e6歐拉圖非歐拉圖返回6/7/2023中國郵遞員問題-定義6/7/2023中國郵遞員問題-算法

Fleury算法基本思想：從任一點(diǎn)出發(fā)，每當(dāng)訪問一條邊時(shí)，先要進(jìn)行檢查．如果可供訪問的邊不只一條，則應(yīng)選一條不是未訪問的邊集的導(dǎo)出子圖的割邊作為訪問邊，直到?jīng)]有邊可選擇為止.6/7/2023

v7e3

v1v2

v3v4e1

e2e4

e5

v5

e6e6

e7

e8

e9e106/7/2023若G不是歐拉圖，則G的任何一個(gè)巡回經(jīng)過某些邊必定多于一次．解決這類問題的一般方法是：在一些點(diǎn)對之間引入重復(fù)邊（重復(fù)邊與它平行的邊具有相同的權(quán)），使原圖成為歐拉圖，但希望所有添加的重復(fù)邊的權(quán)的總和為最?。?/p>

6/7/2023v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e96/7/20236/7/2023（３）求出G1的最小權(quán)理想匹配M，得到奇次頂點(diǎn)的最佳配對．6/7/2023返回6/7/2023哈密爾頓圖返回6/7/2023推銷員問題-定義流動(dòng)推銷員需要訪問某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點(diǎn)．問如何安排旅行路線使總行程最小．這就是推銷員問題．若用頂點(diǎn)表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離（或時(shí)間、或費(fèi)用），于是推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個(gè)頂點(diǎn)至少一次的最短閉通路問題．6/7/2023定義在加權(quán)圖G=(V,E)中，（１）權(quán)最小的哈密爾頓圈稱為最佳H圈(Hamilton圈)．（２）經(jīng)過每個(gè)頂點(diǎn)至少一次的權(quán)最小的閉通路稱為最佳推銷員回路．一般說來，最佳哈密爾頓圈不一定是最佳推銷員回路，同樣最佳推銷員回路也不一定是最佳哈密爾頓圈．H回路，長22最佳推銷員回路，長46/7/20236/7/2023推銷員問題近似算法：二邊逐次修正法：6/7/2023例對以下完備圖，用二邊逐次修正法求較優(yōu)H圈．6/7/2023返回6/7/2023圖論算法（３）－匹配

匹配問題是運(yùn)籌學(xué)的重要問題之一,也是圖論研究的重點(diǎn)內(nèi)容,它提供了解決“人員分配問題”和“最優(yōu)分配問題”一種新的思想.定義1.設(shè)G=<V,E>是無環(huán)圖,ME(G),M,若M中任意兩條邊都不相鄰,則稱M是圖G的一個(gè)匹配.若對圖G的任何匹配M’,均有M’<M,則稱M是圖G的最大匹配,記作’(G).定義2.設(shè)M是圖G的匹配,G中與M中的邊關(guān)聯(lián)的頂點(diǎn)稱為M飽和點(diǎn).若圖G的頂點(diǎn)都是M飽和,則稱為G的完美匹配.6/7/2023說明:(1)完美匹配是最大匹配,反之未然;(2)匹配的定義與邊的方向無關(guān),故匹配是針對無向圖而言.定義3.(可增廣路):設(shè)M是圖G的匹配,P是G的一條路,且在P中,M的邊和E(G)-M的邊交替出現(xiàn),則稱P是G的一條交錯(cuò)路.若M交錯(cuò)路P的兩個(gè)端點(diǎn)為M非飽和點(diǎn),則稱P為M可增廣路.例1.求下圖G的一條交錯(cuò)路和一條可增廣路.623415876/7/2023匹配的幾個(gè)性質(zhì)定理定理1.設(shè)M1和M2是圖G的兩個(gè)不同匹配,由M1M2導(dǎo)出的G的邊導(dǎo)出子圖,記作H,則H的任意連通分支是下列情況之一:(1)邊在M1和M2中交錯(cuò)出現(xiàn)的偶圈.(2)邊在M1和M2中交錯(cuò)出現(xiàn)的路.定理2.M是圖G的最大匹配,當(dāng)且僅當(dāng)G中不存在M可增廣路.定義:設(shè)S是圖G的任意頂點(diǎn)子集,G中與S的頂點(diǎn)鄰接的所有頂點(diǎn)的集合,稱為S的鄰集,記做NG(S).6/7/2023定理3(Hall定理,1935)設(shè)G是有二部劃分(V1,V2)的二分圖,則G含有飽和V1的每個(gè)頂點(diǎn)的匹配M的充要條件是,對SV1,有N(S)S.推論1具有二部劃分(V1,V2)的二分圖G有完美匹配V1=V2,且對SV1(或V2),有N(S)S.推論2.

設(shè)G是k(>0)正則二分圖,則G有完美匹配.由定理3可知,G有飽和V1的匹配M,再據(jù)V1=V2和推論1即知M是完美匹配.推論3.設(shè)G是二部劃分(V1,V2)的簡單二分圖，且V1=V2=n，若(G)n/2，則G有完美匹配.6/7/2023定理4.

G有完美匹配O(G-S)S,SV(G),其中O(G-S)是G-S的奇數(shù)階連通分支數(shù)目例1.有n張紙牌,每張紙牌的正反兩面都寫上1,2,…n的某一個(gè)數(shù),證明:如果每個(gè)數(shù)字恰好出現(xiàn)兩次,則這些紙牌一定可以這樣攤開,使朝上的面中1,2,…n都出現(xiàn).證明:作一個(gè)二分圖G=<V1,V2,E>,其中V1={1,2,…,n}，V2={y1,y2,…,yn}表示這n張紙牌.i與yi之間連接的邊數(shù)等于數(shù)i在紙牌yj中出現(xiàn)的次數(shù),這樣得到的圖G是一個(gè)2-正則二分圖,因此圖G中有完美匹配,設(shè)為M={1yi1,2yi2,…,nyin}

則只要把紙牌yi1中的1朝上,yi2中的2朝上,…,yin的n朝上,這樣攤開,這樣攤開的紙牌就能使上面中1,2,…,n都出現(xiàn).6/7/2023例2.某工廠生產(chǎn)由6種不同顏色的紗布織成的雙色布,由該廠所生產(chǎn)的雙色布中,每一種顏色至少和其他三種顏色搭配.證明可以挑選出三種不同的雙色布,它們含有所有的6種顏色.證明:構(gòu)造圖G=<V,E>,其中V={v1,v2,v3,v4,v5,v6}表示6種顏色,工廠生產(chǎn)出一種顏色vi與vj搭配而成的雙色布邊{vi,vj}E(G).由題意知,G為簡單圖,且每個(gè)結(jié)點(diǎn)的度數(shù)至少為3,下證G中含有一個(gè)完美匹配.

今設(shè){v1,v2}E(G),由于d(v3)≥3,所以存在一個(gè)不同于v1和v2的頂點(diǎn)vi(4≤i≤6),使{v3,vi}E(G),不妨設(shè)vi=4,即{v3,v4}E(G).6/7/2023

如果邊{v5,v6}E(G),由于d(v5)≥3,v1,v2,v3,v4中至少有3個(gè)頂點(diǎn)與v5相鄰,即v5與邊{v1,v2},{v3,v4}中的每一邊的某一個(gè)端點(diǎn)相鄰,不妨設(shè){v1,v5}E(G)和{v3,v5}E(G).

對于頂點(diǎn)v6,同樣與v1,v2,v3,v4中至少3個(gè)頂點(diǎn)相鄰,即在v2和v4中至少有一個(gè)頂點(diǎn)與v6相鄰.如果{v2,v6}E(G),則邊{v1,v5},{v3,v4},{v2,v6}是G的一個(gè)完美匹配;如果{v4,v6}E(G),則{v1,v2},{v3,v5},{v4,v6}是G的一個(gè)完美匹配.

綜上所述,G總存在完美匹配,完美匹配中的三條邊所對應(yīng)的三種雙色布即為所求.6/7/2023最大匹配的生成算法-匈牙利算法定義1.根在x的M交錯(cuò)子圖:設(shè)M是圖G的匹配,x是G中非M飽和點(diǎn).G中由起點(diǎn)為x的M交錯(cuò)路所能連接的頂點(diǎn)集所導(dǎo)出的G的導(dǎo)出子圖稱為根在x的M交錯(cuò)子圖.定理1.設(shè)M是具有二部劃分(V1,V2)的二分圖G的匹配,xV1是非M飽和點(diǎn),H是G中根在x的M交錯(cuò)子圖的頂點(diǎn)集S=H∩V1,T=H∩V2,則:(1)TNG(S);(2)下述三條等價(jià):(a)G中不存在以x為端點(diǎn)的M可增廣路;(b)x是H中唯一的非M飽和點(diǎn);(c)T=NG(S),且T=S-1.(不證)6/7/2023匈牙利算法基本思想:設(shè)G是具有二部劃分(V1,V2)的二分圖,從圖G的任意匹配M開始.若M飽和V1,則M是G的匹配.若M不能飽和V1,則在V1中選擇一個(gè)非M飽和點(diǎn)x,若G中存在以x為起點(diǎn)的M可增廣路P,則M’=MP就是比M更大的匹配,利用M’代替M,并重復(fù)這個(gè)過程.若G中不存在以x為起點(diǎn)的M可增廣路,則令H是根在x的M交錯(cuò)子圖的頂點(diǎn)集,并令S=HV1,T=HV2,由定理1,T=NG(S),且G中不存在以x為起點(diǎn)的M可增廣路,此時(shí)稱x為檢驗(yàn)過的非M飽和點(diǎn).對V1中其它未檢驗(yàn)過的非M飽和點(diǎn)重復(fù)該過程,直到V1中的所有非M飽和點(diǎn)全部檢驗(yàn)過為止.當(dāng)整個(gè)過程結(jié)束時(shí),由于G中不存在M可增廣路,從而M為G的最大匹配.6/7/2023匈牙利算法步驟:設(shè)G是具有二部劃分(V1,V2)的二分圖.(1)任給初始匹配M;(2)若M飽和V1則結(jié)束.否則轉(zhuǎn)(3);(3)在V1中找一非M飽和點(diǎn)x,令S={x},T=;(4)若N(S)=T,則停止,否則任選一點(diǎn)yN(S)-T;(5)若y為M飽和點(diǎn)轉(zhuǎn)(6),否則作求一條從x到y(tǒng)的M可增廣路P,置M=MP,轉(zhuǎn)(2)；(6)由于y是M飽和點(diǎn),故M中有一邊{y,u},置S=S{u},T=T{y},轉(zhuǎn)(4).6/7/2023例1.如圖G所示,V1={x1,x2,x3,x4,x5},V2={y1,y2,y3,y4,y5}，試求圖G的最大匹配.x1,,x2x3x4x5y1y2y3y4y5圖ax1x2x3x4x5y1y2y3y4y5圖b6/7/2023解:任取初始匹配M={x2y2,x3y3,x5y5},如圖(a)中虛線所示.解題過程如下表:MxSTN(S)yN(S)-T{y,u}MP{x2y2,x3y3,x5y5}x1{x1}{y2,y3}y2飽和{y2,x2}{x1,x2}{y2}{y1,y2,y3,y4,y5}y1非飽和(x1y2x2y1){x1y2,x2y1,x3y3x5y5}x4{x4}{y2,x3}y2飽和{y2,x1}{x4,x1}{y2}{y2,y3}y3飽和{y3,x3}{x4,x1,x3}{y2,y3}{y2,y3}N(S)=T,停止6/7/2023因此,M={