运筹与优化-对策论.ppt

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

1、运筹与优化运筹与优化 第十四章 对策论 对 策 论n对策论的基本概念对策论的基本概念n对策论的基本定理对策论的基本定理n矩阵对策的解法矩阵对策的解法第一节第一节 对策论的基本概念对策论的基本概念 对策论亦称竞赛论或博奕论对策论亦称竞赛论或博奕论,是研究具有斗是研究具有斗争或竞争性质的数学理论和方法争或竞争性质的数学理论和方法.具有竞争或对抗性质的行为称为对策行为具有竞争或对抗性质的行为称为对策行为.对策论是研究对策行为中对策论是研究对策行为中竞竞争各方是否存在争各方是否存在最合理的行动方案最合理的行动方案,以及如何找到最合理方案的以及如何找到最合理方案的数学理论和方法数学理论和方法.具有对策行

2、为的模型称为对策模型具有对策行为的模型称为对策模型,或对策或对策.对策三要素对策三要素n局中人局中人:在一个对策行为中在一个对策行为中,有权决定自己行动有权决定自己行动方案的对策者方案的对策者.n n个局中人的集个局中人的集合合I=1,2,I=1,2,n.,n.理智的决策者理智的决策者:不存在侥幸心理者不存在侥幸心理者.n策略集策略集:可供局中人可供局中人i i选择的一个实际可行的完选择的一个实际可行的完整的行动方案称为一个策略整的行动方案称为一个策略s si i,策略集策略集S Si i.局势局势:在对策中在对策中,各局中人所选定的策略构成的各局中人所选定的策略构成的策略组策略组s=(ss=

3、(s1 1,s,s2 2,s sn n).).全体局势全体局势S=SS=S1 1S S2 2S Sn nn赢得函数赢得函数:局势局势s s的函数的函数H Hi i(s).(s).n矩阵对策矩阵对策:二人有限零和对策二人有限零和对策.第二节第二节 对策论的基本定理对策论的基本定理n局中人局中人I I的纯策略集的纯策略集 S S1 1=1 1,2 2,m m;局中人局中人的纯策略集的纯策略集S S2 2=1 1,2 2,n n;对任一纯局对任一纯局势势(i i,j j)()(共共m mn n个个),),局中局中 人人I I的赢得值为的赢得值为a aij ij ,赢得矩阵为赢得矩阵为A=(A=(a

4、aij ij)m mn n.局中人局中人的赢得矩阵为的赢得矩阵为-A.A.n矩阵对策矩阵对策记为记为 G=,G=,，S S1 1，S S2 2；AA 或或 G=SG=S1 1，S S2 2；A.A.田忌田忌齐王齐王 1 1(上中下上中下)2 2(上下中上下中)3 3(中上下中上下)4 4(中下上中下上)5 5(下中上下中上)6 6(下上中下上中)1 1(上中下上中下)2 2(上下中上下中)3 3(中上下中上下)4 4(中下上中下上)5 5(下中上下中上)6 6(下上中下上中)311-11113-11111131-1111131-11-11131-111113n 例例1.“齐王赛马齐王赛马”中，

5、齐王的赢得矩阵为中，齐王的赢得矩阵为:n最优策略最优策略:有利于自己获得最大赢得有利于自己获得最大赢得(或最少损或最少损失失)的策略的策略.n选择最优策略的原则选择最优策略的原则:牢记对方总是以最牢记对方总是以最 不利于你的行动方案来对付你不利于你的行动方案来对付你.n例例2.2.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2;A,;A,其中其中 S S1 1=1 1,2 2,3 3,4 4,S S2 2=1 1,2 2,3 3,试求双方的最优策略和赢得试求双方的最优策略和赢得.n理智行为理智行为:双方各按最不利于自己的情形双方各按最不利于自己的情形 中选择最为利己的结果作为决策的依据中

6、选择最为利己的结果作为决策的依据.n定义定义1.1.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2；A A ,若等式若等式 (1)(1)成立成立,记记 ,则称则称V VG G为对策为对策G G的值的值,称使称使(1(1)成立的纯局势成立的纯局势 为为G G在纯策略下的解在纯策略下的解(或平衡局势、双赢局势或平衡局势、双赢局势).).n定理定理1.1.矩阵对策矩阵对策G=SG=S1 1,S,S2 2；A A 在纯策略在纯策略中有解的充要条件是中有解的充要条件是:存在纯局势存在纯局势 使得使得 (2)(2)(i=1,2,i=1,2,m,j=1,2,m,j=1,2,n).,n).既是其所在既是

7、其所在行的最小元素行的最小元素,又是其所在列的最大元素又是其所在列的最大元素.n定义定义2 2.设实函数设实函数f(x,y)f(x,y)定义在定义在xA,yBxA,yB上上,若存在若存在x x*A,y*B,A,y*B,使得对使得对xA,yB,xA,yB,有有 f(x,y*)f(xf(x,y*)f(x*,y*)f(x,y*)f(x*,y)(3),y)(3)则称则称(x x*,y*),y*)为为f(x,y)f(x,y)的一个鞍点的一个鞍点.n矩阵对策矩阵对策G G在纯策略意义下有解在纯策略意义下有解,且且 的充要条件的充要条件是是:是矩阵是矩阵A A的一个鞍点的一个鞍点.n例例3.3.确定确定p

8、p和和q q的取值范围的取值范围,使矩阵使矩阵A A在在(2 2,2 2)处存在鞍点处存在鞍点.其中其中qa22p，p5,q5n例例4.4.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2;A,;A,其中其中 S S1 1=1 1,2 2,3 3,4 4,S S2 2=1 1,2 2,3 3,试求双方的最优策略和赢得试求双方的最优策略和赢得.n性质性质1(1(无差别性无差别性).).若若(k k,r r)和和 (p p,q q)是对策是对策G G的两个解的两个解,则则 a akrkr =a apqpq.事实上事实上,由由 ,有有 a apqpq a aprpr a akrkr a akqk

9、q a apqpq因此因此 a akrkr =a apqpq.n性质性质2(2(可交换性可交换性).).若若(k k,r r)和和 (p p,q q)是对策是对策G G的两个解的两个解,则则(k k,q q)和和 (p p,r r)也是对策也是对策G G的解的解.由由 a aiq iq a apqpq=a akrkr a akqkq a apqpq =a akrkr a akj kj 得得a aiq iqa akqkq a akj kj,即即a akqkq是鞍点是鞍点.故故(k k,q q)是解是解.同理，同理，(p p,r r)是解是解.n性质性质1 1、2 2表明表明,矩阵对策的值是唯一的

10、矩阵对策的值是唯一的.n例例5.5.P385P385例题例题.n定义定义3.3.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2;A,A=(;A,A=(a aij ij)m mn n.若局中若局中人人I I以概率以概率x xi i00取纯策略取纯策略 i i,局中人局中人以概率以概率y yj j00取取纯策略纯策略 j j,且且 .记记 则则S S1 1*,S,S2 2*分别称为局中人分别称为局中人I I和和的混合策略集的混合策略集.称称xSxS1 1*,ySyS2 2*为局中人为局中人I I和和的混合策略的混合策略,(,(x,y)x,y)为混合局势为混合局势,局中人局中人I I的赢得函数

11、为的赢得函数为称称G G*=S=S1 1*,S,S2 2*,E,E为对策为对策G G的混合扩充的混合扩充.n设设则有则有n定义定义4.4.设设G G*=S=S1 1*,S,S2 2*;E;E是矩阵对策是矩阵对策G=SG=S1 1,S,S2 2;A;A的混合扩充的混合扩充,若若 记其值为记其值为V VG G,则称则称V VG G为对策为对策G G*的值的值,使使(3)(3)成立成立的混合局势的混合局势(x x*,y,y*)为为G G在混合策略意义下的解在混合策略意义下的解.n定理定理2.2.矩阵对策矩阵对策G=SG=S1 1,S,S2 2;A;A 在混合策略在混合策略中有解的充要条件是中有解的充

12、要条件是:(:(x x*,y,y*)为为E(x,y)E(x,y)的的一个鞍一个鞍点点,即对一切即对一切 xSxS1 1*,yS,yS2 2*,有有 E(x,yE(x,y*)E(x)E(x*,y,y*)E(x)E(x*,y)(4),y)(4)n注意注意:G G在纯策略下解存在时在纯策略下解存在时,定义定义4 4中的中的 ;G G在混合策略意义下的解在混合策略意义下的解(x x*,y,y*)存在时存在时,V VG G=E(x=E(x*,y,y*).).n例例4.4.解矩阵对策解矩阵对策 G=SG=S1 1,S,S2 2;A;A ,其其中中n局中人局中人I I取纯策略取纯策略 i i时时,其赢得函数

13、为其赢得函数为 E(i,y)=E(i,y)=a aij ijy yj j ,局中人局中人取纯策略取纯策略 j j时时,其赢得函数为其赢得函数为 E(x,j)=E(x,j)=a aij ijx xi i .由上两式得由上两式得 E(x,y)=E(i,y)E(x,y)=E(i,y)x xi i (5)(5)E(x,y)=E(x,j)E(x,y)=E(x,j)y yj j .(6).(6)n定理定理3.3.设设xSxS1 1*,yS,yS2 2*,则则(x x*,y,y*)是是G G的解的充要条的解的充要条件是件是:对任意对任意i=1,2,i=1,2,m,m 和和 j=1,2,j=1,2,n,n,有

14、有 E(i,yE(i,y*)E)E(x(x*,y,y*)E(x)E(x*,j)(7),j)(7)n定理定理3.3.设设xSxS1 1*,yS,yS2 2*,则则(x x*,y,y*)是是G G的解的充要条的解的充要条件是件是:对任意对任意i=1,2,i=1,2,m,m 和和 j=1,2,j=1,2,n,n,有有 E(i,yE(i,y*)E)E(x(x*,y,y*)E(x)E(x*,j)(7),j)(7)证明证明:设设(x x*,y,y*)是是G G的解的解,则由定理则由定理2,2,有有 E(x,yE(x,y*)E(x)E(x*,y,y*)E(x)E(x*,y),y)(4)(4)由于纯策略是混合

15、策略的特例由于纯策略是混合策略的特例,故故(7)(7)式成立式成立.反之反之,设设(7)(7)式成立式成立,由由(5)(5)、(6)(6)有有 E(x,yE(x,y*)=E(i,y)=E(i,y*)x xi iE(xE(x*,y,y*)x)xi i=E(x=E(x*,y,y*)E(x E(x*,y)=E(x,y)=E(x*,j),j)y yj jE(xE(x*,y,y*)y yj j=E(x=E(x*,y,y*)可知可知(4)(4)式式成立，故成立，故(x x*,y,y*)是是G G的解的解n定理定理4.4.设设x x*SS1 1*,y,y*SS2 2*,则则(x x*,y,y*)是是G G的

16、解的解的充要条件是的充要条件是:存在数存在数v,v,使得使得x x*,y,y*分别是不等分别是不等式组式组 (8)(8)(9)(9)的解的解,且且v=Vv=VG G.n定理定理4.4.证明证明:“”因因G G有解有解,(7),(7)式成立式成立.取取v=E(xv=E(x*,y,y*)就有就有(8),(9).(8),(9).“”因对任意因对任意 xSxS1 1*,yS,yS2 2*,有有 E(x,yE(x,y*)=E(i,y)=E(i,y*)x xi ivxvxi i=v=v E(x E(x*,y)=E(x,y)=E(x*,j),j)y yj jvyvyj j=v=v于是于是 E(x,yE(x,

17、y*)v E(x)v E(x*,y).,y).特别有特别有 E(xE(x*,y,y*)v E(x)v E(x*,y,y*).).故故 v=E(xv=E(x*,y,y*)=V)=VG G.n定理定理5.5.任意矩阵对策任意矩阵对策G=SG=S1 1,S,S2 2;A;A一定存在混一定存在混合策略意义下的解合策略意义下的解.证明证明:由定理由定理4,4,只要证明存在数只要证明存在数v v*和和x x*SS1 1*,y y*SS2 2*,使得使得 (10)(10)为此为此,考虑下列两个线性规划问题考虑下列两个线性规划问题:易知易知(P)P)和和(D)D)互为对偶互为对偶,x=(1,0,x=(1,0,

18、0),0)T TEEm m,w=minw=min a a1j 1j 是是(P)P)的可行解的可行解,y=(1,0,y=(1,0,0),0)T TEEn n,v=maxav=maxai1 i1 是是(D)D)的可行解的可行解.因此因此(P)P)和和(D)D)皆存在最优解皆存在最优解x x*SS1 1*,y,y*SS2 2*,且最优值且最优值 v v*=w=w*.故故(10)(10)式成立式成立.n定理定理6.6.设设(x x*,y,y*)是矩阵对策是矩阵对策G G的解的解,v=Vv=VG G,那么那么 (1).(1).若若x xi i*0,0,则则 ;(2).(2).若若y yj j*0,0,则

19、则 ;(3).(3).若若 ,则则 x xi i*=0;=0;(4).(4).若若 ,则则 y yj j*=0.=0.证明证明:由定义有由定义有 v=v=maxEmaxE(x,y(x,y*)，xSxS1 1*,故故 又因又因 所以所以,当当 x xi i*00，必有必有 ;当当 ,必有必有 x xi i*=0.=0.故故(1),(3)(1),(3)得证得证.同理同理可证可证(2),(4).(2),(4).n定理定理7.7.设矩阵对策设矩阵对策G G1 1=S=S1 1,S,S2 2;A;A1 1 的解集的解集T(GT(G1 1),),G G2 2=S=S1 1,S,S2 2;A;A2 2 的解

20、集为的解集为T(GT(G2 2).).其中其中A A1 1=(=(a aij ij),),A A2 2=(=(a aij ij+p),pR.+p),pR.则则 (1).(1).V VG2G2=V=VG1G1+p;(2).T(G+p;(2).T(G1 1)=T(G)=T(G2 2).).n定理定理8.8.设矩阵对策设矩阵对策G G1 1=S=S1 1,S,S2 2;A;A的解集为的解集为T(GT(G1 1)，G G2 2=S=S1 1,S,S2 2;A;A（RR+）的解集的解集 为为T(GT(G2 2).).则则 (1).(1).V VG2G2=V=VG1G1;(2).T(G;(2).T(G1

21、1)=T(G)=T(G2 2).).n定理定理9.9.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2;A,;A,且且A=-AA=-AT T.则则 (1).(1).V VG G=0;(2).T=0;(2).T1 1(G)=T(G)=T2 2(G).(G).其中其中T T1 1(G)(G)和和T T2 2(G)(G)分别为局中人分别为局中人和局中人和局中人的最优策略集的最优策略集.n定理定理7 7定理定理9 9的证明的证明:利用鞍点的概念和定理利用鞍点的概念和定理3.3.n定义定义5.5.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2;A,;A,其中其中 A=(A=(a aij ij)

22、,),S S1 1=1 1,2 2,m m,S,S2 2=1 1,2 2,n n 若对若对 j=1j=1n,n,都有都有 a akj kja atj tj,则称局中人则称局中人I I的纯策略的纯策略 k k优超于优超于 t t;若对若对 i=1i=1m,m,都有都有 a aip ipa aiq iq ,则称局中人则称局中人的纯策略的纯策略 p p优超于优超于 q q.n定理定理10.10.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2;A,;A,如果纯策略如果纯策略 1 1被纯被纯策略策略 2 2,m m中之一所优超中之一所优超,由由G G可得新的矩阵对可得新的矩阵对策策G G=S=S1

23、 1,S,S2 2;A;A,于是于是有有 (1).(1).V VG G=V=VG G;(2).T;(2).T2 2(G(G)包含包含于于T T2 2(G)(G)中中;(3).(3).若若(x x2 2,x,xm m)T TTT1 1(G(G),),则则 (0,(0,x x2 2,x,xm m)T TTT1 1(G).(G).n推论推论.如果纯策略如果纯策略 1 1被纯策略被纯策略 2 2,m m的凸线的凸线性组合所优超性组合所优超,则定理则定理1010的结论仍成立的结论仍成立.n类似地，对局中人类似地，对局中人，如果纯策略，如果纯策略 1 1被纯策被纯策略略 2 2,n n的凸线性组合所优超的

24、凸线性组合所优超,于是有于是有 (1).(1).V VG G=V=VG G;(2).T (2).T1 1(G(G)包含于包含于T T1 1(G)(G)中中;(3).(3).若若(y y2 2,y,ym m)T TTT2 2(G(G),),则则 (0,(0,y y2 2,y,ym m)T TTT2 2(G).(G).n优超原则：可在赢得矩阵优超原则：可在赢得矩阵A A中划去被其它行中划去被其它行(列列)或其它行或其它行(列列)的凸线性组合所优超的那的凸线性组合所优超的那些行些行(列列).).n例例5.5.设赢得矩阵设赢得矩阵A A如下如下,求解矩阵对策求解矩阵对策G.G.n解解:由于矩阵由于矩阵

25、A A中行中行 r r4 4rr1 1,r,r3 3rr2 2 ,故可从故可从A A中划去中划去第第1 1行和第行和第2 2行行,得到新矩阵得到新矩阵A A1 1.对于对于A A1 1,列列c c1 1cc3 3,c,c2 2cc4 4,(1/3)c,(1/3)c1 1+(2/3)c+(2/3)c3 3 c c5 5,可从可从A A1 1中划去第中划去第3 3列、第列、第4 4列、第列、第5 5列列,得到新矩阵得到新矩阵A A2 2.对于对于A A2 2,r,r1 1rr3 3,从从A A2 2中划去第中划去第3 3行行,得到新矩阵得到新矩阵A A3 3.对于对于A A3 3,由于由于故故A

26、A3 3无鞍点无鞍点 .应用定理应用定理4,4,求解不等式组求解不等式组:7 7x x3 3+4x+4x4 4v 7yv 7y1 1+3y+3y2 2vv 3x 3x3 3+6x+6x4 4v (I)v (I)；4y 4y1 1+6y+6y2 2v ()v ()x x3 3+x+x4 4=1 y=1 y1 1+y+y2 2=1=1 x x3 3,x,x4 40 0 y y1 1,y,y2 200 首先求解下列等式组的非负解首先求解下列等式组的非负解:7 7x x3 3+4x+4x4 4=v 7y=v 7y1 1+4y+4y2 2=v=v 3x 3x3 3+6x+6x4 4=v (I=v (I)

27、4y)4y1 1+6y+6y2 2=v (=v ()x x3 3+x+x4 4=1 y=1 y1 1+y+y2 2=1=1求得求得 x x3 3*=1/3,x=1/3,x4 4*=2/3,v=5,y=2/3,v=5,y1 1*=1/2,y=1/2,y2 2*=1/2.=1/2.于是于是,原对策原对策G G的解是的解是 x*=(0,0,1/3,2/3,0)x*=(0,0,1/3,2/3,0)T T,y*=(1/2,1/2,0,0,0)y*=(1/2,1/2,0,0,0)T T,V,VG G=5.=5.第三节第三节 矩阵对策论的解法矩阵对策论的解法 一、一、22对策的公式法对策的公式法n设设 ,当

28、当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).n例例1.1.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2;A,;A,其中其中 则则对策的最优解为对策的最优解为:x x*=(1/2,1/2),y=(1/2,1/2),y*=(

29、1/4,3/4),V=(1/4,3/4),VG G=5/2=5/2 二、图解法二、图解法n例例2.2.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2;A,;A,其中其中 S S1 1=1 1,2 2,S,S2 2=1 1,2 2,3 3.试用图解法求解试用图解法求解.n解解:设局中人设局中人I I的混合策略为的混合策略为(x x1 1,1-x,1-x1 1)T T,x,x1 10,1.0,1.做两条垂线做两条垂线P P0 0(x(x1 1=0)=0)和和P P1 1(x(x1 1=1),=1),P P0 0 P1 表示局中人表示局中人I I分别取纯策略分别取纯策略 3 3 11 2 2和

30、和 1 1.垂线垂线P P0 0上的值表上的值表 7 7 1 1 示局中人示局中人I I取取 2 2时时,局中人局中人 5 5 B 2 2取各取各 j j时的赢得值时的赢得值.同理同理,2 2 S 2 23 3垂线垂线P P1 1上的值表示局中人上的值表示局中人I I取取 0 A 1 1 1时时,局中人局中人取各取各 j j时的赢得值时的赢得值.图图1 P P0 0 图图1 P1 3 3 11 7 5 5 1 B 2 2 3 3 2 S 2 0 A 1 如图如图1,1,当局中人当局中人I I选择策略选择策略(x x1 1,1-x,1-x1 1)T T时时,其其最少可能的收入是局中人最少可能的收

31、入是局中人选择选择 1 1,2 2,3 3时时所确定的三条直线所确定的三条直线 2 2x x1 1+7(1-x+7(1-x1 1)=v)=v 3x 3x1 1+5(1-x+5(1-x1 1)=v)=v 11x 11x1 1+2(1-x+2(1-x1 1)=v)=v在在x x1 1处的纵坐标中之处的纵坐标中之最小者最小者.所以局中人所以局中人I I 按按max minmax min原则原则,应选择应选择x x1 1=OA,=OA,而而ABAB即为对策值即为对策值.联立过点联立过点B B的两条线段的两条线段 2 2和和 3 3所确定的方程所确定的方程:3 3x x1 1+5(1-x+5(1-x1

32、1)=V)=VG G,11x,11x1 1+2(1-x+2(1-x1 1)=V)=VG G解得解得 x x1 1=3/11,V=3/11,VG G=49/11.=49/11.故局中人故局中人I I的最优策略为的最优策略为x x*=(3/11,8/11)=(3/11,8/11)T T.由于由于B B点是点是 2 2和和 3 3的交点的交点,局中人局中人的最优的最优混合策略必由混合策略必由 2 2和和 3 3组成组成.由定理由定理6,6,联立方程联立方程:3 3y y2 2+11y+11y3 3=49/11,5y=49/11,5y2 2+2y+2y3 3=49/11,y=49/11,y2 2+y+

33、y3 3=1=1 求得求得 y y2 2*=9/11,y=9/11,y3 3*=2/11.=2/11.故局中人故局中人的最优策略为的最优策略为y y*=(0,9/11,2/11)=(0,9/11,2/11)T Tn例例3.3.用图解法求解对策用图解法求解对策G=SG=S1 1,S,S2 2;A,;A,其中其中 S S1 1=1 1,2 2,3 3,S,S2 2=1 1,2 2,n解解:设局中人设局中人的混合策略为的混合策略为(y y1 1,1-y,1-y1 1)T T中中,由图由图2 2可知可知,三三条直线条直线 1 1,2 2,3 3 P0 P1 在任一点在任一点y y1 10,10,1处处

34、 图图2 11 的纵坐标分别是局中的纵坐标分别是局中 7 7 S S 3 3 人人取取(y y1 1,1-y,1-y1 1)T T时的时的 6 6 B B1 1 B B2 2 2 2 6 6 支付支付.根据最不利中选根据最不利中选 取最利己的原则取最利己的原则,局中局中 人人按按 min maxmin max原则原则,2 1 2 0 A1 A2 1局中人局中人应选应选 OAOA1 1yy1 1 OA OA2 2,则对策值为则对策值为6.6.由由 2 2y y1 1+7(1-y+7(1-y1 1)=6,11y)=6,11y1 1+2(1-y+2(1-y1 1)=6)=6解得解得 OAOA1 1=

35、1/5,OA=1/5,OA2 2=4/9.=4/9.故局中人故局中人的最优策略为的最优策略为 y y*=(y=(y1 1,1-y,1-y1 1)T T (1/5 y (1/5 y1 1 4/9).4/9).由于由于B B1 1是是 1 1和和 2 2的交点的交点,B B2 2是是 3 3和和 2 2的交的交点点,根据定理根据定理6,6,可由可由 11(1/5)+2(1-1/5)6,11(1/5)+2(1-1/5)6,得得 x x3 3=0;=0;2(4/9)+7(5/9)6,2(4/9)+7(5/9)v),)v),而而y y1 1*,y,y2 2*,y,y4 4*由方程由方程:4 4y y1

36、1+(8/3)y+(8/3)y2 2+2y+2y4 4=13/4=13/4 y y1 1+5y+5y2 2+7y+7y4 4=13/4=13/4 y y1 1+y+y2 2+y+y4 4=1 7 =1 7 4 4 易知具有无穷多解易知具有无穷多解 5 5 3 3 故局中人故局中人有无穷有无穷 4 4 多个最优混合策略多个最优混合策略.13/4 13/4 2 2 例例4 4说明说明,优超法优超法 1 1 8/38/3 可能划去原矩阵可能划去原矩阵 1 1 对策的一些解对策的一些解.S S 0 0 3/43/4 1 1 P0 图图3 P1 n线性方程组方法线性方程组方法:设设x xi i*、y y

37、j j*均不为均不为零零,先求解等式组先求解等式组 的非负解的非负解.若若(),()(),()的解有负分量，就将的解有负分量，就将(),()(),()的的某些等式改为不等式某些等式改为不等式.三、线性方程组方法三、线性方程组方法 定理定理11.11.设矩阵对策设矩阵对策G=SG=S1 1,S,S2 2;A;A1 1 的值为的值为V VG G,则则 证明证明:因因V VG G是对策的值是对策的值,故故 一方面一方面,得得 n 求解矩阵对策的线性规划方法求解矩阵对策的线性规划方法:另一方面另一方面,有有 故得故得 同理有同理有 根据定理根据定理7,7,可设可设v0.v0.作变换作变换 x xi i

38、=x=xi i/v,/v,i=1,2,i=1,2,m,m,则由定理则由定理4 4有有 (1)(1)根据定理根据定理11,11,于是于是(1)等价于线性规划等价于线性规划(P):同理同理,作变换作变换 yj=y/v,则定理则定理4的另一不的另一不等组等价于线性规划等组等价于线性规划(D):(2)(3)注注:一般先求解问题一般先求解问题(D),再代回变换即可求出原对策再代回变换即可求出原对策解解.n例例5.5.利用线性规划求解对策利用线性规划求解对策G,G,其中其中A:A:n解解:为使对策值为使对策值V0,V0,由定理由定理7,7,求求A A对应的对策对应的对策G G.为此为此,先求局中人先求局中

39、人的最优策略的最优策略,即用单纯形法解线性即用单纯形法解线性 规划规划(D):D):max w=y1+y2+y3 5y1 +4+4y31 y1+6y2+4 4y3 1 4 y1+4y2+8y3 1 y10 y20 y30cj1 1 1 0 0 0CByBby1 y2 y3 y4 y5 y6j 0 0 0y4y5y61115 0 4 1 0 0 1 6 4 0 1 0 4 4 8 0 0 11/511/4j0 1 1 1 0 0 0 1 0 0y1y5y61/54/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 12/151/20j

40、-1/5 0 1 1/5 -1/5 0 0101y1y5y21/51/21/20 1 0 4/5 1/5 0 0 0 0 -4 1 1 -3/2 0 1 6/5 -1/5 0 1/4j-1/4 0 0 -1 0 0 -1/4n由最优表知由最优表知,最优解为最优解为:y=(1/5,1/20,0)y=(1/5,1/20,0)T T,max w=1/4;x=(0,0,1/4)max w=1/4;x=(0,0,1/4)T T,min z=1/4.,min z=1/4.G G的对策值的对策值 V VG G=4.=4.于是于是 y y*=V=VG Gy=(4/5,1/5,0)y=(4/5,1/5,0)T T,x,x*=V=VG Gx=(0,0,1)x=(0,0,1)T T.G G的对策值的对策值 V VG G=V=VG G-2=2.-2=2.n注注:最优表中最优表中 y y4 4YYN N,4 4=0.=0.只要取只要取 y y4 4 进基进基,y y5 5离基离基,再迭代一次再迭代一次,得得 y=(1/10,3/20,0)y=(1/10,3/20,0)T T,max w=1/4=1/V,max w=1/4=1/VG G.则局中人则局中人的另一最优策略的另一最优策略y y*=(2/5,2/5,0)=(2/5,2/5,0)T T.