第三章運輸工具選舉與干線運輸決策(編輯修改稿)
2025-01-16 04:37 本頁面
【文章內容簡介】 距離最短 、 時間最省或是費用最少 。 數(shù)學模型 —— 求網(wǎng)絡圖中二點之間的最短路問題 。 采用網(wǎng)絡規(guī)劃中求最短路 Dijkstra算法 （ 標號算法 ） 。 除了距離以外 ， 還需要考慮通過交通網(wǎng)絡的時間長短 。 起點 A 終點 J 90分鐘 138 348 153 48 90 120 132 48 150 126 132 60 84 84 126 J I H G F E D C B A 例如，從上圖中找出 A與 J之間的最短路線。 最短路與最大流 起點 A 終點 J 90分鐘 138 348 153 48 90 120 132 48 150 126 132 60 84 84 126 J I H G F E D C B A 0,0 A, ? A, ? A,? A, ? A, ? A, 348 A,138 A,90 A, ? 起點 A 終點 J 90分鐘 138 348 153 48 90 120 132 48 150 126 132 60 84 84 126 J I H G F E D C B A 0,0 F, 283 E, 258 B,174 C, 228 D, 339 C, 291 A,138 A,90 I, 384 66 例題 5 要把 A市的一批貨物運送到 B市，根據(jù)兩個城市之間可選擇的行車路線地圖，繪制了圖 5—13的公路網(wǎng)絡。要求尋找一條線路最短的運輸路線。 1 A市 4 5 2 3 7 6 9 8 10 B市 100 150 175 300 275 200 175 275 200 300 200 400 250 125 100 150 ? 圖中 為結點，代表起點、目的地和與行車路線相交的其他城市，其中的數(shù)字為結點編號。 ?箭頭為分支，代表兩個結點之間的公路，箭頭上標明的數(shù)字為運輸里程。 公路網(wǎng)絡 1 解：從終點開始逐步逆向推算。 (1)與終點 10聯(lián)接的結點有兩個，即結點 9和 8； 從結點 9到結點 10只有一條線路，該線路為最短線路，長度 100，記為： （ 910） 100； 同樣，結點 8到結點 10的最短線路為 150，記為 （ 810） 150； (2)結點 6。與 6聯(lián)接的只有一個結點 9， 6至 9的最短里程為 200。而 9至終點 10的最短里程為100．因此 6至終點 10的最短里程為 200十 100＝ 300。記為： (6910)300。 (3)結點 5。與 5聯(lián)接的結點有 8兩個。 5至 9再至終點的最短里程為 400十 100＝ 500， 5至 8再至終點的最短里程為 250十 155＝ 400。 400＜ 500，所以 5至終點的最短里程為 400，記為： (5810)400。 (4) 結點 7。至終點的最短里程為 125十 150＝ 275，記為： (7810) 275。 1 A市 4 5 2 3 7 6 9 8 10 B市 100 150 175 275 200 175 275 200 300 200 400 250 125 100 150 300 (5)結點 4。與 4聯(lián)接的結點有 7三個。 結點 4至 6再到終點的最短里程為 200十 300=500； 結點 4至 5再到終點的最短里程為 175十 400＝ 575； 結點 4至 7再到終點的最短里程為 275十 275＝ 550。 三個里程中以 500為最小，所以結點 4至 l 0的最短里程記為 (4— 6— 9— 10) 500。 (6)結點 2和 3。 用同樣的方法，得到： 結點 2到終點的最短里程為 600。記為： (2— 6— 9— 10)600。 結點 3到終點的最短里程為 575。記為： (3— 7— 8— 10)575。 (5)最后看結點 1。結點 1可以通過三個結點 4連接到終點。 結點 1通過結點 2再到終點的最短里程 100十 600＝ 700，路徑為 （ 1— 2— 6— 9— 10） 700； 結點 1通過結點 4再到終點的最短里程 150十 500＝ 650，路徑為 （ 1— 4— 6— 9— 10） 650； 結點 1通過結點 3再到終點的最短里程 175十 575＝ 750，路徑為 （ 1— 3— 7— 8— 10） 750。 以上三
研究報告相關推薦
鄂ICP備17016276號-1