帶異常值的k-層設(shè)施選址問題是k-層設(shè)施選址問題和帶異常值的無容量設(shè)施選址問題的推廣問題.研究該問題可以幫助提高社會(huì)生產(chǎn)力以及經(jīng)濟(jì)效益,具有極高的實(shí)用價(jià)值.在帶異常值的k-層設(shè)施選址問題中,給定了 k個(gè)設(shè)施集合、顧客集合和非負(fù)整數(shù)q且q<n,其中n是顧客的總數(shù),q為異常值的個(gè)數(shù),即不被服務(wù)的顧客的數(shù)目.每個(gè)設(shè)施集合都有一個(gè)不同的層數(shù),且層數(shù)為{1,2,…,k}.每個(gè)設(shè)施i均可被開設(shè),相應(yīng)的開設(shè)費(fèi)用fi≥0.任意顧客j從設(shè)施i上獲得服務(wù)產(chǎn)生的連接費(fèi)用Cij≥0.該問題的目標(biāo)是在每層設(shè)施集合中開設(shè)一些設(shè)施,將至少n-q個(gè)顧客連接到第1層至第k層的開設(shè)設(shè)施上,使得開設(shè)費(fèi)用和連接費(fèi)用的總費(fèi)用最小.針對(duì)帶異常值的k-層設(shè)施選址問題,我們利用了原始對(duì)偶技巧,得到了近似比為6的算法.本文提出帶異常值的k-層設(shè)施選址問題,該問題是NP-困難問題,在P≠NP的假設(shè)下,不存在多項(xiàng)式時(shí)間的精確算法.對(duì)于NP-困難問題,我們通常利用近似算法進(jìn)行求解.原始對(duì)偶技巧是近似算法設(shè)計(jì)中常用的技巧之一.本文介紹了 k-層設(shè)施選址問題的原始對(duì)偶算法,利用原始對(duì)偶算法的魯棒性,將算法移植到帶異常值的k-層設(shè)施選址問題... 

【文章來源】：北京工業(yè)大學(xué)北京市 211工程院校

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

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景以及研究意義
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 預(yù)備知識(shí)
    1.4 論文結(jié)構(gòu)
第2章 k-層設(shè)施選址問題的原始對(duì)偶算法
    2.1 k-層設(shè)施選址問題
        2.1.1 問題介紹
        2.1.2 數(shù)學(xué)模型
    2.2 原始對(duì)偶算法
        2.2.1 數(shù)學(xué)符號(hào)
        2.2.2 算法
    2.3 本章小結(jié)
第3章 帶異常值的k-層設(shè)施選址問題的6-近似算法
    3.1 帶異常值的k-層設(shè)施選址問題
        3.1.1 問題介紹
        3.1.2 數(shù)學(xué)模型
    3.2 原始對(duì)偶算法
        3.2.1 數(shù)學(xué)符號(hào)
        3.2.2 算法
    3.3 算法分析
    3.4 本章小結(jié)
結(jié)論
參考文獻(xiàn)
致謝


【參考文獻(xiàn)】：
期刊論文
[1]平方度量的k層設(shè)施選址問題的近似算法[J]. 邵嘉婷,徐大川,王鳳敏.  應(yīng)用數(shù)學(xué)學(xué)報(bào). 2016(04)



本文編號(hào)：3410028