10-矩阵对策(ppt文档).ppt
《10-矩阵对策(ppt文档).ppt》由会员分享,可在线阅读,更多相关《10-矩阵对策(ppt文档).ppt(56页珍藏版)》请在咨信网上搜索。
1、第第 10 章章Games Theory矩矩 阵阵 对对 策策对策论对策论的第一扇大门的第一扇大门1第10章 矩阵对策10.1 基本概念基本概念10.2 特殊方法特殊方法10.3 线性规划法线性规划法第第10章章 矩阵对策矩阵对策2第10章 矩阵对策10.1 基本概念基本概念 10.1.10.1.1 1 引言引言引言引言一一、对策现象及其三个要素对策现象及其三个要素 对策对策对策对策:就是竞争或斗争中的决策。就是竞争或斗争中的决策。对策现象的对策现象的三个要素三个要素三个要素三个要素:局中人、策略、得失局中人、策略、得失局中人、策略、得失局中人、策略、得失。(1 1)局中人局中人局中人局中人:
2、参与对策并有切身利益关系与决策权的个人或集体。参与对策并有切身利益关系与决策权的个人或集体。假设假设假设假设:局中人都是局中人都是聪明的聪明的聪明的聪明的。(2 2)策略策略策略策略:每个局中人为了自身利益所能采取的对付其他局中人的每个局中人为了自身利益所能采取的对付其他局中人的 办法或措施,称为该局中人的办法或措施,称为该局中人的策略策略策略策略。一个策略应是在一局对策中,从始至终采取的所有行动的一个策略应是在一局对策中,从始至终采取的所有行动的 一套完整方案。一套完整方案。(3 3)得失得失得失得失:一局对策一局对策一局对策一局对策的的结果结果结果结果,诸如,诸如胜负、名次、损益、效用胜负
3、、名次、损益、效用胜负、名次、损益、效用胜负、名次、损益、效用,等等,等等,统称为统称为得失得失得失得失。3第10章 矩阵对策10.1 基本概念基本概念 例例1 田忌赛马田忌赛马(1 1)局中人局中人局中人局中人:田忌、齐王;田忌、齐王;(2 2)策策策策 略略略略:3 匹马参赛的顺序:匹马参赛的顺序:(上,中,下),上,中,下),(上,下,中)上,下,中)(中,下,上),中,下,上),(中,上,下)中,上,下)(下,上,中),下,上,中),(下,中,上)下,中,上)策略集策略集策略集策略集:每个每个局中人局中人局中人局中人所有策略构成的集合。所有策略构成的集合。局势局势局势局势:(下,上,中
4、下,上,中),(上,中,下上,中,下)(3 3)得得得得 失失失失:一局千金。一局千金。二、二、对策的分类对策的分类 局中人数局中人数:二人二人二人二人对策对策 多人多人多人多人对策对策 策略数:策略数:有限有限有限有限对策对策 无限无限无限无限对策对策 得失总和:得失总和:零和零和零和零和对策对策 非零和非零和非零和非零和对策对策 4第10章 矩阵对策10.1 基本概念基本概念 二、二、对策的分类(续)对策的分类(续)按按相互关系相互关系相互关系相互关系:平等平等对策对策 主从主从对策对策协商协商协商协商对策对策对抗对抗对抗对抗对策对策结结结结 盟盟盟盟对策对策不结盟不结盟不结盟不结盟对策对
5、策 多人多人对策对策联合联合联合联合对策对策合作合作合作合作对策对策 按按数学模型数学模型数学模型数学模型:矩阵矩阵矩阵矩阵对策对策、树图树图树图树图对策对策、微分微分微分微分对策。对策。5第10章 矩阵对策10.1 基本概念基本概念 三、矩阵对策的基本模型三、矩阵对策的基本模型 在二人有限零和对策中,设以在二人有限零和对策中,设以甲方甲方、乙方乙方表示两个表示两个 局中人局中人局中人局中人,以以 S1=1,2,m S2=1,2,n 分别表示分别表示甲方甲方、乙方乙方的的策略集策略集策略集策略集,其中:其中:i(i=1,2,m)甲方甲方的的策略策略策略策略 j (j=1,2,n)乙方乙方的的策
6、略策略策略策略6第10章 矩阵对策10.1 基本概念基本概念 则则 S1 与与 S2 构成构成 mn 个局势个局势 (i,j),i=1,2,m;j=1,2,n令令 aij 甲方甲方甲方甲方关于局势关于局势(i,j)的赢得的赢得则所有则所有 aij 构成一个矩阵构成一个矩阵A=(aij)mn称为称为甲方甲方甲方甲方的的赢得矩阵赢得矩阵。由于甲、乙双方得失总和恒为零,所以由于甲、乙双方得失总和恒为零,所以A还可称为还可称为乙方乙方乙方乙方的的损失矩阵损失矩阵,而,而 A 即乙方的赢得矩阵。即乙方的赢得矩阵。7第10章 矩阵对策10.1 基本概念基本概念 由此可见,在由此可见,在二人有限零和二人有限
7、零和二人有限零和二人有限零和对策中,给定一个局中人的对策中,给定一个局中人的赢得矩阵,则另一个局中人的赢得矩阵也就唯一确定了,而赢得矩阵,则另一个局中人的赢得矩阵也就唯一确定了,而且双方的策略数目也就唯一确定了。这意味着二人有限零和且双方的策略数目也就唯一确定了。这意味着二人有限零和对策总可以由一个局中人的赢得矩阵来刻画,故称这种对策对策总可以由一个局中人的赢得矩阵来刻画,故称这种对策为为矩阵对策矩阵对策矩阵对策矩阵对策。其其基本模型基本模型记为记为 G=S1,S2,A 其中其中 A=(aij)mn 规定为规定为甲方甲方甲方甲方的的赢得矩阵赢得矩阵赢得矩阵赢得矩阵。8第10章 矩阵对策10.1
8、 基本概念基本概念例例1 田忌赛马田忌赛马 设以设以 S S1 1=1 1,2 2,3 3,4 4,5 5,6 6 表示表示田忌田忌田忌田忌的策略集,的策略集,其中:其中:1 1 =(上、中、下上、中、下上、中、下上、中、下),2 2=(上、下、中上、下、中上、下、中上、下、中)3 3=(中、下、上中、下、上中、下、上中、下、上),4 4=(中、上、下中、上、下中、上、下中、上、下)5 5=(下、上、中下、上、中下、上、中下、上、中),6 6=(下、中、上下、中、上下、中、上下、中、上)以以 S2=1,2,3,4,5,6 表示表示齐王齐王的策略集,的策略集,其中:其中:1=(上、中、下上、中、
9、下上、中、下上、中、下),),2=(上、下、中上、下、中上、下、中上、下、中)3=(中、下、上中、下、上中、下、上中、下、上),4=(中、上、下中、上、下中、上、下中、上、下)5=(下、上、中下、上、中下、上、中下、上、中),6=(下、中、上下、中、上下、中、上下、中、上)9第10章 矩阵对策10.1 基本概念基本概念则则田忌的赢得矩阵田忌的赢得矩阵田忌的赢得矩阵田忌的赢得矩阵为:为:1 2 3 4 5 6 1 -3 -1 1 -1 -1 -1 2 -1 -3 -1 1 -1 -1 3 -1 -1 -3 -1 1 -1 4 -1 -1 -1 -3 -1 1 5 1 -1 -1 -1 -3 -1
10、 6 -1 1 -1 -1 -1 -3A=10第10章 矩阵对策10.1 基本概念基本概念10.1.10.1.2 2 纯策略纯策略纯策略纯策略 一、一、鞍点鞍点 例例2 设有对策设有对策G=S1,S2,A,其中其中:1 2 3 4 1 7 -8 -2 3 2 3 6 1 2 3 9 2 -3 -5A=-81-5(max)min aij9613max aij(min)111(2,3)为为最优纯局势最优纯局势。坏坏中求中求好好11第10章 矩阵对策10.1 基本概念基本概念 设有对策设有对策G=S1,S2,A,其中其中 S1=1,2,m,S2=1,2,n A=(aij)mn如果如果A中存在一个元素
11、中存在一个元素a arkrk,满足,满足:a arkrk=max min aij=min max aijijji则把则把 a arkrk 所对应的局势所对应的局势 (r,k)称为对策称为对策G的的解解或或鞍点鞍点,分别称分别称r 甲方甲方的的最优纯策略最优纯策略,记为,记为*=r k 乙方乙方的的最优纯策略最优纯策略,记为,记为*=k a arkrk 对策对策G的的值值,记为,记为v v即即v v=max min aij=min max aij=a arkrk iijj(11-2)12第10章 矩阵对策10.1 基本概念基本概念二、二、鞍点属性鞍点属性 定理定理定理定理1 1 对策对策G=S1
12、,S2,A 在纯策略意义下有解的在纯策略意义下有解的充要条件充要条件充要条件充要条件是:矩阵是:矩阵A中存在一个元素中存在一个元素 a ark rk,它对一切它对一切 i、j 都满足:都满足:上式意味着:上式意味着:a arkrk 是它所在是它所在行行的诸元素中的的诸元素中的最小最小者者,同时又是它所在同时又是它所在列列的诸元素中的的诸元素中的最大最大者者。(11-3)aikarkarj,i=1,2,m;j=1,2,n 13第10章 矩阵对策10.1 基本概念基本概念最优纯策略最优纯策略具有下述具有下述性质性质性质性质:(1)若甲方采用若甲方采用*=r r,则他的赢得至少是则他的赢得至少是v
13、v,即便即便事先公开这一点事先公开这一点,乙方也无法利用这一信息使甲方的赢得乙方也无法利用这一信息使甲方的赢得比比 v v 更少。更少。(2)若乙方采用若乙方采用*=k k,则他的损失至多是则他的损失至多是v v,即便即便事先公开这一点事先公开这一点,甲方也无法利用这一信息使乙方的损失甲方也无法利用这一信息使乙方的损失比比 v v 更多。更多。14第10章 矩阵对策10.1 基本概念基本概念例例3 求解对策求解对策G=S1,S2,A,其中其中:(max)(max)(min)(min)解解 4 3 6 3-2 2 0 -6 5 3 4 3A=4 3 6 3-2 2 0 -6 5 3 4 3 5
14、3 6 31 2 3 4 3-6 3123A=jmin aijimax aij333315第10章 矩阵对策10.1 基本概念基本概念1010.1 1.3 3 混合策略混合策略一、矩阵对策的解一、矩阵对策的解 如前所述如前所述,有些矩阵对策在纯策略下无解。那么在这种有些矩阵对策在纯策略下无解。那么在这种 情况下,双方应如何决策呢?情况下,双方应如何决策呢?例例4 已知对策已知对策G=S1,S2,A,其中其中:S S1 1=1 1,2 2,S2=1,2 A=7 43 616第10章 矩阵对策10.1 基本概念基本概念 局中人甲的局中人甲的期望赢得期望赢得为为:E(x,y)=aijP(ij)=ai
15、jP(i)P(j)=7xy+4x(1-y)+3(1-x)y+6(1-x)(1-y)=6 xy-3y-2 x+6 X=(x1,x2 )T =(x,1-x)TY=(y1,y2)T =(y,1-y)TX*=(1/2,1/2)TY*Y*=(1 1/3 3,2 2/3 3)TE E(X*,Y*Y*)=5 5-2(x-1/2)+5=6(x-1/2)(y-1/3)+5x=1/2 1-x=1/2 y=1/3 1-y=2/3=6y(x-1/2)P(j)7 43 61 12 2P(i)1 2aijjix1-x y 1-y17第10章 矩阵对策10.1 基本概念基本概念 (1)把把S1上的概率分布上的概率分布 X=
16、(x1,x2,xm)T 称为称为甲方的混合策略甲方的混合策略,把把S2上的概率分布上的概率分布 Y=(y1,y2,yn)T 称为称为乙方的混合策略乙方的混合策略,称称(X,Y)为对策为对策G的一个的一个混合局势混合局势。(2)称数学期望称数学期望i=1j=1 m nE E(X,Y)=aij xi yj=XTAY 为甲方的为甲方的期望赢得期望赢得,简称为甲的,简称为甲的赢得赢得,同时又称为同时又称为乙方的乙方的损失损失,而而-E E(X,Y)为乙方的为乙方的赢得赢得。18第10章 矩阵对策10.1 基本概念基本概念 (3)记记 S1*=X=(x1,x2,xm)T|xi0,i=1,2,m,xi=1
17、 甲方甲方的的混合策略集混合策略集,S2*=Y=(y1,y2,yn)T|yj0,j=1,2,n,yj=1 乙方乙方的的混合策略集混合策略集,G*G*=S1*,S2*,E E G=S1,S2,A 的的混合扩充混合扩充。19第10章 矩阵对策10.1 基本概念基本概念 (4)若有若有X*S1*,Y*Y*S2*,使使XX Y YE E(X*,Y*Y*)=max min E E(X,Y)=min max E E(X,Y)XX YYv*v*=max min E E(X,Y)=min max E E(X,Y)=E E(X*,Y*Y*)则则这样,这样,对策对策在纯策略意义下的解在纯策略意义下的解(*,*)就
18、成为就成为(X*,Y*Y*)的一种特殊情况。的一种特殊情况。X*甲甲方的方的最优混合策略最优混合策略 Y*Y*乙乙方的方的最优混合策略最优混合策略 简称简称最优策略最优策略;而;而 (X*,Y*Y*)对策对策G在在混合策略意义下的混合策略意义下的解解 E E(X*,Y*Y*)对策对策G的的值值,记为,记为 v*v*,即,即如如例例例例2 2 2 2 :X*=(0,1,0)T Y*Y*=(0 0,0 0,1 1,0 0)T 2320第10章 矩阵对策10.1 基本概念基本概念二、基本定理二、基本定理 定理定理定理定理2 2 2 2 混合局势混合局势(X*,Y*Y*)是矩阵对策是矩阵对策G的解的的
19、解的充要充要充要充要条件条件 是:对一切是:对一切XS1*和和YS2*,都有都有 E E(X,Y*Y*)E E(X*,Y*Y*)E E(X*,Y)定理定理定理定理3 3 3 3 若存在实数若存在实数v0以及以及 X*S1*,Y*Y*S2*,则,则(X*,Y*Y*)是是G的解,且的解,且v*v*=v0 的的充要充要充要充要条件是:对任意条件是:对任意 iI 和和 jJ,都有都有 E E(ei,Y*Y*)v0 E E(X*,ej)21第10章 矩阵对策10.1 基本概念基本概念推论推论推论推论 设设v*v*是是对策对策G=S1,S2,A 的的值,则方程组值,则方程组的的解解 X X*=(x x1
20、1*,x x2 2*,x xmm*)T 是是甲甲方的最优策略方的最优策略;而而的的解解 Y*=(y1*,y2*,yn*)T 是是乙乙方的最优策略方的最优策略;aij xi v*v*,j=1,2,ni=1 m xi=1j=1nxi 0,i=1,2,m()aij yj v*v*,i=1,2,mi=1 m yj=1j=1nyj 0,j=1,2,n()22第10章 矩阵对策 定理定理定理定理4 4 4 4 若若(X*,Y*Y*)是矩阵对策是矩阵对策G的解的解,v*v*是是G的值的值,则对每一个则对每一个 iI 或或 jJ,都有都有 (1)若若 xi*0,则则 aij y yj j*=v*v*(2)若若
21、 y yj j*0,则则 aij xi*=v*v*(3)若若aij y yj j*v*v*,则则 y yi i*=0 定理定理定理定理5 5 5 5 矩阵对策的基本定理矩阵对策的基本定理 任何矩阵对策任何矩阵对策G=S1,S2,A 在混合策略意义下在混合策略意义下 一定有解。一定有解。10.1 基本概念基本概念23第10章 矩阵对策10.2 特殊方法特殊方法10.2.10.2.1 1 矩阵对策的矩阵对策的矩阵对策的矩阵对策的特殊解法特殊解法特殊解法特殊解法 如前所述,矩阵对策总能用线性规划求解,但求解较繁如前所述,矩阵对策总能用线性规划求解,但求解较繁.而有些特殊的矩阵对策可能有一些更简单的特
22、殊解法。而有些特殊的矩阵对策可能有一些更简单的特殊解法。一、特殊不等式方程组解法一、特殊不等式方程组解法 例例5 甲、乙二人一起玩甲、乙二人一起玩“锤子、剪子、袱子锤子、剪子、袱子”的游戏,的游戏,每人都可从每人都可从 锤、剪、袱锤、剪、袱 中选择一个出法中选择一个出法(纯策略纯策略)从而从而构成一个纯局势。该游戏规定:锤胜剪构成一个纯局势。该游戏规定:锤胜剪,剪胜袱剪胜袱,袱胜锤。袱胜锤。又若规定:胜则得又若规定:胜则得1分分,负则得负则得-1分,平手时双方各得分,平手时双方各得0分分,则甲方的赢得矩阵为:则甲方的赢得矩阵为:24第10章 矩阵对策 -x2+x3 v*v*x1 -x3 v*v
23、*-x1+x2 v*v*x1+x2+x3=1 x1,x2,x3 010.2 特殊方法特殊方法A=()()y2 -y3 v*v*-y1 +y3 v*v*y1 -y2 v*v*y1+y2 +y3 =1 1y1,y2,y3 0 x1x2x30 1 -1-1 0 11 -1 0y1 y2 y3锤锤剪剪袱袱 锤锤 剪剪 袱袱25第10章 矩阵对策10.2 特殊方法特殊方法每组的前三式相加每组的前三式相加 131313131313X*=(,)T,Y*=(,)T -x2+x3 v*v*x1 -x3 v*v*-x1+x2 v*v*x1+x2+x3=1 x1,x2,x3 0()0 0 0再结合再结合 x1+x2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 10 矩阵 对策 ppt 文档
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。