学位论文 > 优秀研究生学位论文题录展示

若干组合优化对策模型中的算法问题

作　者: 孙晓勋
导　师: 方奇志
学　校: 中国海洋大学
专　业: 应用数学
关键词: 网络流对策核心核心稳定性核心包容性对策精确性对策可扩性核子 NP-困难对偶理论纳什均衡
分类号: O225
类　型: 硕士论文
年　份: 2006年
下　载: 122次
引　用: 0次
阅　读: 论文下载

内容摘要

合作对策考虑的是如何将收益v(N)合理地分配给联盟N中的成员。根据不同的合理性要求产生了不同的对策解的概念,如核心,核子等等。在这篇论文中,我们主要讨论的对策模型是由Kalai和Zemel在1982年首先提出的网络流对策,讨论的内容包括:网络流对策的核心稳定性和网络流对策中核子计算的算法问题,主要结果有:我们先定义了一种特殊的弧,称之为亚元,亚元满足的性质是:在网络中去掉亚元后不会影响网络的最大流值。基于这一概念,我们证明了简单网络流对策有稳定的核心当且仅当网络中没有亚元。我们讨论了三个与核心稳定性密切相关的性质:核心的包容性、对策的精确性和可扩性的等价性,并证明了它们这三个性质与如下条件等价:在简单网络中每个(s,t)-截包含一个最小(s,t)-截。(其中s,t分别表示网络的发点和收点)证明了可以在多项式时间内求解简单网络流对策的核子。证明了对于一般的网络流对策,有关核子的计算问题是NP-困难的。非合作对策理论中,最重要、最核心的概念是纳什均衡。在论文的最后一部分中,本文讨论了一种基于线性规划约束的多人决策模型。首先,我们运用线性规划和对偶理论给出了纳什均衡点存在的充分必要条件,进而证明了在这种模型下的纳什均衡点可以在多项式时间内求解。其次,在原有的纳什均衡定义的基础上,我们定义了一个强均衡的概念:payo?-proof纳什均衡,并对所述决策模型研究了payo?-proof纳什均衡的性质和存在性。

全文目录

摘要  3-4
Abstract  4-5
目录  5-7
第一章综述  7-17
  1.1 组合优化对策  7-9
  1.2 计算复杂性理论  9-10
  1.3 组合优化对策及其核心  10-14
  1.4 组合优化对策的核子及其计算复杂性  14-15
  1.5 决策系统中的非合作对策模型及纳什均衡解  15-17
第二章简单网络流对策中核心的稳定性  17-27
  2.1 引言  17-18
  2.2 核心稳定性的定义  18
  2.3 网络流对策  18-19
  2.4 简单网络流对策的核心稳定性  19-23
  2.5 核心的包容性、对策的精确性和可扩性的等价性  23-27
第三章网络流对策中核子的计算复杂性  27-47
  3.1 引言  27-28
  3.2 基本概念  28-29
  3.3 简单网络流对策中核子的计算复杂性  29-38
  3.4 一般网络流对策中核子的计算复杂性  38-47
第四章一类决策模型的payoff-proof 纳什均衡解  47-54
  4.1 引言  47
  4.2 模型和payoff-proof 纳什均衡的定义  47-49
  4.3 纳什均衡的刻划  49-51
  4.4 Payoff-proof 纳什均衡的刻划  51-54
参考文献  54-58
致谢  58

若干组合优化对策模型中的算法问题

内容摘要

全文目录

相似论文