管理运筹学11对策论.ppt

《管理运筹学11对策论.ppt》由会员分享，可在线阅读，更多相关《管理运筹学11对策论.ppt（62页珍藏版）》请在三一办公上搜索。

1、2023/11/4,第一节：引论第二节：矩阵对策第三节：矩阵对策的求解,第十一章 对策论,2023/11/4,第一节：引论,1.内涵：对策论亦称博弈论（Game Theory），具有竞争或对抗性质的行为称为对策行为。2.引例3.对策行为的基本要素4.对策行为的基本假设5.对策行为的分类,2023/11/4,1.引例：齐王赛马,齐王：上、中、下田忌：上、中、下,2023/11/4,1.引例：齐王赛马,齐王：上、中、下田忌：上、中、下,2023/11/4,2.对策行为的基本要素,1.局中人（Player）：在一个对策行为中，有权决定自己行动方案的参加者称为局中人。2.策略（Strategy）：一局

2、对策中，可供局中人选择的完整的行动方案称为策略。3.赢得函数（Score）：一局对策中，局中人使用每一策略都会有所得失，这种得失是全体局中人所采取的一组策略的函数，称为赢得函数。4.局势：一局对策中，各局中人选定的策略所形成的策略组称为一个局势。,2023/11/4,3.对策行为的基本假设,对策行为总是假定每一个局中人都是“理智的”决策者，不存在利用其他局中人的决策失误来扩大自身利益的可能性或相反。,2023/11/4,4.对策行为的分类,2023/11/4,第二节：矩阵对策,1.矩阵对策的数学模型2.矩阵对策解的问题 3.矩阵对策的混合策略4.矩阵对策的基本定理5.矩阵对策解的性质,2023

3、/11/4,1.矩阵对策的数学模型,（1）矩阵对策的内涵：二人有限零和对策，即对策双方的利益是激烈对抗的。（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。,2023/11/4,1.矩阵对策的数学模型,建立二人零和对策的模型就是要根据对实际问题的叙述，确定甲、乙两个局中人的策略集合以及相应的赢得矩阵。不难看出在“齐王赛马

4、”的例子中，齐王的赢得矩阵为：,A=,3 1 1 1 1-11 3 3 3-1 11-1 3 1 1 1-1 1 1 3 1 11 1-1 1 3 11 1 1-1 1 3,2023/11/4,1.矩阵对策的示例1,例1：甲的赢得矩阵,2023/11/4,1.矩阵对策的示例2,例2：从一张红牌和一张黑牌中随机抽取一张，在对乙保密的情况下拿给甲看。若甲看到的是红牌，他可以选择掷硬币或让乙猜；若甲选择掷硬币，出现正面甲赢 p 元，出现反面甲输 q 元；若让乙猜，当乙猜中是红牌时甲输 r 元，否则甲赢 s 元。若甲看到的是黑牌，他只能让乙猜，当乙猜中是黑牌时甲输 u 元，否则甲赢 t 元。试确定甲、

5、乙各自的策略并建立赢得矩阵。,正面1/2,2023/11/4,1.矩阵对策的示例2,正面1/2,若甲决定掷硬币这个策略，则乙的猜红或猜黑已无意义；若抽到黑牌，甲的掷硬币已无意义，只与乙的猜红或猜黑有关。所以，对于局势“掷硬币，猜红”甲的期望赢得为：1/2（1/2p-1/2q）+1/2t=1/4（p-q+2t）,2023/11/4,1.矩阵对策的示例2,正面1/2,2023/11/4,2.矩阵对策解的问题,设矩阵对策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-3,Min,Max 3,局中人甲应选择2，

6、此时不管局中人乙采取什么策略，甲的赢得均不小于3。,2023/11/4,2.矩阵对策解的问题,设矩阵对策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-3,Min,Max 3,局中人甲应选择2，乙应采取2策略；结果甲赢得3，乙付出3。,Max 8 3 6 Min 3,2023/11/4,2.矩阵对策解的问题,定义1：设矩阵对策G=S1，S2，A，其中：S1=1，2，m，S2=1，2，n A=aijmn；若Max min aij=Min max aij=ai*j*则称ai*j*为对策G的值，局势（i*，j*

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

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

9、对策的混合策略,v1=3 v2=4对于两个局中人来说，不存在一个双方均可接受的平衡局势。设矩阵对策G=S1，S2，A，其中：S1=1，m，S2=1，n A=aijmn；则S1*=xi 0，i=1,2,m;x1+x2+xm=1S2*=yj 0，j=1,2,n;y1+y2+yn=1称为局中人的混合策略。,2023/11/4,3.矩阵对策的混合策略,对 x S1*,y S2*称(x,y)为一个混合局势，局中人的赢得函数记成：E(x,y)=xT A y这样便得到一个新的对策G*=S1*,S2*,EG*称为G的混合扩充。,2023/11/4,3.矩阵对策的混合策略,G*=S1*,S2*,E 是G=S1，

10、S2，A的混合扩充，如果max min E(x,y)=min max E(x,y)记其值为VG，则VG为对策G*的值，使上式成立的混合局势（x*，y*）为G 在混合策略意义下的解，x*，y*分别称为局中人甲和乙的最优混合策略。注：策略意义下的解不存在时，自动转向混合策略意义下的解。,x S1*,y S2*,x S1*,y S2*,2023/11/4,3.矩阵对策的混合策略,对策矩阵G=S1，S2，A在混合策略意义下有解的充分必要条件是存在着 x*S1*，y*S2*使（x*，y*）为E(x,y)的一个鞍点，即对于一切x S1*，y S2*有E(x,y*)E(x*,y*)E(x*,y),2023/

11、11/4,3.矩阵对策的混合策略,例：对策矩阵G=S1，S2，A，其中：A=显然G在策略意义下的解不存在，于是设x=(x1,x2)为局中人甲的混合策略，y=(y1,y2)为局中人乙的混合策略，则 S1*=xi 0，i=1,2;x1+x2=1 S2*=yj 0，j=1,2;y1+y2=1局中人甲的赢得期望值是：E(x,y)=xT A y,3,6,5,4,2023/11/4,3.矩阵对策的混合策略,例：E(x,y)=xT A y=3x1y1+6x1y2+5x2y1+4x2y2=-4(x1-1/4)(y1-1/2)+9/2取x*=（1/4，3/4），y*=（1/2，1/2），则E(x,y*)=E(x

12、*,y*)=E(x*,y)=9/2即有 E(x,y*)E(x*,y*)E(x*,y)故x*和y*分别为局中人甲和乙的最优（混合）策略。,2023/11/4,4.矩阵对策的基本定理,定理1：设矩阵对策G=S1，S2，A在策略意义下有解的充分必要条件是存在着局势（i*，j*）使得对于一切i与j都有aij*ai*j*ai*j成立。定理2：对策矩阵G=S1，S2，A在混合策略意义下有解的充分必要条件是存在着 x*S1*，y*S2*使（x*，y*）为E(x,y)的一个鞍点，即对于一切x S1*，y S2*有E(x,y*)E(x*,y*)E(x*,y),2023/11/4,4.矩阵对策的基本定理,定理3：

13、设 x*S1*，y*S2*则（x*，y*）是矩阵对策G的解的充分必要条件是对任意的i(1,2,m)和j(1,2,n)有E(x,y*)E(x*,y*)E(x*,y),2023/11/4,4.矩阵对策的基本定理,定理4：设 x*S1*，y*S2*则（x*，y*）是矩阵对策G的解的充分必要条件是存在数v使得x*和y*分别是不等式组 aijxi v aijyj v xi=1 yj=1 xi 0 yj 0的解，且v=VG。,i,j,(j=1,2,n),(i=1,2,m),(i=1,2,m),(j=1,2,n),2023/11/4,4.矩阵对策的基本定理,定理5：对任一矩阵对策G=S1，S2，A，一定存在

14、混合策略意义下的解。,2023/11/4,5.矩阵对策解的性质,性质1：设（x*，y*）是矩阵对策G=S1，S2，A的解，v=VG，则（1）若xi*0，则 aijyj*=v，（2）若 aijyj*0，则 aijxi*=v，（4）若 aijxi*v，则yj*=0。,2023/11/4,5.矩阵对策解的性质,性质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）。,2023/11/4,5.矩阵对策解的性质,性质3：矩阵对策G1=S

15、1，S2，A、G2=S1，S2，A，其中为大于0的任一常数，则：（1）V G2=V G1；（2）T（G2）=T（G1）。,2023/11/4,5.矩阵对策解的性质,性质4：设一矩阵对策G=S1，S2，A 存在 A=-AT（称为对称对策）则：（1）V G=0；（2）T1（G）=T2（G），分别为局中人甲、乙的最优策略集。,2023/11/4,5.矩阵对策解的性质,性质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

16、7 4 3,例11-6：,2023/11/4,第216页例11-6,由于第4行优超于第1行，第3行优超于第2行，故可去掉第1行和第2行，得到新的赢得矩阵：,A1=,7 3 8 4 5 4 6 5 6 6 5 2 7 4 3,2023/11/4,第216页例11-6,对于A1由于第1列优超于第3列，第2列优超于第4列，1/3（第1列）+2/3(第2列)优超于第5列，故可去掉第3、4、5列，得到新的赢得矩阵：,A2=,7 3 4 6 5 2,2023/11/4,第216页例11-6,对于A2由于第1行优超于第3行，故可去掉第3行，得到新的赢得矩阵：,A3=,7 3 4 6,2023/11/4,第2

17、16页例11-6,对于A3易之于无鞍点存在，应用定理4求解不等式组：,7x3+4x4 v3x3+6x4 v x3+x4=1 x3,x4 0,7y1+3y2 v4y1+6y2 v y1+y2=1 y1,y2 0,2023/11/4,第216页例11-6,求得解为：x3*=1/3，x4*=2/3y1*=1/2，y2*=1/2,于是原矩阵对策的一个解是：x*=（0，0，1/3，2/3，0）T y*=（1/2，1/2，0，0，0）T VG=5,2023/11/4,第三节 矩阵对策的求解,1.22对策的公式法 2.2n 或m2对策的图解法 3.线性方程组求解法 4.线性规划求解法,2023/11/4,1

18、.22对策的公式法,所谓 22对策是指局中人的赢得矩阵为22阶矩阵，即：,如果A有鞍点，则很快就可求出各局中人的最优策略；如果A没有鞍点，则可证明各局中人的最优混合策略中的xi*,yj*均大于零。于是由定理6可知，为求混合策略可求解下列方程组：a11x1+a21x2=v a11y1+a12y2=va12x1+a22x2=v a21y1+a22y2=vx1+x2=1 y1+y2=1,2023/11/4,2.2n 或m2对策的图解法,例：设一矩阵对策G=S1，S2，A，其中 S1=1，2，S2=1，2，3,2 3 11 7 5 2,设局中人甲的混合策略为(x,1-x)T，x0,1。过数轴上坐标为0

19、和1的两点分别做两条垂线 和，垂线上点的纵坐标值分别表示局中人甲采取纯策略1，2 时，局中人乙采取各策略时的赢得值。如下图所示，当局中人甲选择每一混合策略(x,1-x)T时，他可能的最少赢得为局中人乙选择1，2，3时所确定的3条直线在 x 处的纵坐标值的最小值。,2023/11/4,2.2n 或m2对策的图解法,V=2x+7(1-x)V=3x+5(1-x)V=11x+2(1-x)设局中人甲的混合策略为(x,1-x)T，x0,1。过数轴上坐标为0和1的两个点分别做两条垂线 和，垂线上的点的纵坐标值分别表示局中人甲采取纯策略1，2 时，局中人乙采取各策略时的赢得值。如下图所示：,2023/11/4

20、,甲采取混合策略最少的赢得：B1BB2B3甲确定 x 使赢得最大，即最小最大原则,2023/11/4,x=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=62/1149/11E(x*,2)=33/11+58/11=49/11E(x*,3)=113/11+28/11=49/11所以局中人乙的最优混合策略 y*=（0,y2,y3）,2023/11/4,3y2+11y3=VG=49/115y2+2y3=VG=49/11y2+

21、y3=1求解得y*=（0,9/11,2/11）.,2023/11/4,例：设一矩阵对策G=S1，S2，A，其中 S1=1，2，3，S2=1，2 2 7 A=6 6 11 2设乙的混合策略为(y,1-y)，同理有：,2023/11/4,0,1,2,6,7,11,6,2,y,A1,B1,B2,B3,乙采取混合策略最大的支付：7B1B211乙确定 y 使支付最小，即最大最小原则,3,2,1,A2,2023/11/4,OA1 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。故局中人乙的最优混合策略

22、为 y*=（y,1-y），其中 y 1/5，4/9；而故局中人甲的最优策略显然只能是 x*=（0,1,0），即策略2。,2023/11/4,3.线性方程组求解法,根据定理4求解矩阵对策解（x*，y*）的问题等价于求解：aijxi v aijyj v xi=1 yj=1 xi 0 yj 0又根据定理5和定理6，如果x*，y*中各分量均不为零，即可将不等式组转换为方程组：,2023/11/4,3.线性方程组求解法,不等式组转换为方程组：aijxi=v aijyj=v xi=1 yj=1 xi 0 yj 0如果这两个方程组存在非负解x*和y*，则已经求得了矩阵对策的解（x*，y*）。,2023/11

23、/4,3.线性方程组求解法,例：“齐王赛马”齐王的赢得矩阵为 3 1 1 1 1-1 1 3 1 1-1 1 A=1-1 3 1 1 1-1 1 1 3 1 1 1 1-1 1 3 1 1 1 1-1 1 3,2023/11/4,3.线性方程组求解法,设：X*=（x1，x2，x3，x4，x5，x6）T Y*=（y1，y2，y3，y4，y5，y6）T 从矩阵A的元素来看局中人采取任何一个策略的可能性都是存在的，故可事先假设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/

24、6，1/6，1/6，1/6）T对策的值（齐王的期望赢得）为1。,2023/11/4,4.线性规划求解法,根据定理5有矩阵对策的解（x*，y*）等价于下述不等式组的解：aijxi v aijyj v xi=1 yj=1 xi 0 yj 0其中 v=maxmin E(x,y)=minmax E(x,y)就是对策的值VG。做变量变换 xi=xi/v,yj=yj/v于是有：,2023/11/4,4.线性规划求解法,aijxi 1 aijyj 1 xi=1/v yj=1/v xi 0 yj 0其相应的线性规划问题为：min z=xi max w=yj aijxi 1 aijyj 1 xi 0 yj 0,

25、2023/11/4,4.线性规划求解法,例：7 2 9 A=2 9 0 9 0 11Min(x1+x2+x3)Max(y1+y2+y3)7x1+2x2+9x3 1 7y1+2y2+9y3 1 2x1+9x2+0 x3 1 2y1+9y2+0y3 1 9x1+0 x2+11x3 1 9y1+0y2+11y3 1 x1,x2,x3 0 y1,y2,y3 0,2023/11/4,4.线性规划求解法,2023/11/4,4.线性规划求解法,2023/11/4,4.线性规划求解法,2023/11/4,4.线性规划求解法,Y=(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),