• / 60
  • 下载费用:10 金币  

第十二章 对策论.ppt

关 键 词:
第十二章 对策论.ppt
资源描述:
第十二章 对策论,,第一节 引言,对策现象和对策论,对策论又称博奕论或竞赛论(game theory)是研究具有对抗或竞争性质现象的数学理论和方法,是应用数学的一个分支,也是运筹学的一个重要学科,还被认为是经济学研究的一个重要工具。近年来由于对策论在经济管理中的广泛应用而日益受到人们的重视。,对策现象是指具有对抗或竞争性质的现象。,,对策论就是研究在对策现象中各方是否存在最合理的行动方案,以及如何找到合理的行动方案的数学理论与方法。,典型的历史案例—“齐王赛马”,齐王,上马 中马 下马,田忌,上马 中马 下马,各出马一匹进行比赛,田忌策略:,负者要支付胜者千金,上马,下马,中马,上马,下马,中马,对策现象的三要素,局中人(players):指对策中有权决定自己行动方案的对策的参与者。通常用I表示局中人的集合。常常直接用数字标识局中人。对策论关于局中人的一个重要假设是:每个局中人都是“理智的”。,策略(strategies):对策中可供局中人选择的一个实际可行的完整的行动方案。在对策中局中人i的策略集记成Si,一般一个局中人的策略集中至少包含两个策略。一个对策中,由每个局中人所出的策略构成的策略组称为一个局势。设第i个局中人策略记为si,则s=(s1, s2, …, sn)是一个局势,而全部局势的集合可表示为,对策现象的三要素(续),赢的函数(支付函数)(payoff function):对策中当每一个局势s出现后,应该为每个局中人i规定一个赢得值(支付值)Hi(s),显然Hi(s)是定义在S上的函数。,例如在“齐王赛马”中,设s1=(上,中,下)是齐王的一个策略,s2=(中,下,上)是田忌的一个策略,则s1与s2构成了一个局势s12,并且在这一局势中齐王和田忌的赢得值分别为 H1(s12)=1, H2(s12)=-1,一般地,当局中人、策略集、赢得函数这3个要素确定后,一个对策模型也就确定了。,对策问题举例及对策的分类(1),例1 市场购买力争夺问题(p387),市场:下一年的饮食品购买力为4000万元,乡镇企业策略,出售特色饮食品,出售一般饮食品,中心城市企业战略,出售高档饮食品,出售低档饮食品,乡镇企业赢得,2000,3000,1000,3000,对策问题举例及对策的分类(2),例2(p387),局中人:企业I、企业II,策略:企业I在时刻x出售,企业II在时刻y出售,其中x,y[0, 1],赢得函数:在局势(x, y)下企业I的赢得值为,对策问题举例及对策的分类(3),例3 费用分摊问题(p387) 例4 拍卖问题(p387) 例5 囚犯难题(p388),囚犯甲策略,承认,不承认,囚犯乙策略,承认,不承认,(甲赢得,乙赢得),(-7, -7),(0, -9),(-9, 0),(-1, -1),对策问题举例及对策的分类(4),分类:,按局中人的个数:二人对策和多人对策;,按各局中人的赢得函数的代数和是否为零:零和对策和非零和对策;,按局中人之间是否允许合作:合作对策和非合作对策;,按局中人的策略集的元素个数:有限对策和无限对策;,按策略的选择是否与时间无关:静态对策和动态对策;,按模型的数学特征:矩阵对策、连续对策、微分对策、凸对策、随机对策等等,今后我们主要讨论二人有限零和对策(又称为矩阵对策),第二节 矩阵对策,矩阵对策——二人有限零和对策,策略:,,局中人1:,局中人2:,赢得函数值:对于局势,,局中人1:,局中人2:,其中:,称矩阵A=(aij)为局中人1的赢得矩阵,明显地A就是局中人2的支付矩阵。因此对矩阵对策,一旦给出矩阵A,则模型随之确定,矩阵对策的纯策略,一般地,矩阵对策记为G={S1, S2, A},其中S1与S2分别是局中人1和2的策略集。(作为理论探讨实际上并不关心这些策略集中具体有哪些策略,而只关心有几个策略),为了与后面的混合策略区别,这些策略集中的每个策略称为一个纯策略。,例(p389)设有一矩阵对策G={S1, S2, A},其中,矩阵对策的解,局中人1,局中人2,策略3,,,策略3,,策略4,策略1,,局中人如果从自己的角度出发考虑,可见这样做,局中人实际上难以达到使自身利益最大化的目标。因此局中人应该这样考虑每一个策略,当自己采用一个策略时,对方可以肯定会采用某个特定的策略。在此基础上来选择对自己最有利的策略。,矩阵对策的解(续1),从对局中人1的策略来看,对其采用的每个策略,局中人2必定会采用矩阵A中该行最小数对应的策略。,因此局中人1选择其最优策略的方式是:选出A中每行中的最小数,然后再在选出来的数中的最大者对应的策略。也即局中人1选择 对应的策略。,同样,局中人2选择其最优策略的方式是:选出A中每列中的最大数,然后再在选出来的数中的最小者对应的策略。也即局中人1选择 对应的策略。,矩阵对策的解(续2),若在矩阵A中若,则这个数对应的各自的策略所组成的局势就是双方都不得不接受也同意接受的局势。相应的策略就是双方的最优策略。例中局中人1的最优策略为策略2,局中人2的最优策略也是其策略2。,,,矩阵对策的解(续3),定义1 设G={S1, S2, A}为一矩阵对策,其中A=(aij)m×n,若,成立,记其值为Vij,则称Vij为对策的值(也常记为VG),称使得上式成立的纯局势为在纯策略意义下的解(或平衡局势),相应的纯策略称为局中人1和局中人2的最优纯策略。,矩阵对策的解(续4),在例中,可以看到A中平衡局势对应元素a22既是其所在行的最小元素,又是其所在列的最大元素。也就是对所有的i和j,有,定理1 矩阵对策G={S1, S2, A}在纯策略意义下有解(存在平衡局势)的充分必要条件是,矩阵A中存在一个元素,它既是所在行的最小元素又是所在列的最大元素,也即存在 使得,矩阵A中满足上述条件的点 称为鞍点,矩阵对策的解(续5),上述定理的意义是设 是对应着ai*j*的平衡局势,则当局中人1选择策略αi*时,局中人2为了使其所失最小,只能选择策略βj*,否则所失更大。反之亦然。,例(p391)设有矩阵对策G={S1, S2, A}, 其中,易见,因此,都是对策的解,,且VG=5.,矩阵对策的解(续6),上例表明矩阵对策的解可能不是唯一的。若矩阵对策的解不唯一,则解之间具有如下性质。,性质1(无差别性)若 和 是矩阵对策G的两个解,则,性质2(可交换性)若 和 是矩阵对策G的两个解,则 和 也是矩阵对策G的解。,矩阵对策的解(续7),例(p392),局中人1(采购员),,局中人2(自然),,min,-3000 -2500 -2000,max,-1000 -1500 -2000,,,平衡局势为,即采购员最优策略是采购20t煤,矩阵对策的混合策略,在上面的讨论中可以看到,在矩阵对策G={S1, S2, A}中,局中人1能保证的至少赢得是,局中人2能保证的至多所失是,明显地,v1v2,当v1=v2时,矩阵对策G存在纯策略意义下的解,且VG= v1=v2。然而若v1v2,这时按定义,矩阵对策G不存在纯策略意义下的解。,矩阵对策的混合策略(续1),例(p393)设矩阵对策的矩阵是,min,3 4,,max,max,5 6,,min,因此v1=45=v2,于是不存在平衡局势。,由此可见局中人1既可能采用策略1也可能采取策略2,同样局中人2既可能采用1也可能采用2。,矩阵对策的混合策略(续2),既然局中人1没有必然要采用的优势策略,就可以考虑采用一种这样的策略,分别以概率x和(1-x)采用策略1和策略2;同样局中人2也可以这样考虑,分别以概率y和(1-y)采用1和2。局中人这样采用的策略称为混合策略。 例如在上面的对策G中,,可以看成是局中人2的一个混合策略,即局中人以20%的可能性采用策略1而以80%的可能性采用策略2,矩阵对策的混合策略(续3),定义2 设有矩阵对策G={S1, S2, A},其中,记,则分别称 和 为局中人1和局中人2 的混合策略集(或策略集); 和 的元素分别称为局中人1和局中人2的混合策略,由他们的混合策略构成的策略组称为混合局势。,矩阵对策的混合策略(续4),对于一个混合局势(x, y),局中人1的赢得函数值(期望赢得值)为,此外称 为G的混合扩充。 纯策略是混合策略的一种特殊情形。,一个混合策略(x1,…,xm)T可以理解为,若进行多次的对局,它是局中人1取策略1,…,m的频率;若只进行一次对局,则它反映了局中人1对各策略的偏爱程度。,矩阵对策在混合意义下的解,像纯策略的情况一样,若局中人是理智的,则他们会这样考虑自己的策略:当自己采用一个策略时,对方必然采用一个怎样的特定策略,然后据此确定对自己最有利的策略。,例如当局中人1采用策略x时,局中人2为使自己所失最小必定采用满足 的策略,因此局中人1的最优策略就应使,类似地,局中人2的最优策略就应使,矩阵对策在混合意义下的解(续1),定义3 设 是G的混合扩充,如果,记其值为VG,则称VG为对策G的值,称使上式成立的混合局势(x*, y*)为G在混合策略意义下的解(或平衡局势),并分别称x*和y*为局中人1和2的最优混合策略。,今后约定,对矩阵对策G和其混合扩充G*一般不加区别,都用G={S1, S2, A}表示,如果G在纯策略意义下的解不存在,则自然认为讨论的是混合策略意义下的解。,矩阵对策在混合意义下的解(续2),类似定理1,也可以建立混合策略意义下的鞍点型充分必要条件。,定理2 矩阵对策G在混合策略意义下有解的充分必要条件是:存在 使得对任意,例(p394),,矩阵对策在混合意义下的解(续3),取,则,从而,故x*和y*分别是局中人1和2 的最优策略,对策的值(局中人1的期望赢得值)为VG=9/2。,矩阵对策的基本定理,记号,易见E(i, y)是E(x, y)在x=(0,…,0,1,0,…,0)T时的值,即局中人1取纯策略i时的值, 类似地,E(x, j)是局中人2在取纯策略j的值。,第i个,和,矩阵对策的基本定理(续1),定理3 矩阵对策G在混合策略意义下有解的充分必要条件是:存在 使得对任意i=1,2,…m; j=1,2,…,n, 有,与定理2 比较可知定理3大大地简化了局势(x*,y*)是平衡局势的验算工作。理论上,定理2需要无穷多次验算,而定理3只需要经过m×n次验算,矩阵对策的基本定理(续2),定理4 设 则(x*,y*)是矩阵对策G解的充分必要条件是:存在数v 使得x*和y*分别是下面的不等式组的解,矩阵对策的基本定理(续3),将上面的两个不等式组稍做修改为,,,容易看出右边两个线性规划问题互为对偶问题,且都存在可行解。,矩阵对策的基本定理(续4),定理5 任一矩阵对策G={S1, S2, A}一定存在混合意义下的解。,上面的讨论实际上蕴涵了求解矩阵对策的一般方法:对任意矩阵对策问题只要求解线性规划问题,和其对偶问题就可得到局中人1和2的最优策略,从而得到矩阵对策的解。关于具体求解方法后面将进一步介绍。,矩阵对策及其解的基本性质,定理6 设(x*,y*)是矩阵对策G的解,v=VG,则,(1)若 , 则,(2)若 , 则,(3)若 , 则,(3)若 , 则,矩阵对策及其解的基本性质(续1),下面记矩阵对策G的解集为T(G)。,定理7 设有两个矩阵对策G1={S1, S2, A1}, G2={S1, S2, A2}, 其中A1=(aij), A2=(aij+L), L为任一常数,则,(1),(2) T(G1)=T(G2),定理8 设有两个矩阵对策G1={S1, S2, A}, G2={S1, S2, aA}, 其中a0, 为任一常数,则,(1),(2) T(G1)=T(G2),矩阵对策及其解的基本性质(续2),定理9 设G={S1, S2, A}, 其中A=-AT为斜对称矩阵(这样的矩阵对策也称为对称对策),则,(1)VG=0,(2)T1(G)=T2(G),其中T1(G)和T2(G)分别为局中人1和2的最优策略集。,矩阵对策的解法—图解法(1),这种方法适合于求解矩阵对策中有一个局中人只有两个策略的问题。下面通过例子来说明该方法。,例(p398),,,O,I,I,,II,II,1,,,,2,3,11,2,5,7,3,2,1,x,,x,,(x, b1),矩阵对策的解法—图解法(2),,很明显,一般情况下局中人1的赢得值z满足:,z2x+7(1-x),同理 z3x+5(1-x)以及 z11x+2(1-x),于是,z min{2x+7(1-x), 3x+5(1-x), 11x+2(1-x),这表明局中人1的赢得值对应的点必落在图中的阴影区域。,而且局中人1将在区域中找一点使对应的赢得最大。这点就是A,A,,x,矩阵对策的解法—图解法(3),,A,,x,可见局中人1的最优策略就是(x*, 1-x*), 其中x*=OA; 他的最大赢得值就是图中A点的纵坐标VG。通过解下列方程组就可得到x*和VG。,解得x*=3/11, VG=49/11 。从而得到局中人1的最优混合策略为(3/11, 8/11)。,矩阵对策的解法—图解法(4),,A,,x,由图中可以看出局中人2的最优混合策略仅由2和3组成。实际上设 是局中人2的最优混合策略,则因,根据定理6,必有,又因,,3y2+11y3=49/11,5y2+2y3=49/11,y2+y3=1,得局中人2的最优混合策略为(0, 9/11, 2/11),矩阵对策的解法—图解法(5),例(p399),设局中人2的最优混合策略为(y, 1-y), 则当局中人1取策略1时,局中人2的支付为2y+7(1-y),,,O,I,I,,II,II,1,,,2,3,11,2,6,7,3,1,,y,2,一般情况下局中人2的支付不小于2y+7(1-y)。从而局中人2的支付值对应的点落在下阴影区域。,,矩阵对策的解法—图解法(6),,,O,I,I,,II,II,1,,,2,3,11,2,6,7,3,1,,2,,y,明显地,局中人2要适当地选择y*,使得直线y=y*与阴影部分的交点的纵坐标尽可能小。,,,B1,B2,A1,A2,如图可知,A1y* A2, 并且局中人2最小的支付VG=6,由方程组,得A1=1/5, A2=4/9, 因此局中人2的最优混合策略为(y*, 1-y*), 其中1/5 y* 4/9。,矩阵对策的解法—方程组法(1),由定理4知,求矩阵对策的解等价于求解不等式组,由定理6,若在最优策略中有 则上述不等式组的求解又转化为如下的方程组的求解,矩阵对策的解法—方程组法(2),如果这两个方程组存在非负解。则得到矩阵对策问题的解。,如果这两个方程组不存在非负解,则可视具体情况将方程组中的某些等式改为不等式,继续试求解,直到求的矩阵对策的解。,这种方法由于事先假定 因此当最优策略的某些分量实际不为零时,这两个方程组可能无解。,矩阵对策的解法—方程组法(3),但如果矩阵对策中的矩阵为22的矩阵,即,若不存在鞍点,则可以证明最优混合策略中的 均大于零。于是这时的方程组,一定存在严格的非负解(它就是要求的最优策略),矩阵对策的解法—方程组法(4),此外矩阵对策的值此时为,优超原则(1),对于矩阵对策问题,若矩阵A中第i行的各元素均大于或等于第j行的对应元素,则称局中人1的策略i优超于j。当i优超于j时,局中人1在任何情况下将优先使用策略i而不会使用策略j,因此可在矩阵A中将i对应的行去掉。,对于矩阵A的列,若某一列的各元素都小于或等于另一列的对应元素,则称该列对应的策略优超于另一列对应的策略,并且求解时可将矩阵的另一列去掉。,优超原则(2),在求解时,利用优超原则有时可以将较高阶的矩阵化为较低阶的矩阵,从而简化求解。,例(p400)求解矩阵对策G={S1, S2, A}, 其中,优超原则(3),,α3优超于α2 α4优超于α1,β2优超于β3、 β4、 β5,,α3优超于α5,,,累次取优,优超原则(4),这样本例转化为求解如下矩阵对应的对策问题:,由方程组法,只需要解方程组,其非负解为,原问题的一个解为,齐王赛马问题的解(1),齐王赛马问题中两人的策略为,齐王的赢得矩阵为(p389),齐王赛马问题的解(2),显然,齐王赛马问题中的矩阵不存在鞍点,因此不存在纯策略意义上的解。而求混合意义下的解可转化为求解方程组(p402)的问题,方程组的一个解是:xi=1/6 (i=1, 2, …, 6), yj=1/6 (j=1, 2, …, 8)。即双方都以1/6的概率选取每个纯策略,或者说都在六个纯策略中完全随机地选取一个作为最优策略,总的结局是:齐王赢的概率为5/6,赢得的期望为1千金。,但如果田忌可以先观察到齐王的策略,再据此选择自己的策略,则他可以采用下马对上马,上马对中马,中马对下马的方式稳胜齐王。这表明在对策现象中公开策略一方通常是要吃亏的。,矩阵对策的解法—线性规划法(1),由定理5的结论可知矩阵对策的最优解可通过求解如下的互为对偶的线性规划问题得到。,(P),(D),下面先说明它们是互为对偶的线性规划问题,(P)的变量:,目标函数系数:,,系数矩阵,右端常数,,矩阵对策的解法—线性规划法(2),记对偶变量为 则对偶问题为,目标函数:,约束条件:,变量约束:,令 yj = -zj (j=1,2,…,n) 就得到(D),矩阵对策的解法—线性规划法(3),为了方便地求解上述线性规划问题,在(P)中作变换,则(P)约束条件化为,再注意到max w等价于min{1/w}, 故(P)可以写成如下的等价形式,矩阵对策的解法—线性规划法(4),(P’),类似地,若进行变换,则(D)可以化为等价形式,(D’),矩阵对策的解法—线性规划法(5),例(p403)利用线性规划法求解矩阵对策问题,其中矩阵为,解:需要求解两个互为对偶的线性规划,(P),(D),下面用单纯形法求解(D),矩阵对策的解法—线性规划法(6),矩阵对策的解法—线性规划法(7),可见上述线性规划问题的解分别为,于是局中人1和2的最优混合策略分别为,局中人1:,局中人2:,,矩阵对策的值为:,矩阵对策的求解流程,写出矩阵A,利用优超原则变换矩阵,找出鞍点并求出纯策略意义下的最优解,用方程组法求解,用图解法求解,用线性规划法求解,Y,N,Y,Y,N,N,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:第十二章 对策论.ppt
链接地址:https://www.weizhuannet.com/p-10071091.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开