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

基于最小费用支撑树的合作对策问题

作　者: 王小燕
导　师: 谢政
学　校: 国防科学技术大学
专　业: 应用数学
关键词: 合作对策组合优化最小费用支撑树特征函数核心
分类号: O225
类　型: 硕士论文
年　份: 2005年
下　载: 79次
引　用: 0次
阅　读: 论文下载

内容摘要

对策论由于有其特殊的研究领域,且研究方法多种多样,因而与其它数学分支产生了较多的联系。近十年来,随着对策论的发展,它与组合最优化理论的联系越来越密切,两门学科互为对方提供数学手段,共同走向纵深。本文旨在将组合优化中的最小费用支撑树的理论技巧用于解决对策论中一些问题,从而加深它们之间的联系。主要工作如下:1.支付对策中局中人数目变化的合作对策问题,分别给出了局中人数目变化前后该合作对策的分配、核心、核仁、Shapley值的对应情况。2.局中人数目变化的最小费用支撑树对策问题。在局中人数目减少的情况下,给出了顶点相应减少的最小费用支撑树的算法,并基于该算法给出了最小费用支撑树对策联盟K直接离去以后的核心中的分配。因为在可以挽回联盟K的情况下该分配不满足总体支付最小性,所以又给出了可以挽回联盟K的情况下的一个更公平、更合理的分配,且这个分配具有联盟的稳定性和总体支付最小性。在局中人增加的情况下,讨论顶点及边相应增加的最小费用支撑树的变化情况,得出了局中人集合K?加入后的最小费用支撑树对策的核心中的分配。3.最小费用k度限制支撑树对策问题。分别给出了最小费用支撑树的源点度数大于k和小于k时,可行交换的具体形式及复杂性估计,并在此基础上改进了Glover-Klingman算法,给出了改进的Glover-Klingman算法的复杂性估计。利用对策中的威胁理论、旁支付理论制订了两种规则,分别给出了这两种规则对应下的特征函数,并利用这两个特征函数与最小费用支撑树对策特征函数的策略等价关系求出了核心中的分配,从而证明了在这两种规则下最小费用k度限制树对策的核心非空。4.加权最短路树形图对策问题。建立了最短路树形图对策和加权最短路树形图对策模型,并求出了此对策问题在多种意义下的分配。其中问题2、3、4是由最小费用支撑树对策延伸出来的支付对策问题。

全文目录

摘要  6-7
Abstract  7-8
第一章引言  8-12
  1.1 组合对策的研究现状与发展趋势  8-10
  1.2 论文的组织和安排  10-12
第二章预备知识  12-18
  2.1 合作n 人对策  12-16
  2.2 最小费用支撑树对策  16-18
第三章局中人数目变化时的支付对策  18-24
  3.1 局中人数目变化时的分配  18-20
  3.2 局中人数目变化时的核心  20
  3.3 局中人变化时的核仁  20-22
  3.4 局中人数目变化时的Shapley 值  22-23
  3.5 小结  23-24
第四章局中人数目变化的最小费用支撑树对策  24-32
  4.1 局中人减少的最小费用支撑树对策  24-28
  4.2 局中人增加的最小费用支撑树对策  28-31
  4.3 小结  31-32
第五章最小费用k 度限制树对策  32-41
  5.1 最小费用k 度限制树  32-37
  5.2 改进的Glover-Klingman 算法  37
  5.3 最小费用k 度限制树对策模型  37-38
  5.4 最小费用k 度限制树对策的核心  38-40
  5.5 小结  40-41
第六章加权最短路树形图对策  41-47
  6.1 问题背景介绍及对策模型  41
  6.2 基本概念  41-43
  6.3 最短路树形图对策  43-44
  6.4 加权最短路树形图对策  44-46
  6.5 小结  46-47
结论  47-48
致谢  48-49
参考文献  49-52
附录硕士阶段的主要工作  52

基于最小费用支撑树的合作对策问题

内容摘要

全文目录

相似论文