边覆盖对策的均衡性及其算法

姚春玲

中国海洋大学

摘要：

组合合作对策，又称组合最优化对策，是建立在组合最优化模型上的合作对策.合作对策理论研究的核心问题是如何将联盟的整体收益(或费用)公平合理地分配给每个局中人.不同的分配合理性要求导出了合作对策中不同对策解的概念.其中，核心是最重要的对策解的概念之一，它体现了分配的子联盟合理性.若核心非空，则称对策是均衡的.本文主要讨论建立在图的边覆盖问题基础上的几个合作对策模型及其均衡性，并从算法和计算复杂性角度对核心进行了研究.主要研究内容有：
(1)首先定义了由图的整数边覆盖问题导出的两类合作对策模型-松弛和严格的{k}-边覆盖对策；利用边覆盖问题的整数规划模型和对偶理论，给出这两类边覆盖对策均衡性的刻画和它们之间的等价性，并讨论了相关的算法问题.
(2)定义了由图的分数边覆盖问题导出的两类合作对策模型-松弛和严格的分数边覆盖对策；利用对偶理论证明了这两类边覆盖对策都是均衡的，并给出了它们核心之间的关系.

关键词：边覆盖对策;核心;均衡性;拉格朗日对偶;多项式时间算法

授予单位：中国海洋大学

授予学位：硕士

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

导师姓名：方奇志

学位年度：2008

语种：中文

分类号：O225

页数：31

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