設(shè)施選址問題在市政工程、電信領(lǐng)域、信息檢索、供應(yīng)鏈設(shè)計(jì)等方面有廣泛的應(yīng)用,從上個(gè)世紀(jì)六十年代以來一直是組合優(yōu)化領(lǐng)域中的熱點(diǎn)問題.最經(jīng)典的是無容量設(shè)施選址問題,具體地,給出位置確定的設(shè)施集合和位置確定的顧客集合,每個(gè)設(shè)施有相應(yīng)的開設(shè)費(fèi)用,顧客和設(shè)施之間有連接費(fèi)用,目標(biāo)是確定一些設(shè)施開設(shè),將顧客連接到開設(shè)的設(shè)施上,使得開設(shè)設(shè)施的費(fèi)用與連接費(fèi)用之和最小.由于設(shè)施選址問題是NP-難的,設(shè)計(jì)精確算法計(jì)算時(shí)間無法保證.啟發(fā)式算法雖然能在較短的時(shí)間內(nèi)得到可行解,但問題解決過程中容易陷入局部最優(yōu),不能通過理論分析得到近似比,一般情況下也很難得到最優(yōu)解.因此,大部分研究采用設(shè)計(jì)近似算法解決問題.設(shè)施選址問題應(yīng)用廣泛,各種變形問題發(fā)展勢頭強(qiáng)勁,例如k-中位問題,帶有容量的設(shè)施選址問題,魯棒設(shè)施選址問題,隨機(jī)設(shè)施選址問題,k-層設(shè)施選址問題等.本論文研究了幾類設(shè)施選址問題,介紹數(shù)學(xué)模型,設(shè)計(jì)近似算法并給出算法的理論分析.設(shè)施選址問題中,當(dāng)容量約束和開設(shè)設(shè)施基數(shù)約束同時(shí)出現(xiàn)時(shí),問題變得復(fù)雜,目前沒有常數(shù)近似算法.論文首先對(duì)非一致軟容量k-設(shè)施選址問題進(jìn)行研究,利用拉格朗日松弛技巧和隨機(jī)算法得到該問題容量違反的... 

【文章頁數(shù)】：87 頁

【學(xué)位級(jí)別】：博士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景
    1.2 國內(nèi)外研究歷史和現(xiàn)狀
    1.3 基本知識(shí)
    1.4 主要結(jié)果
    1.5 論文結(jié)構(gòu)
第2章 軟容量k-設(shè)施選址問題
    2.1 數(shù)學(xué)模型
    2.2 預(yù)備知識(shí)
    2.3 算法與分析
    2.4 本章小結(jié)
第3章 平方度量動(dòng)態(tài)設(shè)施選址問題
    3.1 數(shù)學(xué)模型
    3.2 算法及分析
    3.3 提高的算法與分析
    3.4 本章小結(jié)
第4章 魯棒動(dòng)態(tài)設(shè)施選址問題
    4.1 數(shù)學(xué)模型
    4.2 算法與分析
    4.3 提高的算法與分析
    4.4 本章小結(jié)
第5章 平方度量帶下界的半徑和問題
    5.1 數(shù)學(xué)模型
    5.2 松弛問題算法與分析
    5.3 原問題的算法與分析
    5.4 本章小結(jié)
結(jié)論
參考文獻(xiàn)
攻讀博士學(xué)位期間發(fā)表的學(xué)術(shù)論文
致謝


【參考文獻(xiàn)】：
期刊論文
[1]設(shè)施選址問題的近似算法綜述[J]. 徐大川,杜東雷,吳晨晨.  數(shù)學(xué)進(jìn)展. 2014(06)



本文編號(hào)：3676813