1、數學建模任意兩個城市之間的最廉價路線參與人員信息：2022 年6月_6_日、問題提出某公司在六個城市 C1、C2、C3 C4 C5 C6中都有分公司，從 Ci到Cj的 直達航班票價由下述矩陣的第i行、第j列元素給出表示無直達航班，該 公司想算出一張任意兩個城市之間最廉價路線表，試做出這樣的表來。廠0 508 40 25 10、50 0 15 20258 15 0 10 20 840 20 10 0 10 25258 20 10 0 5510 2(8 25 55 0/二、問題分析假設網絡中的每條邊都有一個數值(長度、本錢、時間等)，那么找出兩節點(通 常是源節點和阱節點)之間總權和最小的路徑就是

2、最短路問題。最短路問題是網 絡理論解決的典型問題之一，可用來解決管路鋪設、線路安裝、廠區布局和設備 更新等實際問題。最短路問題，我們通常歸屬為三類：單源最短路徑問題、確定 起點終點的最短路徑問題、全局最短路徑問題求圖中所有的最短路徑。題中要求算出一張任意城市間的最廉價路線表，屬于全局最短路問題，并且使得該公司總經理能夠與各個子公司之間自由往返。此兩點為主要約束條件 Floyd算法，具體原理如下：(1)我們確定此題為全局最短路問題，并采用求距離矩陣的方法根據路線及票價表建立帶權矩陣W，并把帶權鄰接矩陣我 w作為距離矩陣 的初始值，即 D(0) (dij(0)vv W2求路徑矩陣的方法在建立距離矩

3、陣的同時可建立路徑矩陣 R，R (rij)vv , ©的含義是從v到Vj 的最短路徑要經過點號為厲的點。3查找最短路徑的方法假設昇 P1，那么點p是點i到j的最短距離的中間點，然后用同樣的方法 再分頭查找。三、模型假設：1. 各城市間的飛機線路固定不變2. 各城市間飛機線路的票價不改變4.不考慮雷雨云、低云、大風、雷暴、冰雹等主要天氣因素對飛行的影響。四、模型建立建立帶權鄰接矩陣：根據飛機路線及票價表建立帶權鄰接矩陣，在帶權鄰接矩陣中用插入頂點的方法依次構造出6個矩陣。采用floyd算法步驟為：Di,j: i到j的最短距離Ri,j : i到j之間的插入點輸入帶權鄰接距陣 w賦初值：對

4、所有i,j,w,jdi,j, j n,j,k 1.更新D,j, R,j:對所有i, j假設di,k dk,jdi,j，那么di ,k dk,jdi, j , kri,j .假設k v,停止；否那么k 1 k，轉2.運行程序得：050InE402&10soC15207525Inf01020Inf4020100ID2525201035LQInf益35Q12315&12a41&123斗5&12345B1345112341&0506540251050C152D7S25551吁010£QAQ10201001025257E20la3510254025350

5、12£501162152151112Z416Du -Q506540IQ50015203525閒1510£04040201001025埜35ECllan芻10254025350DK =211I224q4斗435516616Du =050SO40E5105001520mo255015010£0354020100ID25戲30201003510253525350R =£445&12?44B4234呂4I2345& =0SO<53S2510500152030254呂1501020貼555010010252530201

6、0a3510253525350251244t122斗23344446441650453525IQ0IE203025150Id20352C1001025302010035為3525350o503525to2555&234-4B23454234564345124115D6使最后得到的矩陣D 6為飛機的最廉價矩陣。五、模型求解結果根據模型求解，分析得出任意兩個城市之間最廉價線路及票價為:C1 f C2: 1 f 62; 35C1 f C3:1 f 5f 3,1 f 6f 4f 3;45C1 f C4:1 f 6f 4, 1f 5f 4 ； 35C1 f C5： 1f 5 ； 25C1 f C6:1 f 6 ； 10C2 f C3： 2f 3 ； 15C2 f C4： 2f 4 ； 20C2 f C5： 2f 4f 5 ； 30C2 f C6： 2f 5 ； 25C3 f C4： 3f 4 ； 10C3 f C5 :