运筹与优化-对策论.ppt

《运筹与优化-对策论.ppt》由会员分享，可在线阅读，更多相关《运筹与优化-对策论.ppt（44页珍藏版）》请在三一办公上搜索。

1、运筹与优化,第十四章 对策论,对 策 论,对策论的基本概念对策论的基本定理矩阵对策的解法,第一节 对策论的基本概念,对策论亦称竞赛论或博奕论,是研究具有斗争或竞争性质的数学理论和方法.具有竞争或对抗性质的行为称为对策行为.对策论是研究对策行为中竞争各方是否存在最合理的行动方案,以及如何找到最合理方案的数学理论和方法.具有对策行为的模型称为对策模型,或对策.,对策三要素,局中人:在一个对策行为中,有权决定自己行动方案的对策者.n个局中人的集合I=1,2,n.理智的决策者:不存在侥幸心理者.策略集:可供局中人i选择的一个实际可行的完整的行动方案称为一个策略si,策略集Si.局势:在对策中,各局中人

2、所选定的策略构成的策略组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=

3、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*

4、,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.事实上,由,有 apq apr akr akq apq因此 akr=apq.,性质2(可交换性).若(k,r)和(p,q)是对策G的两个解,则(k,q)和(p,r)也是对策G的解

5、.由 aiq apq=akr akq apq=akr akj 得aiqakq akj,即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的混合扩充,若,记

6、其值为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

7、)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

8、(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=v E(x*,y)=E(x*,j)yjvyj=v于是 E(x,y*)v E(x*,y).特别有 E(x*,y*)v E(x*,y*).故 v=

9、E(x*,y*)=VG.,定理5.任意矩阵对策G=S1,S2;A一定存在混合策略意义下的解.证明:由定理4,只要证明存在数v*和x*S1*,y*S2*,使得(10)为此,考虑下列两个线性规划问题:,易知(P)和(D)互为对偶,x=(1,0,0)TEm,w=min a1j 是(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

10、*=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.则

11、(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

12、(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

13、)c3 c5,可从A1中划去第3列、第4列、第5列,得到新矩阵A2.,对于A2,r1r3,从A2中划去第3行,得到新矩阵A3.对于A3,由于,故A3无鞍点.应用定理4,求解不等式组:7x3+4x4v 7y1+3y2v 3x3+6x4v(I)；4y1+6y2v()x3+x4=1 y1+y2=1 x3,x40 y1,y20,首先求解下列等式组的非负解:7x3+4x4=v 7y1+4y2=v 3x3+6x4=v(I)4y1+6y2=v()x3+x4=1 y1+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

14、)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,

15、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),P0 P1 表示局中人I分别取纯策略 3 112和1.垂线P0上的值表 7 1 示局中人I取2时,局中人 5 B 2取各j时的赢得值.同理,2 S 23垂线P1上的值表示局中人I取 0 A 1 1时,局中人取各j时的赢得值.图1,P0 图1 P1 3 11 7,5 1 B 2 3 2 S 2 0 A 1,如图1,当局中人I选择策略(x1,1-x1)T时,其最少可能的

16、收入是局中人选择1,2,3时所确定的三条直线,2x1+7(1-x1)=v 3x1+5(1-x1)=v 11x1+2(1-x1)=v在x1处的纵坐标中之最小者.所以局中人I 按max min原则,应选择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/1

17、1,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,3 P0 P1 在任一点y10,1处 图2 11 的纵坐标分别是局中 7 S 3 人取(y1,1-y1)T时的 6 B1 B2 2 6 支付.根据最不利中选 取最利己的原则,局中 人按 min max原则,2 1 2 0 A1 A2 1,局中人应选 OA1y1 OA2,则对策值为6.由 2y1+7(1-y1)=6,11y1+2(1-y1)=6解得 OA1=1/5,

18、OA2=4/9.故局中人的最优策略为 y*=(y1,1-y1)T(1/5 y1 4/9).由于B1是1和2的交点,B2是3和2的交点,根据定理6,可由 11(1/5)+2(1-1/5)6,得 x3=0;2(4/9)+7(5/9)6,得x1=0.于是得x1*=x3*=0,x2*=1.故局中人I取纯策略2.,例4.求赢得矩阵A的矩阵对策G.解法1.优超法:因列c2c3,故可划去第3列;又因(2/3)c4+(1/3)c1=c2,故可划去第2列.于是,求赢得矩阵A的矩阵对策G.其中 从而求得原对策G的一个解为 x*=(3/4,1/4)T,y*=(5/8,0,0,3/8)T,VG=13/4.解法2.图解

19、法:由图可见,局中人I的最优策略为x*=(3/4,1/4)T.若局中人的最优策略为y*=(y1*,y2*,y3*,y4*)T,有y3*=0(4x1+5(1-x1)v),而y1*,y2*,y4*由方程:4y1+(8/3)y2+2y4=13/4 y1+5y2+7y4=13/4 y1+y2+y4=1 7 4 易知具有无穷多解 5 3 故局中人有无穷 4 多个最优混合策略.13/4 2 例4说明,优超法 1 8/3 可能划去原矩阵 1 对策的一些解.S 0 3/4 1,P0 图3 P1,线性方程组方法:设xi*、yj*均不为零,先求解等式组 的非负解.若(),()的解有负分量，就将(),()的某些等式

20、改为不等式.,三、线性方程组方法,定理11.设矩阵对策G=S1,S2;A1的值为VG,则 证明:因VG是对策的值,故 一方面,得,求解矩阵对策的线性规划方法:,另一方面,有 故得 同理有,根据定理7,可设v0.作变换 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.为此,先求局中人的最优策略,即用单纯形法解线性 规划(D):max w=y1+y2+y3 5y1+4y31 y1+6y2+4y3 1 4 y1+4y2+8y3 1 y10 y20 y30,由最优表知,最优解为:y=(1/5,1/20,0)T,max w=1/4;x=(0,0,1/4)T,min z=1/4.G的对策值 VG=4.于是 y*=VGy=(4/5,1/5,0)T,x*=VGx=(0,0,1)T.G的对策值 VG=VG-2=2.注:最优表中 y4YN,4=0.只要取 y4 进基,y5离基,再迭代一次,得 y=(1/10,3/20,0)T,max w=1/4=1/VG.则局中人的另一最优策略y*=(2/5,2/5,0)T.,