运筹与优化-对策论

运筹与优化,第十四章对策论,对策论,对策论的基本概念对策论的基本定理矩阵对策的解法,第一节对策论的基本概念,对策论亦称竞赛论或博奕论,是研究具有斗争或竞争性质的数学理论和方法.具有竞争或对抗性质的行为称为对策行为.对策论是研究对策行为中竞争各方是否存在最合理的行动方案,以及如何找到最合理方案的数学理论和方法.具有对策行为的模型称为对策模型,或对策.,对策三要素,局中人:在一个对策行为中,有权决定自己行动方案的对策者.n个局中人的集合I=1,2,n.理智的决策者:不存在侥幸心理者.策略集:可供局中人i选择的一个实际可行的完整的行动方案称为一个策略si,策略集Si.局势:在对策中,各局中人所选定的策略构成的策略组s=(s1,s2,sn).全体局势S=S1S2Sn赢得函数:局势s的函数Hi(s).矩阵对策:二人有限零和对策.,第二节对策论的基本定理,局中人I的纯策略集S1=1,2,m;局中人的纯策略集S2=1,2,n;对任一纯局势(i,j)(共mn个),局中人I的赢得值为aij,赢得矩阵为A=(aij)mn.局中人的赢得矩阵为-A.矩阵对策记为G=,，S1，S2；A或G=S1，S2；A.,例1.“齐王赛马”中，齐王的赢得矩阵为:,最优策略:有利于自己获得最大赢得(或最少损失)的策略.选择最优策略的原则:牢记对方总是以最不利于你的行动方案来对付你.例2.设矩阵对策G=S1,S2;A,其中S1=1,2,3,4,S2=1,2,3,试求双方的最优策略和赢得.理智行为:双方各按最不利于自己的情形中选择最为利己的结果作为决策的依据.,定义1.设矩阵对策G=S1,S2；A,若等式(1)成立,记,则称VG为对策G的值,称使(1)成立的纯局势为G在纯策略下的解(或平衡局势、双赢局势).定理1.矩阵对策G=S1,S2；A在纯策略中有解的充要条件是:存在纯局势使得(2)(i=1,2,m,j=1,2,n).既是其所在行的最小元素,又是其所在列的最大元素.,定义2.设实函数f(x,y)定义在xA,yB上,若存在x*A,y*B,使得对xA,yB,有f(x,y*)f(x*,y*)f(x*,y)(3)则称(x*,y*)为f(x,y)的一个鞍点.矩阵对策G在纯策略意义下有解,且的充要条件是:是矩阵A的一个鞍点.例3.确定p和q的取值范围,使矩阵A在(2,2)处存在鞍点.其中,qa22p，p5,q5,例4.设矩阵对策G=S1,S2;A,其中S1=1,2,3,4,S2=1,2,3,试求双方的最优策略和赢得.,性质1(无差别性).若(k,r)和(p,q)是对策G的两个解,则akr=apq.事实上,由,有apqaprakrakqapq因此akr=apq.,性质2(可交换性).若(k,r)和(p,q)是对策G的两个解,则(k,q)和(p,r)也是对策G的解.由aiqapq=akrakqapq=akrakj得aiqakqakj,即akq是鞍点.故(k,q)是解.同理，(p,r)是解.性质1、2表明,矩阵对策的值是唯一的.例5.P385例题.,定义3.设矩阵对策G=S1,S2;A,A=(aij)mn.若局中人I以概率xi0取纯策略i,局中人以概率yj0取纯策略j,且.记则S1*,S2*分别称为局中人I和的混合策略集.称xS1*,yS2*为局中人I和的混合策略,(x,y)为混合局势,局中人I的赢得函数为称G*=S1*,S2*,E为对策G的混合扩充.,设则有定义4.设G*=S1*,S2*;E是矩阵对策G=S1,S2;A的混合扩充,若,记其值为VG,则称VG为对策G*的值,使(3)成立的混合局势(x*,y*)为G在混合策略意义下的解.,定理2.矩阵对策G=S1,S2;A在混合策略中有解的充要条件是:(x*,y*)为E(x,y)的一个鞍点,即对一切xS1*,yS2*,有E(x,y*)E(x*,y*)E(x*,y)(4)注意:G在纯策略下解存在时,定义4中的;G在混合策略意义下的解(x*,y*)存在时,VG=E(x*,y*).例4.解矩阵对策G=S1,S2;A,其中,局中人I取纯策略i时,其赢得函数为E(i,y)=aijyj,局中人取纯策略j时,其赢得函数为E(x,j)=aijxi.由上两式得E(x,y)=E(i,y)xi(5)E(x,y)=E(x,j)yj.(6)定理3.设xS1*,yS2*,则(x*,y*)是G的解的充要条件是:对任意i=1,2,m和j=1,2,n,有E(i,y*)E(x*,y*)E(x*,j)(7),定理3.设xS1*,yS2*,则(x*,y*)是G的解的充要条件是:对任意i=1,2,m和j=1,2,n,有E(i,y*)E(x*,y*)E(x*,j)(7)证明:设(x*,y*)是G的解,则由定理2,有E(x,y*)E(x*,y*)E(x*,y)(4)由于纯策略是混合策略的特例,故(7)式成立.反之,设(7)式成立,由(5)、(6)有E(x,y*)=E(i,y*)xiE(x*,y*)xi=E(x*,y*)E(x*,y)=E(x*,j)yjE(x*,y*)yj=E(x*,y*)可知(4)式成立，故(x*,y*)是G的解,定理4.设x*S1*,y*S2*,则(x*,y*)是G的解的充要条件是:存在数v,使得x*,y*分别是不等式组(8)(9)的解,且v=VG.,定理4.证明:“”因G有解,(7)式成立.取v=E(x*,y*)就有(8),(9).“”因对任意xS1*,yS2*,有E(x,y*)=E(i,y*)xivxi=vE(x*,y)=E(x*,j)yjvyj=v于是E(x,y*)vE(x*,y).特别有E(x*,y*)vE(x*,y*).故v=E(x*,y*)=VG.,定理5.任意矩阵对策G=S1,S2;A一定存在混合策略意义下的解.证明:由定理4,只要证明存在数v*和x*S1*,y*S2*,使得(10)为此,考虑下列两个线性规划问题:,易知(P)和(D)互为对偶,x=(1,0,0)TEm,w=mina1j是(P)的可行解,y=(1,0,0)TEn,v=maxai1是(D)的可行解.因此(P)和(D)皆存在最优解x*S1*,y*S2*,且最优值v*=w*.故(10)式成立.,定理6.设(x*,y*)是矩阵对策G的解,v=VG,那么(1).若xi*0,则;(2).若yj*0,则;(3).若,则xi*=0;(4).若,则yj*=0.证明:由定义有v=maxE(x,y*)，xS1*,故,又因所以,当xi*0，必有;当,必有xi*=0.故(1),(3)得证.同理可证(2),(4).,定理7.设矩阵对策G1=S1,S2;A1的解集T(G1),G2=S1,S2;A2的解集为T(G2).其中A1=(aij),A2=(aij+p),pR.则(1).VG2=VG1+p;(2).T(G1)=T(G2).,定理8.设矩阵对策G1=S1,S2;A的解集为T(G1)，G2=S1,S2;A（R+）的解集为T(G2).则(1).VG2=VG1;(2).T(G1)=T(G2).定理9.设矩阵对策G=S1,S2;A,且A=-AT.则(1).VG=0;(2).T1(G)=T2(G).其中T1(G)和T2(G)分别为局中人和局中人的最优策略集.定理7定理9的证明:利用鞍点的概念和定理3.,定义5.设矩阵对策G=S1,S2;A,其中A=(aij),S1=1,2,m,S2=1,2,n若对j=1n,都有akjatj,则称局中人I的纯策略k优超于t;若对i=1m,都有aipaiq,则称局中人的纯策略p优超于q.定理10.设矩阵对策G=S1,S2;A,如果纯策略1被纯策略2,m中之一所优超,由G可得新的矩阵对策G=S1,S2;A,于是有(1).VG=VG;(2).T2(G)包含于T2(G)中;(3).若(x2,xm)TT1(G),则(0,x2,xm)TT1(G).,推论.如果纯策略1被纯策略2,m的凸线性组合所优超,则定理10的结论仍成立.类似地，对局中人，如果纯策略1被纯策略2,n的凸线性组合所优超,于是有(1).VG=VG;(2).T1(G)包含于T1(G)中;(3).若(y2,ym)TT2(G),则(0,y2,ym)TT2(G).优超原则：可在赢得矩阵A中划去被其它行(列)或其它行(列)的凸线性组合所优超的那些行(列).,例5.设赢得矩阵A如下,求解矩阵对策G.解:,由于矩阵A中行r4r1,r3r2,故可从A中划去第1行和第2行,得到新矩阵A1.,对于A1,列c1c3,c2c4,(1/3)c1+(2/3)c3c5,可从A1中划去第3列、第4列、第5列,得到新矩阵A2.,对于A2,r1r3,从A2中划去第3行,得到新矩阵A3.对于A3,由于,故A3无鞍点.应用定理4,求解不等式组:7x3+4x4v7y1+3y2v3x3+6x4v(I)；4y1+6y2v()x3+x4=1y1+y2=1x3,x40y1,y20,首先求解下列等式组的非负解:7x3+4x4=v7y1+4y2=v3x3+6x4=v(I)4y1+6y2=v()x3+x4=1y1+y2=1求得x3*=1/3,x4*=2/3,v=5,y1*=1/2,y2*=1/2.于是,原对策G的解是x*=(0,0,1/3,2/3,0)T,y*=(1/2,1/2,0,0,0)T,VG=5.,第三节矩阵对策论的解法一、22对策的公式法,设,当A无鞍点时,可以证明G有严格非负解:x1*=(a22-a21)/(a11+a22)-(a12+a21),x2*=(a11-a12)/(a11+a22)-(a12+a21);y1*=(a22-a12)/(a11+a22)-(a12+a21),y2*=(a11-a21)/(a11+a22)-(a12+a21);VG=(a11a22-a12a21)/(a11+a22)-(a12+a21).例1.设矩阵对策G=S1,S2;A,其中则对策的最优解为:x*=(1/2,1/2),y*=(1/4,3/4),VG=5/2,二、图解法,例2.设矩阵对策G=S1,S2;A,其中S1=1,2,S2=1,2,3.试用图解法求解.解:设局中人I的混合策略为(x1,1-x1)T,x10,1.做两条垂线P0(x1=0)和P1(x1=1),P0P1表示局中人I分别取纯策略3112和1.垂线P0上的值表71示局中人I取2时,局中人5B2取各j时的赢得值.同理,2S23垂线P1上的值表示局中人I取0A11时,局中人取各j时的赢得值.图1,P0图1P13117,51B232S20A1,如图1,当局中人I选择策略(x1,1-x1)T时,其最少可能的收入是局中人选择1,2,3时所确定的三条直线,2x1+7(1-x1)=v3x1+5(1-x1)=v11x1+2(1-x1)=v在x1处的纵坐标中之最小者.所以局中人I按maxmin原则,应选择x1=OA,而AB即为对策值.,联立过点B的两条线段2和3所确定的方程:3x1+5(1-x1)=VG,11x1+2(1-x1)=VG解得x1=3/11,VG=49/11.故局中人I的最优策略为x*=(3/11,8/11)T.由于B点是2和3的交点,局中人的最优混合策略必由2和3组成.由定理6,联立方程:3y2+11y3=49/11,5y2+2y3=49/11,y2+y3=1求得y2*=9/11,y3*=2/11.故局中人的最优策略为y*=(0,9/11,2/11)T,例3.用图解法求解对策G=S1,S2;A,其中S1=1,2,3,S2=1,2,解:设局中人的混合策略为(y1,1-y1)T中,由图2可知,三条直线1,2,3P0P1在任一点y10,1处图211的纵坐标分别是局中7S3人取(y1,1-y1)T时的6B1B226支付.根据最不利中选取最利己的原则,局中人按minmax原则,2120A1A21,局中人应选OA1y1OA2,则对策值为6.由2y1+7(1-y1)=6,11y1+2(1-y1)=6解得OA1=1/5,OA2=4/9.故局中人的最优策略为y*=(y1,1-y1)T(1/5y14/9).由于B1是1和2的交点,B2是3和2的交点,根据定理6,可由11(1/5)+2(1-1/5)0.作变换xi=xi/v,i=1,2,m,则由定理4有(1)根据定理11,于是(1)等价于线性规划(P):,同理,作变换yj=y/v,则定理4的另一不等组等价于线性规划(D):,(2),(3),注:一般先求解问题(D),再代回变换即可求出原对策解.,例5.利用线性规划求解对策G,其中A:解:为使对策值V0,由定理7,求A对应的对策G.为此,先求局中人的最优策略,即用单纯形法解线性规