运筹学教学对策论.pptx
《运筹学教学对策论.pptx》由会员分享,可在线阅读,更多相关《运筹学教学对策论.pptx(67页珍藏版)》请在咨信网上搜索。
1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学 课课 件件对对 策策 论论Game TheoryGame Theory 第一节第一节 对策论的基本概念和分类对策论的基本概念和分类发发 展展 简简 史史1912年年E.Zermelo “关于集合论在象棋对策中的应用关于集合论在象棋对策中的应用”1921年年E.Borel 引入最优策略引入最优策略1928年年J.V.Neumann证明了一些猜想证明了一些猜想博奕论博奕论(Game Theory)也就是运筹学中的对策论。也就是运筹学中的对策论。对策思想最早产生于我国古代。对策思想最早产生于我国古代。早在两千多年前
2、的春秋时期,孙武在早在两千多年前的春秋时期,孙武在孙子兵法孙子兵法中论述的军事思想和治国策略,就蕴育了丰富和深中论述的军事思想和治国策略,就蕴育了丰富和深刻的对策论思想。孙武的后代孙膑,为田忌谋划,刻的对策论思想。孙武的后代孙膑,为田忌谋划,巧胜齐王,这个著名的巧胜齐王,这个著名的“田忌赛马田忌赛马”,就是典型的,就是典型的对策思想的成功运用。对策思想的成功运用。产生标志产生标志作为一门学科的创立,则是以美国数学家冯作为一门学科的创立,则是以美国数学家冯.诺依曼诺依曼(John Von Neumann)和经济学家奥斯卡和经济学家奥斯卡.摩根斯坦摩根斯坦(Oskar Morgenstern)合著
3、的合著的博奕论与经济行为博奕论与经济行为(The Game Theory and Economic Behavior)(1944)一书出版为标志,他们奠定和形成了这门学科的理一书出版为标志,他们奠定和形成了这门学科的理论与方法论基础。论与方法论基础。发展成熟发展成熟Nash均衡、经济博奕论、信息不对称对策和广义对均衡、经济博奕论、信息不对称对策和广义对策策基本概念基本概念在策略型博奕中,一个对策有以下几种基本要素:在策略型博奕中,一个对策有以下几种基本要素:一局中人一局中人(players):即博奕的参与者,他们是博奕的决策主体。根据自己的利益即博奕的参与者,他们是博奕的决策主体。根据自己的利
4、益要求决定自己的决策,记第要求决定自己的决策,记第i个局中人为个局中人为i,局中人集合为,局中人集合为1,2,I,即共有,即共有I个局中人。我们将某个局中人以外的其它个局中人。我们将某个局中人以外的其它局中人称为局中人称为“i的对手的对手”,记为,记为-i。对策中利益一致的参加者只能看成一个局中人,例:桥牌中对策中利益一致的参加者只能看成一个局中人,例:桥牌中的东、西两方。的东、西两方。对策论中对局中人的一个重要假设:每个局中人都是对策论中对局中人的一个重要假设:每个局中人都是“理智理智的的”,即每一个局中人都不存在侥幸心理,不存在利用其他,即每一个局中人都不存在侥幸心理,不存在利用其他局中人
5、决策的失误来扩大自身利益的行为。局中人决策的失误来扩大自身利益的行为。在策略型博奕中,一个对策有以下几种基本要素:在策略型博奕中,一个对策有以下几种基本要素:一局中人一局中人 即指每个局中人在对策中可以选择采用的行动方即指每个局中人在对策中可以选择采用的行动方案,但这个方案必须是一个完整的行动,而不是行动案,但这个方案必须是一个完整的行动,而不是行动的某一步。每个局中人均有可供选择的多种策略。的某一步。每个局中人均有可供选择的多种策略。二策略二策略(strategies):基本概念基本概念三支付或收益三支付或收益(payoffs):二策略二策略一局中人一局中人在策略型博奕中,一个对策有以下几种
6、基本要素:在策略型博奕中,一个对策有以下几种基本要素:是是指指一一局局博博奕奕的的得得失失。或或者者说说是是局局中中人人从从各各种种策策略略组组合合中中获获得得的的效效用用,它它是是策策略略组组合合的的函函数数。如如果果局局中中人人得得失失的的总总和和为为零零,则则称称这这种种对对策策为为零零和和对对策策(博弈);(博弈);否则,称为否则,称为非零和对策非零和对策(博奕博奕)。基本概念基本概念局势:局势:一个对策中,每一个局中人所出策略形成的策一个对策中,每一个局中人所出策略形成的策略组称为一个局势。略组称为一个局势。设设si是第是第i个局中人的一个策略,则个局中人的一个策略,则n个局中人的策
7、略个局中人的策略形成的策略组形成的策略组s=s1,s2,sn,就是一个局势。就是一个局势。全部局势的集合全部局势的集合S记为:记为:模模 型型局中人局中人 两个或两个以上两个或两个以上-决策者决策者策略集合策略集合 策略策略-决策决策 局势局势-状态状态支付函数支付函数 支付关于局势的函数支付关于局势的函数-决策依据和标准决策依据和标准 模型模型分分 类类局中人局中人 两人对策、多人对策两人对策、多人对策策略策略 有限对策、无限对策;非合作对策、合作对策有限对策、无限对策;非合作对策、合作对策支付支付 零和对策、非零和对策零和对策、非零和对策时间时间 单阶段对策、多阶段对策单阶段对策、多阶段对
8、策对策模型众多,但占有重要地位的是二人有限零和对对策模型众多,但占有重要地位的是二人有限零和对策(矩阵对策)。它是一类最简单的对策模型,策(矩阵对策)。它是一类最简单的对策模型,它它的结果也是研究其他对策模型的基础。的结果也是研究其他对策模型的基础。第二节第二节二人有限零和对策模型二人有限零和对策模型 二人有限零和对策二人有限零和对策二人二人:参加对策的局中人有两个;:参加对策的局中人有两个;有限有限:局中人的策略集都为有限集;:局中人的策略集都为有限集;零和零和:在任一局势下,两个局中人的赢得之和总等于在任一局势下,两个局中人的赢得之和总等于0,即,即,一个局中人的所得值恰好是另一个局中人的
9、所失值,双方的一个局中人的所得值恰好是另一个局中人的所失值,双方的利益是完全对抗的。利益是完全对抗的。设局中人设局中人I和和II的策略集分别为的策略集分别为对任一纯局势对任一纯局势,记局中人,记局中人I的赢得值为的赢得值为则则I的赢得矩阵为的赢得矩阵为例:甲、乙各出示一枚硬币,在不让对方看见的情况例:甲、乙各出示一枚硬币,在不让对方看见的情况下,将硬币放在桌子上,若两个硬币都呈正面或都下,将硬币放在桌子上,若两个硬币都呈正面或都呈反面则甲得呈反面则甲得1分,乙付出分,乙付出1分;若两个硬币一个呈分;若两个硬币一个呈正面另一个呈反面则乙得正面另一个呈反面则乙得1分,甲付出分,甲付出1分分局中人局
10、中人:甲、乙:甲、乙甲的赢得矩阵为甲的赢得矩阵为例例(齐王与田忌赛马)(齐王与田忌赛马)这个问题中齐王和田忌各自拥有的策略为:这个问题中齐王和田忌各自拥有的策略为:S1=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(下中上下中上),(下上中下上中)S2=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(下中上下中上),(下上中下上中)则对应的齐王的赢得矩阵为则对应的齐王的赢得矩阵为例:甲乙两人玩猜拳游戏,游戏中双方同时分别出石例:甲乙两人玩猜拳游戏,游戏中双方同时分别出石头、布或剪刀。规则是剪刀赢布,布赢石头,石头头、布或剪刀。规则是剪刀赢布
11、,布赢石头,石头赢剪刀,赢者得一分。若出的相同,算和局都不得赢剪刀,赢者得一分。若出的相同,算和局都不得分。试列出甲的赢得矩阵。分。试列出甲的赢得矩阵。石头布剪刀石头0-11布10-1剪刀-110第三节第三节矩阵对策的纯策略矩阵对策的纯策略例:设有一矩阵对策例:设有一矩阵对策其中其中解:对局中人解:对局中人I而言,最大赢得是而言,最大赢得是9,若想得到这个赢得,若想得到这个赢得,他要选择纯策略他要选择纯策略 ,由于局中人,由于局中人II也是理智的竞争也是理智的竞争者,他已考虑到局中人者,他已考虑到局中人I打算出打算出 的心理,则准备以的心理,则准备以 对付之,使局中人对付之,使局中人I不但得不
12、到不但得不到9,反而失掉,反而失掉10.局中人局中人I当然也会猜到局中人当然也会猜到局中人II的心理,故而出的心理,故而出 来对付,使局中人来对付,使局中人II得不到得不到10,反而失掉,反而失掉6,如果双方都不想冒险,都不存在侥幸心理,而是考虑到对方必然如果双方都不想冒险,都不存在侥幸心理,而是考虑到对方必然会设法使自己所得最少这一点,就应该从各自可能出现的最不利会设法使自己所得最少这一点,就应该从各自可能出现的最不利的情形中选择一个最有利的情形作为决策的依据,这就是所谓的的情形中选择一个最有利的情形作为决策的依据,这就是所谓的“理智行为理智行为”,也是对策双方实际上可以接受并采取的一种稳妥
13、方,也是对策双方实际上可以接受并采取的一种稳妥方法。法。对策双方处于完全对抗的环境中,因此,各自都采取保守态对策双方处于完全对抗的环境中,因此,各自都采取保守态度,从最坏处着眼,并力争较好的结局。所以,局中人度,从最坏处着眼,并力争较好的结局。所以,局中人A采用采用maxmin准则,局中人准则,局中人B采用采用minmax准则。准则。相应于这种准则下,对策双方采取的各自的策略称为相应于这种准则下,对策双方采取的各自的策略称为对策的解对策的解。双方采取上述策略,连续重复进行对策,其输赢的平均值称为双方采取上述策略,连续重复进行对策,其输赢的平均值称为相应对策问题的对策值相应对策问题的对策值,记为
14、,记为v对策问题选择解的准则对策问题选择解的准则b1b2bna1c11c12c1na2c21c22c2namcm1cm2cmn设局中人设局中人A的策略有的策略有 ,局中人,局中人B的策略有的策略有 ,A的赢得矩阵为的赢得矩阵为maxmin准则准则:当当A依据此原则选择策略时,总考虑不管选哪一个策略依据此原则选择策略时,总考虑不管选哪一个策略都将得到最坏的结局。即都将得到最坏的结局。即minmax准则准则:当当B依据此原则选择策略时,总考虑不管选哪一个策略依据此原则选择策略时,总考虑不管选哪一个策略都将得到最坏的结局(最大损失)。即都将得到最坏的结局(最大损失)。即均均 衡衡 解解按照这个定义,
15、例中的均衡解为按照这个定义,例中的均衡解为继续分析前例继续分析前例:此时的平衡局势此时的平衡局势 ,对应的值,对应的值 既是其所在既是其所在行的最小元素,又是其所在列的最大元素,即有行的最小元素,又是其所在列的最大元素,即有一般地,有如下定义和结论:一般地,有如下定义和结论:证明:证明:另一方面,对任意的另一方面,对任意的i,j,由,由由(由(1),(),(2)得)得必要性:必要性:设有设有i*,j*,使得使得则由则由有有注注以上定理的对策意义为:一个平衡局势以上定理的对策意义为:一个平衡局势 应该具应该具有这样的性质:当局中人有这样的性质:当局中人A选择了策略选择了策略 后,局后,局中人中人
16、B为了使其损失最小,只能选择策略为了使其损失最小,只能选择策略 ,否则,否则就可能损失更多;反之,当局中人就可能损失更多;反之,当局中人B选择了策略选择了策略 后,局中人后,局中人A为了得到最大赢得也只能选择策略为了得到最大赢得也只能选择策略 否则就会赢得较少,双方的竞争在局势否则就会赢得较少,双方的竞争在局势 下达下达到了一个平衡状态。到了一个平衡状态。例例 子子例例 子子例例 求下面的矩阵对策的解求下面的矩阵对策的解解:计算解:计算此时,此时,i*=1,3;j*=2,4所以,所以,(a1,b2),(a1,b4),(a2,b2),(a2,b4)都是对策的解。都是对策的解。由以上例子知,对策的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 教学 策论
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。