网络流对策中若干对策解的算法研究

闫林成

中国海洋大学

摘要：

合作对策考虑的中心问题是如何将联盟的整体费用(收益)公平合理的分配给联盟N中的每个成员。根据不同的合理性要求产生了不同的对策解的概念,如核心、N-核、稳定集和Shapley值等。对策解的定义往往是非常复杂的,算法设计是组合合作对策中重要的课题。网络流对策源于网络中与最大流相关的收益分配问题,是一类重要的组合合作对策,其算法研究具有重要意义。本文主要探讨网络流对策的核心和相对N-核的算法,主要结果有:
(1)讨论了带有公共弧的简单网络流对策模型的核心元素的刻画；利用最大流问题的弧一流表达式和线性规划的对偶理论给出核心非空的充要条件的一个新证明；在此基础上证明了该对策中有关核心的几个算法问题(判断核心的非空性、判定给定分配是否归属核心、构造核心元素)都是多项式时间可解的。
(2)对于不具有公共弧的简单网络流对策模型,建立了其相对N-核的有效的刻画；首先证明了当网络中最大流值等于1时,相对N-核与对策的核心相同,不一定是单点集；其次利用Kopelowitz’s序列线性规划方法和线性规划对偶理论证明当网络中最大流值大于1时,相对N-核与N-核是相同的(同为单点集),并且相对N-核可在局中人个数的多项式时间内得到求解。

关键词：合作对策;网络流;线性规划;收益分配

授予单位：中国海洋大学

授予学位：硕士

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

导师姓名：方奇志

学位年度：2011

语种：中文

分类号：O221.1

页数：39

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