數學建模與數學試驗

最短路問題10/10/數學建模第1頁第1頁實驗目試驗內容2．會用MATLAB軟件求最短路1．理解最短路算法及其應用1．圖論基本概念2．最短路問題及其算法3．最短路應用4．建模案例：最優截斷切割問題5．試驗作業10/10/數學建模第2頁第2頁圖論基本概念一、圖概念1．圖定義2．頂點次數

3．子圖二、圖矩陣表示1．關聯矩陣2．鄰接矩陣返回10/10/數學建模第3頁第3頁定義有序三元組G=(V,E,)稱為一個圖,假如：圖定義10/10/數學建模第4頁第4頁定義定義10/10/數學建模第5頁第5頁10/10/數學建模第6頁第6頁返回10/10/數學建模第7頁第7頁頂點次數10/10/數學建模第8頁第8頁例在一次聚會中，結識奇數個人人數一定是偶數.返回10/10/數學建模第9頁第9頁子圖返回10/10/數學建模第10頁第10頁關聯矩陣注：假設圖為簡樸圖返回10/10/數學建模第11頁第11頁鄰接矩陣注：假設圖為簡樸圖10/10/數學建模第12頁第12頁返回10/10/數學建模第13頁第13頁最短路問題及其算法一、基本概念二、固定起點最短路三、每對頂點之間最短路返回10/10/數學建模第14頁第14頁基本概念10/10/數學建模第15頁第15頁返回10/10/數學建模第16頁第16頁固定起點最短路最短路是一條路徑，且最短路任一段也是最短路．假設在u0-v0最短路中只取一條，則從u0到其余頂點最短路將構成一棵以u0為根樹．因此,可采用樹生長過程來求指定頂點到其余頂點最短路．10/10/數學建模第17頁第17頁10/10/數學建模第18頁第18頁算法環節：10/10/數學建模第19頁第19頁

TOMATLAB(road1)10/10/數學建模第20頁第20頁10/10/數學建模第21頁第21頁

12

34

5

6

7

8返回10/10/數學建模第22頁第22頁每對頂點之間最短路1．求距離矩陣辦法2．求路徑矩陣辦法3．查找最短路路徑辦法（一）算法基本思想（三）算法環節返回10/10/數學建模第23頁第23頁算法基本思想返回10/10/數學建模第24頁第24頁算法原理——求距離矩陣辦法返回10/10/數學建模第25頁第25頁算法原理——求路徑矩陣辦法在建立距離矩陣同時可建立路徑矩陣R．即當k被插入任何兩點間最短路徑時，被統計在R(k)中，依次求時求得，可由來查找任何點對之間最短路路徑．返回)(nR10/10/數學建模第26頁第26頁i

j算法原理——

查找最短路路徑辦法pkp2p1p3q1q2qm則由點i到j最短路路徑為：返回10/10/數學建模第27頁第27頁算法環節10/10/數學建模第28頁第28頁

TOMATLAB(road2(floyd))返回

10/10/數學建模第29頁第29頁一、可化為最短路問題多階段決議問題二、選址問題1．中心問題2．重心問題返回10/10/數學建模第30頁第30頁可化為最短路問題多階段決議問題10/10/數學建模第31頁第31頁10/10/數學建模第32頁第32頁10/10/數學建模第33頁第33頁返回10/10/數學建模第34頁第34頁

選址問題--中心問題

TOMATLAB(road3(floyd))10/10/數學建模第35頁第35頁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,故應將消防站設在v3處.返回10/10/數學建模第36頁第36頁

選址問題--重心問題返回10/10/數學建模第37頁第37頁試驗作業

生產策略問題：當代化生產過程中，生產部門面臨突出問題之一，便是如何選取合理生產率.生產率過高，造成產品大量積壓，使流動資金不能及時回籠；生產率過低，產品不能滿足市場需要，使生產部門失去贏利機會.可見，生產部門在生產過程中必須時刻注意市場需求改變，以便適時調整生產率，獲取最大收益.某生產廠家年初要制定生產策略，已預知其產品在年初需求量為a=6萬單位，并以b=1萬單位/月速度遞增.若生產產品過剩，則需付單位產品單位時間（月）庫存保管費C