設施選址問題基於線性規劃的近似算法研究

《設施選址問題基於線性規劃的近似算法研究》是依託北京工業大學，由李改弟擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：設施選址問題基於線性規劃的近似算法研究
• 項目類別：青年科學基金項目
• 項目負責人：李改弟
• 依託單位：北京工業大學

項目摘要

設施選址問題是組合最佳化領域一個重要的模型，在運籌學、計算機科學、庫存管理等方面都有廣泛的套用。本項目主要採用線性規劃捨入、原始對偶和dual-fitting算法研究設施選址問題的三個變形。擬研究的主要內容有：1.擬採用線性規劃捨入方法，設計出新的選擇cluster中心的算法，降低非cluster中心顧客的連線費用，改進k-層無容量設施選址問題的近似比3;基於Gabor & van Ommeren對k-層無容量設施選址問題提出的新模型，採用dual-fitting和原始對偶技巧，改進組合算法最好的近似比3.27；採用原始對偶算法，改進k-層集中器選址問題的近似比。2.容錯設施選址問題常數近似比的組合算法的設計；相同需求容錯設施選址問題的近似比的改進。3.研究凹設施選址問題的線性規劃捨入算法；倉庫零售商網路設計博弈和隨機運輸庫存網路設計博弈的單調費用分攤算法。

結題摘要

設施選址問題是組合最佳化領域的一個經典的NP困難問題，在運籌學、計算機科學和管理科學有廣泛的套用。本項目研究基於線性規劃捨入的近似算法，我們的研究內容和結果有： (1)倉庫零售商網路設計博弈： 我們對倉庫零售商網路設計博弈給出了一個具有單調性、競爭性和3-近似費用恢復的費用分攤方案。我們的費用分攤方案是緊的。該算法給倉庫零售商網路設計給出了開設倉庫方案、以及零售商之間費用分攤方案。 (2)多層的經濟批量生產博弈:我們得到了一個單調、競爭和 2β(2β + 1)--近似費用恢復的費用分攤方案，這裡 β＞1是個常數。該算同時法給出了多層經濟批量生產方案、各層生產商間的成本分攤方案。 (3) 帶線性和次模懲罰的k層設施選址問題：當懲罰費用是線性時，我們給出了3近似算法，改進了Asadi等的近似比4；當懲罰費用是次模函式時，通過採用Wu &Xu對k層設施選址問題的雙因子近似算法技巧，我們得到了3.314近似算法。 (4)帶下界約束的設施選址問題: 我們推廣了Guha等關於下界約束設施選址變形的雙標準近似算法，考慮帶有懲罰和下界約束的設施選址問題，得到了同樣近似比的雙標準近似算法。進一步地，我們推廣這個結果到帶有懲罰、軟容量和下界約束的設施選址問題，得到了近似比是Guha等2倍的雙標準近似算法。 (5)動態設施選址問題： 我們考慮了帶次模懲罰的動態設施選址問題，推廣Jain& Vazirani的算法到這個變形，給出了組合的、原始對偶3近似算法。