带异常值的k-层设施选址问题的近似算法

发布时间：2021-09-25 16:01

　　带异常值的k-层设施选址问题是k-层设施选址问题和带异常值的无容量设施选址问题的推广问题.研究该问题可以帮助提高社会生产力以及经济效益,具有极高的实用价值.在带异常值的k-层设施选址问题中,给定了 k个设施集合、顾客集合和非负整数q且q<n,其中n是顾客的总数,q为异常值的个数,即不被服务的顾客的数目.每个设施集合都有一个不同的层数,且层数为{1,2,…,k}.每个设施i均可被开设,相应的开设费用fi≥0.任意顾客j从设施i上获得服务产生的连接费用Cij≥0.该问题的目标是在每层设施集合中开设一些设施,将至少n-q个顾客连接到第1层至第k层的开设设施上,使得开设费用和连接费用的总费用最小.针对带异常值的k-层设施选址问题,我们利用了原始对偶技巧,得到了近似比为6的算法.本文提出带异常值的k-层设施选址问题,该问题是NP-困难问题,在P≠NP的假设下,不存在多项式时间的精确算法.对于NP-困难问题,我们通常利用近似算法进行求解.原始对偶技巧是近似算法设计中常用的技巧之一.本文介绍了 k-层设施选址问题的原始对偶算法,利用原始对偶算法的鲁棒性,将算法移植到带异常值的k-层设施选址问题... 

【文章来源】：北京工业大学北京市 211工程院校

【文章页数】：41 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景以及研究意义
    1.2 国内外研究现状
    1.3 预备知识
    1.4 论文结构
第2章 k-层设施选址问题的原始对偶算法
    2.1 k-层设施选址问题
        2.1.1 问题介绍
        2.1.2 数学模型
    2.2 原始对偶算法
        2.2.1 数学符号
        2.2.2 算法
    2.3 本章小结
第3章 带异常值的k-层设施选址问题的6-近似算法
    3.1 带异常值的k-层设施选址问题
        3.1.1 问题介绍
        3.1.2 数学模型
    3.2 原始对偶算法
        3.2.1 数学符号
        3.2.2 算法
    3.3 算法分析
    3.4 本章小结
结论
参考文献
致谢


【参考文献】：
期刊论文
[1]平方度量的k层设施选址问题的近似算法[J]. 邵嘉婷,徐大川,王凤敏.  应用数学学报. 2016(04)



本文编号：3410028