基于网络选址问题的对策、决策模型的算法研究

王光源

中国海洋大学

摘要：

选址问题是组合优化理论中一个有意义的、重要的研究领域。本文讨论两种基于选址问题的对策、决策模型：七一控制集对策模型和设施选址决策模型。对于k-控制集对策，我们着重研究了两种七一控制集对策模型，讨论了它们的关系，并给出了有关核心的非空性证明，主要结果有●给出了两种k-控制集对策模型，讨论了两种k-控制集对策核心的内在联系，证明了在一类特殊网络上它们的核心一定非空，以及构造核心元素的多项式时间算法。
对于设施选址决策模型，我们推广了现有的模型，研究了在多数原则下决策解的性质和有关算法问题，主要结果有给出了决策解的定义，特别对于树型网络，我们给出了寻找该决策模型中的决策解的快速算法。
●讨论了一般网络图上决策模型中的决策解存在的计算复杂性,以及设施数目被看作问题的输入规模时决策解存在的计算复杂性。

关键词：控制集对策;决策解;多项式时间算法;网络;选址问题

授予单位：中国海洋大学

授予学位：硕士

学科专业：运筹学与控制论

导师姓名：方奇志

学位年度：2006

语种：中文

分类号：TP393.0

页数：31

在线出版日期：2007-08-07（万方平台首次上网日期，不代表论文的发表时间）