运筹与优化-对策论

运筹与优化

第十四章对策论

运筹与优化--对策论对策论对策论的基本概念对策论的基本定理矩阵对策的解法运筹与优化--对策论第一节对策论的基本概念

对策论亦称竞赛论或博奕论,是研究具有斗争或竞争性质的数学理论和方法.

具有竞争或对抗性质的行为称为对策行为.

对策论是研究对策行为中竞争各方是否存在最合理的行动方案,以及如何找到最合理方案的数学理论和方法.

具有对策行为的模型称为对策模型,或对策.运筹与优化--对策论

对策三要素局中人:在一个对策行为中,有权决定自己行动方案的对策者.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},试求双方的最优策略和赢得.理智行为:双方各按最不利于自己的情形中选择最为利己的结果作为决策的依据.运筹与优化--对策论定义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)定义在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)处存在鞍点.其中∵q≤a22≤p

，∴p≥5,q≤5运筹与优化--对策论例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的解.

由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的混合扩充.运筹与优化--对策论设则有定义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)的一个鞍点,即对一切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

},其中运筹与优化--对策论局中人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.运筹与优化--对策论定理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)为此,考虑下列两个线性规划问题:运筹与优化--对策论

易知(P)和(D)互为对偶,x=(1,0,…,0)T∈Em,w=min

a1j是(P)的可行解,y=(1,0,…,0)T∈En,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*)，x∈S1*,故

运筹与优化--对策论又因所以,当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),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.解:

由于矩阵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.运筹与优化--对策论

对于A2,r1≥r3,从A2中划去第3行,得到新矩阵A3.对于A3,由于故A3无鞍点.应用定理4,求解不等式组:

7x3+4x4≥v7y1+3y2≤v3x3+6x4≥v(I)；4y1+6y2≤v(Ⅱ)x3+x4=1y1+y2=1x3,x4≥0

y1,y2≥0运筹与优化--对策论

首先求解下列等式组的非负解:

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.运筹与优化--对策论第三节矩阵对策论的解法

一、2×2对策的公式法设,当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,x1∈[0,1].做两条垂线P0(x1=0)和P1(x1=1),P0

P1

表示局中人I分别取纯策略β3

11α2和α1.垂线P0上的值表

7

β1

示局中人I取α2时,局中人5B

β2Ⅱ取各βj时的赢得值.同理,

2

S

23垂线P1上的值表示局中人I取

0A1

α1时,局中人Ⅱ取各βj时的赢得值.图1

运筹与优化--对策论

P0

图1P1

β3

11

7

5

β1

B

β2

3

2S2

0A1

如图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,α3

P0

P1

在任一点y1∈[0,1]处

图211

的纵坐标分别是局中

7

S

α3

人Ⅱ取(y1,1-y1)T时的

6B1B2

α26

支付.根据最不利中选取最利己的原则,局中人Ⅱ按minmax原则,

2

α1

2

0

A1

A2

1运筹与优化--对策论局中人Ⅱ应选OA1≤y1≤OA2,则对策值为6.由

2y1+7(1-y1)=6,11y1+2(1-y1)=6解得OA1=1/5,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.优超法:

因列c2≤c3,故可划去第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.图解法:

由图可见,局中人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/4y1+5y2+7y4=13/4y1+y2+y4=17β4

易知具有无穷多解5β3

故局中人Ⅱ有无穷4

多个最优混合策略.13/4β2

例4说明,优超法β1

8/3

可能划去原矩阵1

对策的一些解.S03/41P0

图3P1

运筹与优化--对策论线性方程组方法:

设xi*、yj*均不为零,先求解等式组

的非负解.

若(Ⅰ),(Ⅱ)的解有负分量，就将(Ⅰ),(Ⅱ)的某些等式改为不等式.

三、线性方程组方法运筹与优化--对策论

定理11.设矩阵对策G={S1,S2;A1}的值为VG,

则证明:因VG是对策的值,故一方面,

得

求解矩阵对策的线性规划方法:运筹与优化--对策论

另一方面,有

故得

同理有

运筹与优化--对策论

根据定理7,可设v>0.作变换xi’=xi/v,i=1,2,…m,则由定理4有

(1)

根据定理11,

于是(1)等价于线性规划(P):

运筹与优化--对策论

同理,作变换yj’=y/v,则定理4的另一不等组等价于线性规划(D):(2)(3)注:一般先求解问题(D),再代回变换即可求出原对策解.运筹与优化--对策论例5.利用线性规划求解对策G,其中A:解:为使对策值V≥0,由定理7,