运筹与优化--对策论

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.“齐王赛马”中，齐王的赢得矩阵为:,最优策略:有利于自己获得最大赢得(或最少损失)的策略. 选择最优策略的原则:

3、牢记对方总是以最 不利于你的行动方案来对付你. 例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). 既是其所在 行的最小元素,又是其所在列的最大元素.,定义

4、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)处存在鞍点.其中,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. 事实上,由 ,有

5、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 得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*, yS

6、2*为局中人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)的 一个鞍点,即对一切 xS1*,yS2*,有 E(x,y*)E(x*,y*)E(x*,y) (4) 注意:G在纯策略下解存在时,定义4中的 ;G在混合策略意义下的解(x*,y*

7、) 存在时,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.设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,有

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

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

10、in 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*=0 . 证明: 由定义有 v=maxE(x,y*)，xS1* ,故,又因 所以,当 xi*0，必有 ; 当 ,必有 xi*=0 . 故(1),(3)得证.同理可证(2),(4).,定理7.设矩阵对策G1=S1,S2;A1的解集

11、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. 则 (1).VG=0 ; (2). T1(G)=T2(G). 其中T1(G)和T2(G)分别为局中人和局中人的最优策略集. 定理7定理9的证明: 利用鞍点的概念和定理3.,定义5.

12、 设矩阵对策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(G),则 (0,x2,xm)TT1(G).,推论.如果纯策略1被纯策略2 , m的凸线性组合所

13、优超,则定理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)c3 c5 , 可从A1中划去第3列、第4列、

14、第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

15、*=(0,0,1/3,2/3,0)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,其

16、中 则对策的最优解为: 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 ,x10,1. 做两条垂线P0(x1=0)和P1(x1=1), P0 P1 表示局中人I分别取纯策略 3 11 2和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

17、2 S 2 0 A 1,如图1,当局中人I选择策略(x1,1-x1)T时,其 最少可能的收入是局中人选择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组成

18、.由定理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 在任一点y10,1处 图2 11 的纵坐标分别是局中 7 S 3 人取(y1,1-y1)T时的 6 B1 B2 2 6 支付.根据最不利中选 取最利己的原则,局中 人按 min max原则,2 1 2 0 A1

19、 A2 1,局中人应选 OA1y1 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.优超法: 因列c2c3 ,故可划去第3列; 又因(2/3)c4+(1/3)c

20、1=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/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*均不为零,先