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

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

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

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

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


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



本文編號：3410028