運籌學(xué)教程胡云權(quán)第五版第五章圖與網(wǎng)絡(luò)分析(編輯修改稿)
2025-05-27 12:10 本頁面
【文章內(nèi)容簡介】 各用戶所在位置如圖所示 ， 鋪設(shè)各用戶點的煤氣管道所需的費用 （ 單位：萬元 ） 如圖邊上的數(shù)字所示 。 要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線 ， 并求所需的總費用 。 A B C D E F G H I J K S 2 2 2 2 2 2 4 5 2 6 3 4 5 3 1 最小支撐樹問題 [例 ]今有煤氣站 A， 將給一居民區(qū)供應(yīng)煤氣 ， 居民區(qū)各用戶所在位置如圖所示 ， 鋪設(shè)各用戶點的煤氣管道所需的費用 （ 單位：萬元 ） 如圖邊上的數(shù)字所示 。 要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線 ， 并求所需的總費用 。 A B C D E F G H I J K S 2 2 2 2 2 2 5 2 6 3 4 5 3 1 最小支撐樹問題 [例 ]今有煤氣站 A， 將給一居民區(qū)供應(yīng)煤氣 ， 居民區(qū)各用戶所在位置如圖所示 ， 鋪設(shè)各用戶點的煤氣管道所需的費用 （ 單位：萬元 ） 如圖邊上的數(shù)字所示 。 要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線 ， 并求所需的總費用 。 A B C D E F G H I J K S 2 2 2 2 2 2 2 6 3 4 5 3 1 最小支撐樹問題 [例 ]今有煤氣站 A， 將給一居民區(qū)供應(yīng)煤氣 ， 居民區(qū)各用戶所在位置如圖所示 ， 鋪設(shè)各用戶點的煤氣管道所需的費用 （ 單位：萬元 ） 如圖邊上的數(shù)字所示 。 要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線 ， 并求所需的總費用 。 A B C D E F G H I J K S 2 2 2 2 2 2 2 6 3 4 5 3 1 最小支撐樹問題 [例 ]今有煤氣站 A， 將給一居民區(qū)供應(yīng)煤氣 ， 居民區(qū)各用戶所在位置如圖所示 ， 鋪設(shè)各用戶點的煤氣管道所需的費用 （ 單位：萬元 ） 如圖邊上的數(shù)字所示 。 要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線 ， 并求所需的總費用 。 I A B C D E F G H J K S 2 2 2 2 2 2 2 3 4 5 3 1 最小支撐樹問題 [例 ]今有煤氣站 A， 將給一居民區(qū)供應(yīng)煤氣 ， 居民區(qū)各用戶所在位置如圖所示 ， 鋪設(shè)各用戶點的煤氣管道所需的費用 （ 單位：萬元 ） 如圖邊上的數(shù)字所示 。 要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線 ， 并求所需的總費用 。 I J A B C D E F G H K S 2 2 2 2 2 2 2 3 4 3 1 此即為最經(jīng)濟(jì)的煤氣管道路線，所需的總費用為 25萬元 最小支撐樹問題 案例分析： 默登公司的聯(lián)網(wǎng)問題 默登（ Modern）公司的管理層決定鋪設(shè)最先進(jìn)的光纖網(wǎng)絡(luò)，為它的主要中心之間提供高速通信。圖 1中的節(jié)點顯示了該公司主要中心的分布圖。虛線是鋪設(shè)光纜可能的位置。每條虛線旁邊的數(shù)字表示成本（單位：百萬美元）。 問： 需要鋪設(shè)哪些光纜使得總成本最低？ A B C E G F D 2 5 2 7 4 5 7 1 3 1 4 4 圖 1 光纜鋪設(shè)費用圖 最小支撐樹問題 A B C E G F D 2 2 5 1 3 1 圖 1 光纜鋪設(shè)最小費用圖 案例分析： 默登公司的聯(lián)網(wǎng)問題 最小支撐樹問題 問題描述： 設(shè) G=(V,E)為連通圖，圖中各邊 (vi， vj)有權(quán)數(shù)lij（ lij=∞表示 vi、 vj 間無邊， vs、 vt為圖中任意兩點，求一條道路 181。，使從 vs到 vt的所有路中總權(quán)數(shù)最小。 v2 v1 v3 v4 v5 v6 v7 v8 v9 1 6 3 2 2 2 2 6 6 1 3 3 10 10 4 4 【 例 】 求網(wǎng)絡(luò)中 v1到 v9的最短路 最短路問題 解法 1： Dijkstra（狄克斯拉）標(biāo)號法 基本思想： 從起點 vs開始，逐步給每個結(jié)點 vj標(biāo)號 [dj， vi]，其中 dj為
法律信息相關(guān)推薦
鄂ICP備17016276號-1