參與人員資訊 ：
2012 年 6 月 6 日
一、問題提出
某公司在六個城市c1、c2、c3、c4、c5、c6中都有分公司，從ci到cj的直達航班票價由下述矩陣的第i行、第j列元素給出（∞表示無直達航班），該公司想算出一張任意兩個城市之間最廉價路線表，試做出這樣的表來。
0 50 ∞ 40 25 10
50 0 15 20 ∞ 25
∞ 15 0 10 20 ∞
40 20 10 0 10 25
25 ∞ 20 10 0 55
10 25 ∞ 25 55 0
二 、問題分析
若網路中的每條邊都有乙個數值(長度、成本、時間等)，則找出兩節點(通常是源節點和阱節點)之間總權和最小的路徑就是最短路問題。最短路問題是網路理論解決的典型問題之一，可用來解決管路鋪設、線路安裝、廠區布局和裝置更新等實際問題。最短路問題，我們通常歸屬為三類：
單源最短路徑問題、確定起點終點的最短路徑問題、全域性最短路徑問題———求圖中所有的最短路徑。
題中要求算出一張任意城市間的最廉價路線表，屬於全域性最短路問題，並且使得該公司總經理能夠與各個子公司之間自由往返。（此兩點為主要約束條件）
floyd演算法，具體原理如下：
（1） 我們確定本題為全域性最短路問題，並採用求距離矩陣的方法
根據路線及票價表建立帶權矩陣，並把帶權鄰接矩陣我w作為距離矩陣的初始值，即
（2）求路徑矩陣的方法
在建立距離矩陣的同時可建立路徑矩陣，，的含義是從到的最短路徑要經過點號為的點。
（3）查詢最短路徑的方法
若，則點是點到的最短距離的中間點，然後用同樣的方法再分頭查詢。
三、 模型假設：
1.各城市間的飛機線路固定不變
2.各城市間飛機線路的票價不改變
3.忽略乘客除票價以外的各項開銷費用
4.不考慮雷雨雲、低雲、大風、雷暴、冰雹等主要天氣因素對飛行的影響。
四、 模型建立
建立帶權鄰接矩陣：
根據飛機路線及票價表建立帶權鄰接矩陣， 在帶權鄰接矩陣中用插入頂點的方法依次構造出 6 個矩陣。
採用floyd演算法步驟為:
:到的最短距離
：到之間的插入點
輸入帶權鄰接距陣
(1) 賦初值：對所有
(2) 更新,:對所有,若，則
,.(3) 若,停止；否則，轉（2）.
執行程式得：
d (1)
d (2) 、
d(3)、
d (4) 、
d（ 5）、
d（6），
使最後得到的矩陣 d ( 6 ) 為飛機的最廉價矩陣。
五、 模型求解結果
根據模型求解，分析得出任意兩個城市之間最廉價線路及票價為：
c1→c2: 1→6→2；35
c1→c3:1→5→3,1→6→4→3;45
c1→c4:1→6→4，1→5→4﹔35
c1→c5∶1→5﹔25
c1→c6:1→6﹔10
c2→c3∶2→3﹔15
c2→c4∶2→4﹔20
c2→c5∶2→4→5﹔30
c2→c6∶2→5﹔25
c3→c4∶3→4﹔10
c3→c5∶3→5∶3→4→5﹔20
c3→c6∶3→4→6﹔35
c4→c5∶4→5﹔10
c4→c6∶4→6﹔25
c5→c6∶5→4→6﹔35
第二次作業
案例分析題 一 案情 四川省瀘州市某公司職工黃永彬和蔣倫芳1963年結婚，但是妻子蔣一直沒有生育，後來只得抱養了乙個兒子。由此原因給家庭籠罩上了一層陰影。1994年，黃永彬認識了乙個名叫張學英的女子，並且在與張認識後的第二年同居。黃的妻子蔣發現這一事實以後，進行勸告但是無效。1996年底，黃永彬和張...
數學建模第二次實驗報告
第二次作業 要求 第二次作業主要是考察學生對matlab基礎知識掌握情況，尤其是迴圈語句，每名同學都有八個小題，根據具體情況給出分值。1 用起泡法對10個數由小到大排序，即將相鄰兩個數比較，將小的調到前頭。2 有乙個4 5矩陣，程式設計求出其最大值及其所處位置。3 程式設計求。4 一球從100公尺高...
圖論第二次作業
一 第四章 4.3 1 畫乙個有euler閉跡和hamilton圈的圖 2 畫乙個有euler閉跡但沒有hamilton圈的圖 3 畫乙個有hamilton圈但沒有euler閉跡的圖 4 畫乙個既沒有euler閉跡也沒有hamilton圈的圖 解 1 乙個有euler閉跡和hamilton圈的圖形如...