运筹学—对策论(三)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,定理1 矩阵对策G=S,1,，,S,2,i*,j*,）使得对一切i=1,2, ,m, j=1,2, ,n, 均有a,ij*, a,i*j*, a,i*j,。,E(,x,y,*) E(,x,*,y,*) E(,x,*,y,),定理2 矩阵对策G= S,1, S,2,;A 在混合策略意义下有解的充要条件是：存在,x,*,S,1,* ,y,*,S,2,*,使(,x,*,y,*)为E(,x,y,)的一个鞍点，即对一切,x,S,1,* ,y,S,2,*，有,复习已讲的矩阵对策内容,1,E(i,y,*) E(,x,*,y,*) E(,x,*,j),定理3 设,x,*,S,1,* ,y,*,S,2,*,则(,x,*,y,*)是G的解的充要条件是：对任意i=1,2, ,m和j=1,2, ,n，有,定理4 设,x,*,S,1,* ,y,*,S,2,*,则(,x,*,y,*)是G的解的充要条件是：存在,v,使得,x,*和,y,*分别是不等式组,v, j=1,2, ,n,i=1,m,a,ij,x,i,1,i=1,m,x,i,x,i,0 , i=1,2, ,m,v, i=1,2, ,m,j=1,n,a,ij,y,j,1,j=1,n,y,i,y,j,0 , j=1,2, ,n,和,的解，且,v,=V,G,。,E(,x,j),E(i,y,),2,定理5 对任一矩阵对策G= S,1, S,2,;A，一定存在混合策略意义下的解。,运筹学对策论(三),记矩阵对策G的解集为T(G), 关于对策解集有下列两个性质：,定理6 设有两个矩阵对策 G,1,= S,1, S,2,;A,1,，G,2,= S,1, S,2,;A,2, ，其中A,1,=(a,ij,), A,2,=(a,ij,+L),L为任一常数，则有 V,G2,= V,G1,+L T(G,1,)=T(G,2,),例 1 设G,1,和G,2,赢得矩阵分别为,5 1,A,1,=,2 4,4 0,7 3,A,2,=,4 6,6 2,3,定义5 设G=S,1,，,S,2,；A为矩阵对策，其中S,1,=,1,2, ,m,，S,2,=,1,2, , ,n, ，A=（a,ij,）,mn,。如果对一切j=1,2, ,n,都有,a,i,0,j,a,k,0,j,即矩阵A的第i,0,行均不小于第k,0,行的对应元素，则称局中人的纯策略,i,0,优超于,k,0,；同样，若对一切i= 1,2, ,m, 都有,a,ij,0,a,il,0,即矩阵A的第l,0,列均不小于第j,0,列的对应元素，则称局中人的纯策略,j,0,优超于,l,0,。,定理7 设有两个矩阵对策 G,1,= S,1, S,2,;A，G,2,= S,1, S,2,;,A ，其中,0,为任一常数，则有 V,G2,=,V,G1, T(G,1,)=T(G,2,),例 2 设G,1,和G,2,赢得矩阵分别为,3 2,A,1,=,2 4,2 0,6 4,A,2,=,4 8,4 0,4,定理8 设G=S,1,，,S,2,；A为矩阵对策，其中S,1,=,1,2, ,m,，S,2,=,1,2, , ,n, ，,A=（a,ij,）,mn,。如果纯策略,1,被,2, ,m,中之一所优超,，由G可得到一个新的矩阵对策G： G= S,1,S,2,；A 其中S,1,= ,2, ,m,，,A =（a,ij,）,(m1)n,a,ij,= a,ij, i=2, ,m , j=1,2, ,n ,则V,G,=V,G,； G中局中人的最优策略就是其在G中的最优策略；若(x,2,*, , x,m,*),T,是G中局中人的最优策略，则x*= (0，x,2,*, , x,m,*),T,便是其在G中的最优策略。,例 3 设G赢得矩阵为,3 2 2,A=,5 2 3,2 5 1,5,推论 ： 在定理8中，若纯策略,1,不是为,2, ,m,中之一所优超,，而是为,2, ,m,的某个凸线性组合所优超，定理的结论仍然成立。,优超原则：定理8给出了一个简化赢得矩阵A的原则，称之为优超原则。根据这个原则，当局中人的某纯策略,i,被其它纯策略或纯策略的凸线性组合所优超，可在矩阵A中划去第i行而得到一个与原对策G等价但赢得矩阵阶数较小的对策G，通过求G而得到G的解。,7 3 9 9,A=,4 6 8 5.5,6 0 8 3,例：,1/3(第1列)+2/3 (第2列)优超第4列,6,例 4 设赢得矩阵为,3 2 0 3 0,5 0 2 5 9,7 3 9 5 9,A=,4 6 8 7 5.5,6 0 8 8 3,求解这个矩阵对策。,解：,由于第4行优超第1行，第3行优超第2行，故可划去第1行和第2行，得到新的赢得矩阵,7 3 9 5 9,A,1,=,4 6 8 7 5.5,6 0 8 8 3,对A,1,第1列优超第3列，第2列优超第4列，1/3(第1列)+2/3 (第2列)优超第5列，故可划去第3 45列，得到新的赢得矩阵,7 3,A,2,=,4 6,6 0,7 3,A,3,=,4 6,A,2,第1行优超第3行，故划去第3行，得到,7,对于A,3,，易知无鞍点，应用定理4，求解不等式组,7x,3,+4x,4,3x,3,+6x,4,x,3,+x,4,=1,X,3,x,4, 0,和,7y,1,+3y,2,4y,1,+6y,2,y,1,+y,2,=1,y,1,y,2, 0,7x,3,+4x,4,=,3x,3,+6x,4,=,x,3,+x,4,=1,7y,1,+3y,2,=,4y,1,+6y,2,=,y,1,+y,2,=1,首先考虑方程组的解,求解得x,3,*=1/3，x,4,*=2/3； y,1,*=1/2，y,2,*=1/2；,=5,于是，原矩阵对策的一个解就是：,X*=(0,0,1/3,2/3,0),T,， Y*=(1/2, 1/2,0,0,0 ),T,，,V,G,=5,8,练习题,“二指莫拉问题”。甲乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的指数叫出来。如果只有一个人猜测正确，则他所赢得的数目为二人所出指数之和，否则重新开始。写出该对策中各局中人的策略集合及甲的赢得矩阵，并回答局中人是否存在某种出法比其它出法更为有利。,9,