运筹学对策论.ppt

管理科学与工程学院管理科学与工程学院2024/5/22 周三1第十二章 博弈论 1 引论 2 博弈论的概念及历史沿革 3 矩阵对策的最优纯策略 4 矩阵对策的混合策略 5 我们从博弈论中学习什么管理科学与工程学院管理科学与工程学院2024/5/22 周三21 引论 为了对什么是博弈论以及博弈包括哪些类型等问题有一些更清晰的理解和认识，本节先介绍几个典型的简单博弈问题实例，并对它们作初步的分析。其实博弈本身就如这些实例一样，并不像人们通常理解的那样深奥、复杂，当然，要想完全弄懂它，也的确需要下一番功夫。回本章目录管理科学与工程学院管理科学与工程学院2024/5/22 周三3 一、猜币博弈 古老的流传广泛的猜硬币游戏想来对于我们每一个人来说都不陌生，而正是这样的一个简单游戏构成了一个最基本的博弈问题。这个游戏非常简单，两人通过猜硬币的正反面赌输赢，其中一人抛起一枚硬币，用手盖住后，由另一方猜是正面朝上还是反面朝上，若猜对，则猜者赢，盖硬币者输；否则，猜者输，而盖硬币者赢。管理科学与工程学院管理科学与工程学院2024/5/22 周三4 如果我们记赢的一方收益为1角（记为收益1），输的一方损失1角（记为收益-1），则我们可用表12-1中收益矩阵表示这个猜硬币博弈问题。表12-1 猜币博弈 猜硬猜硬币币方方盖硬盖硬币币方方正正 面面反反 面面正正 面面-1，11，-1反反 面面1，-1-1，1管理科学与工程学院管理科学与工程学院2024/5/22 周三5 表12-1中盖硬币者和猜硬币者为本博弈的两个博弈方，它们各有正面和反面两种可选择的情况（策略）。由于每一方都不会让对方在选择之前知道自己的选择（当然也不可能提前知道），因此，此博弈可看作两博弈方是同时作决策的。收益矩阵中数组元素表示在所处行列对应的两博弈方的策略组合下双方各自的收益，其中前一数字表示盖硬币者的收益，后一数字表示猜硬币者的收益。管理科学与工程学院管理科学与工程学院2024/5/22 周三6 本例两博弈方的可选策略数较少，只有各两种，又只有四种可能的结果，因此相对简单一些，但它却充分体现了博弈问题的基本特性，即取胜的关键都是不能让另一方猜到自己的策略而同时自己又要尽可能猜出对方的策略。在多次重复中，如果双方的决策方式都正确，则我们求得平均的双方收益，这一问题当然也可以通过概率论来解答。管理科学与工程学院管理科学与工程学院2024/5/22 周三7 二、齐威王与田忌赛马 齐威王与大将田忌赛马是在我国民间流传很广的故事，它主要是讲田忌的谋士孙膑如何运用计谋帮助田忌以弱胜强战胜齐威王。我们从这个故事中可以引出一个很好的博弈问题。管理科学与工程学院管理科学与工程学院2024/5/22 周三8 春秋战国时期齐威王有一个嗜好，就是愿与别人赛马，经常约手下大将田忌与他赛马。赛马的规则是这样的：每次双方各出三匹马，一对一比赛三场，每一场的败者要输一千金给胜者。齐威王的三匹马按实力都可分为上、中、下三等。由于齐威王的上、中、下三匹马都分别比田忌的上、中、下三匹马略胜一筹，因此田忌每次都是连输三场，要输掉三千金。管理科学与工程学院管理科学与工程学院2024/5/22 周三9 实际上，田忌的上马虽不如齐威王的上马，却比齐威王的中马和下马都要好，同样，田忌的中马则比齐威王的下马要好一些，田忌每次都输三场是有些冤枉的。后来田忌的谋士孙膑知道这一情况后，给田忌出了个主意，即让田忌不要用自己的上马去对抗齐威王的上马，而是用下马去对抗齐威王的上马，上马则去对抗齐威王的中马，中马去对抗齐威王的下马。这样，虽然第一场田忌必败无疑，但后两场田忌却都能胜，二胜一负，田忌反而能赢齐威王一千金。管理科学与工程学院管理科学与工程学院2024/5/22 周三10 这个故事生动地告诉我们，巧妙地运用策略是那么的重要。在实力、条件一定的情况下，对已方力量和有利条件的巧妙调度和运用常会起到意想不到的效果。管理科学与工程学院管理科学与工程学院2024/5/22 周三11 但是，如果这个故事到这里就结束了，那它还只是一个单方面运用策略的较为简单的问题，因为在赛马的齐威王和田忌两方中，只有田忌一方意识到策略的重要性，在安排马的出场次序方面运用策略，而齐威王一方却没有充分运用策略来应对田忌的策略，显然还构不成一个双人博弈的问题。这里为说明问题，我们不妨假设齐威王发觉田忌在使用计谋，明白了自己为什么输金的原因而及时地调整自己的对策。这样，齐威王与田忌的赛马也就成了一个具有策略依存特征的决策较量，构成了一个典型的博弈问题。管理科学与工程学院管理科学与工程学院2024/5/22 周三12 这个重新设定的齐威王与田忌赛马的博弈问题可以用博弈的术语表示如下：（1）该博弈中有两个博弈参与者，即齐威王和田忌。（2）两博弈参与者可选择的策略即为各自马的出场次序，因为三匹马的排列次序共有6种，因此双方各有6种可选择的策略（如表1-3）。（3）根据前面的讨论，假设双方在决策之前都不能预先知道对方的决策，因此可以看作是同时选择策略的，而且决策选择没有先后次序的关系。管理科学与工程学院管理科学与工程学院2024/5/22 周三13（4）如果把赢一千金记成收益为1，输一千金记成收益为-1，则两博弈参与者在各种策略组合下的收益如表14-2收益矩阵中数组元素所示，每个数组表示两博弈参与者在对应行列代表的双方策略下各自的收益，其中前一个数字表示齐威王的收益，后一个数字表示田忌的收益。管理科学与工程学院管理科学与工程学院2024/5/22 周三14表12-2 齐威王与田忌赛马博弈.上中上中下下上下上下中中中上中上下下中下中下上上下上下上中中下中下中上上上上 中中 下下3，-31，-11，-11，-1-1，11，-1上上 下下 中中1，-13，-31，-11，-11，-1-1，1中中 上上 下下1，-1-1，13，-31，-11，-11，-1中中 下下 上上-1，11，-11，-13，-31，-11，-1下下 上上 中中1，-11，-11，-1-1，13，-31，-1下下 中中 上上1，-11，-1-1，11，-11，-13，-3田忌齐威王 管理科学与工程学院管理科学与工程学院2024/5/22 周三15 由表12-2我们可以看到，如果按照严格的博弈问题的假设来重新安排这一游戏的话，齐威王只要把从策略集中选择策略的顺序不断改动（随机产生选择），不让田忌掌握策略规律，齐威王的胜率（统计事件）显然要高于田忌。管理科学与工程学院管理科学与工程学院2024/5/22 周三16 2 博弈论的概念及历史沿革一、概念，什么是博弈论 1概念：博弈：就是一些个人、团队或组织，面对一定的环境条件，在一定的规则下，同时或者先后、一次或者多次、从各自允许选择的行为或策略中进行选择并加以实施，从而最大化己方效用的行为过程。回本章目录管理科学与工程学院管理科学与工程学院2024/5/22 周三17 博弈论：Game Theory 是研究决策主体的行为发生直接相互作用时候的决策、以及这种决策的均衡问题的理论。是研究博弈过程中、局中人各自所选策略的科学。是研究局中人的行为、局中人形成决策时的相互影响、以及他们之间的冲突与合作关系的科学。管理科学与工程学院管理科学与工程学院2024/5/22 周三18张维迎的定义 “博弈论是研究决策主体的行为发生直接相互作用时候的决策以及这种决策的均衡问题的”，也就是说，当一个主体，好比说一个人或一个企业的选择受到其他人、其他企业选择的影响，而且反过来影响到其他人、其他企业选择时的决策问题和均衡问题。所以在这个意义上说，博弃论又称为“对策论”.管理科学与工程学院管理科学与工程学院2024/5/22 周三192、理性人假设博弈论的基本假设是：理性人假设博弈论认为：参与人都是理性人。理性人：即有一个很好定义的偏好，在给定的约束条件下，总是设法最大化自己的偏好。“理性”又分为集体理性和个人理性。集体理性导致合作，个人理性导致非合作。于是，博弈又有合作博弈与非合作博弈之分。管理科学与工程学院管理科学与工程学院2024/5/22 周三20例 囚徒困境1950年，数学家A.W.Tucker任斯坦福大学客座教授，在给心理学家作演讲时，讲了两个囚犯的故事：囚犯困境(Prisoners Dilemma)：囚徒B-8，-80，-10-10，0-1，-1囚徒A 坦白抵赖坦白抵赖管理科学与工程学院管理科学与工程学院2024/5/22 周三21囚徒困境说明了什么在（坦白、坦白）这个组合中，和都不能通过单方面的改变行动增加自己的收益，于是谁也没有动力游离这个组合，因此这个组合是纳什均衡，也叫非合作均衡。囚徒困境反映了个人理性和集体理性的矛盾。如果和都选择抵赖，各判刑年，显然比都选择坦白各判刑年好得多。当然，和可以在被警察抓到之前订立一个攻守同盟，但是这可能不会有用，因为它不构成纳什均衡，没有人有积极性遵守这个协定,显然最好的策略是双方都抵赖.管理科学与工程学院管理科学与工程学院2024/5/22 周三22囚徒困境的意义“囚徒的两难选择”有着广泛而深刻的意义。个人理性与集体理性的冲突，各人追求利己行为而导致的最终结局是一个“纳什均衡”，也是对所有人都不利的结局。他们两人都是在坦白与抵赖策略上首先想到自己，这样他们必然要服长的刑期。只有当他们都首先替对方着想时，或者相互合谋(串供)时，才可以得到最短时间的监禁的结果。管理科学与工程学院管理科学与工程学院2024/5/22 周三23对经典经济学的冲击“纳什均衡”首先对亚当斯密的“看不见的手”的原理提出挑战。按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。国富论：“通过追求(个人的)自身利益，他常常会比其实际上想做的那样更有效地促进社会利益。”从“纳什均衡”我们引出了“看不见的手”的原理的一个悖论：从利己目的出发，结果损人不利己，既不利己也不利他。两个囚徒的命运就是如此。从这个意义上说，“纳什均衡”提出的悖论实际上动摇了西方经济学的基石。管理科学与工程学院管理科学与工程学院2024/5/22 周三24NASH均衡条件下的行为规则合作是有利的“利己策略”。但它必须符合以下黄金律：按照你愿意别人对你的方式来对别人，但只有他们也按同样方式行事才行。所谓“己所不欲勿施于人”。但前提是人所不欲勿施于我。管理科学与工程学院管理科学与工程学院2024/5/22 周三253博弈论的要素 博弈论的提法可能太过于学术化，容易让人们退避三舍。其实它有一个非常通俗的名字-游戏理论（博弈论的英文名字叫做，如果直译，就是游戏理论）。博弈论在我国还有一个名字，叫对策论。这些名字都很好理解，博弈字面意思就是赌博、下棋，赌博和下棋当然是游戏了，赌博和下棋的时候常常要千方百计地应付对手，自然是要讲究对策了。管理科学与工程学院管理科学与工程学院2024/5/22 周三26（1）参与人 playersv一个博弈中的决策主体，他的目的是通过选择行动（或战略）以最大化自己的支付（效用水平）。参与人可能是自然人，也可能是团体，如企业，国家等。v重要的是：每个参与人必须有可供选择的行动和一个很好定义的偏好函数。不做决策的被动主体只能被当作环境参数。虚拟参与人pseudo-player为了分析方便，自然nature被当作虚拟参与人。自然代表决定外生随机变量的概率分布的机制。比如房地产开发中市场需求的大小。管理科学与工程学院管理科学与工程学院2024/5/22 周三27（2）策略集局中人选择对付其它局中人的行动方案称为策略；某局中人的所有可能策略全体称为策略集；局中人各自使用一个对策就形成了一个局势，一个局势决定了各局中人的对策结果，称为该局势对策的益损值。（3）一局势对策的益损值管理科学与工程学院管理科学与工程学院2024/5/22 周三28（4）行动 ACTIONS OR MOVES参与人在博弈的某个时点的决策变量。（坦白）N个参与人的行动的有序集称为行动组合（坦白，抵赖）。行动的顺序对于博弈的结果非常重要。有关静态和动态博弈的区分就是基于行动的顺序做出的。同样的行动集合，行动的顺序不同，每个参与人的最有决策就不同，博弈的结果也不同。尤其在不完全信息博弈中，后行动者依赖观察先行动者的行动来获取信息。管理科学与工程学院管理科学与工程学院2024/5/22 周三29（5）信息 information参与人有关博弈的知识，特别是有关自然的选择，其他参与人的特征和行动的知识。完美信息perfect information:指一个参与人对其他参与人的行动选择有准确的理解。（6）均衡equilibrium指所有参与人的最优战略的组合。纳什均衡，指的是这样一种战略组合：这种战略组合由所有参与人的最优战略联合组成。当别人战略给定的情况下，没有任何一个参与人有积极性改选其他战略，从而没有人愿意打破现已形成的这种均衡。如：囚徒困境问题中的（坦白，坦白）管理科学与工程学院管理科学与工程学院2024/5/22 周三30二、历史沿革 上世纪50年代以前：1944年冯.诺依曼（Neumann）和摩根斯坦（Morgensten）合著的博弈论和经济行为一书的出版，标志着博弈理论框架的基本形成。50年代到70年代：纳什（Nash）为非合作博弈的一般理论和合作博弈的谈判理论奠定了基础，提出了博议论中最重要的概念纳什均衡；70年代到90年代：博弈论作为一种方法论开始大量应用于经济学，在纳什等人的努力下博弈论逐步形成了一个完整的理论体系。90年代至今：博弈论和经济学交融发展，博弈论已经成为现代经济学中重要的方法论。回本章目录管理科学与工程学院管理科学与工程学院2024/5/22 周三31三位诺贝尔经济学奖获得者的工作 1994年为表彰纳什（Nash）,泽尔腾（Selten）,和海萨尼（Harsanyi）在博弈论上做出的贡献，三人被授予诺贝尔经济学奖。管理科学与工程学院管理科学与工程学院2024/5/22 周三32三位大师主要的贡献 1950年和1951年纳什的两篇关于非合作博弈论的重要论文，彻底改变了人们对竞争和市场的看法。他证明了非合作博弈及其均衡解，并证明了均衡解的存在性，即著名的纳什均衡。从而揭示了博弈均衡与经济均衡的内在联系。因为在现实世界中，非合作博弈要比合作博弈普遍得多。管理科学与工程学院管理科学与工程学院2024/5/22 周三33Selten and Harsanyi泽尔腾（1965）将纳什均衡的概念引入了动态分析，提出了“精炼纳什均衡”概念；以及进一步刻画不完全信息动态博弈的“完备贝叶斯纳什均衡”而海萨尼则发展了刻画不完全信息静态博弈的“贝叶斯纳什均衡”（19671968）。总之，他俩进一步将纳什均衡动态化，加入了接近实际的不完全信息条件。他们的工作为后人继续发展博弈论，提供了基本思路和模型 管理科学与工程学院管理科学与工程学院2024/5/22 周三34三、分类 在博弈论中可以根据不同方式对博弈问题进行分类，通常分类的方式有（1）根据局中人的个数，分为二人博弈和多人博弈；（2）根据各局中人的赢得函数的代数和是否为零，可分为零和博弈和非零和博弈；（3）根据局中人是否合作，又可分为合作博弈和非博弈对策；（4）根据局中人的策略集中个数，又分为有限博弈和无限博弈（或连续博弈）；（5）也可根据局中人掌握信息的情况及决策选择是否和时间有关可分为完全信息静态博弈、完全信息动态博弈、非完全信息静态博弈及非完全信息动态博弈；回本章目录管理科学与工程学院管理科学与工程学院2024/5/22 周三35博弈的分类及对应的均衡静态静态动态动态完全完全信息信息完全信息静态博弈；完全信息静态博弈；纳什均衡；纳什均衡；Nash(1950)完全信息动态博弈；完全信息动态博弈；子博弈精炼纳什均衡；泽子博弈精炼纳什均衡；泽尔腾（尔腾（1965）不完全不完全信息信息不完全信息静态博弈；贝叶不完全信息静态博弈；贝叶斯纳什均衡；斯纳什均衡；海萨尼（海萨尼（1967-1968）不完全信息动态博弈，不完全信息动态博弈，精炼贝叶斯纳什均衡；精炼贝叶斯纳什均衡；泽尔腾泽尔腾（1975）Kreps,Wilson(1982),Fudenberg,Tirole(1991)管理科学与工程学院管理科学与工程学院2024/5/22 周三36 2、完全信息动态博弈 在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复杂一些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略而采取行动，而先行者也会知道后行者会根据他的行动采取何种行动，因此先行者会考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信息动态对策问题。1、完全信息静态博弈囚徒困境问题（前述）管理科学与工程学院管理科学与工程学院2024/5/22 周三37 例 某行业中只有一个垄断企业A，有一个潜在进入者企业B。B可以选择进入或不进入该行业这两种行动，而A当B进入时，可以选择默认或者报复两种行动。如果B进入后A企业报复，将造成两败俱伤的结果，但如果A默认B进入，必然对A的收益造成损失。同样的，如果B进入而A报复，则B受损，反之，将受益。把此关系用图表示。默许默许报复报复50,10050,100-20,0-20,00,2000,2000,2000,200进入进入不进入不进入图图1-2 A1-2 A、B B的行动及结果的行动及结果A AB B管理科学与工程学院管理科学与工程学院2024/5/22 周三38 由分析可知，上例中（B选择不进入，A选择报复）和（B选择进入，A选择默许）都是纳什均衡解。但在实际中，（B选择不进入，A选择报复）这种情况是不可能出现的。因为B知道他如果进入，A只能默许，所以只有（B选择进入，A选择默许）会发生。或者说，A选择报复行动是不可置信的威胁。对策论的术语中，称（A选择默许，B选择进入）为精炼纳什均衡。当只当参与人的战略在每一个子对策中都构成纳什均衡，这个纳什均衡才称为精炼纳什均衡。当然，如果A下定决心一定要报复B，即使自己暂时损失。这时威胁就变成了可置信的，B就会选择不进入，（B选择不进入，A选择报复）就成为精炼纳什均衡。军事交战时，“破釜沉舟”讲的就是一种可置信威胁。实际企业经营中也有很多类似的例子。管理科学与工程学院管理科学与工程学院2024/5/22 周三393、不完全信息静态博弈市场进入博弈。前述的“市场进入博弈”，考虑如下变化：进入者并不知道在位者的成本函数，认为在位者可能是高成本也可能是低成本，当然在位者自己知道。遇到不同成本函数的在位者支付矩阵不同：高成本在位者高成本在位者低成本在位者低成本在位者允许允许斗争斗争允许允许斗争斗争进进入入者者进入进入40，50-10，030，80-10，100不进入不进入0，3000，3000，4000，400管理科学与工程学院管理科学与工程学院2024/5/22 周三404、不完全信息动态博弈市场进入博弈 市场进入问题考虑如下情况：假定分两个时期，第一时期，在位者垄断市场，进入者决定进入或不进入，若进入，在第二时期双方竞争；否则第二阶段在位者仍然垄断市场。在位者可能是高成本，也可能是低成本。进入者只知道在位者是高成本的概率为p，低成本的概率为1-p。进入者只有一种类型，如果进入，生产成本与高成本在位者相同。在位者根据自己成本操纵垄断价格限制进入者进入，进入者根据观察到的价格判断在位者的成本，修正p为p1，作为自己下一步决策的依据。管理科学与工程学院管理科学与工程学院2024/5/22 周三41 5、多人非合作博弈 有三个或三个以上博弈方参加的博弈就是“多人博弈”。多人博弈同样也是博弈方在意识到其他博弈方的存在，意识到其他博弈方对自己决策的反应和反作用存在的情况下寻求自身最大利益的决策活动。因而，它们的基本性质和特征与两人博弈是相似的，我们常常可以用研究两人博弈同样的思路和方法来研究它们，或将两人博弈的结论推广到多人博弈。不过，毕竟多人博弈中出现了更多的追求各自利益的独立决策者，因此，策略的相互依存关系也就更为复杂，对任一博弈方的决策引起的反应也就要比两人博弈复杂得多。并且，在多人博弈中还有一个与两人博弈有本质区别的特点，即可能存在“破坏者”。所谓破坏者即一个博弈中具有下列特征的博弈方：其策略选择对自身的得益没有任何影响，但却会影响其它博弈方的得益，有时这种影响甚至有决定性的作用。例如有三个城市争夺某届奥运会的主办权。管理科学与工程学院管理科学与工程学院2024/5/22 周三42 多人博弈可以分为合作的和非合作的。非合作博弈顾名思义，就是局中人之间不存在合作，即各局中人在采取行动之前，没有事前的交流和约定，在其行为发生相互作用时，也不会达成任何有约束力的协议。每个局中人都选择于已最有利的策略以使效用水平最大化。然而，在非合作博弈中，双方的利益也并非是完全冲突的，即对一个局中人有利的局势并不一定对其他局中人一定不利，故多人非合作博弈不一定是零和博弈。如同矩阵对策中纯策略意义下的解有时不存在一样，有些非合作博弈也不存在纯策略纳什均衡。在这种情况下，局中人就必须考虑混合策略。管理科学与工程学院管理科学与工程学院2024/5/22 周三43 6、非零和博弈 所谓零和博弈，就是一方的收益必定是另一方的损失。这种博弈的特点是不管各博弈方如何决策，最后各博弈方得益之和总是为零。有某些博弈中，每种结果之下各博弈方的得益之和不等于0，但总是等于一个非零常数，就称之为“常和博弈”。当然，可以将零和博弈本身看作是常和博弈的特例。“零和博弈”和“常和博弈”之外的所有博弈都可被称为“非零和博弈”。非零和博弈即意味着在不同策略组合（结果）下各博弈方的得益之和一般是不相同的。如前述囚徒困境就是典型的非零和博弈。应该说，非零和博弈是最一般的博弈类型，而常和博弈和零和博弈都是它的特例。在非零和博弈中，存在着总得益较大的策略组合和总得益较小的策略组合之间的区别，这也就意味着在博弈方之间存在着互相配合，争取较大的总得益和个人得益的可能性。两人零和博弈是完全对抗性的，总得益为0，其解法可能性根据矩阵对策予以求解，但在非零和博弈下，矩阵对策求解法已经不适用了，下面用例子予以说明。管理科学与工程学院管理科学与工程学院2024/5/22 周三44 例3 甲乙两公司生产同一产品，均想以登广告扩大产品销售，每家公司都有“登”与“不登”两种策略，双方的得益矩阵如下。登登不登不登3,23,29,-39,-3-2,8-2,86,56,5登登不登不登图图1-3 1-3 甲乙两家公司行动及结果甲乙两家公司行动及结果乙乙甲甲 我们根据得益矩阵来分析。从甲公司立场上看，登有利，不管乙公司如何，保证赢利至少是3，最多是9。如果不登，可能要蒙受损失2。从乙公司的立场上看，同样理由，还是登广告好。但是，这是从理智行为出发的策略，是以彼此不能合作为前提的。上述两公司均采取登广告的策略是稳定的结局。可是，如果彼此能够合作，而都不登广告，免去了广告费，反而各自的赢利要多。在彼此不能合作的情况下，如果甲不登，恰好乙登，甲只好出现败局，这是非理智的策略，带有危险性。因此，非零和博弈常常不易获得最理想的答案。对于三个以上的多人零和博弈，互相利害关系更加复杂。管理科学与工程学院管理科学与工程学院2024/5/22 周三45在众多博弈模型中，占有重要地位的是二人有限零和博弈（又称矩阵对策）：所谓二人有限零和博弈是指有2个局中人，每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。通常将矩阵对策记为:G=S1,S2,A S1：甲的策略集；S2：乙的策略集；A：甲的赢得矩阵。“齐王赛马”是一个矩阵策略。3矩阵对策的最优纯策略回本章目录管理科学与工程学院管理科学与工程学院2024/5/22 周三46在甲方的赢得矩阵中：A=aijmni 行代表甲方策略 i=1,2,m；j 行代表乙方策略 j=1,2,n；aij 代表甲方取策略 i，乙方取策略 j，这一局势下甲方的益损值。此时乙方的益损值为-aij（零和性质）。在考虑各方采用的策略时，必须注意一个前提，就是双方都是理智的，即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。2 矩阵对策的最优纯策略3矩阵对策的最优纯策略管理科学与工程学院管理科学与工程学院2024/5/22 周三47 例：甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看作一种策略，双方各选一种策略参赛。比赛共赛三局，规定每局胜者得1分，输者得-1分，可知三赛三胜得3分，三赛二胜得1分，三赛一胜得-1分，三赛三负得-3分。甲队的策略集为S1=1，2，3，乙队的策略集为S2=1，2，3。根据以往比赛的资料，有甲队的赢得矩阵为A，如下所示，请问这次比赛各队采用哪种阵容上场最为稳妥?3矩阵对策的最优纯策略管理科学与工程学院管理科学与工程学院2024/5/22 周三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矩阵对策的最优纯策略管理科学与工程学院管理科学与工程学院2024/5/22 周三49 例 某单位采购员在秋天决定冬季取暖用煤的储量问题，已知在正常的冬季气温条件下要消耗15吨煤，在较暖和较冷的天气下要消耗10吨和20吨。假定冬天的煤价随天气寒冷程度而有所变化，在较暖和、正常、较冷的气候条件下每吨煤价分别为10元、15元、20元。又设冬季时煤炭价格为每吨10元。在没有关于当年冬季准确的气象预报的条件下，秋天储煤多少吨能使得单位的支出最少？解：局中人I为采购员，局中人II为大自然，采购员有三个策略，买10吨、15吨、20吨。分别记为 1，2，3。大自然也有三个策略：暖、正常、冷，分别记为 1，2，3。3矩阵对策的最优纯策略管理科学与工程学院管理科学与工程学院2024/5/22 周三50赢得矩阵如下：在此表上计算，有 得故（3，3）为对策G的解，VG=-200。1 1 2 2 3 3 1 1(10(10吨）吨）-100-175-300 2 2(15(15吨）吨）-150-150-250 3 3(20(20吨）吨）-200-200-200 1 1 2 2 3 3minmin 1 1(10(10吨）吨）-100-175-300-300 2 2(15(15吨）吨）-150-150-250-250 3 3(20(20吨）吨）-200-200-200-200*maxmax-100-150-200*3矩阵对策的最优纯策略管理科学与工程学院管理科学与工程学院2024/5/22 周三51 设矩阵对策 G=S1,S2,A。当 max min aij min max aij i j j i时，不存在最优纯策略。例：设一个赢得矩阵如下:min 5 9 5 A=max 6 策略 2 8 6 6 i max 8 9 min 8 策略 1 j4矩阵对策的混合策略回本章目录管理科学与工程学院管理科学与工程学院2024/5/22 周三52 当甲取策略 2，乙取策略 1时，甲实际赢得8比预期的多2，乙当然不满意。考虑到甲可能取策略 2这一点，乙采取策略 2。若甲也分析到乙可能采取策略 2这一点，取策略 1，则赢得更多为9 。此时，对两个局中人甲、乙来说，没有一个双方均可接受的平衡局势，其主要原因是甲和乙没有执行上述原则的共同基础，即 max min aij min max aij。i j j i 一个自然的想法：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）-即混合策略。4矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三53 求解混合策略的问题有图解法、迭代法、线性方程法和线性规划法等，我们这里只介绍线性规划法，其他方法略。例：设甲使用策略 1的概率为X1，使用策略 2的概率为X2，并设在最坏的情况下，甲赢得的平均值为V（未知）。5 9 A=STEP 1 8 6 1)X1+X2=1 X1,X2 0 4矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三542)无论乙取何策略，甲的平均赢得应不少于V:对乙取 1：5X1+8X2 V对乙取 2：9X1+6X2 V注意 V0,因为A各元素为正。STEP 2 作变换：X1=X1/V;X2=X2/V得到上述关系式变为：X1+X2=1/V (V愈大愈好）待定 5X1+8X2 1 9X1+6X2 1 X1,X2 04矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三55建立线性模型：min X1+X2 s.t.5X1+8X2 1 X1=1/21 9X1+6X2 1 X2=2/21 X1,X2 0 1/V=X1+X2=1/7 所以，V=7 返回原问题：X1=X1V=1/3 X2=X2V=2/3于是甲的最优混合策略为：以1/3的概率选 1，以2/3的概率选 2，最优值V=7。4矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三56 同样可求乙的最优混合策略：设乙使用策略 1的概率为Y1 Y1+Y2=1设乙使用策略 2的概率为Y2 Y1,Y2 0 设在最坏的情况下，甲赢得的平均值为V。这也是乙损失的平均值，越小越好。作变换：Y1=Y1/V，Y2=Y2/V 建立线性模型：max Y1+Y2 s.t.5Y1+9Y2 1 Y1=1/14 8Y1+6Y2 1 Y2=1/14 Y1,Y2 0 1/V=Y1+Y2=1/7 所以，V=7 4矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三57返回原问题：Y1=Y1V=1/2 Y2=Y2V=1/2于是乙的最优混合策略为：以 的概率选 1；以 的概率选 2，最优值 V=7。当赢得矩阵中有非正元素时，V 0 的条件不一定成立，可以作下列变换：选一正数 k，令矩阵中每一元素加上 k 得到新的正矩阵A，其对应的矩阵对策G=S1,S2,A 与 G=S1,S2,A 解相同，但VG=VG k。4矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三58例：求解“齐王赛马”问题。已知齐王的赢得矩阵A求得故不存在纯策略问题下的解，可求其混合策略。A中有负元素，可以取k=2,在A的每个元素上加2得到A如下：4矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三59 建立对G=S1，S2，A中求甲方最佳策略的线性规划如下：Min x1+x2+x3+x4+x5+x6 约束条件：5x1+3x2+3x3+x4+3x5+3x6 1 3x1+5x2+x3+3x4+3x5+3x6 1 3x1+3x2+5x3+3x4+3x5+x6 1 3x1+3x2+3x3+5x4+x5+3x6 1 x1+3x2+3x3+3x4+5x5+3x6 1 3x1+x2+3x3+3x4+3x5+5x6 1 xi 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，此时VG=V=3。4矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三60 同样可以建立对策G=S1，S2，A中求乙方最佳策略的线性规划如下：Min y1+y2+y3+y4+y5+y6 约束条件：5y1+3y2+3y3+3y4+y5+3y6 1 3y1+5y2+3y3+3y4+3y5+y6 1 3y1+y2+5y3+3y4+3y5+3y6 1 y1+3y2+3y3+5y4+3y5+3y6 1 3y1+3y2+3y3+y4+5y5+3y6 1 3y1+3y2+y3+3y4+3y5+5y6 1 yi0,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矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三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-52-34 1（出1）2（出2）3（出3）3（出3）2（出2）1（出1）甲的赢 得甲的策略4矩阵对策的混合策略乙的策略管理科学与工程学院管理科学与工程学院2024/5/22 周三62即甲的赢得矩阵为A：可知无纯策略意义的解，下面求其在混合策略下的解。A的各元素都加上6，得到建立线性规划模型如下：Min x1+x2+x3 Max y1+y2+y3 S.T.8x1+3x2+10 x3 1 8y1+3y2+10y31 3x1+10 x2+x3 1 3y1+10y2+y3 1 10 x1+x2+12x3 1 10y1+y2+12y31 x1,x2,x3 0 y1,y2,y3 0 4矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三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矩阵对策的混合策略管理科学与工程学院管理科学与工程学院2024/5/22 周三64例4 甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有:(1)降低产品价格；(2)提高产品质量；(3)推出新产品。乙企业考虑采取的策略措施有(1)增加广告费用；(2)增设维修网点，加强售后服务；(3)改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，由于各自采取的措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，试求出这两个企业各自的最优策略。3-58-6510108-12 1（措施1）2（措施2）3（措施3）3（措施3）2（措施2）1（措施1）4矩阵对策的混合策略甲的赢 得甲的策略乙的策略管理科学与工程学院管理科学与工程学院2024/5/22 周三65解：易知此对策无纯策略意义下的解。把A的每一个元素加上12，得到A建立线性规划模型如下：Min x1+x2+x3 Max y1+y2+y3 S.T.22x1+20 x21 22y1+6y2+15y3 1 6x1+17x2+22x3 1 20y1+17y2+7y3 1 15x1+7x2+20 x3 1 22y2+20y3 1 x1,x2,x30 y1,y2,y30得到：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.