設(shè)施選址問題的近似算法

《運(yùn)籌與管理科學(xué)叢書》序

總序

前言

第1章緒論

1.1無容量限制的設(shè)施選址問題

1.2設(shè)施選址問題的各種變形

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

2.1STA算法

2.2Chudak—Shmoys算法

2.2.1簡單的4一近似算法

2.2.2隨機(jī)（1 3/e）一近似算法

2.2.3隨機(jī)f1 2/e）一近似算法

2.2.41.7336一近似算法

2.3Sviridenko算法

2.4Byrka—Aardal算法

2.5Li算法

第3章無容量限制的設(shè)施選址問題的原始對(duì)偶算法

3.1Jain—Vazirani算法

3.2Pal—Tardos算法

3.3MMSV算法

3.4JMS算法

3.5MYz算法

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

4.1AGKMMP算法

4.2貪婪增廣算法

4.3Guha—Khuller算法

4.3.12.408—近似算法

4.3.2設(shè)施費(fèi)用相同情形

4.3.3近似比下界

4.4Charikar—Guha算法

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

4.4.21.8526—近似算法

4.4.31.728—近似算法

第5章有容量限制的設(shè)施選址問題

5.1軟容量限制的設(shè)施選址問題

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

5.2.1多交換局部搜索算法

5.2.2算法分析

5.2.3緊的例子

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

第6章k層設(shè)施選址問題

6.1問題介紹

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

6.3光滑化的原始對(duì)偶算法

6.4組合算法

6.52層設(shè)施選址問題

第7章凹設(shè)施選址問題

7.1光滑化的原始對(duì)偶算法

7.2對(duì)偶擬合算法

第8章不確定設(shè)施選址問題

8.1兩階段隨機(jī)設(shè)施選址問題

8.2風(fēng)險(xiǎn)可調(diào)的兩階段隨機(jī)設(shè)施選址問題

8.3動(dòng)態(tài)設(shè)施選址問題

第9章設(shè)施選址問題的其他變形

9.1次模懲罰設(shè)施選址問題

9.2帶服務(wù)安置費(fèi)用的設(shè)施選址博弈

9.3極大形式的k層設(shè)施選址問題

9.4硬容量限制的k層設(shè)施選址問題

參考文獻(xiàn)

索引

《運(yùn)籌與管理科學(xué)叢書》已出版書目2100433B

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

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

所謂設(shè)施，是指生產(chǎn)運(yùn)作過程得以進(jìn)行的硬件手段，通常是由工廠、辦公樓、車間、設(shè)備、倉庫等物質(zhì)實(shí)體所構(gòu)成。

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

設(shè)施選址包括兩個(gè)層次的問題：

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

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

設(shè)施選址單一設(shè)施選址

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

負(fù)荷距離法（load-distance method）

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

因素評(píng)分法

因素評(píng)分法在常用的選址方法中也許是使用得最廣泛的一種，因?yàn)樗院唵我锥哪Ｊ綄⒏鞣N不同因素綜合起來。運(yùn)用這種因素評(píng)分法應(yīng)注意：在運(yùn)用因素評(píng)分法計(jì)算過程中可以感覺到，由于確定權(quán)數(shù)和等級(jí)得分完全靠人的主觀判斷，只要判斷有誤差就會(huì)影響評(píng)分?jǐn)?shù)值，最后影響決策的可能性。關(guān)于確定權(quán)數(shù)的方法很多，比較客觀準(zhǔn)確的方法是層次分析法，該方法操作并不復(fù)雜，有較為嚴(yán)密的科學(xué)依據(jù)，我們推薦在做多方案多因素評(píng)價(jià)時(shí)盡可能采用層次分析法。

盈虧分析法

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

選址度量法

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

重心法

重心法是一種布置單個(gè)設(shè)施的方法，這種方法要考慮現(xiàn)有設(shè)施之間的距離和要運(yùn)輸?shù)呢浳锪?。它?jīng)常用于中間倉庫的選擇。在最簡單的情況下，這種方法假設(shè)運(yùn)入和運(yùn)出成本是相等的，它并未考慮在不滿載的情況下增加的特殊運(yùn)輸費(fèi)用。

設(shè)施選址設(shè)施網(wǎng)絡(luò)選址

設(shè)施網(wǎng)絡(luò)中的新址選擇比單一設(shè)施選擇問題更復(fù)雜，因?yàn)樵谶@種情況下決定新設(shè)施的地點(diǎn)位置時(shí)，還必須同時(shí)考慮到新設(shè)施與其它現(xiàn)有設(shè)施之間的相互影響和作用。如果規(guī)劃的好，各個(gè)設(shè)施之間會(huì)相互促進(jìn)，否則就會(huì)起到副面作用。設(shè)施網(wǎng)絡(luò)選址包括以下幾個(gè)方法：

簡單的中線模式法

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

德爾菲分析模型

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

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

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

模擬方法（simulation）

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

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

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

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

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

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

戰(zhàn)略目標(biāo)

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