發(fā)布時間：2021-09-25 16:01

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

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

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

【學位級別】：碩士

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


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



本文編號：3410028