运筹与优化--对策论

运筹与优化第十四章对策论对策论对策论的基本概念对策论的基本定理矩阵对策的解法第一节对策论的基本概念对策论亦称竞赛论或博奕论,是研究具有斗争或竞争性质的数学理论和方法.具有竞争或对抗性质的行为称为对策行为.对策论是研究对策行为中竞争各方是否存在最合理的行动方案,以及如何找到最合理方案的数学理论和方法.具有对策行为的模型称为对策模型,或对策.对策三要素局中人:在一个对策行为中,有权决定自己行动方案的对策者.n个局中人的集合I={1,2,…,n}.理智的决策者:不存在侥幸心理者.策略集:可供局中人i选择的一个实际可行的完整的行动方案称为一个策略si,策略集Si.局势:在对策中,各局中人所选定的策略构成的策略组s=(s1,s2,…sn).全体局势S=S1×S2×…×Sn赢得函数:局势s的函数Hi(s).矩阵对策:二人有限零和对策.第二节对策论的基本定理局中人I的纯策略集S1={α1,α2,…αm};局中人Ⅱ的纯策略集S2={β1,β2,…βn};对任一纯局势(αi,βj)(共m×n个),局中人I的赢得值为aij,赢得矩阵为A=(aij)m×n.局中人Ⅱ的赢得矩阵为-A.矩阵对策记为G={Ⅰ,Ⅱ，S1，S2；A}或G={S1，S2；A}.田忌齐王β1(上中下)β2(上下中)β3(中上下)β4(中下上)β5(下中上)β6(下上中)α1(上中下)α2(上下中)α3(中上下)α4(中下上)α5(下中上)α6(下上中)311-11113-11111131-1111131-11-11131-111113例1.“齐王赛马”中，齐王的赢得矩阵为:最优策略:有利于自己获得最大赢得(或最少损失)的策略.选择最优策略的原则:牢记对方总是以最不利于你的行动方案来对付你.例2.设矩阵对策G={S1,S2;A},其中S1={α1,α2,α3,α4},S2={β1,β2,β3},试求双方的最优策略和赢得.理智行为:双方各按最不利于自己的情形中选择最为利己的结果作为决策的依据.6031019423816A定义1.设矩阵对策G={S1,S2；A},若等式(1)成立,记,则称VG为对策G的值,称使(1)成立的纯局势为G在纯策略下的解(或平衡局势、双赢局势).定理1.矩阵对策G={S1,S2；A}在纯策略中有解的充要条件是:存在纯局势使得(2)(i=1,2,…,m,j=1,2,…,n).既是其所在行的最小元素,又是其所在列的最大元素.jiijminjijnjmiaaa1111maxminminmaxjiGaV),(ji),(jijijiijaaajia定义2.设实函数f(x,y)定义在x∈A,y∈B上,若存在x*∈A,y*∈B,使得对x∈A,y∈B,有f(x,y*)≤f(x*,y*)≤f(x*,y)(3)则称(x*,y*)为f(x,y)的一个鞍点.矩阵对策G在纯策略意义下有解,且的充要条件是:是矩阵A的一个鞍点.例3.确定p和q的取值范围,使矩阵A在(α2,β2)处存在鞍点.其中jiGaVjia32610561pqA∵q≤a22≤p，∴p≥5,q≤5例4.设矩阵对策G={S1,S2;A},其中S1={α1,α2,α3,α4},S2={β1,β2,β3},试求双方的最优策略和赢得.6565142185750262A性质1(无差别性).若(αk,βr)和(αp,βq)是对策G的两个解,则akr=apq.事实上,由,有apq≤apr≤akr≤akq≤apq因此akr=apq.jijiijaaa性质2(可交换性).若(αk,βr)和(αp,βq)是对策G的两个解,则(αk,βq)和(αp,βr)也是对策G的解.由aiq≤apq=akr≤akq≤apq=akr≤akj得aiq≤akq≤akj,即akq是鞍点.故(αk,βq)是解.同理，(αp,βr)是解.性质1、2表明,矩阵对策的值是唯一的.例5.P385例题.定义3.设矩阵对策G={S1,S2;A},A=(aij)m×n.若局中人I以概率xi≥0取纯策略αi,局中人Ⅱ以概率yj≥0取纯策略βj,且.记则S1*,S2*分别称为局中人I和Ⅱ的混合策略集.称x∈S1*,y∈S2*为局中人I和Ⅱ的混合策略,(x,y)为混合局势,局中人I的赢得函数为称G*={S1*,S2*,E}为对策G的混合扩充.1,111njjmiiyx}1,0),,,({1211miiimmxxExxxxS}1,0),,,({1212njjjnnyyEyyyySjijiijTyxaAyxyxE),(设则有定义4.设G*={S1*,S2*;E}是矩阵对策G={S1,S2;A}的混合扩充,若2211maxmin(,)minmax(,)(3)ySySxSxSExyExy),(min),(minmax**2*2*1yxEyxESySySx),(max),(maxmin**1*1*2yxEyxESxSxSy),(max),(),(min*****1*2yxEyxEyxESxSy记其值为VG,则称VG为对策G*的值,使(3)成立的混合局势(x*,y*)为G在混合策略意义下的解.定理2.矩阵对策G={S1,S2;A}在混合策略中有解的充要条件是:(x*,y*)为E(x,y)的一个鞍点,即对一切x∈S1*,y∈S2*,有E(x,y*)≤E(x*,y*)≤E(x*,y)(4)注意:G在纯策略下解存在时,定义4中的;G在混合策略意义下的解(x*,y*)存在时,VG=E(x*,y*).例4.解矩阵对策G={S1,S2;A},其中jiGaV4563A局中人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.设x∈S1*,y∈S2*,则(x*,y*)是G的解的充要条件是:对任意i=1,2,…,m和j=1,2,…,n,有E(i,y*)≤E(x*,y*)≤E(x*,j)(7)定理3.设x∈S1*,y∈S2*,则(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*)xi≤E(x*,y*)∑xi=E(x*,y*)E(x*,y)=∑E(x*,j)yj≥E(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.miiimiiijxxnjvxa110,1,,2,1njjjnjjijyymivya110,1,,2,1定理4.证明:“”因G有解,(7)式成立.取v=E(x*,y*)就有(8),(9).“”因对任意x∈S1*,y∈S2*,有E(x,y*)=∑E(i,y*)xi≤∑vxi=vE(x*,y)=∑E(x*,j)yj≥∑vyj=v于是E(x,y*)≤v≤E(x*,y).特别有E(x*,y*)≤v≤E(x*,y*).故v=E(x*,y*)=VG.定理5.任意矩阵对策G={S1,S2;A}一定存在混合策略意义下的解.证明:由定理4,只要证明存在数v*和x*∈S1*,y*∈S2*,使得(10)为此,考虑下列两个线性规划问题:miiijnjjijxavya11)11(01,,2,1..max)(11miiimiiijxxnjwxatswP易知(P)和(D)互为对偶,x=(1,0,…,0)T∈Em,w=mina1j是(P)的可行解,y=(1,0,…,0)T∈En,v=maxai1是(D)的可行解.因此(P)和(D)皆存在最优解x*∈S1*,y*∈S2*,且最优值v*=w*.故(10)式成立.)12(01,,2,1..min)(11njjjnjjijyymivyatsvD定理6.设(x*,y*)是矩阵对策G的解,v=VG,那么(1).若xi*0,则;(2).若yj*0,则;(3).若,则xi*=0;(4).若,则yj*=0.证明:由定义有v=maxE(x,y*)，x∈S1*,故jjijvyaiiijvxajjijvyaiiijvxa0),(),(max1yiEyxEyavSxjjij又因所以,当xi*0，必有;当,必有xi*=0.故(1),(3)得证.同理可证(2),(4).0,0)(iijjiijijijixyxavyavxjjijvyajjijvya定理7.设矩阵对策G1={S1,S2;A1}的解集T(G1),G2={S1,S2;A2}的解集为T(G2).其中A1=(aij),A2=(aij+p),p∈R.则(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=1～n,都有akj≥atj,则称局中人I的纯策略αk优超于αt;若对i=1～m,都有aip≤aiq,则称局中人Ⅱ的纯策略β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)T∈T1(G’),则(0,x2,…,xm)T∈T1(G).推论.如果纯策略α1被纯策略α2,…αm的凸线性组合所优超,则定理10的结论仍成立.类似地，对局中人Ⅱ，如果纯策略β1被纯策略β2,…,βn的凸线性组合所优超,于是有(1).VG’=VG;(2).T1(G’)包含于T1(G)中;(3).若(y2,…,ym)T∈T2(G’),则(0,y2,…,ym)T∈T2(G).优超原则：可在赢得矩阵A中划去被其它行(列)或其它行(列)的凸线性组合所优超的那些行(列).例5.设赢得矩阵A如下,求解矩阵对策G.解:388065.57864959379520503023A388065.57864959371A0664372A由于矩阵A中行r4≥r1,r3≥r2,故可从A中划去第1行和第2行,得到新矩阵A1.对于A1,列c1≤c3,c2≤c4,(1/3)c1+(2/3)c3≤c5,可从A1中划去第3列、第4列、第5列,得到新矩阵A2.,4minmaxijjia6maxminijija0664372A对于A2,r1≥r3,