設(shè)施選址問(wèn)題的近似算法內(nèi)容簡(jiǎn)介

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

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

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

總序

前言

第1章緒論

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

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

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

2.1STA算法

2.2Chudak—Shmoys算法

2.2.1簡(jiǎn)單的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章無(wú)容量限制的設(shè)施選址問(wèn)題的原始對(duì)偶算法

3.1Jain—Vazirani算法

3.2Pal—Tardos算法

3.3MMSV算法

3.4JMS算法

3.5MYz算法

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

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è)施選址問(wèn)題

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

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

5.2.1多交換局部搜索算法

5.2.2算法分析

5.2.3緊的例子

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

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

6.1問(wèn)題介紹

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

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

6.4組合算法

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

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

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

7.2對(duì)偶擬合算法

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

索引

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

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

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

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

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

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

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

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

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

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

因素評(píng)分法

因素評(píng)分法在常用的選址方法中也許是使用得最廣泛的一種，因?yàn)樗院?jiǎn)單易懂的模式將各種不同因素綜合起來(lái)。運(yùn)用這種因素評(píng)分法應(yīng)注意：在運(yùn)用因素評(píng)分法計(jì)算過(guò)程中可以感覺(jué)到，由于確定權(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)常用于中間倉(cāng)庫(kù)的選擇。在最簡(jiǎn)單的情況下，這種方法假設(shè)運(yùn)入和運(yùn)出成本是相等的，它并未考慮在不滿載的情況下增加的特殊運(yùn)輸費(fèi)用。

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

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

簡(jiǎn)單的中線模式法

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

德?tīng)柗品治瞿Ｐ?

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

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

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

模擬方法（simulation）

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

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

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

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

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

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

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

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