數(shù)學(xué)建模第二次作業(yè)3

1、 數(shù) 學(xué) 建 模任意兩個城市之間的最廉價路線參與人員信息 ： 2012 年 6 月 6 日 一、問題提出 某公司在六個城市C1、C2、C3、C4、C5、C6中都有分公司，從Ci到Cj的直達航班票價由下述矩陣的第i行、第j列元素給出（表示無直達航班），該公司想算出一張任意兩個城市之間最廉價路線表，試做出這樣的表來。0 50 40 25 1050 0 15 20 25 15 0 10 20 40 20 10 0 10 2525 20 10 0 55 10 25 25 55 0二 、問題分析若網(wǎng)絡(luò)中的每條邊都有一個數(shù)值(長度、成本、時間等)，則找出兩節(jié)點(通常是源節(jié)點和阱節(jié)點)之間總權(quán)和最小的路徑就

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

3、的最短路徑要經(jīng)過點號為的點。（3）查找最短路徑的方法若，則點是點到的最短距離的中間點，然后用同樣的方法再分頭查找。三、 模型假設(shè)： 1.各城市間的飛機線路固定不變 2.各城市間飛機線路的票價不改變 3.忽略乘客除票價以外的各項開銷費用 4.不考慮雷雨云、低云、大風(fēng)、雷暴、冰雹等主要天氣因素對飛行的影響。 四、 模型建立 建立帶權(quán)鄰接矩陣： 根據(jù)飛機路線及票價表建立帶權(quán)鄰接矩陣， 在帶權(quán)鄰接矩陣中用插入頂點的方法依次構(gòu)造出 6 個矩陣。 采用floyd算法步驟為:到的最短距離：到之間的插入點 輸入帶權(quán)鄰接距陣 (1) 賦初值：對所有(2) 更新,:對所有,若，則 ,.(3) 若,停止；否則，轉(zhuǎn)（2）. 運行程序得： D (1) D (2) 、 D(3)、 D (4) 、 D（ 5）、 D（6），使最后得到的矩陣 D ( 6 ) 為飛機的最廉價矩陣。 五、 模型求解結(jié)果 根據(jù)模型求解，分析得出任意兩個城市之間最廉價線路及票價為： C1C2: 162；35 C1C3:153,1643;45 C1C4:164，15435 C1C51525 C1C6:1610 C2C32315 C2C42420 C2C524530 C2C62525