运筹学12对策论精选ppt课件.ppt

运筹学课程建设组 1 第十二章博弈论 1引论 2博弈论的概念及历史沿革 3矩阵对策的最优纯策略 4矩阵对策的混合策略 5我们从博弈论中学习什么 运筹学课程建设组 2 1引论 为了对什么是博弈论以及博弈包括哪些类型等问题有一些更清晰的理解和认识 本节先介绍几个典型的简单博弈问题实例 并对它们作初步的分析 其实博弈本身就如这些实例一样 并不像人们通常理解的那样深奥 复杂 当然 要想完全弄懂它 也的确需要下一番功夫 回本章目录 运筹学课程建设组 3 一 猜币博弈古老的流传广泛的猜硬币游戏想来对于我们每一个人来说都不陌生 而正是这样的一个简单游戏构成了一个最基本的博弈问题 这个游戏非常简单 两人通过猜硬币的正反面赌输赢 其中一人抛起一枚硬币 用手盖住后 由另一方猜是正面朝上还是反面朝上 若猜对 则猜者赢 盖硬币者输 否则 猜者输 而盖硬币者赢 运筹学课程建设组 4 如果我们记赢的一方收益为1角 记为收益1 输的一方损失1角 记为收益 1 则我们可用表12 1中收益矩阵表示这个猜硬币博弈问题 表12 1猜币博弈 运筹学课程建设组 5 表12 1中盖硬币者和猜硬币者为本博弈的两个博弈方 它们各有正面和反面两种可选择的情况 策略 由于每一方都不会让对方在选择之前知道自己的选择 当然也不可能提前知道 因此 此博弈可看作两博弈方是同时作决策的 收益矩阵中数组元素表示在所处行列对应的两博弈方的策略组合下双方各自的收益 其中前一数字表示盖硬币者的收益 后一数字表示猜硬币者的收益 运筹学课程建设组 6 本例两博弈方的可选策略数较少 只有各两种 又只有四种可能的结果 因此相对简单一些 但它却充分体现了博弈问题的基本特性 即取胜的关键都是不能让另一方猜到自己的策略而同时自己又要尽可能猜出对方的策略 在多次重复中 如果双方的决策方式都正确 则我们求得平均的双方收益 这一问题当然也可以通过概率论来解答 运筹学课程建设组 7 二 齐威王与田忌赛马齐威王与大将田忌赛马是在我国民间流传很广的故事 它主要是讲田忌的谋士孙膑如何运用计谋帮助田忌以弱胜强战胜齐威王 我们从这个故事中可以引出一个很好的博弈问题 运筹学课程建设组 8 春秋战国时期齐威王有一个嗜好 就是愿与别人赛马 经常约手下大将田忌与他赛马 赛马的规则是这样的 每次双方各出三匹马 一对一比赛三场 每一场的败者要输一千金给胜者 齐威王的三匹马按实力都可分为上 中 下三等 由于齐威王的上 中 下三匹马都分别比田忌的上 中 下三匹马略胜一筹 因此田忌每次都是连输三场 要输掉三千金 运筹学课程建设组 9 实际上 田忌的上马虽不如齐威王的上马 却比齐威王的中马和下马都要好 同样 田忌的中马则比齐威王的下马要好一些 田忌每次都输三场是有些冤枉的 后来田忌的谋士孙膑知道这一情况后 给田忌出了个主意 即让田忌不要用自己的上马去对抗齐威王的上马 而是用下马去对抗齐威王的上马 上马则去对抗齐威王的中马 中马去对抗齐威王的下马 这样 虽然第一场田忌必败无疑 但后两场田忌却都能胜 二胜一负 田忌反而能赢齐威王一千金 运筹学课程建设组 10 这个故事生动地告诉我们 巧妙地运用策略是那么的重要 在实力 条件一定的情况下 对已方力量和有利条件的巧妙调度和运用常会起到意想不到的效果 运筹学课程建设组 11 但是 如果这个故事到这里就结束了 那它还只是一个单方面运用策略的较为简单的问题 因为在赛马的齐威王和田忌两方中 只有田忌一方意识到策略的重要性 在安排马的出场次序方面运用策略 而齐威王一方却没有充分运用策略来应对田忌的策略 显然还构不成一个双人博弈的问题 这里为说明问题 我们不妨假设齐威王发觉田忌在使用计谋 明白了自己为什么输金的原因而及时地调整自己的对策 这样 齐威王与田忌的赛马也就成了一个具有策略依存特征的决策较量 构成了一个典型的博弈问题 运筹学课程建设组 12 这个重新设定的齐威王与田忌赛马的博弈问题可以用博弈的术语表示如下 1 该博弈中有两个博弈参与者 即齐威王和田忌 2 两博弈参与者可选择的策略即为各自马的出场次序 因为三匹马的排列次序共有6种 因此双方各有6种可选择的策略 如表1 3 3 根据前面的讨论 假设双方在决策之前都不能预先知道对方的决策 因此可以看作是同时选择策略的 而且决策选择没有先后次序的关系 运筹学课程建设组 13 4 如果把赢一千金记成收益为1 输一千金记成收益为 1 则两博弈参与者在各种策略组合下的收益如表14 2收益矩阵中数组元素所示 每个数组表示两博弈参与者在对应行列代表的双方策略下各自的收益 其中前一个数字表示齐威王的收益 后一个数字表示田忌的收益 运筹学课程建设组 14 表12 2齐威王与田忌赛马博弈 田忌 齐威王 运筹学课程建设组 15 由表12 2我们可以看到 如果按照严格的博弈问题的假设来重新安排这一游戏的话 齐威王只要把从策略集中选择策略的顺序不断改动 随机产生选择 不让田忌掌握策略规律 齐威王的胜率 统计事件 显然要高于田忌 运筹学课程建设组 16 2博弈论的概念及历史沿革 一 概念 什么是博弈论1 概念 博弈 就是一些个人 团队或组织 面对一定的环境条件 在一定的规则下 同时或者先后 一次或者多次 从各自允许选择的行为或策略中进行选择并加以实施 从而最大化己方效用的行为过程 回本章目录 运筹学课程建设组 17 博弈论 GameTheory是研究决策主体的行为发生直接相互作用时候的决策 以及这种决策的均衡问题的理论 是研究博弈过程中 局中人各自所选策略的科学 是研究局中人的行为 局中人形成决策时的相互影响 以及他们之间的冲突与合作关系的科学 运筹学课程建设组 18 张维迎的定义 博弈论是研究决策主体的行为发生直接相互作用时候的决策以及这种决策的均衡问题的 也就是说 当一个主体 好比说一个人或一个企业的选择受到其他人 其他企业选择的影响 而且反过来影响到其他人 其他企业选择时的决策问题和均衡问题 所以在这个意义上说 博弃论又称为 对策论 运筹学课程建设组 19 2 理性人假设 博弈论的基本假设是 理性人假设博弈论认为 参与人都是理性人 理性人 即有一个很好定义的偏好 在给定的约束条件下 总是设法最大化自己的偏好 理性 又分为集体理性和个人理性 集体理性导致合作 个人理性导致非合作 于是 博弈又有合作博弈与非合作博弈之分 运筹学课程建设组 20 例囚徒困境 1950年 数学家A W Tucker任斯坦福大学客座教授 在给心理学家作演讲时 讲了两个囚犯的故事 囚犯困境 Prisoner sDilemma 囚徒B 囚徒A 坦白 抵赖 坦白 抵赖 运筹学课程建设组 21 囚徒困境说明了什么 在 坦白 坦白 这个组合中 和 都不能通过单方面的改变行动增加自己的收益 于是谁也没有动力游离这个组合 因此这个组合是纳什均衡 也叫非合作均衡 囚徒困境反映了个人理性和集体理性的矛盾 如果 和 都选择抵赖 各判刑 年 显然比都选择坦白各判刑 年好得多 当然 和 可以在被警察抓到之前订立一个 攻守同盟 但是这可能不会有用 因为它不构成纳什均衡 没有人有积极性遵守这个协定 显然最好的策略是双方都抵赖 运筹学课程建设组 22 囚徒困境的意义 囚徒的两难选择 有着广泛而深刻的意义 个人理性与集体理性的冲突 各人追求利己行为而导致的最终结局是一个 纳什均衡 也是对所有人都不利的结局 他们两人都是在坦白与抵赖策略上首先想到自己 这样他们必然要服长的刑期 只有当他们都首先替对方着想时 或者相互合谋 串供 时 才可以得到最短时间的监禁的结果 运筹学课程建设组 23 对经典经济学的冲击 纳什均衡 首先对亚当 斯密的 看不见的手 的原理提出挑战 按照斯密的理论 在市场经济中 每一个人都从利己的目的出发 而最终全社会达到利他的效果 国富论 通过追求 个人的 自身利益 他常常会比其实际上想做的那样更有效地促进社会利益 从 纳什均衡 我们引出了 看不见的手 的原理的一个悖论 从利己目的出发 结果损人不利己 既不利己也不利他 两个囚徒的命运就是如此 从这个意义上说 纳什均衡 提出的悖论实际上动摇了西方经济学的基石 运筹学课程建设组 24 NASH均衡条件下的行为规则 合作是有利的 利己策略 但它必须符合以下黄金律 按照你愿意别人对你的方式来对别人 但只有他们也按同样方式行事才行 所谓 己所不欲勿施于人 但前提是人所不欲勿施于我 运筹学课程建设组 25 3 博弈论的要素 博弈论的提法可能太过于学术化 容易让人们退避三舍 其实它有一个非常通俗的名字 游戏理论 博弈论的英文名字叫做 如果直译 就是 游戏理论 博弈论在我国还有一个名字 叫对策论 这些名字都很好理解 博弈字面意思就是赌博 下棋 赌博和下棋当然是游戏了 赌博和下棋的时候常常要千方百计地应付对手 自然是要讲究对策了 运筹学课程建设组 26 1 参与人players 一个博弈中的决策主体 他的目的是通过选择行动 或战略 以最大化自己的支付 效用水平 参与人可能是自然人 也可能是团体 如企业 国家等 重要的是 每个参与人必须有可供选择的行动和一个很好定义的偏好函数 不做决策的被动主体只能被当作环境参数 虚拟参与人pseudo player为了分析方便 自然nature被当作虚拟参与人 自然代表决定外生随机变量的概率分布的机制 比如房地产开发中市场需求的大小 运筹学课程建设组 27 2 策略集 局中人选择对付其它局中人的行动方案称为策略 某局中人的所有可能策略全体称为策略集 局中人各自使用一个对策就形成了一个局势 一个局势决定了各局中人的对策结果 称为该局势对策的益损值 3 一局势对策的益损值 运筹学课程建设组 28 4 行动ACTIONSORMOVES 参与人在博弈的某个时点的决策变量 坦白 N个参与人的行动的有序集称为行动组合 坦白 抵赖 行动的顺序对于博弈的结果非常重要 有关静态和动态博弈的区分就是基于行动的顺序做出的 同样的行动集合 行动的顺序不同 每个参与人的最有决策就不同 博弈的结果也不同 尤其在不完全信息博弈中 后行动者依赖观察先行动者的行动来获取信息 运筹学课程建设组 29 5 信息information 参与人有关博弈的知识 特别是有关自然的选择 其他参与人的特征和行动的知识 完美信息perfectinformation 指一个参与人对其他参与人的行动选择有准确的理解 6 均衡equilibrium 指所有参与人的最优战略的组合 纳什均衡 指的是这样一种战略组合 这种战略组合由所有参与人的最优战略联合组成 当别人战略给定的情况下 没有任何一个参与人有积极性改选其他战略 从而没有人愿意打破现已形成的这种均衡 如 囚徒困境问题中的 坦白 坦白 运筹学课程建设组 30 二 历史沿革 上世纪50年代以前 1944年冯 诺依曼 Neumann 和摩根斯坦 Morgensten 合著的 博弈论和经济行为 一书的出版 标志着博弈理论框架的基本形成 50年代到70年代 纳什 Nash 为非合作博弈的一般理论和合作博弈的谈判理论奠定了基础 提出了博议论中最重要的概念 纳什均衡 70年代到90年代 博弈论作为一种方法论开始大量应用于经济学 在纳什等人的努力下博弈论逐步形成了一个完整的理论体系 90年代至今 博弈论和经济学交融发展 博弈论已经成为现代经济学中重要的方法论 回本章目录 运筹学课程建设组 31 三位诺贝尔经济学奖获得者的工作1994年为表彰纳什 Nash 泽尔腾 Selten 和海萨尼 Harsanyi 在博弈论上做出的贡献 三人被授予诺贝尔经济学奖 运筹学课程建设组 32 三位大师主要的贡献 1950年和1951年纳什的两篇关于非合作博弈论的重要论文 彻底改变了人们对竞争和市场的看法 他证明了非合作博弈及其均衡解 并证明了均衡解的存在性 即著名的纳什均衡 从而揭示了博弈均衡与经济均衡的内在联系 因为在现实世界中 非合作博弈要比合作博弈普遍得多 运筹学课程建设组 33 SeltenandHarsanyi 泽尔腾 1965 将纳什均衡的概念引入了动态分析 提出了 精炼纳什均衡 概念 以及进一步刻画不完全信息动态博弈的 完备贝叶斯纳什均衡 而海萨尼则发展了刻画不完全信息静态博弈的 贝叶斯纳什均衡 1967 1968 总之 他俩进一步将纳什均衡动态化 加入了接近实际的不完全信息条件 他们的工作为后人继续发展博弈论 提供了基本思路和模型 运筹学课程建设组 34 三 分类 在博弈论中可以根据不同方式对博弈问题进行分类 通常分类的方式有 1 根据局中人的个数 分为二人博弈和多人博弈 2 根据各局中人的赢得函数的代数和是否为零 可分为零和博弈和非零和博弈 3 根据局中人是否合作 又可分为合作博弈和非博弈对策 4 根据局中人的策略集中个数 又分为有限博弈和无限博弈 或连续博弈 5 也可根据局中人掌握信息的情况及决策选择是否和时间有关可分为完全信息静态博弈 完全信息动态博弈 非完全信息静态博弈及非完全信息动态博弈 回本章目录 运筹学课程建设组 35 博弈的分类及对应的均衡 运筹学课程建设组 36 2 完全信息动态博弈在完全信息静态对策中 假设各方都同时选择行动 现在情况稍复杂一些 如果各方行动存在先后顺序 后行的一方会参考先行者的策略而采取行动 而先行者也会知道后行者会根据他的行动采取何种行动 因此先行者会考虑自己行动会对后行者的影响后选择行动 这类问题称为完全信息动态对策问题 1 完全信息静态博弈 囚徒困境问题 前述 运筹学课程建设组 37 例某行业中只有一个垄断企业A 有一个潜在进入者 企业B B可以选择进入或不进入该行业这两种行动 而A当B进入时 可以选择默认或者报复两种行动 如果B进入后A企业报复 将造成两败俱伤的结果 但如果A默认B进入 必然对A的收益造成损失 同样的 如果B进入而A报复 则B受损 反之 将受益 把此关系用图表示 运筹学课程建设组 38 由分析可知 上例中 B选择不进入 A选择报复 和 B选择进入 A选择默许 都是纳什均衡解 但在实际中 B选择不进入 A选择报复 这种情况是不可能出现的 因为B知道他如果进入 A只能默许 所以只有 B选择进入 A选择默许 会发生 或者说 A选择报复行动是不可置信的威胁 对策论的术语中 称 A选择默许 B选择进入 为精炼纳什均衡 当只当参与人的战略在每一个子对策中都构成纳什均衡 这个纳什均衡才称为精炼纳什均衡 当然 如果A下定决心一定要报复B 即使自己暂时损失 这时威胁就变成了可置信的 B就会选择不进入 B选择不进入 A选择报复 就成为精炼纳什均衡 军事交战时 破釜沉舟 讲的就是一种可置信威胁 实际企业经营中也有很多类似的例子 运筹学课程建设组 39 3 不完全信息静态博弈 市场进入博弈 前述的 市场进入博弈 考虑如下变化 进入者并不知道在位者的成本函数 认为在位者可能是高成本也可能是低成本 当然在位者自己知道 遇到不同成本函数的在位者支付矩阵不同 运筹学课程建设组 40 4 不完全信息动态博弈 市场进入博弈市场进入问题考虑如下情况 假定分两个时期 第一时期 在位者垄断市场 进入者决定进入或不进入 若进入 在第二时期双方竞争 否则第二阶段在位者仍然垄断市场 在位者可能是高成本 也可能是低成本 进入者只知道在位者是高成本的概率为p 低成本的概率为1 p 进入者只有一种类型 如果进入 生产成本与高成本在位者相同 在位者根据自己成本操纵垄断价格限制进入者进入 进入者根据观察到的价格判断在位者的成本 修正p为p1 作为自己下一步决策的依据 运筹学课程建设组 41 5 多人非合作博弈有三个或三个以上博弈方参加的博弈就是 多人博弈 多人博弈同样也是博弈方在意识到其他博弈方的存在 意识到其他博弈方对自己决策的反应和反作用存在的情况下寻求自身最大利益的决策活动 因而 它们的基本性质和特征与两人博弈是相似的 我们常常可以用研究两人博弈同样的思路和方法来研究它们 或将两人博弈的结论推广到多人博弈 不过 毕竟多人博弈中出现了更多的追求各自利益的独立决策者 因此 策略的相互依存关系也就更为复杂 对任一博弈方的决策引起的反应也就要比两人博弈复杂得多 并且 在多人博弈中还有一个与两人博弈有本质区别的特点 即可能存在 破坏者 所谓破坏者即一个博弈中具有下列特征的博弈方 其策略选择对自身的得益没有任何影响 但却会影响其它博弈方的得益 有时这种影响甚至有决定性的作用 例如有三个城市争夺某届奥运会的主办权 运筹学课程建设组 42 多人博弈可以分为合作的和非合作的 非合作博弈顾名思义 就是局中人之间不存在合作 即各局中人在采取行动之前 没有事前的交流和约定 在其行为发生相互作用时 也不会达成任何有约束力的协议 每个局中人都选择于已最有利的策略以使效用水平最大化 然而 在非合作博弈中 双方的利益也并非是完全冲突的 即对一个局中人有利的局势并不一定对其他局中人一定不利 故多人非合作博弈不一定是零和博弈 如同矩阵对策中纯策略意义下的解有时不存在一样 有些非合作博弈也不存在纯策略纳什均衡 在这种情况下 局中人就必须考虑混合策略 运筹学课程建设组 43 6 非零和博弈所谓零和博弈 就是一方的收益必定是另一方的损失 这种博弈的特点是不管各博弈方如何决策 最后各博弈方得益之和总是为零 有某些博弈中 每种结果之下各博弈方的得益之和不等于0 但总是等于一个非零常数 就称之为 常和博弈 当然 可以将零和博弈本身看作是常和博弈的特例 零和博弈 和 常和博弈 之外的所有博弈都可被称为 非零和博弈 非零和博弈即意味着在不同策略组合 结果 下各博弈方的得益之和一般是不相同的 如前述囚徒困境就是典型的非零和博弈 应该说 非零和博弈是最一般的博弈类型 而常和博弈和零和博弈都是它的特例 在非零和博弈中 存在着总得益较大的策略组合和总得益较小的策略组合之间的区别 这也就意味着在博弈方之间存在着互相配合 争取较大的总得益和个人得益的可能性 两人零和博弈是完全对抗性的 总得益为0 其解法可能性根据矩阵对策予以求解 但在非零和博弈下 矩阵对策求解法已经不适用了 下面用例子予以说明 运筹学课程建设组 44 例3甲乙两公司生产同一产品 均想以登广告扩大产品销售 每家公司都有 登 与 不登 两种策略 双方的得益矩阵如下 我们根据得益矩阵来分析 从甲公司立场上看 登有利 不管乙公司如何 保证赢利至少是3 最多是9 如果不登 可能要蒙受损失2 从乙公司的立场上看 同样理由 还是登广告好 但是 这是从理智行为出发的策略 是以彼此不能合作为前提的 上述两公司均采取登广告的策略是稳定的结局 可是 如果彼此能够合作 而都不登广告 免去了广告费 反而各自的赢利要多 在彼此不能合作的情况下 如果甲不登 恰好乙登 甲只好出现败局 这是非理智的策略 带有危险性 因此 非零和博弈常常不易获得最理想的答案 对于三个以上的多人零和博弈 互相利害关系更加复杂 运筹学课程建设组 45 在众多博弈模型中 占有重要地位的是二人有限零和博弈 又称矩阵对策 所谓二人有限零和博弈是指有2个局中人 每个局中人的策略集的策略数目都是有限的 每一局势的对策均有确定的损益值 并且对同一局势的两个局中人的益损值之和为零 通常将矩阵对策记为 G S1 S2 A S1 甲的策略集 S2 乙的策略集 A 甲的赢得矩阵 齐王赛马 是一个矩阵策略 3矩阵对策的最优纯策略 回本章目录 运筹学课程建设组 46 在甲方的赢得矩阵中 A aij m ni行代表甲方策略i 1 2 m j行代表乙方策略j 1 2 n aij代表甲方取策略i 乙方取策略j 这一局势下甲方的益损值 此时乙方的益损值为 aij 零和性质 在考虑各方采用的策略时 必须注意一个前提 就是双方都是理智的 即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据 2矩阵对策的最优纯策略 3矩阵对策的最优纯策略 运筹学课程建设组 47 例 甲乙乒乓球队进行团体对抗赛 每队由三名球员组成 双方都可排成三种不同的阵容 每一种阵容可以看作一种策略 双方各选一种策略参赛 比赛共赛三局 规定每局胜者得1分 输者得 1分 可知三赛三胜得3分 三赛二胜得1分 三赛一胜得 1分 三赛三负得 3分 甲队的策略集为S1 1 2 3 乙队的策略集为S2 1 2 3 根据以往比赛的资料 有甲队的赢得矩阵为A 如下所示 请问这次比赛各队采用哪种阵容上场最为稳妥 3矩阵对策的最优纯策略 运筹学课程建设组 48 矩阵A中每行的最小元素分别为1 3 1 在这些最少赢得中最好的结果是1 故甲队会采取策略 1 无论对手采取何策略 甲队至少得1分 对于乙队 1 2 3 可能带来的最少赢得 即A中每列的最大元素 分别为3 1 3 乙队会采取 2策略 确保甲队不会超过1分 1和 2分别称为局中人甲队 乙队的最优策略 由于双方必然选择这一种策略 所以 这种策略又称为最优纯策略 这种最优纯策略只有当赢得矩阵A aij 中等式成立时 双方才有最优纯策略 并把 1 2 称为对策G在纯策略下的解 又称 1 2 为对策G的鞍点 把其值V称之为对策G S1 S2 A 的值 3矩阵对策的最优纯策略 运筹学课程建设组 49 例某单位采购员在秋天决定冬季取暖用煤的储量问题 已知在正常的冬季气温条件下要消耗15吨煤 在较暖和较冷的天气下要消耗10吨和20吨 假定冬天的煤价随天气寒冷程度而有所变化 在较暖和 正常 较冷的气候条件下每吨煤价分别为10元 15元 20元 又设冬季时煤炭价格为每吨10元 在没有关于当年冬季准确的气象预报的条件下 秋天储煤多少吨能使得单位的支出最少 解 局中人I为采购员 局中人II为大自然 采购员有三个策略 买10吨 15吨 20吨 分别记为 1 2 3 大自然也有三个策略 暖 正常 冷 分别记为 1 2 3 3矩阵对策的最优纯策略 运筹学课程建设组 50 赢得矩阵如下 在此表上计算 有得故 3 3 为对策G的解 VG 200 3矩阵对策的最优纯策略 运筹学课程建设组 51 设矩阵对策G S1 S2 A 当maxminaij minmaxaijijji时 不存在最优纯策略 例 设一个赢得矩阵如下 min595A max6策略 2866imax89min8策略 1j 4矩阵对策的混合策略 回本章目录 运筹学课程建设组 52 当甲取策略 2 乙取策略 1时 甲实际赢得8比预期的多2 乙当然不满意 考虑到甲可能取策略 2这一点 乙采取策略 2 若甲也分析到乙可能采取策略 2这一点 取策略 1 则赢得更多为9 此时 对两个局中人甲 乙来说 没有一个双方均可接受的平衡局势 其主要原因是甲和乙没有执行上述原则的共同基础 即maxminaij minmaxaij ijji一个自然的想法 对甲 乙 给出一个选取不同策略的概率分布 以使甲 乙 在各种情况下的平均赢得 损失 最多 最少 即混合策略 4矩阵对策的混合策略 运筹学课程建设组 53 求解混合策略的问题有图解法 迭代法 线性方程法和线性规划法等 我们这里只介绍线性规划法 其他方法略 例 设甲使用策略 1的概率为X1 使用策略 2的概率为X2 并设在最坏的情况下 甲赢得的平均值为V 未知 59A STEP1861 X1 X2 1X1 X2 0 4矩阵对策的混合策略 运筹学课程建设组 54 2 无论乙取何策略 甲的平均赢得应不少于V 对乙取 1 5X1 8X2 V对乙取 2 9X1 6X2 V注意V 0 因为A各元素为正 STEP2作变换 X1 X1 V X2 X2 V得到上述关系式变为 X1 X2 1 V V愈大愈好 待定5X1 8X2 19X1 6X2 1X1 X2 0 4矩阵对策的混合策略 运筹学课程建设组 55 建立线性模型 minX1 X2s t 5X1 8X2 1X1 1 219X1 6X2 1X2 2 21X1 X2 01 V X1 X2 1 7所以 V 7返回原问题 X1 X1V 1 3X2 X2V 2 3于是甲的最优混合策略为 以1 3的概率选 1 以2 3的概率选 2 最优值V 7 4矩阵对策的混合策略 运筹学课程建设组 56 同样可求乙的最优混合策略 设乙使用策略 1的概率为Y1 Y1 Y2 1设乙使用策略 2的概率为Y2 Y1 Y2 0设在最坏的情况下 甲赢得的平均值为V 这也是乙损失的平均值 越小越好 作变换 Y1 Y1 V Y2 Y2 V建立线性模型 maxY1 Y2s t 5Y1 9Y2 1Y1 1 148Y1 6Y2 1Y2 1 14Y1 Y2 01 V Y1 Y2 1 7所以 V 7 4矩阵对策的混合策略 运筹学课程建设组 57 返回原问题 Y1 Y1V 1 2Y2 Y2V 1 2于是乙的最优混合策略为 以 的概率选 1 以 的概率选 2 最优值V 7 当赢得矩阵中有非正元素时 V 0的条件不一定成立 可以作下列变换 选一正数k 令矩阵中每一元素加上k得到新的正矩阵A 其对应的矩阵对策G S1 S2 A 与G S1 S2 A 解相同 但VG VG k 4矩阵对策的混合策略 运筹学课程建设组 58 例 求解 齐王赛马 问题 已知齐王的赢得矩阵A求得故不存在纯策略问题下的解 可求其混合策略 A中有负元素 可以取k 2 在A的每个元素上加2得到A 如下 4矩阵对策的混合策略 运筹学课程建设组 59 建立对G S1 S2 A 中求甲方最佳策略的线性规划如下 Minx1 x2 x3 x4 x5 x6约束条件 5x1 3x2 3x3 x4 3x5 3x6 13x1 5x2 x3 3x4 3x5 3x6 13x1 3x2 5x3 3x4 3x5 x6 13x1 3x2 3x3 5x4 x5 3x6 1x1 3x2 3x3 3x4 5x5 3x6 13x1 x2 3x3 3x4 3x5 5x6 1xi 0 i 1 2 6可解得解为 x1 x4 x5 0 x2 x3 x6 0 111 v 3 x1 x4 x5 0 x2 x3 x6 1 3 即X 0 1 3 1 3 0 0 1 3 T 所以甲的最优策略为作出策略 2 3 6的概率都为0 333 而作出 1 4 5的概率为0 此时V G V 3 4矩阵对策的混合策略 运筹学课程建设组 60 同样可以建立对策G S1 S2 A 中求乙方最佳策略的线性规划如下 Miny1 y2 y3 y4 y5 y6约束条件 5y1 3y2 3y3 3y4 y5 3y6 13y1 5y2 3y3 3y4 3y5 y6 13y1 y2 5y3 3y4 3y5 3y6 1y1 3y2 3y3 5y4 3y5 3y6 13y1 3y2 3y3 y4 5y5 3y6 13y1 3y2 y3 3y4 3y5 5y6 1yi 0 i 1 2 6可解得解为 y1 y4 y5 0 111 y2 y3 y6 0 v 3 y1 y4 y5 1 3 y2 y3 y6 0 即Y 1 3 0 0 1 3 1 3 0 T 所以田忌的最优混合策略为作出策略 1 4 5的概率都为1 3 而作出 2 3 6的概率为0 此时VG VG k 1 4矩阵对策的混合策略 运筹学课程建设组 61 齐王赛马问题的对策最优解可简记为X 0 1 3 1 3 0 0 1 3 T Y 1 3 0 0 1 3 1 3 0 T 对策值VG 1 例两个局中人进行对策 规则是两人互相独立的各自从1 2 3这三个数字中任意选写一个数字 如果两人所写的数字之和为偶数 则局中人乙支付给局中人甲以数量为此和数的报酬 如果两人所写数字之和为奇数 则局中人甲付给局中人乙以数量为此和数的报酬 试求出其最优策略 解 首先计算局中人甲的赢得矩阵如下表 4 56 34 5 2 34 1 出1 2 出2 3 出3 3 出3 2 出2 1 出1 甲的赢得甲的策略 4矩阵对策的混合策略 乙的策略 运筹学课程建设组 62 即甲的赢得矩阵为A 可知无纯策略意义的解 下面求其在混合策略下的解 A的各元素都加上6 得到建立线性规划模型如下 Minx1 x2 x3Maxy1 y2 y3S T 8x1 3x2 10 x3 18y1 3y2 10y3 13x1 10 x2 x3 13y1 10y2 y3 110 x1 x2 12x3 110y1 y2 12y3 1x1 x2 x3 0y1 y2 y3 0 4矩阵对策的混合策略 运筹学课程建设组 63 得到x1 0 25 x2 0 50 x3 0 25 y1 0 25 y2 0 50 y3 0 25 即此对策的解为X 0 25 0 50 0 25 T Y 0 25 0 50 0 25 T VG VG k 0 4矩阵对策的混合策略 运筹学课程建设组 64 例4甲乙两个企业生产同一种电子产品 甲企业可以采取的策略措施有 1 降低产品价格 2 提高产品质量 3 推出新产品 乙企业考虑采取的策略措施有 1 增加广告费用 2 增设维修网点 加强售后服务 3 改进产品性能 由于甲乙两个企业财力有限 都只能采取一个措施 假定这两个企业所占有的市场总份额一定 由于各自采取的措施不同 通过预测今后两个企业的市场占有份额变动情况如下表 试求出这两个企业各自的最优策略 3 58 6510 108 12 1 措施1 2 措施2 3 措施3 3 措施3 2 措施2 1 措施1 4矩阵对策的混合策略 甲的赢得甲的策略 乙的策略 运筹学课程建设组 65 解 易知此对策无纯策略意义下的解 把A的每一个元素加上12 得到A 建立线性规划模型如下 Minx1 x2 x3Maxy1 y2 y3S T 22x1 20 x2 122y1 6y2 15y3 16x1 17x2 22x3 120y1 17y2 7y3 115x1 7x2 20 x3 122y2 20y3 1x1 x2 x3 0y1 y2 y3 0得到 x1 0 027 x2 0 020 x3 0 023 y1 0 0225 y2 0 0225 y3 0 025 V 14 29 x1 0 3858 x2 0 2858 x3 0 3286 y1 0 3215 y2 0 3215 y3 0 3572 即此对策的解为X 0 3858 0 2858 0 3286 T Y 0 3215 0 3215 0 3572 T VG VG k 2 29 4矩阵对策的混合策略 运筹学课程建设组 66 优超原则 假设矩阵对策G S1 S2 A 甲方赢得矩阵A aij m n若存在两行 列 s行 列 的各元素均优于t行 列 的元素 即asj atjj 1 2 n ais aiti 1 2 m 称甲方策略 s优超于 t s优超于 t 优超原则 当局中人甲方的策略 t被其它策略所优超时 可在其赢得矩阵A中划去第t行 同理 当局中人乙方的策略 t被其它策略所优超时 可在矩阵A中划去第t列 如此得到阶数较小的赢得矩阵A 其对应的矩阵对策G S1 S2 A 与G S1 S2 A 等价 即解相同 4矩阵对策的混合策略 运筹学课程建设组 67 例 设甲方的益损值 赢得矩阵为32030被第3 4行所优超50259被第3行所优超A 7395946875 560883得到73959被第1列所优超A1 46875 5被第2列所优超60883 4矩阵对策的混合策略 运筹学课程建设组 68 得到739A2 465 5603被第1行所优超得到739被第1列所优超A3 465 573最终得到A4 46 4矩阵对策的混合策略 运筹学课程建设组 69 对A4计算 用线性规划方法得到 注意 余下的策略为 3 4 1 2 甲 X 0 0 1 15 2 15 0 TV 5X 0 0 1 3 2 3 0 T乙 Y 1 10 1 10 0 0 0 TV 5Y 1 2 1 2 0 0 0 T 注 利用优超原则化简赢得矩阵时 有可能将原对策问题的解也划去一些 多解情况 线性规划求解时有可能是多解问题 4矩阵对策的混合策略 运筹学课程建设组 70 5我们从博弈论中学习什么 博弈论并不是经济学的一个分支 它只是一种方法 这也是为什么许多人将其看成数学的一个分支的缘故 博弈论已经在政治 经济 外交和社会学领域有了广泛的应用 它为解决不同实体的冲突和合作提供了一个宝贵的方法 在对参与者行为研究这一点上 博弈论和经济学家的研究模式是完全一样的 经济学越来越转向人与人关系的研究 特别是人与人之间行为的相互影响和相互作用 人与人之间利益和冲突 竞争与合作 而这正是博弈论的研究对象 回本章目录 运筹学课程建设组 71 5我们从博弈中学习什么 博弈论告诉人们 要学会理解他人都有自己的思想 每个个体都是理性的 所以必须了解竞争对手的思想 商业关系被认为是一种相互作用 但博弈论并不是疗法 并不是处方 它并不告诉你该付多少钱买东西 这是计算机或者字典的任务 博弈论只是提供一些关系的例证 一些有用的解决问题的方法 这种思维方法也许是企业家应该学习的 对于经济学家 也许需要学习它的理论模型 它的实验方式 回本章目录 运筹学课程建设组 72 博弈论是一个强有力的分析工具 现在 它不仅在经济学领域 在军事 政治 商业征战 社会科学领域以及生物学等自然科学领域都有非常重大的影响 工程学中如控制论工程也少不了它 帮助大家形成博弈论的基本概念 实际上它是非常精深的 现在与它紧密联系的经济学分支是信息经济学 信号游戏 拍卖形式 激励机制 委托人 代理人理论和公共财政学是博弈论和信息经济学研究的重要课题 运筹学课程建设组 73 对博弈论的两种极端评价 从20世纪70年代末期 学者们逐渐形成一个共识 当一个人或群体与他或他们的博弈论对手都能以理性的方式做出决策行为的时候 那就是博弈论大显身手的场合 有人将博弈论比作Mendel的遗传理论和Darwin的自然选择对生物学的影响 或者Newton的天体力学对物理学的奠基作用 真正的社会并不严格是博弈论的理想对象 无论是股票市场上的投机现象 还是受制于传统文化的惯性影响下的体制选择 如同混沌动力系统理论带给人们的初始兴奋之后 博弈论并不具有有历史上像物理学中理论的预测能力 运筹学课程建设组 74 几个例子 1 囚徒困境在经济学和生活中的例子中东石油输出国OPEC限