运筹学—对策论(三).ppt

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

1、定理定理1 矩阵对策矩阵对策G=S1，S2；A在纯策略意义下有解在纯策略意义下有解的充要条件是：存在纯局势（的充要条件是：存在纯局势（i*,j*）使得对一切使得对一切i=1,2,m,j=1,2,n,均有均有aij*ai*j*ai*j 。E(x,y*)E(x*,y*)E(x*,y)定理定理2 矩阵对策矩阵对策G=S1,S2;A 在混合策略意义下有解在混合策略意义下有解的充要条件是：存在的充要条件是：存在x*S1*,y*S2*,使使(x*,y*)为为E(x,y)的一个鞍点，即对一切的一个鞍点，即对一切x S1*,y S2*，有有复习已讲的矩阵对策内容复习已讲的矩阵对策内容E(i,y*)E(x*,y

2、*)E(x*,j)定理定理3 设设x*S1*,y*S2*,则则(x*,y*)是是G的解的充要的解的充要条件是：对任意条件是：对任意i=1,2,m和和j=1,2,n，有有定理定理4 设设x*S1*,y*S2*,则则(x*,y*)是是G的解的充要的解的充要条件是：存在条件是：存在v,使得使得x*和和y*分别是不等式组分别是不等式组v ,j=1,2,n i=1 m aijxi1 i=1 m xixi0,i=1,2,mv ,i=1,2,m j=1 n aijyj1 j=1 n yiyj0,j=1,2,n和和的的解，且解，且v=VG。E(x,j)E(i,y)定理定理5 对任一矩阵对策对任一矩阵对策G=S

3、1,S2;A，一定存在混合一定存在混合策略意义下的解。策略意义下的解。运筹学运筹学对策论对策论(三三)记矩阵对策记矩阵对策G的解集为的解集为T(G),关于对策解集有下列关于对策解集有下列两个性质：两个性质：定理定理6 设有两个矩阵对策设有两个矩阵对策 G1=S1,S2;A1，G2=S1,S2;A2，其中其中A1=(aij),A2=(aij+L),L为任一常数，则为任一常数，则有有 VG2=VG1+L T(G1)=T(G2)例例 1 设设G1和和G2赢得矩阵分别为赢得矩阵分别为 5 1A1=2 44 0 7 3A2=4 66 2定义定义5 设设G=S1，S2；A为矩阵对策，其中为矩阵对策，其中S

4、1=1,2,m，S2=1,2,n，A=（aij）mn 。如果对一切如果对一切j=1,2,n,都有都有ai0j ak0j 即即矩阵矩阵A的第的第i0行均不小于第行均不小于第k0行的对应元素，则称局行的对应元素，则称局中人中人的纯策略的纯策略i0优超于优超于k0 ；同样，若对一切同样，若对一切i=1,2,m,都有都有aij0 ail0即即矩阵矩阵A的第的第l0列均不小于第列均不小于第j0列的对应元素，则称局中人列的对应元素，则称局中人的纯策略的纯策略 j0优超于优超于 l0。定理定理7 设有两个矩阵对策设有两个矩阵对策 G1=S1,S2;A，G2=S1,S2;A，其中其中0为任一常数，则有为任一常

5、数，则有 VG2=VG1 T(G1)=T(G2)例例 2 设设G1和和G2赢得矩阵分别为赢得矩阵分别为 3 2A1=2 42 0 6 4A2=4 84 0定理定理8 设设G=S1，S2；A为矩阵对策，其中为矩阵对策，其中S1=1,2,m，S2=1,2,n，A=（aij）mn 。如果纯策略如果纯策略1被被2,m中之一所优中之一所优超超，由，由G可得到一个新的矩阵对策可得到一个新的矩阵对策G：G=S1,S2；A 其中其中S1=2,m，A =（aij）(m1)n aij=aij ,i=2,m,j=1,2,n ,则则V G=VG；G中局中人中局中人的最优策略就的最优策略就是其在是其在G中的最优策略；中

6、的最优策略；若若(x2*,xm*)T是是G中局中局中人中人的最优策略，则的最优策略，则x*=(0，x2*,xm*)T便是其便是其在在G中的最优策略。中的最优策略。例例 3 设设G赢得矩阵为赢得矩阵为 3 2 2A=5 2 3 2 5 1推论推论：在定理在定理8中，若纯策略中，若纯策略1不是为不是为2,m中之一所优超中之一所优超，而是为而是为2,m的的某个凸线性组某个凸线性组合所优超，定理的结论仍然成立。合所优超，定理的结论仍然成立。优超原则：优超原则：定理定理8给出了一个简化赢得矩阵给出了一个简化赢得矩阵A的原则，的原则，称之为优超原则。根据这个原则，当局中人称之为优超原则。根据这个原则，当局

7、中人的某的某纯策略纯策略i被被其它纯策略或纯策略的凸线性组合所优其它纯策略或纯策略的凸线性组合所优超，可在矩阵超，可在矩阵A中划去第中划去第i行而得到一个与原对策行而得到一个与原对策G等价但赢得矩阵阶数较小的对策等价但赢得矩阵阶数较小的对策G，通过求通过求G而得而得到到G的解。的解。7 3 9 9A=4 6 8 5.5 6 0 8 3例：例：1/3(第第1列列)+2/3(第第2列列)优超第优超第4列列例例 4 设赢得矩阵为设赢得矩阵为3 2 0 3 05 0 2 5 9 7 3 9 5 9A=4 6 8 7 5.56 0 8 8 3求解求解这个矩这个矩阵对策。阵对策。解：解：由于第由于第4行优

8、超第行优超第1行，第行，第3行优超第行优超第2行，故可划行，故可划去第去第1行和第行和第2行，得到新的赢得矩阵行，得到新的赢得矩阵 7 3 9 5 9A1=4 6 8 7 5.56 0 8 8 3对对A1第第1列优超第列优超第3列，第列，第2列优超第列优超第4列，列，1/3(第第1列列)+2/3(第第2列列)优超第优超第5列，故可划去第列，故可划去第3 4 5列，得到新列，得到新的赢得矩阵的赢得矩阵 7 3A2=4 66 0 7 3A3=4 6A2第第1行优超第行优超第3行，故划去第行，故划去第3行，得到行，得到对于对于A3，易知无鞍点，应用定理易知无鞍点，应用定理4，求解不等式组，求解不等式

9、组7x3+4x4 3x3+6x4 x3+x4=1X3,x4 0和和7y1+3y2 4y1+6y2 y1+y2=1y1,y2 07x3+4x4=3x3+6x4=x3+x4=17y1+3y2=4y1+6y2=y1+y2=1首先考虑方程组的解首先考虑方程组的解求解得求解得x3*=1/3，x4*=2/3；y1*=1/2，y2*=1/2；=5于是，原矩阵对策的一个解就是：于是，原矩阵对策的一个解就是：X*=(0,0,1/3,2/3,0)T，Y*=(1/2,1/2,0,0,0)T ，VG=5练习题练习题 “二指莫拉问题二指莫拉问题”。甲乙二人游戏，每人。甲乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的出一个或两个手指，同时又把猜测对方所出的指数叫出来。如果只有一个人猜测正确，则他指数叫出来。如果只有一个人猜测正确，则他所赢得的数目为二人所出指数之和，否则重新所赢得的数目为二人所出指数之和，否则重新开始。写出该对策中各局中人的策略集合及甲开始。写出该对策中各局中人的策略集合及甲的赢得矩阵，并回答局中人是否存在某种出法的赢得矩阵，并回答局中人是否存在某种出法比其它出法更为有利。比其它出法更为有利。