多產(chǎn)品選址問題的算法設(shè)計(jì)與分析.pdf

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

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