設施選址問題的近似算法目錄

《運籌與管理科學叢書》序

總序

前言

第1章緒論

1.1無容量限制的設施選址問題

1.2設施選址問題的各種變形

第2章無容量限制的設施選址問題的線·性規(guī)劃舍入算法

2.1STA算法

2.2Chudak—Shmoys算法

2.2.1簡單的4一近似算法

2.2.2隨機（1 3/e）一近似算法

2.2.3隨機f1 2/e）一近似算法

2.2.41.7336一近似算法

2.3Sviridenko算法

2.4Byrka—Aardal算法

2.5Li算法

第3章無容量限制的設施選址問題的原始對偶算法

3.1Jain—Vazirani算法

3.2Pal—Tardos算法

3.3MMSV算法

3.4JMS算法

3.5MYz算法

第4章無容量限制的設施選址問題的局部搜索算法

4.1AGKMMP算法

4.2貪婪增廣算法

4.3Guha—Khuller算法

4.3.12.408—近似算法

4.3.2設施費用相同情形

4.3.3近似比下界

4.4Charikar—Guha算法

4.4.1（1 √2 ε）一近似算法

4.4.21.8526—近似算法

4.4.31.728—近似算法

第5章有容量限制的設施選址問題

5.1軟容量限制的設施選址問題

5.2硬容量限制的設施選址問題的局部搜索算法

5.2.1多交換局部搜索算法

5.2.2算法分析

5.2.3緊的例子

5.3硬容量限制的設施選址問題的線性規(guī)劃舍入算法

第6章k層設施選址問題

6.1問題介紹

6.2線性規(guī)劃舍入算法

6.3光滑化的原始對偶算法

6.4組合算法

6.52層設施選址問題

第7章凹設施選址問題

7.1光滑化的原始對偶算法

7.2對偶擬合算法

第8章不確定設施選址問題

8.1兩階段隨機設施選址問題

8.2風險可調的兩階段隨機設施選址問題

8.3動態(tài)設施選址問題

第9章設施選址問題的其他變形

9.1次模懲罰設施選址問題

9.2帶服務安置費用的設施選址博弈

9.3極大形式的k層設施選址問題

9.4硬容量限制的k層設施選址問題

參考文獻

索引

《運籌與管理科學叢書》已出版書目2100433B

設施選址問題是經典的NP-難解問題之一，在運籌學、計算機科學和管理科學中有著廣泛的應用。徐大川等編著的《設施選址問題的近似算法》介紹了設施選址問題及其變形的近似算法。主要內容包括：無容量限制的設施選址問題的線性規(guī)劃舍入算法、無容量限制的設施選址問題的原始對偶算法、無容量限制的設施選址問題的局部搜索算法、有容量限制的設施選址問題、k層設施選址問題、凹設施選址問題、不確定設施選址問題、設施選址問題的其他變形等。

《設施選址問題的近似算法》可作為運籌學、計算機科學、管理科學和應用數學專業(yè)的高年級本科生和研究生的教材和參考書，亦可供相關研究領域科研人員參考。

所謂設施，是指生產運作過程得以進行的硬件手段，通常是由工廠、辦公樓、車間、設備、倉庫等物質實體所構成。

所謂設施選址，是指如何運用科學的方法決定設施的地理位置，使之與企業(yè)的整體經營運作系統(tǒng)有機結合，以便有效、經濟地達到企業(yè)的經營目的。

設施選址包括兩個層次的問題：

第一：選位，即選擇什么地區(qū)（區(qū)域）設置設施，沿海還是內地，南方還是北方，等等。在當前全球經濟一體化的大趨勢之下，或許還要考慮是國內還是國外；

第二：定址。地區(qū)選定以后，具體選擇在該地區(qū)的什么位置設置設施，也就是說，在已選定的地區(qū)內選定一片土地作為設施的具體位置。設施選址還包括這樣兩類問題：一是選擇一個單一的設施位置；二是在現有的設施網絡中部新點。

設施選址單一設施選址

單一設施選址是指獨立地選擇一個新的設施地點，其運營不受企業(yè)現有設施網絡的影響。在有些情況下，所要選擇位置的新設施是現有設施網絡中的一部分，如某餐飲公司要新開一個餐館，但餐館是與現有的其他餐館獨立運營的，這種情況也可看作單一設施選址。單一設施選址又分以下幾種方法：

負荷距離法（load-distance method）

負荷距離法的目標是在若干個候選方案中，選定一個目標方案，他可以使總負荷（貨物、人或其他）移動的距離最小。當與市場的接近程度等因素至關重要時，使用這一方法可從眾多候選方案中快速篩選出最有吸引力的方案。這一方法也可在設施布置中使用。

因素評分法

因素評分法在常用的選址方法中也許是使用得最廣泛的一種，因為它以簡單易懂的模式將各種不同因素綜合起來。運用這種因素評分法應注意：在運用因素評分法計算過程中可以感覺到，由于確定權數和等級得分完全靠人的主觀判斷，只要判斷有誤差就會影響評分數值，最后影響決策的可能性。關于確定權數的方法很多，比較客觀準確的方法是層次分析法，該方法操作并不復雜，有較為嚴密的科學依據，我們推薦在做多方案多因素評價時盡可能采用層次分析法。

盈虧分析法

盈虧分析法是廠房選址的一種基本方法，亦稱生產成本比較分析法。這種方法基于以下假設：可供選擇的各個方案均能滿足廠址選擇的基本要求，但各方案的投資額不同，投產以后原材料、燃料、動力等變動成本不同。這時，可利用損益平衡分析法的原理，以投產后生產成本的高低作為比較的標準。

選址度量法

選址度量法是一種既考慮定量因素、又考慮定性因素的用以支持設施選址的方法。

重心法

重心法是一種布置單個設施的方法，這種方法要考慮現有設施之間的距離和要運輸的貨物量。它經常用于中間倉庫的選擇。在最簡單的情況下，這種方法假設運入和運出成本是相等的，它并未考慮在不滿載的情況下增加的特殊運輸費用。

設施選址設施網絡選址

設施網絡中的新址選擇比單一設施選擇問題更復雜，因為在這種情況下決定新設施的地點位置時，還必須同時考慮到新設施與其它現有設施之間的相互影響和作用。如果規(guī)劃的好，各個設施之間會相互促進，否則就會起到副面作用。設施網絡選址包括以下幾個方法：

簡單的中線模式法

簡單的中線模式法是一種廠址選擇的方法。這種方法有其局限性。這種方法只假設坐標上最優(yōu)的點（即是使總的運輸距離最短的點）是一個可行的建廠點，并不考慮在那里現在是否有道路，也不考慮自然地形、人口密度，以及其他許多在布點時應考慮的重要事項。

德爾菲分析模型

典型的布置分析考慮的是單一設施的選址，其目標有供需之間的運輸時間或距離極小化，成本的極小化，平均反應時間的極小化。但是，有些選址分析涉及多個設施和多個目標，其決策目標相對模糊，甚至帶有感情色彩。解決這類選址問題的一個方法是使用德爾菲分析模型，該模型在決策過程中考慮了各種影響因素。使用德爾菲分析模型涉及三個小組，即協(xié)調小組、預測小組和戰(zhàn)略小組。每個小組在決策中發(fā)揮不同的作用。

啟發(fā)式方法（heuristics）

啟發(fā)式方法只尋找可行解，而不是最優(yōu)解。負荷距離法中的重心法就是一種啟發(fā)式方法。有許多計算機化了的啟發(fā)式方法，可解決m，n達幾百、幾千的問題。早在60年代，就有人提出了用啟發(fā)式方法解決大型設施選址問題。今天，啟發(fā)式方法已經廣泛在很多場合應用。

模擬方法（simulation）

模擬是試圖通過模型重現某一系統(tǒng)的行為或活動，而不必實地去建造并運轉一個系統(tǒng)，那樣會造成巨大的浪費，或根本沒有可能實地去進行運轉實驗。模擬方法有許多種應用，在選址問題中，模擬可以使分析者通過反復改變和組合各種參數，多次試行來評價不同的選址方案，模擬方法可描述多方面的影響因素，因此比運輸表法有更大的實用意義。

優(yōu)化方法（optimization）

運輸表法實際上就是一種優(yōu)化方法，雖然只是某一方位問題的最優(yōu)。這種方法求出的不是可行解、滿意解，而是最優(yōu)解，即：在所有可能的方案中，不會有比它更好的了。但是由于這種方法要從理論上證明是最優(yōu)，所以它在使用上有兩大局限性：

1）模型必須較抽象、較簡單，否則得不出解。但由此而使模型的描述距實際較遠；

2）很多定性因素被忽略掉了，因此不可能得出在考慮定性條件下可能得出的很多結論。2100433B

對一個企業(yè)來說，設施選址是建立和管理企業(yè)的第一步，也是事業(yè)擴大的第一步。設施選址的重要性顯而易見。其重要性主要在于：設施選支隊設施建成后的設施布置以及投產后的生產經營費用、產品和服務質量以及成本都有極大而長久的影響。一旦選擇不當，它所帶來的不良后果不是通過建成后的加強和完善管理等其他措施可以彌補的。因此，在進行設施選址時，必須充分考慮到多方面因素的影響，慎重決策。其次，除新建企業(yè)的設施選址問題以外，隨著經濟的發(fā)展，城市規(guī)模的擴大，以及地區(qū)之間的發(fā)展差異，很多企業(yè)面臨著遷址的問題。等等。可見，設施選址是很多企業(yè)都面臨的，現代企業(yè)生產運作管理中的一個重要問題。

戰(zhàn)略目標

對于一個特定的企業(yè)，其最優(yōu)選址取決于該企業(yè)的類型。工業(yè)選址決策主要是為了追求成本最小化；而零售業(yè)或專業(yè)服務性組織機構一般都追求收益最大化；至于倉庫選址，可能要綜合考慮成本及運輸速度的問題?？傊?，設施選址的戰(zhàn)略目標是使廠址選擇能給工廠帶來最大化的收益。