《运筹学课程对策论.ppt》由会员分享，可在线阅读，更多相关《运筹学课程对策论.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 V
3、ickreyWilliam Vickrey）纳什的基本贡献是证明了非合作博弈均衡解及纳什的基本贡献是证明了非合作博弈均衡解及其存在性，建立了作为博弈论基础的其存在性，建立了作为博弈论基础的“纳什均纳什均衡衡”概念；海萨尼则把不完全信息纳入到博弈概念；海萨尼则把不完全信息纳入到博弈论方法体系中；泽尔腾的贡献在于将博弈论由论方法体系中；泽尔腾的贡献在于将博弈论由静态向动态的扩展，建立了静态向动态的扩展，建立了“子博弈精练纳什子博弈精练纳什均衡均衡”的概念。的概念。这两位经济学家的贡献集中于运用博弈论这两位经济学家的贡献集中于运用博弈论对现实经济问题的解释。对现实经济问题的解释。博弈论导论博弈论和诺
4、贝尔经济学奖现在学习的是第4页，共56页这三位作为不对称信息市场理论的奠基人这三位作为不对称信息市场理论的奠基人被授予诺贝尔经济学奖，以表彰他们分别被授予诺贝尔经济学奖，以表彰他们分别在柠檬品市场等不对称信息理论研究领域在柠檬品市场等不对称信息理论研究领域做出的基础性贡献。这些贡献发展了博弈做出的基础性贡献。这些贡献发展了博弈论的方法体系，拓宽了其经济解释范围。论的方法体系，拓宽了其经济解释范围。贡献主要在于通过实验室实验来测试根据经济学贡献主要在于通过实验室实验来测试根据经济学理论而做出预测的未知或不确定性。是对以博弈理论而做出预测的未知或不确定性。是对以博弈论为基础构建的理论模型进行实证证
5、伪工作的一论为基础构建的理论模型进行实证证伪工作的一大创举。大创举。他们通过博弈理论分析增加了世人对合作与他们通过博弈理论分析增加了世人对合作与冲突的理解。其理论模型应用在解释社会中冲突的理解。其理论模型应用在解释社会中不同性质的冲突、贸易纠纷、价格之争以及不同性质的冲突、贸易纠纷、价格之争以及寻求长期合作的模式等经济学和其他社会科寻求长期合作的模式等经济学和其他社会科学领域。学领域。博弈论导论博弈论和诺贝尔经济学奖n20012001：阿克洛夫（：阿克洛夫（AkerlofAkerlof）、斯宾塞（）、斯宾塞（SpenceSpence）、斯蒂格利茨（）、斯蒂格利茨（StiglitzStiglit
6、z）o20022002：弗农史密斯（：弗农史密斯（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 在位者在位者 默许默许 斗争斗争进入进入不进入不进入 进入者进入者纳什均衡：纳什均衡：（进（进 入，默许）入，默许）（不进入，斗争）（不进入，斗争）著名博弈问题著名博弈问题现在学习的是第1
10、0页，共56页智 猪 博 弈按钮食槽著名博弈问题著名博弈问题现在学习的是第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 functi
16、onpayoff 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
22、11 11 11 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-
24、(10100+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)=-2500200)=-2500 3 3(20 20 吨吨)-(20-(20100)=-100)=-20002000-(20-(20100)=-2000100)=-2000-(20-(20100)=-2000100)=-2000甲甲乙乙a aijij则赢得矩阵为：则赢得
25、矩阵为：现在学习的是第24页，共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(
28、x*,y*)f(x*,y)则称则称(x*,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页
29、，共56页定义定义4 4（混合局势、混合策略意义下的解、对策值）（混合局势、混合策略意义下的解、对策值）现在学习的是第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 策略的优势策略。策略的优势策略。对局中人乙，希望对策的局势值越小越好。若对局中人乙，
31、希望对策的局势值越小越好。若 第第j j 列所有元素列所有元素第第k列所有元素，即列所有元素，即 ，i=1,2,i=1,2,m,m，则乙则乙理智，必采用理智，必采用j j 纯策略而舍去纯策略而舍去 k 纯策略，不影纯策略，不影响最优策略和策略鞍点值响最优策略和策略鞍点值。此时称。此时称 j j 策略为对策略为对 k 策策略的优势策略。略的优势策略。若存在优势策略，则支付矩阵阶数可降低若存在优势策略，则支付矩阵阶数可降低优势原则优势原则：（某一策略对其他策略具有支配作用）（某一策略对其他策略具有支配作用）现在学习的是第39页，共56页由由G G得到一个新的矩阵策略得到一个新的矩阵策略G G现在学
32、习的是第40页，共56页原赢得矩阵原赢得矩阵按优势原则简化后赢得矩阵按优势原则简化后赢得矩阵现在学习的是第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列列倍数之和不能超倍数之和不能超过过
33、1（概率组合）（概率组合）第第1 1行优超行优超于第于第3 3行行划去第划去第2行行现在学习的是第46页，共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,x
34、n n*););解得乙的最优混合策解得乙的最优混合策 略为略为 Y Y*=(y=(y1 1*,y,yn n*)对策值对策值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页 甲小孩的期望值方程为甲小孩的期望值方程为：乙小孩的期望值方程为乙小孩的期望值方程为：解得甲的最优混合策略为解得甲
35、的最优混合策略为 X X*=(1/3,1/3,1/3),=(1/3,1/3,1/3),V V*=0=0 解得乙的最优混合策略为解得乙的最优混合策略为 Y Y*=(1/3,1/3,1/3),=(1/3,1/3,1/3),V V*=0;=0;甲甲、乙乙两两小小孩孩均均以以1/31/3的的同同等等概概率率取取石石头头、剪剪刀刀、布布纯纯策策略略，在在不不考考虑虑其其它它因因素素的的前前提提下下，多多局局竞竞争争的的结结果果是是最最终终和和局局，谁谁也不占优势，反映双方纯策略实力相等。也不占优势，反映双方纯策略实力相等。现在学习的是第50页，共56页例：例：求齐王与田忌赛马对策的最优混合策略求齐王与田
36、忌赛马对策的最优混合策略 无鞍点无鞍点且不能缩减且不能缩减 设齐王的混合策略为设齐王的混合策略为(x(x1 1,x,x2 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田忌的最优混合策略为田忌的最
37、优混合策略为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),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页求出最优混合策略和对策值，并且有求出
38、最优混合策略和对策值，并且有：现在学习的是第54页，共56页 例：例：求下列对策的最优混合策略求下列对策的最优混合策略 解下列方程组解下列方程组：解下列方程组解下列方程组：无鞍点且不能缩无鞍点且不能缩 设设甲甲的的混混合合策策略略为为(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页