论文部分内容阅读
合作对策考虑的中心问题是如何将联盟的整体费用(收益)公平合理的分配给联盟Ⅳ中的每个成员。根据不同的合理性要求产生了不同的对策解的概念,如核心,核仁和Shapley值等。核仁是刻画合作对策分配合理性的一个重要的解的概念,它不但弥补了核心可能不存在的缺陷,而且这种解是由唯一的一个分配构成。Wallmeier在1983年提出了加权核仁的概念,也就是f-核仁的概念。由于f-核仁定义的复杂性,其算法方面的研究很少。本文讨论两个组合合作对策模型的f-核仁的计算问题:最大权合作对策模型和网络流对策。基于线性规划对偶理论、多面体理论和图论中的相关结果,本文主要讨论了最大权合作对策的两类具体的f-核仁,平均核仁与相对核仁的算法问题以及简单网络流对策的相对核仁的算法问题。主要结果有:
●讨论了f-核仁的性质:当所有非平凡子联盟S均满足fs>0时,f-核仁存在且必是单点集;给出了f-核仁的Kopelowitzs序列线性规划解法。同时,给出例子说明当存在子联盟的费用函数为零时,相对核仁不一定为单点集。
以●针对最大权合作对策模型,给出计算平均核仁和相对核仁的递推公式,并由此说明该对策的平均核仁和相对核仁均可以在局中人个数的多项式时间内得到求解。
●对于简单网络流对策,在求解核仁的对偶线性规划理论基础上,给出相对核仁的“关键子集”的刻画,由此证明相对核仁与核仁相同,说明简单网络流对策的相对核仁可以在多项式时间内得到求解。