若干边覆盖对策的均衡性研究

刘艳枝

中国海洋大学

摘要：

具有特征函数的合作对策模型Г=(N，c)是由局中人集合Ⅳ和支付特征函数c∶2<'N>→R构成的．如果每个局中人子集对应的特征函数值可通过求解某个组合最优化问题所确定，则称该对策为组合合作对策．整体支付c(N)的不同的分配合理性要求导出了合作对策的各种解的概念．其中，核心是最重要的对策解之一，它体现了分配的子联盟合理性．若核心非空，则称该对策是均衡的．本文主要针对建立在图的边覆盖问题基础上的各种合作对策模型，从算法和计算复杂性角度对核心进行讨论．主要研究内容有：
(1) 首先定义了由图的边覆盖问题导出的两类合作对策模型—松弛和严格边覆盖对策；利用边覆盖问题的一个新的0-1规划模型和拉格朗日对偶理论，给出了这两类边覆盖对策均衡性的刻画和它们之间的等价性．
(2)定义了由图的整数边覆盖问题导出的两类合作对策模型——松弛和严格．{к}-边覆盖对策；延用(1)中的研究方法，给出了这两类对策均衡的等价条件，并讨论了相关的算法问题．
(3)针对从图的七．边覆盖问题引出的合作对策模型，利用线性规划对偶理论得到了其核心非空的一个充分条件及构造核心分配的多项式时间算法，并将这一结果推广到了一般的七．集合覆盖对策模型中.

关键词：边覆盖对策;均衡性;对偶理论;合作对策模型

授予单位：中国海洋大学

授予学位：硕士

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

导师姓名：方奇志

学位年度：2007

语种：中文

分类号：O221.7

页数：31

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