店鋪選址最短路徑與選址問題(編輯修改稿)
2025-03-03 05:28 本頁面
【文章內容簡介】 第 5步： ① v5是剛得到 P標號的點。因為 (v5， v6)， (v5 ， v7)∈ E， 而且 v6和 v7都是 T標號，故修改它們的 T標號為 T(v6)＝ min[T(v6)， P(v5)+w56]＝ min[9， 7+1]= 8 T(v7)＝ min[T(v7)， P(v5)+w57]＝ min[+∞， 7+7]=14 ② 在所有 T標號中， T(v6)＝ 8最小，于是令：P(v6)＝ 8。 第 6步： ① v6是剛得到 P標號的點。因為 (v6， v7)∈ E， 而且 v7為 T標號，故修改它的 T標號為 T(v7)＝ min[T(v7)， P(v6)+w67]＝ min[14， 8+5]=13 ② 目前只有 v7是 T標號，故令： P(v7)＝ 13。 從城鎮(zhèn) v1到 v7之間的最短路徑為 (v1， v2， v3， v5， v6， v7)， 最短路徑長度為 13。 二、選址問題 選址問題，是現(xiàn)代地理學研究的主要問題之一。選址問題涉及人類生產、生活、文化、娛樂等各個方面。 選址問題的數(shù)學模型取決于兩個方面的條件 ：可供選址的范圍、條件；怎樣判定選址的質量。 本節(jié)的討論僅限于選址的范圍是一個地理網絡，而且選址位置位于網絡圖的某一個或幾個頂點上。 對這樣的選址問題，根據其選址的質量判據，可以將其歸納為求網絡圖的中心點與中位點兩類問題。 （一） 中心點選址問題 例 ：某縣要在其所轄的 6個鄉(xiāng)鎮(zhèn)之一修建一個消防站，為 6個鄉(xiāng)鎮(zhèn)服務，要求消防站至最遠鄉(xiāng)鎮(zhèn)的距離達到最小。 n 中心點選址問題的質量判據 使最佳選址位置所在的頂點的最大服務距離為最小。 中心點選址問題適宜于醫(yī)院、消防站點等一類服務設施的布局問題。 設 G＝（ V， E） 是一個無向簡單連通賦權圖，連接兩個頂點的邊的權值代表它們之間的距離，對于每一個頂點 vi， 它與各個頂點之間的最短路徑長度為 di1， di2， … ， din。 這些距離中的最大數(shù)稱為頂點 vi的最大服務距離，記為 e(vi)。 那么，中心點選址問題，就是求網絡圖 G的中心點 ，使得 n 中心點選址問題的數(shù)學描述 例 2：假設某縣下屬的 6個鄉(xiāng)鎮(zhèn)及其之間公路聯(lián)系如圖所示。每一頂點代表一個鄉(xiāng)鎮(zhèn)；每一條邊代表連接兩個鄉(xiāng)鎮(zhèn)之間的公路，每一條邊旁的數(shù)字代表該條公路的長度。現(xiàn)在要設立一個消防站，為全縣的6個鄉(xiāng)鎮(zhèn)服務。試問該消防站應該設在哪一個鄉(xiāng)鎮(zhèn)（頂點）？ 圖 解 ： 第 1步： 用標號法求出每一個頂點 vi至其他各個頂點 vj的最短路徑長度 dij（ i， j ＝ 1， 2，… ， 6）， 并將它們寫成如下的距離矩陣 第 2步： 求每一個頂點的最大服務距離。顯然，它們分別是矩陣 D中各行的最大值，即： e(
法律信息相關推薦
鄂ICP備17016276號-1