运筹学课程对策论课件.ppt

《运筹学课程对策论课件.ppt》由会员分享，可在线阅读，更多相关《运筹学课程对策论课件.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学课程对策论第1页，此课件共56页哦二、引言二、引言三、矩阵对策三、矩阵对策u对策现象对策现象u对策论对策论u对策问题的三个基本要素对策问题的三个基本要素u对策问题的分类对策问题的分类u具有鞍点的矩阵对策具有鞍点的矩阵对策u无鞍点的矩阵对策无鞍点的矩阵对策u最优混合策略的解法最优混合策略的解法本章主要内容本章主要内容一、对策论导论一、对策论导论第2页，此课件共56页哦 博弈论导论博弈论的演化历程 n 最早的对策论思想产生于中国春秋时期，孙武的最早的对策论思想产生于中国春秋时期，孙武的孙孙子兵法子兵法 n现代经济博弈论起源可以追溯到现代经济博弈论起源可以追溯到19441944年，由美国著名年

2、，由美国著名数学家冯数学家冯诺依曼（诺依曼（John NeumannJohn Neumann）与经济学家奥）与经济学家奥摩根斯坦（摩根斯坦（Oscar MorgenstenOscar Morgensten）合著的）合著的博弈论与博弈论与经济行为经济行为第3页，此课件共56页哦n19941994：纳什（：纳什（NashNash）、海萨尼（）、海萨尼（J.HarsanyiJ.Harsanyi）、泽尔腾（）、泽尔腾（R.SeltenR.Selten）o19961996莫里斯（莫里斯（James A.MirrleesJames A.Mirrlees）和维克瑞（）和维克瑞（William Vickrey

3、William Vickrey）纳什的基本贡献是证明了非合作博弈均衡解及其存纳什的基本贡献是证明了非合作博弈均衡解及其存在性，建立了作为博弈论基础的在性，建立了作为博弈论基础的“纳什均衡纳什均衡”概念；概念；海萨尼则把不完全信息纳入到博弈论方法体系中；海萨尼则把不完全信息纳入到博弈论方法体系中；泽尔腾的贡献在于将博弈论由静态向动态的扩展，泽尔腾的贡献在于将博弈论由静态向动态的扩展，建立了建立了“子博弈精练纳什均衡子博弈精练纳什均衡”的概念。的概念。这两位经济学家的贡献集中于运用博弈论这两位经济学家的贡献集中于运用博弈论对现实经济问题的解释。对现实经济问题的解释。博弈论导论博弈论和诺贝尔经济学奖

4、第4页，此课件共56页哦这三位作为不对称信息市场理论的奠基人这三位作为不对称信息市场理论的奠基人被授予诺贝尔经济学奖，以表彰他们分别被授予诺贝尔经济学奖，以表彰他们分别在柠檬品市场等不对称信息理论研究领域在柠檬品市场等不对称信息理论研究领域做出的基础性贡献。这些贡献发展了博弈做出的基础性贡献。这些贡献发展了博弈论的方法体系，拓宽了其经济解释范围。论的方法体系，拓宽了其经济解释范围。贡献主要在于通过实验室实验来测试根据经贡献主要在于通过实验室实验来测试根据经济学理论而做出预测的未知或不确定性。是对济学理论而做出预测的未知或不确定性。是对以博弈论为基础构建的理论模型进行实证证伪以博弈论为基础构建的

5、理论模型进行实证证伪工作的一大创举。工作的一大创举。他们通过博弈理论分析增加了世人对合作与冲突的他们通过博弈理论分析增加了世人对合作与冲突的理解。其理论模型应用在解释社会中不同性质的冲理解。其理论模型应用在解释社会中不同性质的冲突、贸易纠纷、价格之争以及寻求长期合作的模式突、贸易纠纷、价格之争以及寻求长期合作的模式等经济学和其他社会科学领域。等经济学和其他社会科学领域。博弈论导论博弈论和诺贝尔经济学奖n20012001：阿克洛夫（：阿克洛夫（AkerlofAkerlof）、斯宾塞（）、斯宾塞（SpenceSpence）、斯蒂格利茨（）、斯蒂格利茨（StiglitzStiglitz）o20022

6、002：弗农史密斯（：弗农史密斯（SmithSmith）o20052005：奥曼（：奥曼（AumannAumann）、谢林（）、谢林（SchellingSchelling）第5页，此课件共56页哦约翰约翰纳什纳什1928年生于美国 约翰约翰纳什（纳什（JOHN F.NASH）美）美国人国人(1928-)，由于他与另外两位，由于他与另外两位数学家在非合作博弈的均衡分析理数学家在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响，而弈论和经济学产生了重大影响，而获得获得1994年诺贝尔经济奖。年诺贝尔经济奖。纳什均衡纳什均衡(完全信息静态博

7、弈完全信息静态博弈)卡内基卡内基梅隆大学科学硕士、普林斯顿大学数学博梅隆大学科学硕士、普林斯顿大学数学博士。士。主要研究领域：主要研究领域：博弈论博弈论和微分几何学和微分几何学。主要。主要贡献：非合作博弈均衡、经济博弈论贡献：非合作博弈均衡、经济博弈论 第6页，此课件共56页哦约翰约翰福布斯福布斯纳什纳什第7页，此课件共56页哦 美丽心灵美丽心灵是一部关于一个真实天才的极富人性的是一部关于一个真实天才的极富人性的剧情片。故事的原型是数学家小约翰剧情片。故事的原型是数学家小约翰-福布斯福布斯-纳什纳什(Nash),(Nash),普林斯顿大学的著名教授，诺贝尔经济学奖的获普林斯顿大学的著名教授，诺

8、贝尔经济学奖的获得者得者(1994(1994年年)，他在博弈理论方面的巨大发现甚至改，他在博弈理论方面的巨大发现甚至改变了我们的日常生活。但另一方面，纳什也是一个悲变了我们的日常生活。但另一方面，纳什也是一个悲剧人物，他的一生为精神分裂症所困。在历经苦痛的剧人物，他的一生为精神分裂症所困。在历经苦痛的人生里，纳什一方面在运用自己那优美绝伦的大脑，人生里，纳什一方面在运用自己那优美绝伦的大脑，另一方面也在与他的大脑进行着顽强的抗争。最终理另一方面也在与他的大脑进行着顽强的抗争。最终理性为他带来了心灵的和平，纳什终于摘取了科学事业性为他带来了心灵的和平，纳什终于摘取了科学事业上的桂冠。上的桂冠。第

9、8页，此课件共56页哦 囚徒困境问题囚徒困境问题纳什均衡：纳什均衡：（坦白，坦白）（坦白，坦白）-1，-1-10，0 0，-10 -8，-8囚徒囚徒B坦白坦白抵赖抵赖坦白坦白抵赖抵赖囚徒囚徒A坦白从宽，抗拒从严坦白从宽，抗拒从严著名博弈问题著名博弈问题著名博弈问题著名博弈问题第9页，此课件共56页哦 市场进入阻挠市场进入阻挠 0，300 0，300 -10，0 40，50 在位者在位者 默许默许 斗争斗争进入进入不进入不进入 进入者进入者纳什均衡：纳什均衡：（进（进 入，默许）入，默许）（不进入，斗争）（不进入，斗争）著名博弈问题著名博弈问题著名博弈问题著名博弈问题第10页，此课件共56页哦智

10、 猪 博 弈按钮食槽著名博弈问题著名博弈问题著名博弈问题著名博弈问题第11页，此课件共56页哦 假设猪圈里有一头大猪、一头小猪。猪圈假设猪圈里有一头大猪、一头小猪。猪圈的一头有猪食槽，另一头安装着控制猪食供应的一头有猪食槽，另一头安装着控制猪食供应的按钮，按一下按钮会有的按钮，按一下按钮会有1010个单位的猪食进槽，个单位的猪食进槽，但是谁按按钮就会首先付出但是谁按按钮就会首先付出2 2个单位的成本，个单位的成本，若大猪先到槽边，大小猪吃到食物的收益比是若大猪先到槽边，大小猪吃到食物的收益比是9191；同时到槽边，收益比是；同时到槽边，收益比是7373；小猪先到；小猪先到槽边，收益比是槽边，收

11、益比是6464。那么，在两头猪都有智。那么，在两头猪都有智慧的前提下，慧的前提下，最终结果是小猪选择？最终结果是小猪选择？。第12页，此课件共56页哦小猪小猪行行动等待等待大猪大猪行行动5 14 4等待等待9 -10 0小猪的选择将是等待小猪的选择将是等待第13页，此课件共56页哦 齐王赛马齐王赛马著名博弈问题著名博弈问题著名博弈问题著名博弈问题齐王与田忌赛马齐王与田忌赛马.双方约定双方约定:从各自的上中下三个等级从各自的上中下三个等级 的马中各选一匹参赛的马中各选一匹参赛;每匹马只能参赛一次每匹马只能参赛一次;每次比赛双方各出一匹马每次比赛双方各出一匹马,负者负者要付给胜者千金要付给胜者千金

12、.不同等级的马不同等级的马不同等级的马不同等级的马,高等级优于低等级高等级优于低等级高等级优于低等级高等级优于低等级;同等级的马中同等级的马中同等级的马中同等级的马中,齐王的马优于田忌的马齐王的马优于田忌的马齐王的马优于田忌的马齐王的马优于田忌的马;如何对策如何对策如何对策如何对策?第14页，此课件共56页哦引言引言 对策现象对策现象 各种比赛：体育、棋类等比赛各种比赛：体育、棋类等比赛 政治方面：外交谈判政治方面：外交谈判 经济方面：贸易谈判、争夺市场、各种经营竞争等经济方面：贸易谈判、争夺市场、各种经营竞争等 具有竞争或对抗性质的现象具有竞争或对抗性质的现象第15页，此课件共56页哦对策论

13、对策论 对策论是关于相互影响的决策者的研究。是研究具有对策论是关于相互影响的决策者的研究。是研究具有竞争或者对抗性质现象的理论与方法。竞争或者对抗性质现象的理论与方法。研究对策现象的一种研究对策现象的一种定量分析理论与方法。也称为博弈论定量分析理论与方法。也称为博弈论 参加竞争或对抗的各方具有不同的利益和目标，为了达到各参加竞争或对抗的各方具有不同的利益和目标，为了达到各自的利益和目标，各方必须考虑对手的各种可能的行动方案，并自的利益和目标，各方必须考虑对手的各种可能的行动方案，并力图选择对自己最有利或最合理的方案。力图选择对自己最有利或最合理的方案。第16页，此课件共56页哦对策问题的三个基

14、本要素对策问题的三个基本要素 1 1局中人（局中人（playersplayers）一一个个对对策策中中有有权权决决定定自自己己行行动动方方案案的的对对策策参参加加者者称称为为局局中中人人。通通常常用用I I表表示示局局中中人人的的集集合合，如如果果有有n n个个局局中中人人，则则I I1,2,1,2,n,n。对策论中对局中人的一个重要的假设：每个局中人都是对策论中对局中人的一个重要的假设：每个局中人都是“理性理性的的”、等智力的。、等智力的。2 2策略（策略（strategiesstrategies）对策中，可供局中人选择的一个实际可行的完整的行动对策中，可供局中人选择的一个实际可行的完整的行

15、动方案称为一个策略。一般每个局中人的策略集方案称为一个策略。一般每个局中人的策略集S S中至少应包括中至少应包括两个策略。两个策略。第17页，此课件共56页哦 如如“齐王与田忌赛马齐王与田忌赛马”中：中：齐王有齐王有6 6个策略：个策略：(上中下上中下)，(上下中上下中),(),(中上下中上下),(),(中下上中下上),(),(下上中下上中),(),(下中上下中上)田忌有田忌有6 6个策略：个策略：(上中下上中下)，(上下中上下中),(),(中上下中上下),(),(中下上中下上),(),(下上中下上中),(),(下中上下中上)3.3.赢得函数赢得函数(支付函数支付函数)（payoff func

16、tionpayoff function）局势：局势：每个局中人从各自的策略集合中选取一个策略参加对策，每个局中人从各自的策略集合中选取一个策略参加对策，形成的一个处于竞争的策略组。形成的一个处于竞争的策略组。如：齐王选策略如：齐王选策略(上中下上中下)，田忌选策略田忌选策略(中上下中上下)，构成一个局，构成一个局势势(上中下上中下)，(中上下中上下)。局势的得失总和为。局势的得失总和为0 0。一局对策的得失，即局中人的得失。叫一局对策的得失，即局中人的得失。叫赢得（支付）函赢得（支付）函数数，对有限策略集，叫，对有限策略集，叫赢得（支付）赢得（支付）矩阵矩阵。第18页，此课件共56页哦设设s

17、si i是是第第i i个个局局中中人人的的一一个个策策略略，则则n n个个局局中中人人的的策策略略形形成成的的策策略略组组合合s s(s(s1 1，s s2 2,s,sn n)就是一个局势。若记就是一个局势。若记S S为全部局势的集合，则为全部局势的集合，则 S SS S1 1SS2 2SSn n 当当一一个个局局势势s s出出现现后后，应应该该为为每每一一局局中中人人i i规规定定一一个个赢赢得得值值(或或所所失失值值)H)Hi i(s)(s)。显显然然，H Hi i(s)(s)是是定定义义在在S S上上的的函函数数，称称为为局局中中人人i i的的赢赢得得函函数数。在在“齐王赛马齐王赛马”中

18、，局中人集合中，局中人集合I I1,21,2，齐王和田忌的策略集可分别用，齐王和田忌的策略集可分别用 表表示示。这这样样,齐齐王王的的任任一一策策略略i i和和田田忌忌的的任任一一策策略略j j就就构构成成了了个个局局势势s sijij，如如果果1 1=(=(上上,中中,下下)，l l(上上,中中,下下)则则在在局局势势s s1111下下，齐齐王王的的赢得为赢得为H H1 1(s(s1111)3 3，田忌的赢得为，田忌的赢得为H H2 2(s(s1111)=-3)=-3 当当局局中中人人、策策略略集集和和赢赢得得函函数数这这3 3个个要要素素确确定定后后，一一个个对对策策模模型型也也就就给定了

19、。给定了。第19页，此课件共56页哦 例例：两两个个赌赌博博参参加加者者甲甲、乙乙各各出出示示一一枚枚硬硬币币，在在不不让让对对方方看看见见的的情情况况下下，将将硬硬币币放放在在桌桌子子上上，若若两两个个硬硬币币都都呈呈正正面面或或都都呈呈反反面面则则甲甲得得1 1元元，乙乙付付出出1 1元元；若若两两个个硬硬币币一一个个呈呈正正面面另另一一个个呈呈反反面面则则乙乙得得1 1元元，甲甲付付出出1 1元。元。局中人：局中人：甲、乙甲、乙策略：策略：s si i=正面，反面正面，反面 i=1,2 i=1,2局势：局势：S=(S=(正正,反反)，(正正,正正)，(反反,正正)，(反反,反反)支支付付

20、函函数数：H H1 1(正正,反反)=)=-1-1，H H1 1(正正,正正)=1)=1，H H1 1(反反,正正)=)=-1-1，H H1 1(反反,反反)=1)=1，H H2 2(正正,反反)=)=1 1，H H2 2(正正,正正)=)=-1-1，H H2 2(反反,正正)=1)=1，H H2 2(反反,反反)=-1)=-1第20页，此课件共56页哦对策问题的分类对策问题的分类对对策策动动态态对对 策策静静态态对对 策策结结盟盟对对 策策不不结结盟盟对对 策策微分对策微分对策联合对策联合对策合作对策合作对策有有限限无无限限二人二人多人多人二人二人多人多人零和零和非零和非零和零和零和非零和非

21、零和零和零和非零和非零和零和零和非零和非零和第21页，此课件共56页哦矩阵对策矩阵对策 二人有限零和对策（对抗对策）：二人有限零和对策（对抗对策）：局中人局中人2 2个个 每个局中人的策略集中的策略数目有限每个局中人的策略集中的策略数目有限 每一局势的对策均有确定的损益值，并且对同一局势每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。的两个局中人的益损值之和为零。第22页，此课件共56页哦 1 1(上中下上中下)2 2(上下中上下中)3 3(中上下中上下)4 4(中下上中下上)5 5(下上中下上中)6 6(下中上下中上)1 1(上中下上中下)3 31 11 11 1

22、1 1-1-1 2 2(上下中上下中)1 13 31 11 1-1-11 1 3 3(中上下中上下)1 1-1-13 31 11 11 1 4 4(中下上中下上)-1-11 11 13 31 11 1 5 5(下上中下上中)1 11 1-1-11 13 31 1 6 6(下中上下中上)1 11 11 1-1-11 13 3齐王齐王田忌田忌a aijij第23页，此课件共56页哦 例例：某某单单位位秋秋季季决决定定冬冬季季取取暖暖用用煤煤的的贮贮量量。冬冬季季用用煤煤贮贮量量在在较较暖暖、正正常常和和较较冷冷情情况况下下分分为为1010、1515和和2020吨吨。设设冬冬季季煤煤价价也也随随寒寒

23、冷冷程程度度而而变变，在在上上述述三三种种情情况况下下分分别别为为100100、150150和和200200元元/吨，已知秋季煤价为吨，已知秋季煤价为100100元元/吨，冬季气象未能予知，问秋季合理贮煤量为多少？吨，冬季气象未能予知，问秋季合理贮煤量为多少？设设局局中中人人甲甲为为：贮贮煤煤量量决决策策者者；局局中中人人乙乙为为：未未来来冬冬季季气气候候。费费用用总总和和=秋秋季季贮贮煤煤量量费费用用+冬冬季季补补购煤量费用购煤量费用 1 1(较暖较暖)2 2(正常正常)3 3(较冷较冷)1 1(10(10 吨吨)-(10-(10100)=-100)=-10001000-(10-(10100

24、+5100+5150)=-150)=-17501750-(10-(10100+10100+10200)=-200)=-30003000 2 2(15 15 吨吨)-(15-(15100)=-100)=-15001500-(15-(15100)=-1500100)=-1500-(15-(15100+5100+5200)=-200)=-25002500 3 3(20 20 吨吨)-(20-(20100)=-100)=-20002000-(20-(20100)=-2000100)=-2000-(20-(20100)=-2000100)=-2000甲甲乙乙a aijij则赢得矩阵为：则赢得矩阵为：第2

25、4页，此课件共56页哦第25页，此课件共56页哦矩阵对策问题解的假设：矩阵对策问题解的假设：例：设有一矩阵博弈例：设有一矩阵博弈G=SG=S1 1，S S2 2；HH，其中，其中H=具有鞍点的矩阵对策具有鞍点的矩阵对策第26页，此课件共56页哦 如果双方部不想冒险、都不存在侥幸心理，而是考虑到对方如果双方部不想冒险、都不存在侥幸心理，而是考虑到对方必然会设法使自己所得最少这一点，就应该必然会设法使自己所得最少这一点，就应该从各自可能出现的从各自可能出现的最不利的情形中选择一个最有利的情形作为决策的依据最不利的情形中选择一个最有利的情形作为决策的依据，这就是，这就是所谓所谓“理智行为理智行为”，

26、也是对策双方实际上可以接受并采取的一，也是对策双方实际上可以接受并采取的一种种稳妥的方法。稳妥的方法。从各自可能出现的最不利的情形中选择一个最有利的情形作为从各自可能出现的最不利的情形中选择一个最有利的情形作为决策的依据决策的依据局中人局中人1局中人局中人2H=H=第27页，此课件共56页哦 定义定义1 1：设设G=SG=S1 1，S S2 2；HH为一矩阵博弈，其中为一矩阵博弈，其中S S1 1=1 1,2 2,m m，S S2 2=1 1,2 2,n n，H=(aH=(aijij)mnmn，若等式，若等式成立。记成立。记 ，称，称vG为博弈博弈G的的值，使上式成立的，使上式成立的纯局局势

27、为纯策略下的解，策略下的解，分分别称称为局中人局中人1，2的最的最优纯策略。策略。定理定理1 矩阵博弈矩阵博弈G=S1，S2；H在纯策略意义下有解的充要条件是：在纯策略意义下有解的充要条件是：存在纯局势存在纯局势 ，使得对任意，使得对任意i和和j，有，有 第28页，此课件共56页哦充分性：充分性：第29页，此课件共56页哦必要性：必要性：第30页，此课件共56页哦定义定义2（鞍点）（鞍点）设设f(x,y)为一个定义在为一个定义在xA 及及yB上的实值函数，若上的实值函数，若存在存在x*A，y*B，使得对一切，使得对一切xA 和和yB有有f(x,y*)f(x*,y*)f(x*,y)则称则称(x*

28、,y*)为函数为函数f的一个的一个鞍点。鞍点。鞍点鞍点 行元素行元素变化趋势变化趋势列元素列元素变化趋势变化趋势具有鞍点对策求解：具有鞍点对策求解：第31页，此课件共56页哦 无鞍点的矩阵对策无鞍点的矩阵对策 两小孩玩游戏：两小孩玩游戏：1 1(石头石头)2 2(剪刀剪刀)3 3(布布)1 1(石头石头)0 01 1-1-1 2 2(剪刀剪刀)-1-10 01 1 3 3(布布)1 1-1-10 0甲甲乙乙a aijij赢得矩阵为：赢得矩阵为：（无鞍点）（无鞍点）第32页，此课件共56页哦定义定义3 3（混合策略）（混合策略）第33页，此课件共56页哦定义定义4 4（混合局势、混合策略意义下的

29、解、对策值）（混合局势、混合策略意义下的解、对策值）第34页，此课件共56页哦例题：例题：第35页，此课件共56页哦 定理定理4 4（存在性定理）：（存在性定理）：任意一个给定的矩阵对策一定有解，局中人任意一个给定的矩阵对策一定有解，局中人双方总有一个最优混合策略，即：双方总有一个最优混合策略，即：第36页，此课件共56页哦 定理定理5 5：若矩阵对策值为若矩阵对策值为V V，则下面两组不等式的解是局中人甲、，则下面两组不等式的解是局中人甲、乙的最优混合策略：乙的最优混合策略：第37页，此课件共56页哦 矩阵对策在矩阵对策在混合策略意义下混合策略意义下的解总是存在的，的解总是存在的，求解的基本

30、方法求解的基本方法为为线性规划线性规划法。法。第38页，此课件共56页哦 对局中人甲，希望对策的局势值越大越好。若对局中人甲，希望对策的局势值越大越好。若 第第i i行所有元素行所有元素第第l 行所有元素，即行所有元素，即 j=1,2,j=1,2,n,n，则则甲理智，必采用甲理智，必采用 i i 纯策略而舍去纯策略而舍去 l 纯策略，不影响最优策略和策略鞍点值纯策略，不影响最优策略和策略鞍点值。此时称。此时称 i i 策略为对策略为对 l 策略的优势策略。策略的优势策略。对局中人乙，希望对策的局势值越小越好。若对局中人乙，希望对策的局势值越小越好。若 第第j j 列所有元素列所有元素第第k列所

31、有元素，即列所有元素，即 ，i=1,2,i=1,2,m,m，则乙则乙理智，必采用理智，必采用j j 纯策略而舍去纯策略而舍去 k 纯策略，不影纯策略，不影响最优策略和策略鞍点值响最优策略和策略鞍点值。此时称。此时称 j j 策略为对策略为对 k 策策略的优势策略。略的优势策略。若存在优势策略，则支付矩阵阶数可降低若存在优势策略，则支付矩阵阶数可降低优势原则优势原则：（某一策略对其他策略具有支配作用）（某一策略对其他策略具有支配作用）第39页，此课件共56页哦由由G G得到一个新的矩阵策略得到一个新的矩阵策略G G第40页，此课件共56页哦原赢得矩阵原赢得矩阵按优势原则简化后赢得矩阵按优势原则简

32、化后赢得矩阵第41页，此课件共56页哦第第4 4行优行优于第于第1 1行行划去第划去第1行行第42页，此课件共56页哦第第3 3行优行优于第于第2 2行行划去第划去第2行行第43页，此课件共56页哦第第1 1列列优超于优超于第第3 3列列划划去去第第3列列第44页，此课件共56页哦第第2 2列列优超于优超于第第4 4列列划划去去第第4列列第45页，此课件共56页哦划划去去第第5列列1/31/3 第第1 1列列+2/32/3 第第2 2列列优超于第优超于第5 5列列倍数之和不能超倍数之和不能超过过1（概率组合）（概率组合）第第1 1行优超行优超于第于第3 3行行划去第划去第2行行第46页，此课件

33、共56页哦 解析法：解析法：适用于缩减后的支付矩阵为适用于缩减后的支付矩阵为nnnn方阵的无鞍点对策问方阵的无鞍点对策问题。题。设设 甲的混合策略为甲的混合策略为(x(x1 1,x,x2 2,x,xn n)，乙的混合策略为乙的混合策略为(y(y1 1,y,y2 2,y,yn n)。赢得期望值为：。赢得期望值为：第47页，此课件共56页哦 甲的期望值方程为甲的期望值方程为：乙的期望值方程为乙的期望值方程为：解得甲的最优混解得甲的最优混 合策略为合策略为 X X*=(x=(x1 1*,x,xn n*););解得乙的最优混合策解得乙的最优混合策 略为略为 Y Y*=(y=(y1 1*,y,yn n*

34、)对策值对策值V=VV=V*第48页，此课件共56页哦例：例：求两小孩玩游戏对策的最优混合策略求两小孩玩游戏对策的最优混合策略无鞍点且不能缩减。无鞍点且不能缩减。设甲的混合策略为设甲的混合策略为(x(x1 1,x,x2 2,x,x3 3)，乙的混合策略为乙的混合策略为(y(y1 1,y,y2 2,y,y3 3)。得失期望值为：。得失期望值为：第49页，此课件共56页哦 甲小孩的期望值方程为甲小孩的期望值方程为：乙小孩的期望值方程为乙小孩的期望值方程为：解得甲的最优混合策略为解得甲的最优混合策略为 X X*=(1/3,1/3,1/3),=(1/3,1/3,1/3),V V*=0=0 解得乙的最优

35、混合策略为解得乙的最优混合策略为 Y Y*=(1/3,1/3,1/3),=(1/3,1/3,1/3),V V*=0;=0;甲甲、乙乙两两小小孩孩均均以以1/31/3的的同同等等概概率率取取石石头头、剪剪刀刀、布布纯纯策策略略，在在不不考考虑虑其其它它因因素素的的前前提提下下，多多局局竞竞争争的的结结果果是是最最终终和和局局，谁谁也不占优势，反映双方纯策略实力相等。也不占优势，反映双方纯策略实力相等。第50页，此课件共56页哦例：例：求齐王与田忌赛马对策的最优混合策略求齐王与田忌赛马对策的最优混合策略 无鞍点无鞍点且不能缩减且不能缩减 设齐王的混合策略为设齐王的混合策略为(x(x1 1,x,x2

36、 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6)田忌的混合策略为田忌的混合策略为(y(y1 1,y,y2 2,y,y3 3,y,y4 4,y,y5 5,y,y6 6)第51页，此课件共56页哦 齐王的期望值方程为齐王的期望值方程为：田忌的期望值方程为田忌的期望值方程为齐王的最优混合策略为齐王的最优混合策略为X X*=(1/6,1/6,1/6,1/6,1/6,1/6)(1/6,1/6,1/6,1/6,1/6,1/6)V V*=1=1田忌的最优混合策略为田忌的最优混合策略为Y Y*=(1/6,1/6,1/6,1/6,1/6,1/6),(1/6,1/6,1/6,1/6,1/6,1/6)

37、,V V*=1=1 第52页，此课件共56页哦 拉格朗日乘子法：拉格朗日乘子法：适用于缩减后的支付矩阵为适用于缩减后的支付矩阵为nnnn方阵方阵的无鞍点对策问题。的无鞍点对策问题。设设 甲的混合策略为甲的混合策略为(x(x1 1,x,x2 2,x,xn n)乙的混合策略为乙的混合策略为(y(y1 1,y,y2 2,y,yn n)。得失期望值为：。得失期望值为：s.t.s.t.,即即:s.:s.t.t.,第53页，此课件共56页哦求出最优混合策略和对策值，并且有求出最优混合策略和对策值，并且有：第54页，此课件共56页哦 例：例：求下列对策的最优混合策略求下列对策的最优混合策略 解下列方程组解下

38、列方程组：解下列方程组解下列方程组：无鞍点且不能缩无鞍点且不能缩 设设甲甲的的混混合合策策略略为为(x(x1 1,x,x2 2,x,x3 3)，乙乙的的混混合合策策略略为为(y(y1 1,y,y2 2,y,y3 3)。拉拉氏氏函函数数为：为：第55页，此课件共56页哦 解解得得乙乙的的最最优优混混合合策策略略为为Y Y*=(14/45,11/45,20/45),=(14/45,11/45,20/45),V V*=29/45=29/45 解得甲的最优混合策略为解得甲的最优混合策略为 X X*=(20/45,11/45,14/45),=(20/45,11/45,14/45),V V*=29/45=29/45 注注意意：因因为为没没有有顾顾及及变变量量非非负负的的要要求求，解解析析法法与与拉拉氏氏法法不不是是对对所所有的有解支付矩阵均能得到正确答案。有的有解支付矩阵均能得到正确答案。例：例：求下列对策的最优混合策略。求下列对策的最优混合策略。无鞍点且不能缩减无鞍点且不能缩减 第56页，此课件共56页哦