多產品選址問題的算法設計與分析.pdf

1、選址問題是組合優(yōu)化領域中的一類重要問題，它是對于一些網絡服務器、核電站或者物流中心等有限且重要的資源進行選址決策，在生產管理與調度，網絡通信，理論計算機科學等方面有廣泛的應用。 本文研究了設施選址中的一類模型：多產品選址模型(K-PUFLP)。Huang和Li(2007)首先提出了一類在度量空間特性下的多產品選址模型，并給出了一個近似比不超過2k-1的啟發(fā)式算法。本文的主要工作如下： 第一章是緒論部分，簡單地介紹了選址問

2、題的相關定義、記號及相關知識，描述了多產品選址模型的一些特性。 第二章研究了多產品選址問題的整數及線性模型。對于K-PUFLPN(K≥2)，提出了一個改進的算法ME，并證明了該算法最壞性能比不超過3/2k-1。另外，對于算法ME求解2-PUFLPN，給出了2是該算法緊界的證明。并討論了它的線性規(guī)劃問題的松馳的整數間隙。 第三章對兩類算法落到樹結構上的性能進行了分析和討論，通過找到一個反例，給出了算法ME的解落到樹結構上不