本文關鍵詞：關于可靠性設施布局問題的近似算法

  更多相關文章： 設施布局問題 可靠性 近似算法 貪心算法 原始對偶

【摘要】：設施布局問題的研究始于20世紀60年代，主要研究選擇修建設施的位置和數(shù)量以及與需要得到服務的城市之間的分配關系，使得設施的修建費用和設施與城市之間的連接費用之和達到最小。設施布局問題自提出以來，，就一直占據(jù)著運籌學研究中的中心位置，在理論、算法設計和直用方面得到了廣泛研究。隨著實際直用的深入，設施布局問題產(chǎn)生了許多相直的變型和擴展。其中，具有可靠性的設施布局問題就是近年來一個熱點研究問題。 在現(xiàn)實生活中，受自然災害，工幾罷工，恐怖襲擊等因素的影響，修建的設施可能會出現(xiàn)故障，故連接到它的城市無法得到供直，這就直接影響到了整個系統(tǒng)的可靠性。針對如何以相對較小的代價換取設施布局可靠性的提升，研究幾員提出了可靠性設施布局問題�，F(xiàn)有的可靠性設施布局問題的算法基本都是基于拉格朗日松弛與連續(xù)近似方法設計的，雖然對某些實例有較好的效果，但是住住運算時間過長，而且不具有理論上好的近似度。 本文著重討論可靠性設施布局問題的組合算法設計，主要工作如下： (1)對經(jīng)典設施布局問題的各種變型和推廣進行了概括總結，并系統(tǒng)地給出了可靠性設施布局問題的數(shù)學模型； (2)對設施布局問題現(xiàn)有的算法和算法設計技巧進行了歸納；分忻了現(xiàn)有可靠性設施布局問題的算法一一拉格朗日松弛方法和連續(xù)近似方法的缺點與不足，提出了該問題組合算法的設計思路； (3)參考經(jīng)典設施布局問題的貪心算法、原始對偶算法和容錯性問題中分階段分層次處理的思想，設計了可靠性設施布局問題的一個組合算法。該算法不僅在理論上具有很好的常數(shù)近似度，而且還具有運算復雜性低的優(yōu)點。這對于之前的可靠性設施布局問題只有數(shù)值實驗算法，是一個很大的進步。
【學位授予單位】：中國海洋大學
【學位級別】：碩士
【學位授予年份】：2011
【分類號】：TB114

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前3條

1 潘銳;朱大銘;馬紹漢;;一般設施定位問題計算復雜度和近似算法研究[J];計算機研究與發(fā)展;2007年05期

2 寧釗;石勝飛;李建中;王朝坤;;傳感器網(wǎng)絡中一種支持多分辨率區(qū)域查詢的數(shù)據(jù)存儲方法[J];計算機研究與發(fā)展;2012年03期

3 李委霖;張鵬;朱大銘;;On Constrained Facility Location Problems[J];Journal of Computer Science & Technology;2008年05期

本文編號：1201797