《矩阵对策的基本定理精选课件.ppt》由会员分享，可在线阅读，更多相关《矩阵对策的基本定理精选课件.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于矩阵对策的基本定理第一页，本课件共有33页2023/3/122.1 矩阵对策的数学模型二人有限零和对策%二人零和对策就是矩阵对策,是指只有两个参加对策的局中人,每个局中人都只有有限个策略可供选择。在任一局势下,两个局中人的赢得之和总是等于零,即双方的利益是激烈对抗的。矩阵对策的表示%设局中人有 m 个纯策略 1,2,m,局中人有 n 个纯策略 1,2,n,则局中人、的策略集分别为 S1=1,2,m S2=1,2,n第二页，本课件共有33页2023/3/13%当局中人选定纯策略 i 和局中人选定纯策略 j 后,就形成了一个纯局势(i,j)。这样的纯局势可构成 m n 矩阵。对任一纯局势(i,
2、j),记局中人的赢得值为 aij,则称矩阵 A=(aij)mn 为局中人 I 的赢得矩阵(或为局中人 II 的支付矩阵)，这样，局中人 II 的赢得矩阵即为 A。%矩阵对策常记为：G=I,II;S1,S2;A或 G=S1,S2;A第三页，本课件共有33页2023/3/14例 齐王赛马的赢得矩阵第四页，本课件共有33页2023/3/15例6%设有一矩阵对策 G=S1,S2;A,其中 S1=1,2,3,4 ,S2=1,2,3，局中人 I 的赢得矩阵为%试分析局中人 I 和 II 分别使用什么策略最有利？又在什么局势下对双方都有利？第五页，本课件共有33页2023/3/16定义定义1 设 G=S1,
3、S2;A为矩阵对策。其中 S1=1,2,m ,S2=1,2,n ,A=(aij)mn 若成立以下等式则称 VG 为对策 G 的值,并称使上述等式成立的纯局势(i*,j*)为 G 在纯策略下的解(或平衡局势),i*与 j*分别称为局中人,的最优纯策略。第六页，本课件共有33页2023/3/17例7%求解矩阵对策 G=S1,S2;A,其中第七页，本课件共有33页2023/3/18定理定理1 矩阵对策 G=S1,S2;A 在纯策略意义下有解的充分必要条件是:存在纯局势(i*,j*)使得对一切 i=1,m,j=1,n,均有 aij*ai*j*ai*j证明：第八页，本课件共有33页2023/3/19充分
4、性（前提：对任意 i,j 有 aij*ai*j*ai*j）%由不等式左边知，j*列的任一元素不超过 ai*j*，从而 j*列的最大元也不超过 ai*j*.即：%同理对不等式右边，ai*j*不超过 i*行的任一元素，从而 ai*j*不超过 i*行的最小元素，即有%因此可得%而对每列的最大元中的最小者及每行的最小元中的最大者有%即：j*列的任一元素i*行的任一元素第九页，本课件共有33页2023/3/110%另外，对任意 i,j 有，任意元素 aij 不小于其所在行的最小元，也不大于其所在列的最大元，即%不等式左边又说明，矩阵中每一行的最小元都不超过 aij，从而每一行的最小元中的最大者也不超过
5、aij，即%同理，由不等式的右边也可得%从而有%结合(1),(2)即可得第十页，本课件共有33页2023/3/111必要性%假设有 i*,j*使%上式右边说明 ai*j*是第 j*列中最大元，即%同理左边说明 ai*j*是第 i*行中最小元，即%而对任意 i 应有%同理对任意 j 应有%综上可得%即第十一页，本课件共有33页2023/3/112定义定义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)则称(x*,y*)为函数 f 的一个鞍点。矩阵对策的解与鞍点%若将局势矩
6、阵视为二元函数 f(x,y)的定义域，则赢得矩阵即为其值域；从而，若矩阵对策有解的充要条件是 ai*j*是赢得矩阵的鞍点。第十二页，本课件共有33页2023/3/113例8%求对策的解。设矩阵对策 G=S1,S2;A,其中 S1=1,2,3,4 ,S2=1,2,3,4 ,赢得矩阵为第十三页，本课件共有33页2023/3/114%一般矩阵对策的解可以是不唯一的。当解不唯一时,解之间的关系具有下面两条性质。性质1 无差别性%即若(i1,j1)和(i2,j2)是对策 G 的两个解,则 ai1j1=ai2j2;性质2 可交换性%即若(i1,j1)和(i2,j2)是对策 G 的两个解,则 (i1,j2)
7、和(i2,j1)也是解。第十四页，本课件共有33页2023/3/1152.2 矩阵对策的混合策略定义定义3 设有矩阵对策 G=S1,S2;A,其中 S1=1,2,m ,S2=1,2,n ,A=(aij)mn 记则 S1*和 S2*分别称为局中人和的混合策略集;x S1*和 y S2*分别称为局中人和的混合策略,称(x,y)为一个混合局势,局中人的赢得函数记成新的对策记成 G*=S1*,S2*,E,它是对策 G 的混合扩充。第十五页，本课件共有33页2023/3/116定义定义4 设 G*=S1*,S2*;E 是矩阵对策 G=S1,S2;A的混合扩充,如果记其值为 VG.则称 VG 为对策 G*
8、的值,使上式成立的混合局势(x*,y*)称为 G 在混合策略意义下的解(或简称解),x*和 y*分别称为局中人和 的最优混合策略(或简称最优策略)。第十六页，本课件共有33页2023/3/117定理定理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)第十七页，本课件共有33页2023/3/1182.3 矩阵对策的基本定理两个记号:%当局中人取纯策略 i 时,记其相应的赢得函数为 E(i,y),于是%当局中人 取纯策略
9、 j 时,记其相应的赢得函数为 E(x,j),于是%则有第十八页，本课件共有33页2023/3/119定理定理3 设 x*S1*,y*S2*,则(x*,y*)为 G 的解的充要条件是:对任意 i=1,m 和 j=1,n 有 E(i,y*)E(x*,y*)E(x*,j)证明：%必要性：由定理2有:E(x,y*)E(x*,y*)E(x*,y)，又纯策略只是混合策略特殊情形，所以有 E(i,y*)E(x*,y*)E(x*,j)%充分性：由 E(i,y*)E(x*,y*)E(x*,j)对 i,j 成立，有第十九页，本课件共有33页2023/3/120定理定理4 设 x*S1*,y*S2*,则(x*,y
10、*)为 G 的解的充要条件是:存在数 v,使得 x*和 y*分别是不等式组(1)和(2)的解,且 v=VG。第二十页，本课件共有33页2023/3/121定理4的证明%“”设 x*S1*,y*S2*,(x*,y*)是 G 的解，则由定理3，对 i=1,2,m,j=1,2,n,有%所以由上可知 x*与 y*分别是不等式组(1),(2)的解。第二十一页，本课件共有33页2023/3/122%“”设不等式组(1),(2)的解分别为 x*与 y*,则有%另：%所以有 E(x*,y*)=v,由定理3即知对策 G 有解。第二十二页，本课件共有33页2023/3/123定理定理5 对任一矩阵对策 G=S1,
11、S2;A,一定存在混合策略意义下的解。第二十三页，本课件共有33页2023/3/124定理定理6 设(x*,y*)是矩阵对策 G 的解,v=VG,则(1)若 xi*0,则(2)若 yj*0,则(3)若 则 xi*=0(4)若 则 yj*=0.第二十四页，本课件共有33页2023/3/125证明：%由定义有，%其中 xi*0,i=1,m.%这说明，m 项非负数之和为零，从而和式中每一项均为零。故当有某项中的 xi*0 的话，则与其对应的项必有如下结果(反之亦然)：第二十五页，本课件共有33页2023/3/126%例如，设(x*,y*)是矩阵对策 G 的解,v=VG,若有 x2*0，则有%反之，若
12、有 i=3 使%则有 x3*=0.以此类推。第二十六页，本课件共有33页2023/3/127定理定理7 设有两个矩阵对策 G1=S1,S2;A1 G2=S1,S2;A2 其中 A1=(aij),A2=(aij+L),L 为任一常数,则有(1)VG2=VG1+L(2)T(G1)=T(G2)第二十七页，本课件共有33页2023/3/128定理定理8 设有两个矩阵对策 G1=S1,S2;A G2=S1,S2;A其中 0 为任一常数。则(1)VG2=VG1(2)T(G1)=T(G2)第二十八页，本课件共有33页2023/3/129定理定理9 设 G=S1,S2;A为矩阵对策,且 A=-AT 为反对称矩
13、阵(亦称这种对策为对称对策)。则(1)VG=0(2)T1(G)=T2(G)其中 T1(G)和 T2(G)分别为局中人和的最优策略集。第二十九页，本课件共有33页2023/3/130定义定义5 设有矩阵对策 G=S1,S2;A,其中 S1=1,m,S2=1,n,A=(aij)如果对一切 j=1,n 都有 aij akj,即矩阵 A 的第 i 行元素均大于或等于大于或等于第 k 行的对应元素,则称局中人的纯策略 i 优超于k;同样,若对一切 i=1,m,都有 aij ail,即矩阵 A 的第 j 列元素均小于或等于小于或等于第 l 列的对应元素,则称局中人的纯策略 j 优超于l.第三十页，本课件共
14、有33页2023/3/131定理定理10 设 G=S1,S2;A为矩阵对策,其中 S1=1,m,S2=1,n,A=(aij)如果纯策略 1 被其余纯策略 2,m 中之一所优超,由 G 可得到一新的矩阵对策 G=S1,S2;A,其中 S1=2,m A=(aij)(m1)n,aij=a1j,i=2,m,j=1,n,于是有(1)VG=VG;(2)G 中局中人的最优策略就是其在 G 的最优策略;(3)若(x2*,xm*)T 是G 中局中人的最优策略,则 x*=(0,x2*,xm*)T 便是其在 G 中的最优策略。第三十一页，本课件共有33页2023/3/132推论推论 在定理10 中,若 1 不是为纯策略 2,m 中之一所优超,而是为 2,m 的某个凸线性组合所优超,定理的结论仍然成立。提示%定理10 及其推论给出了一个化简赢得矩阵A 的原则,称之为优超原则。根据这个原则,当局中人的某纯策略 ai 被其他纯策略或纯策略的凸线性组合所优超时,可在矩阵 A 中划去第 i 行而得到一个与原对策 G 等价但赢得矩阵阶数较小的对策 G,而 G 的求解往往比 G 的求解容易些,通过求解 G 而得到 G 的解。类似地,对局中人来说,可以在赢得矩阵A 中划去被其他列或其他列的凸线性组合所优超的那些列。第三十二页，本课件共有33页2023/3/1感感谢谢大大家家观观看看第三十三页，本课件共有33页