新编管理运筹学11对策论课件.ppt

1、2022-8-13第一节：引论第二节：矩阵对策第三节：矩阵对策的求解2022-8-131.内涵：对策论亦称博弈论（Game Theory），具有竞争或对抗性质的行为称为对策行为。2.引例3.对策行为的基本要素4.对策行为的基本假设5.对策行为的分类2022-8-13齐王：上、中、下田忌：上、中、下 2022-8-13齐王：上、中、下田忌：上、中、下2022-8-131.局中人（Player）：在一个对策行为中，有权决定自己行动方案的参加者称为局中人。2.策略（Strategy）：一局对策中，可供局中人选择的完整的行动方案称为策略。3.赢得函数（Score）：一局对策中，局中人使用每一策略都会有

2、所得失，这种得失是全体局中人所采取的一组策略的函数，称为赢得函数。4.局势：一局对策中，各局中人选定的策略所形成的策略组称为一个局势。2022-8-13 对策行为总是假定每一个局中人都是“理智理智的的”决策者，不存在利用其他局中人的决策失误来扩大自身利益的可能性或相反。2022-8-13对策动态对策静态对策结盟对策不结盟对策联合对策合作对策无限对策有限对策二人多人零 和非零和零 和非零和同有限对策2022-8-131.矩阵对策的数学模型2.矩阵对策解的问题 3.矩阵对策的混合策略4.矩阵对策的基本定理5.矩阵对策解的性质2022-8-13（1）矩阵对策的内涵：二人有限零和对策，即对策双方的利益

3、是激烈对抗的。（2）矩阵对策的数学模型：甲：有m个策略，表示为S1=（1,2,3,m)乙：有n个策略，表示为S2=（1,2,3,n)当甲选定策略i、乙选定策略j 时，就形成了一个局势（i,j）。可见这样的局势总共有m n个，对任意局势（i,j）甲的赢得值为aij，即甲的赢得矩阵为Amn=aij。因为对策是零和的，所以乙的赢得矩阵为 -Amn。2022-8-13 建立二人零和对策的模型就是要根据对实际问题的叙述，确定甲、乙两个局中人的策略集合以及相应的赢得矩阵。不难看出在“齐王赛马”的例子中，齐王的赢得矩阵为：A=3 1 1 1 1 -11 3 3 3 -1 11 -1 3 1 1 1-1 1

4、1 3 1 11 1 -1 1 3 11 1 1 -1 1 3 2022-8-13 乙 甲石头剪子布石头01-1剪子-101布1-10例1：甲的赢得矩阵 2022-8-13例2：从一张红牌和一张黑牌中随机抽取一张，在对乙保密的情况下拿给甲看。若甲看到的是红牌，他可以选择掷硬币或让乙猜；若甲选择掷硬币，出现正面甲赢 p 元，出现反面甲输 q 元；若让乙猜，当乙猜中是红牌时甲输 r 元，否则甲赢 s 元。若甲看到的是黑牌，他只能让乙猜，当乙猜中是黑牌时甲输 u 元，否则甲赢 t 元。试确定甲、乙各自的策略并建立赢得矩阵。正面1/2抽到红牌1/2抽到黑牌1/2掷硬币让乙猜让乙猜猜红反面1/2p-q-

5、r猜红猜黑猜黑st-u 2022-8-13正面1/2抽到红牌1/2抽到黑牌1/2掷硬币让乙猜让乙猜猜红反面1/2p-q-r猜红猜黑猜黑st-u 若甲决定掷硬币这个策略，则乙的猜红或猜黑已无意义；若抽到黑牌，甲的掷硬币已无意义，只与乙的猜红或猜黑有关。所以，对于局势“掷硬币，猜红”甲的期望赢得为：1/2（1/2p-1/2q）+1/2t=1/4（p-q+2t）2022-8-13正面1/2抽到红牌1/2抽到黑牌1/2掷硬币让乙猜让乙猜猜红反面1/2p-q-r猜红猜黑猜黑st-u 乙甲猜红猜黑掷硬币1/4（p-q+2t）1/4（p-q-2u）让乙猜1/2（-r+t）1/2（s-u）2022-8-13

6、设矩阵对策G=S1，S2，A，其中：S1=1，2，3，4，S2=1，2，3，A=-4 2 -6 -6 4 3 5 3 8 -1 -10 -10-3 0 6 -3MinMax 3局中人甲应选择2，此时不管局中人乙采取什么策略，甲的赢得均不小于3。2022-8-13 设矩阵对策G=S1，S2，A，其中：S1=1，2，3，4，S2=1，2，3 A=-4 2 -6 -6 4 3 5 3 8 -1 -10 -10-3 0 6 -3MinMax 3局中人甲应选择2，乙应采取2策略；结果甲赢得3，乙付出3。Max 8 3 6 Min 3 2022-8-13 定义1：设矩阵对策G=S1，S2，A，其中：S1=

7、1，2，m，S2=1，2，n A=aijmn；若Max min aij =Min max aij =ai*j*则称ai*j*为对策G的值，局势（i*，j*）为G的解，i*和j*分别称为局中人的最优策略。ijij 2022-8-13 由于ai*j*既是其所在行的最小值，又是其所在列的最大值，于是有：aij*ai*j*ai*j定理1：设矩阵对策G=S1，S2，A在策略意义下有解的充分必要条件是存在着局势（i*，j*）使得对于一切i与j都有aij*ai*j*ai*j成立。2022-8-13 例：设矩阵对策G=S1，S2，A，赢得矩阵为：A=7 5 6 5 5 2 -3 9 -4 -4 6 5 7 5

8、 5 0 1 -1 2 -1MinMax=5 Max 7 5 9 5 Min=5i =1,3，j =2,4，ai*j*=5，四个局势均为矩阵对策的解。2022-8-13 对矩阵对策G=S1，S2，A来说，局中人甲有把握的最小赢得是：v1=max min aij局中人乙有把握的最大损失是：v2=min max aij 当v1=v2时，对矩阵对策有策略意义下的解；然而并非总是如此，经常是 v1 v2（总有v1 v2），此时没有策略意义下的解。ijij 2022-8-13A=-4 4 -6 -6 4 3 5 3 8 -1 -10 -10-3 0 6 -3MinMax 3Max 8 4 5 Min 4

9、v1=3 v2=4 2022-8-13 v1=3 0，则 aijyj*=v，（2）若 aijyj*0，则 aijxi*=v，（4）若 aijxi*v，则yj*=0。2022-8-13 性质2：矩阵对策G1=S1，S2，A1、G2=S1，S2，A2，解集分别为T（G1）和 T（G2），若其中有A1=（aij）、A2=（aij+L），L为任一常数，则：（1）V G2=V G1+L；（2）T（G2）=T（G1）。2022-8-13 性质3：矩阵对策G1=S1，S2，A、G2=S1，S2，A，其中为大于0的任一常数，则：（1）V G2=V G1；（2）T（G2）=T（G1）。2022-8-13 性质4

10、：设一矩阵对策G=S1，S2，A 存在 A=-AT（称为对称对策）则：（1）V G=0；（2）T1（G）=T2（G），分别为局中人甲、乙的最优策略集。2022-8-13 性质5：设一矩阵对策G=S1，S2，A，若在S1（或、和S2）中出现被优超的策略，那么去掉被优超的策略所形成的新的矩阵对策与原矩阵对策同解。A=4 0 2 3 -2-2 1 4 -4 3 7 3 8 4 5 4 6 5 6 6 5 2 7 4 3例11-6：2022-8-13 由于第4行优超于第1行，第3行优超于第2行，故可去掉第1行和第2行，得到新的赢得矩阵：A1=7 3 8 4 5 4 6 5 6 6 5 2 7 4 3

11、2022-8-13 对于A1由于第1列优超于第3列，第2列优超于第4列，1/3（第1列）+2/3(第2列)优超于第5列，故可去掉第3、4、5列，得到新的赢得矩阵：A2=7 3 4 6 5 2 2022-8-13 对于A2由于第1行优超于第3行，故可去掉第3行，得到新的赢得矩阵：A3=7 3 4 6 2022-8-13 对于A3易之于无鞍点存在，应用定理4求解不等式组：7x3+4x4 v3x3+6x4 v x3+x4 =1 x3,x4 07y1+3y2 v4y1+6y2 v y1+y2 =1 y1,y2 0 2022-8-13 求得解为：x3*=1/3，x4*=2/3y1*=1/2，y2*=1/

12、2于是原矩阵对策的一个解是：x*=（0，0，1/3，2/3，0）T y*=（1/2，1/2，0，0，0）T VG=52022-8-13 1.22对策的公式法 2.2n 或m2对策的图解法 3.线性方程组求解法 4.线性规划求解法2022-8-13 所谓 22对策是指局中人的赢得矩阵为22阶矩阵，即：A=a11 a12 a21 a22 如果A有鞍点，则很快就可求出各局中人的最优策略；如果A没有鞍点，则可证明各局中人的最优混合策略中的xi*,yj*均大于零。于是由定理6可知，为求混合策略可求解下列方程组：a11x1+a21x2=v a11y1+a12y2=va12x1+a22x2=v a21y1+

13、a22y2=vx1+x2=1 y1+y2=12022-8-13 例：设一矩阵对策G=S1，S2，A，其中 S1=1，2，S2=1，2，3 2 3 11 7 5 2A=设局中人甲的混合策略为(x,1-x)T，x0,1。过数轴上坐标为0和1的两点分别做两条垂线 和 ，垂线上点的纵坐标值分别表示局中人甲采取纯策略1，2 时，局中人乙采取各策略时的赢得值。如下图所示，当局中人甲选择每一混合策略(x,1-x)T时，他可能的最少赢得为局中人乙选择1，2，3时所确定的3条直线在 x 处的纵坐标值的最小值。2022-8-13A=2 3 11 7 5 2 V=2x+7(1-x)V=3x+5(1-x)V=11x+

14、2(1-x)设局中人甲的混合策略为(x,1-x)T，x0,1。过数轴上坐标为0和1的两个点分别做两条垂线 和，垂线上的点的纵坐标值分别表示局中人甲采取纯策略1，2 时，局中人乙采取各策略时的赢得值。如下图所示：2022-8-13甲采取混合策略最少的赢得：B1BB2B3甲确定 x 使赢得最大，即最小最大原则012571132xAB1B2BB3123 2022-8-13x=OA,AB即为对策值VG求解 x 及VG，解方程组：VG=3x+5(1-x)VG=11x+2(1-x)求得 x=3/11,VG=49/11；所以甲的最优策略为x*=（3/11，8/11）E(x*,1)=23/11+78/11=6

15、2/1149/11E(x*,2)=33/11+58/11=49/11E(x*,3)=113/11+28/11=49/11所以局中人乙的最优混合策略 y*=（0,y2,y3）2022-8-133y2+11y3=VG=49/115y2+2y3=VG=49/11y2+y3=1求解得y*=（0,9/11,2/11）.2022-8-13l例：设一矩阵对策G=S1，S2，A，其中l S1=1，2，3，S2=1，2 l 2 7l A=6 6l 11 2l设乙的混合策略为(y,1-y)，同理有：2022-8-13012671162yA1B1B2B3乙采取混合策略最大的支付：7B1B211乙确定 y 使支付最小

16、，即最大最小原则321A2 2022-8-13OA1 y OA2 VG=6 2y+7(1-y)=6 6y+6(1-y)=6 6y+6(1-y)=611y+2(1-y)=6求得 OA1=1/5,OA2=4/9。故局中人乙的最优混合策略为 y*=（y,1-y），其中 y 1/5，4/9；而故局中人甲的最优策略显然只能是 x*=（0,1,0），即策略2。2022-8-13l根据定理4求解矩阵对策解（x*，y*）的问题等价于求解：l aijxi v aijyj vl xi=1 yj=1l xi 0 yj 0l又根据定理5和定理6，如果x*，y*中各分量均不为零，即可将不等式组转换为方程组：2022-8

17、-13l不等式组转换为方程组：l aijxi=v aijyj=vl xi=1 yj=1l xi 0 yj 0l如果这两个方程组存在非负解x*和y*，则已经求得了矩阵对策的解（x*，y*）。2022-8-13l例：“齐王赛马”齐王的赢得矩阵为l 3 1 1 1 1 -1l 1 3 1 1 -1 1l A=1 -1 3 1 1 1l -1 1 1 3 1 1l 1 1 -1 1 3 1 l 1 1 1 -1 1 3l 2022-8-13 设：X*=（x1，x2，x3，x4，x5，x6）T Y*=（y1，y2，y3，y4，y5，y6）T 从矩阵A的元素来看局中人采取任何一个策略的可能性都是存在的，故

18、可事先假设X*，Y*中各分量均不为零；于是有：ATX=v AY=v xi=1 yj=1 求得解为：X*=（1/6，1/6，1/6，1/6，1/6，1/6）T Y*=（1/6，1/6，1/6，1/6，1/6，1/6）T对策的值（齐王的期望赢得）为1。2022-8-13l根据定理5有矩阵对策的解（x*，y*）等价于下述不等式组的解：l aijxi v aijyj vl xi=1 yj=1l xi 0 yj 0l其中 v=maxmin E(x,y)=minmax E(x,y)就是对策的值VG。做变量变换 xi=xi/v,yj=yj/vl于是有：2022-8-13l aijxi 1 aijyj 1l

19、xi=1/v yj=1/vl xi 0 yj 0l其相应的线性规划问题为：l min z=xi max w=yj l aijxi 1 aijyj 1l xi 0 yj 0 2022-8-13l例：7 2 9l A=2 9 0l 9 0 11lMin(x1+x2+x3)Max(y1+y2+y3)l7x1+2x2+9x3 1 7y1+2y2+9y3 1 l2x1+9x2+0 x3 1 2y1+9y2+0y3 1 l9x1+0 x2+11x3 1 9y1+0y2+11y3 1 l x1,x2,x3 0 y1,y2,y3 0 2022-8-13cj111000wCBXBby1y2y3s1s2s3000

20、s1s2s31117292909011100010001cj-zj1110000 2022-8-13cj111000wCBXBby1y2y3s1s2s3001s1s2y12/97/91/90012904/9-22/911/9100010-7/9-2/91/9cj-zj01-2/900-1/91/9 2022-8-13cj111000CBXBby1y2y3s1s2s3011s1y2y14/817/811/900101080/81-22/8111/9100-2/91/90-59/81-2/811/9cj-zj004/810-1/9-7/81 2022-8-13cj111000CBXBby1y2y3s1s2s3111y3y2y11/201/101/2000101010081/8011/40-99/80-9/401/2011/40-59/80-9/4081/80cj-zj000-1/20-1/10-1/20Y=(1/20,1/10,1/20)w=1/5 v=5Y*=5(1/20,1/10,1/20)=(1/4,1/2,1/4)X*=(1/4,1/2,1/4)