运筹与优化--对策论.ppt

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,运筹与优化,第十四章 对策论,对 策 论,对策论的基本概念,对策论的基本定理,矩阵对策的解法,第一节 对策论的基本概念,对策论亦称竞赛论或博奕论,是研究具有斗,争或竞争性质的数学理论和方法.,具有竞争或对抗性质的行为称为对策行为.,对策论是研究对策行为中竞争各方是否存在,最合理的行动方案,以及如何找到最合理方案的,数学理论和方法.,具有对策行为的模型称为对策模型,或对策.,对策三要素,局中人:,在一个对策行为中,有权决定自己行动,方案的对策者.n个局中人的集合I=1,2,n.,理智的决策者:,不存在侥幸心理者.,策略集:,可供局中人i选择的一个实际可行的完,整的行动方案称为一个策略s,i,策略集S,i,.,局势:,在对策中,各局中人所选定的策略构成的,策略组s=(s,1,s,2,s,n,).全体局势S=S,1,S,2,S,n,赢得函数:,局势s的函数H,i,(s).,矩阵对策:,二人有限零和对策.,第二节 对策论的基本定理,局中人I的纯策略集 S,1,=,1,2,m,;局中人的纯策略集S,2,=,1,2,n,;对任一纯局势(,i,j,)(共mn个),局中,人I的赢得值为a,ij,赢得矩阵为A=(a,ij,),mn,.,局中人的赢得矩阵为-A.,矩阵对策,记为 G=,，S,1,，S,2,；A,或 G=S,1,，S,2,；A.,田忌,齐王,1,(上中下),2,(上下中),3,(中上下),4,(中下上),5,(下中上),6,(下上中),1,(上中下),2,(上下中),3,(中上下),4,(中下上),5,(下中上),6,(下上中),3,1,1,-1,1,1,1,3,-1,1,1,1,1,1,3,1,-1,1,1,1,1,3,1,-1,1,-1,1,1,3,1,-1,1,1,1,1,3,例,1.“,齐王赛马”中，齐王的赢得矩阵为,:,最优策略:有利于自己获得最大赢得(或最少损失)的策略.,选择最优策略的原则:牢记对方总是以最,不利于你的行动方案来对付你.,例2.设矩阵对策G=S,1,S,2,;A,其中,S,1,=,1,2,3,4,S,2,=,1,2,3,试求双方的最优策略和赢得.,理智行为:双方各按最不利于自己的情形,中选择最为利己的结果作为决策的依据.,定义1.设矩阵对策G=S,1,S,2,；A,若等式,(1),成立,记 ,则称V,G,为对策G的值,称使(1),成立的纯局势 为G在纯策略下的解,(或平衡局势、双赢局势).,定理1.矩阵对策G=S,1,S,2,；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,)处存在鞍点.其中,qa,22,p,，,p5,q,5,例4.设矩阵对策G=S,1,S,2,;A,其中,S,1,=,1,2,3,4,S,2,=,1,2,3,试求双方的最优策略和赢得.,性质,1(,无差别性,).若(,k,r,),和,(,p,q,),是对策,G,的两个解,则,a,kr,=,a,pq,.,事实上,由,有,a,pq,a,pr,a,kr,a,kq,a,pq,因此,a,kr,=,a,pq,.,性质2(可交换性).若(,k,r,)和(,p,q,),是对策G的两个解,则(,k,q,)和(,p,r,),也是对策G的解.,由 a,iq,a,pq,=a,kr,a,kq,a,pq,=a,kr,a,kj,得a,iq,a,kq,a,kj,即a,kq,是鞍点.,故(,k,q,)是解.同理，(,p,r,)是解.,性质1、2表明,矩阵对策的值是唯一的.,例5.P385例题.,定义3.设矩阵对策G=S,1,S,2,;A,A=(a,ij,),mn,.若局中,人I以概率x,i,0取纯策略,i,局中人以概率y,j,0取,纯策略,j,且 .记,则S,1,*,S,2,*,分别称为局中人I和的混合策略集.称xS,1,*,yS,2,*,为局中人I和的混合策略,(x,y)为混合局势,局中人I的赢得函数为,称G,*,=S,1,*,S,2,*,E为对策G的混合扩充.,设,则有,定义4.设G,*,=S,1,*,S,2,*,;E是矩阵对策,G=S,1,S,2,;A的混合扩充,若,记其值为V,G,则称V,G,为对策G,*,的值,使(3)成立,的混合局势(x,*,y,*,)为G在混合策略意义下的解.,定理2.矩阵对策G=S,1,S,2,;A,在混合策略,中有解的充要条件是:(x,*,y,*,)为E(x,y)的,一个鞍点,即对一切 xS,1,*,yS,2,*,有,E(x,y,*,)E(x,*,y,*,)E(x,*,y)(4),注意:G在纯策略下解存在时,定义4中的,;G在混合策略意义下的解(x,*,y,*,),存在时,V,G,=E(x,*,y,*,).,例4.解矩阵对策 G=S,1,S,2,;A,其中,局中人I取纯策略,i,时,其赢得函数为,E(i,y)=a,ij,y,j,局中人取纯策略,j,时,其赢得函数为,E(x,j)=a,ij,x,i,.,由上两式得,E(x,y)=E(i,y)x,i,(5),E(x,y)=E(x,j)y,j,.(6),定理3.设xS,1,*,yS,2,*,则(x,*,y,*,)是G的解的充要条件是:对任意i=1,2,m 和 j=1,2,n,有 E(i,y,*,)E(x,*,y,*,)E(x,*,j)(7),定理3.设xS,1,*,yS,2,*,则(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,*,)x,i,E(x,*,y,*,)x,i,=E(x,*,y,*,),E(x,*,y)=E(x,*,j)y,j,E(x,*,y,*,)y,j,=E(x,*,y,*,)可知(4)式成立，故(x,*,y,*,)是G的解,定理4.设x,*,S,1,*,y,*,S,2,*,则(x,*,y,*,)是G的解,的充要条件是:存在数v,使得x,*,y,*,分别是不等,式组,(8),(9),的解,且v=V,G,.,定理4.证明:“”因G有解,(7)式成立.取,v=E(x,*,y,*,)就有(8),(9).,“”因对任意 xS,1,*,yS,2,*,有,E(x,y,*,)=E(i,y,*,)x,i,vx,i,=v,E(x,*,y)=E(x,*,j)y,j,vy,j,=v,于是 E(x,y,*,)v E(x,*,y).,特别有 E(x,*,y,*,)v E(x,*,y,*,).,故 v=E(x,*,y,*,)=V,G,.,定理5.任意矩阵对策G=S,1,S,2,;A一定存在混,合策略意义下的解.,证明:由定理4,只要证明存在数v,*,和x,*,S,1,*,y,*,S,2,*,使得,(10),为此,考虑下列两个线性规划问题:,易知(P)和(D)互为对偶,x=(1,0,0),T,E,m,w=min,a,1j,是(P)的可行解,y=(1,0,0),T,E,n,v=maxa,i1,是(D)的可行解.,因此(P)和(D)皆存在最优解x,*,S,1,*,y,*,S,2,*,且最优值 v,*,=w,*,.故(10)式成立.,定理6.设(x,*,y,*,)是矩阵对策G的解,v=V,G,那么,(1).若x,i,*,0,则 ;,(2).若y,j,*,0,则 ;,(3).若 ,则 x,i,*,=0;,(4).若 ,则 y,j,*,=0.证明:由定义有 v=maxE(x,y,*,)，xS,1,*,故,又因,所以,当 x,i,*,0，必有 ;,当 ,必有 x,i,*,=0.,故(1),(3)得证.同理可证(2),(4).,定理7.设矩阵对策G,1,=S,1,S,2,;A,1,的解集T(G,1,),G,2,=S,1,S,2,;A,2,的解集为T(G,2,).其中A,1,=(a,ij,),A,2,=(a,ij,+p),pR.则,(1).V,G2,=V,G1,+p;(2).T(G,1,)=T(G,2,).,定理8.设矩阵对策G,1,=S,1,S,2,;A的解集为T(G,1,)，G,2,=S,1,S,2,;A（R,+,）的解集,为T(G,2,).则,(1).V,G2,=V,G1,;(2).T(G,1,)=T(G,2,).,定理9.设矩阵对策G=S,1,S,2,;A,且A=-A,T,.则,(1).V,G,=0;(2).T,1,(G)=T,2,(G).,其中T,1,(G)和T,2,(G)分别为局中人和局中人的最优策略集.,定理7定理9的证明:,利用鞍点的概念和定理3.,定义5.设矩阵对策G=S,1,S,2,;A,其中 A=(a,ij,),S,1,=,1,2,m,S,2,=,1,2,n,若对 j=1n,都有 a,kj,a,tj,则称局中人I的纯策略,k,优超于,t,;若对 i=1m,都有 a,ip,a,iq,则称局中人的纯策略,p,优超于,q,.,定理10.设矩阵对策G=S,1,S,2,;A,如果纯策略,1,被纯策略,2,m,中之一所优超,由G可得新的矩阵对策G,=S,1,S,2,;A,于是有,(1).V,G,=V,G,;(2).T,2,(G,)包含于T,2,(G)中;,(3).若(x,2,x,m,),T,T,1,(G,),则,(0,x,2,x,m,),T,T,1,(G).,推论.如果纯策略,1,被纯策略,2,m,的凸线性组合所优超,则定理10的结论仍成立.,类似地，对局中人，如果纯策略,1,被纯策略,2,n,的凸线性组合所优超,于是有 (1).V,G,=V,G,;,(2).T,1,(G,)包含于T,1,(G)中;,(3).若(y,2,y,m,),T,T,2,(G,),则,(0,y,2,y,m,),T,T,2,(G).,优超原则：可在赢得矩阵A中划去被其它行(列)或其它行(列)的凸线性组合所优超的那些行(列).,例5.设赢得矩阵A如下,求解矩阵对策G.,解:,由于矩阵A中行 r,4,r,1,r,3,r,2,故可从A中划去,第1行和第2行,得到新矩阵A,1,.,对于A,1,列c,1,c,3,c,2,c,4,(1/3)c,1,+(2/3)c,3,c,5,可从A,1,中划去第3列、第4列、第5列,得到新矩阵A,2,.,对于A,2,r,1,r,3,从A,2,中划去第3行,得到新矩阵A,3,.,对于A,3,由于,故A,3,无鞍点.应用定理4,求解不等式组:,7x,3,+4x,4,v 7y,1,+3y,2,v,3x,3,+6x,4,v (I)；4y,1,+6y,2,v (),x,3,+x,4,=1 y,1,+y,2,=1,x,3,x,4,0 y,1,y,2,0,首先求解下列等式组的非负解:,7x,3,+4x,4,=v 7y,1,+4y,2,=v,3x,3,+6x,4,=v (I,)4y,1,+6y,2,=v (,),x,3,+x,4,=1 y,1,+y,2,=1,求得 x,3,*,=1/3,x,4,*,=2/3,v=5,y,1,*,=1/2,y,2,*,=1/2.,于是,原对策G的解是,x*=(0,0,1/3,2/3,0),T,y*=(1/2,1/2,0,0,0),T,V,G,=5.,第三节 矩阵对策论的解法,一、22对策的公式法,设 ,当A无鞍点时,可以证明G有严格,非负解:x,1,*,=(a,22,-a,21,)/(a,11,+a,22,)-(a,12,+a,21,),x,2,*,=(a,11,-a,12,)/(a,11,+a,22,)-(a,12,+a,21,);,y,1,*,=(a,22,-a,12,)/(a,11,+a,22,)-(a,12,+a,21,),y,2,*,=(a,11,-a,21,)/(a,11,+a,22,)-(a,12,+a,21,);,V,G,=(a,11,a,22,-a,12,a,21,)/(a,11,+a,22,)-(a,12,+a,21,),.,例1.设矩阵对策G=S,1,S,2,;A,其中,则,对策的最优解为:,x,*,=(1/2,1/2),y,*,=(1/4,3/4),V,G,=5/2,二、图解法,例2.设矩阵对策G=S,1,S,2,;A,其中,S,1,=,1,2,S,2,=,1,2,3,.试用图解法求解.,解:设局中人I的混合策略为(x,1,1-x,1,),T,x,1,0,1.,做两条垂线P,0,(x,1,=0)和P,1,(x,1,=1),P,0,P,1,表示局中人I分别取纯策略,3,11,2,和,1,.垂线P,0,上的值表,7,1,示局中人I取,2,时,局中人,5,B,2,取各,j,时的赢得值.同理,2,S,2,3,垂线P,1,上的值表示局中人I取,0,A,1,1,时,局中人取各,j,时的赢得值.,图1,P,0,图1,P,1,3,11,7,5,1,B,2,3,2 S 2 0,A,1,如图1,当局中人I选择策略(x,1,1-x,1,),T,时,其,最少可能的收入是局中人选择,1,2,3,时,所确定的三条直线,2x,1,+7(1-x,1,)=v,3x,1,+5(1-x,1,)=v,11x,1,+2(1-x,1,)=v,在x,1,处的纵坐标中之,最小者.所以局中人I,按max min原则,应选择,x,1,=OA,而AB即为对策值.,联立过点B的两条线段,2,和,3,所确定的方程:3x,1,+5(1-x,1,)=V,G,11x,1,+2(1-x,1,)=V,G,解得 x,1,=3/11,V,G,=49/11.,故局中人I的最优策略为x,*,=(3/11,8/11),T,.,由于B点是,2,和,3,的交点,局中人的最优,混合策略必由,2,和,3,组成.由定理6,联立方程:,3y,2,+11y,3,=49/11,5y,2,+2y,3,=49/11,y,2,+y,3,=1,求得 y,2,*,=9/11,y,3,*,=2/11.,故局中人的最优策略为y,*,=(0,9/11,2/11),T,例3.用图解法求解对策G=S,1,S,2,;A,其中,S,1,=,1,2,3,S,2,=,1,2,解:设局中人的混合策略为(y,1,1-y,1,),T,中,由图2可知,三条直线,1,2,3,P,0,P,1,在任一点y,1,0,1处,图2,11,的纵坐标分别是局中,7,S,3,人取(y,1,1-y,1,),T,时的,6 B,1,B,2,2,6,支付.根据最不利中选,取最利己的原则,局中,人按 min max原则,2,1,2,0,A,1,A,2,1,局中人应选 OA,1,y,1,OA,2,则对策值为6.由,2y,1,+7(1-y,1,)=6,11y,1,+2(1-y,1,)=6,解得 OA,1,=1/5,OA,2,=4/9.,故局中人的最优策略为,y,*,=(y,1,1-y,1,),T,(1/5 y,1,4/9).,由于B,1,是,1,和,2,的交点,B,2,是,3,和,2,的交,点,根据定理6,可由,11(1/5)+2(1-1/5)6,得 x,3,=0;,2(4/9)+7(5/9)v),而y,1,*,y,2,*,y,4,*,由方程:,4y,1,+(8/3)y,2,+2y,4,=13/4,y,1,+5y,2,+7y,4,=13/4,y,1,+y,2,+y,4,=1 7,4,易知具有无穷多解 5,3,故局中人有无穷 4,多个最优混合策略.,13/4,2,例4说明,优超法,1,8/3,可能划去原矩阵 1,对策的一些解.S,0,3/4,1,P,0,图3 P,1,线性方程组方法:,设x,i,*,、y,j,*,均不为零,先求解等式组,的非负解.,若(),()的解有负分量，就将(),()的,某些等式改为不等式.,三、线性方程组方法,定理11.设矩阵对策G=S,1,S,2,;A,1,的值为V,G,则,证明:因V,G,是对策的值,故,一方面,得,求解矩阵对策的线性规划方法,:,另一方面,有,故得,同理有,根据定理7,可设v0.作变换 x,i,=x,i,/v,i=1,2,m,则由定理4有,(1),根据定理11,于是(1)等价于线性规划(P):,同理,作变换 y,j,=y/v,则定理4的另一不等组等价于线性规划(D):,(2),(3),注:一般先求解问题(D),再代回变换即可求出原对策解.,例5.利用线性规划求解对策G,其中A:,解:为使对策值V0,由定理7,求A,对应的对策G.为此,先求局中人的最优策略,即用单纯形法解线性,规划(D):,max w=y,1,+y,2,+y,3,5y,1,+4,y,3,1,y,1,+6y,2,+,4,y,3,1,4,y,1,+4y,2,+,8y,3,1,y,1,0 y,2,0 y,3,0,c,j,1 1 1 0 0 0,C,B,y,B,b,y,1,y,2,y,3,y,4,y,5,y,6,j,0,0,0,y,4,y,5,y,6,1,1,1,5 0 4 1 0 0,1 6 4 0 1 0,4 4 8 0 0 1,1/5,1,1/4,j,0,1 1 1 0 0 0,1,0,0,y,1,y,5,y,6,1/5,4/5,1/5,1 0 4/5 1/5 0 0,0 6 16/5 -1/5 1 0,0 4 24/5 -4/5 0 1,2/15,1/20,j,-1/5,0 1 1/5 -1/5 0 0,1,0,1,y,1,y,5,y,2,1/5,1/2,1/20,1 0 4/5 1/5 0 0,0 0 -4 1 1 -3/2,0 1 6/5 -1/5 0 1/4,j,-1/4,0 0 -1 0 0 -1/4,由最优表知,最优解为:y=(1/5,1/20,0),T,max w=1/4;x=(0,0,1/4),T,min z=1/4.,G,的对策值 V,G,=4.于是,y,*,=V,G,y=(4/5,1/5,0),T,x,*,=V,G,x=(0,0,1),T,.,G的对策值 V,G,=V,G,-2=2.,注:最优表中 y,4,Y,N,4,=0.只要取 y,4,进基,y,5,离基,再迭代一次,得,y=(1/10,3/20,0),T,max w=1/4=1/V,G,.,则局中人的另一最优策略y,*,=(2/5,2/5,0),T,.,