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

1、 數(shù) 學(xué) 建 模任意兩個(gè)城市之間的最廉價(jià)路線參與人員信息 ： 2012 年 6 月 6 日 一、問題提出 某公司在六個(gè)城市C1、C2、C3、C4、C5、C6中都有分公司，從Ci到Cj的直達(dá)航班票價(jià)由下述矩陣的第i行、第j列元素給出（表示無直達(dá)航班），該公司想算出一張任意兩個(gè)城市之間最廉價(jià)路線表，試做出這樣的表來。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ò)中的每條邊都有一個(gè)數(shù)值(長度、成本、時(shí)間等)，則找出兩節(jié)點(diǎn)(通常是源節(jié)點(diǎn)和阱節(jié)點(diǎn))之間總權(quán)和最小的路徑就

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

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