运筹学5 2

5.2两人有限零和对策5.2.1两人有限零和对策的数学模型5.2.2在纯策略下有解对策的解法5.2.3具有混合策略的对策5.2.1两人有限零和对策的数学模型1.“齐王田忌”赛马模型设每场比赛中，赢者得1分，负者–1分（和局各为0分）即每一个局势下，两人赢得函数之和为零，齐王赢得函数 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 为：田齐上下下上中中王忌策赢中上中下上下齐得略下中上中下上王策略（上中下）3111-11（上下中）13111-1（中上下）1-13111（中下上）-111311（下上中）111-131（下中上）11-1113()()((()()))称矩阵A为赢得矩阵：?3111?1311??1?131A???1113??111?1???11?11?11??1?1?11??11?31??13??2.一般两人有限零和对策的模型(1)局中人I的纯策略为?1，?，?m;局中人II的纯策略为?1,?,?n,(n不一定等于m),各自的策略集为SI???1，?2，?，?m?,SII???1,?2,?,?n?(2)赢得函数（离散的）aij:在局势（?i,?j）下，局中人I的赢得为aij,当然局中人II的赢得为?aij。形成局中人I的赢得矩阵为:?a11a12?a1n??a?a?a21222n??A?(aij)m?n??????????am1am2?amn?显然局中人II的赢得矩阵为?A.(3)两人有限零和对策数学模型的标记：???I，II；SI,SII；A?或???SI,SII;A?3.实例（例1）今有甲、乙两厂生产同一种产品，它们都想通过内部改革挖潜，获得更多的市场份额。已知两厂分别都有三个策略措施，据预测，当双方采取不同的策略措施后两厂的市场占有份额变动情况如表5.2所示。表5.2乙份甲厂产额品厂策变市动(%)场略甲厂策略?1?2?3?1?2?310-131210-5685???S甲，S乙；A?，这也是两人有限零和对策，数学模型为其中S甲???1，?2，?3?，S乙???1，?2，?3?分别表示甲、乙两厂的策略集，?10?13???A??1210?5?,??685??表示甲厂的赢得矩阵。当S甲、S乙和A确定后，局中人甲、乙应如何“理智地”选取对自己最为有利的策略，以谋取最大的赢得（或最少损失），须认真地分析。5.2.2在纯策略下有解对策的解法1.通过例1分析，导出思想甲企业在选纯策略?2时，可能赢得最大12分，而乙可能失去12分，但理智的乙企业会考虑到这一点，乙会采取策略?3，使甲失去最多(5分)，而乙此时反会赢得5分。如甲考虑到乙会出策略?3时，他会采取?3，使其赢得最多5分。所以局中人在选每一个策略时，应考虑到对方会使自己损失最大（赢得最少）然后在最大损失中求胜（最少赢得中有最大收获）。甲企业：?1?最少赢得min?10,?1,3???1?2?最少赢得min?12,10,?5???5;?3?最少赢得min?6,8,5??5;考虑最少赢得中最佳决策：max??1,?5,5??5甲企业应选最优策略?3，此时即使乙最聪明，也可赢得5分（也可能多于5分），乙企业：?1?最大的损失max?10,12,6??12;?2?最大的损失max??1,10,8??10;?3?最大的损失max?3,?5,5??5;考虑最大损失中最少者（将最大损失控制在最小）min?12,10,5??5乙企业应选最优策略?3.2.一般对策???SI，SII；A?(1)如maxminaij?minmaxaij?ai*j*,ijji称局势（?i*,?j*）为?的在纯策略下的解(或均衡局势),?i,?j分别称为局中人I和II的纯最优策略,**ai*j*称为?的（最优）值，也称ai*j*为矩阵A的鞍点。注：minaij????第i行求最小，jmaxaij????第j列求最大i(2)求均衡局势的矩阵标号法：Step1.将赢得矩阵A中各行的最小元素标上圆圈a；Step2.将A中各列的最大元素加上方框a；Step3.如存在同时标上圆圈和方框的元素ai*j*，则最优值为ai*j*,即为矩阵A的鞍点。例??A????10126?1108???5?，?5?3ai*j*?a33?5???B?????65084423??64?73??2?1??543.均衡局势存在性定理1：在纯策略下矩阵对策??（SI，SII；A）有解（存在均衡局势）当且仅当存在纯局势（?i*,?j*）使得aij*?ai*j*?ai*j,?i?1~m,j?1~n4.纯策略下对策解的性质：设(?i1,?j1),(?i2,?j2)为Γ=(SⅠ,SⅡ;A)的两个解，则：①ai1j1=ai2j2(无差异性)②(?i1,?j2)及(?i2,?j1)也是Γ的解。(可交换性)本段作业：p151.5.5,5.85.8(a,b)交叉处改为(a2,b2)交叉处5.2.3具有混合策略的对策引子：对于一般的Γ=(SⅠ,S;A)，不一定存在均衡Ⅱ局势，如“齐王田忌赛马”。因此必须扩充解的意义，研究一种混合策略，即局中人选取策略?i是随机的，由其概率xi控制。1.定义设对策Γ=(SⅠ,SⅡ;A),SⅠ={?1,?,?m},SⅡ={?1,?,?n},引进mm*SⅠ={x?(x1,x2,?,xm)?E:xi?0,i?1,2,?,m,?xi?1}SⅡ*={y?(y1,y2,?,yn)?E:yj?0,j?1,2,?,n,?yj?1}nj?1ni?1①SⅠ*,SⅡ*称为Ⅰ和Ⅱ的混合策略集；(x,y)称为混合局势。②x∈SⅠ*,y∈SⅡ*分别称为Ⅰ和Ⅱ的混合策略(策略)③混合赢得函数的期望值(出现纯局势(?i,?j)的概率为xiyj)E(x,y)???aijxiyj?xAyi?1j?1mnT④??(S,S;E)为?的混合扩充.*S注：x∈I表示局中人Ⅰ以概率xi选纯策略?i**I*II2.混合对策解的定义如果maxminE(x,y)=minmaxE(x,y)=E(x*,y*)(5.3a)****x∈SⅠy∈SⅡy∈SⅡx∈SⅠ成立，称(x*,y*)为Γ在混合策略下的解，VΓ=E(x*,y*)称为对策Γ在混合策略下的值(简称为值)，x*,y*分别称为局中人Ⅰ和Ⅱ的最优混合策略(简称最优策略)3.混合对策解的存在性定理2.(对策基本定理)任何一个矩阵对策Γ=(SⅠ,SⅡ;A)一定存在混合策略下的解(x*,y*)。( 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 较复杂)定理2的作用：①解决解的存在性；②在求(x*,y*)时，只要解(5.3a)一边即可，不必两边同时解。?97?例3.设Γ=(SⅠ,SⅡ;A)中A??,求其最优混合策略。??28?解：*SⅠ={x?(x1,x2):x1,x2?0,x1?x2?1}?x2?1?x1SⅡ*={y?(y1,y2):y1,y2?0,y1?y2?1}?y2?1?y1?y1?E(x,y)?(x1,1?x1)A??1?y???8x1y1?x1?6y1?8?(8x1?6)y1?(8?x1)1???E(x,y)63令*?8x1?6?0?x1???y184?E(x,y)1令*?8y1?1?0?y1??x1831*17***x2?1?x1?1??,y2?1?y1?1??448831*17*x?(,),y?(,)44881VΓ=74正确求解：~E(x1)?min{E(x,y)?(8x1?6)y1?(8?x1):0?y1?1}*31??y?0,13，此时解1x??8?x1?8??7,当1444???8?x当x1?3，此时解y1*?041?*3?7x1?2x?当14，此时解y1?131而且8?x1?8??7，当x1?344431，当x?37x1?2?7??2?714441~3~故max{E(x1):0?x1?1}?7?E()44*13*1*1**于是x?,x2?,y?(y1,1?y1),V??7444局中人Ⅱ有无穷多个最优混合策略。4.混合对策解的充要条件定理3.设x*∈SⅠ*，y*∈SⅡ*，则(x*,y*)为Γ在混合策略下的解当且仅当E(x,y)?E(x,y)?E(x,y),?x∈SⅠ*，y∈SⅡ*(5.3)定理4.(x*,y*)为对策的解当且仅当****E(?i,y)?E(x,y)?E(x,?j),??i∈SⅠ，?j∈SⅡ(5.4)其中E(?i,y*)?E(ei,y*)?eiA(y*)T*~T~E(x,?j)?E(x,ej)?xAejm~nei?(0,?,0,1,?,0)?E,ej?(0,?,0,1,0,?0)?E******定理5.(x*,y*)为对策的解当且仅当存在数v，使得x*和y*分别是不等式组???和不等式组?a?xi?1mmijii?1mx?v,j?1,2,?,n,?xA?ve(5.5)i?1,xi?0,i?1,2,?,m?j?1?n??yjj?1Tay?v,i?1,2,?,m,?Ay?ve?ijj(5.6)?1,yj?0,j?1,2,?,n**的解，此时v?V??E(x,y)注：该定理提供求解混合对策的一种方法。例5.利用定理5求解“齐王田忌赛马”对策。(p128)?31111?1??1311?11????1?13111?A?????111311??11?1131?????111?113??解：?xA?ve?6????xi?1,xi?0?i?1?3x1?x2?x3?x4?x5?x6?v?x?3x?x?x?x?x?v23456?1?x1?x2?3x3?x4?x5?x6?v??x1?x2?x3?3x4?x5?x6?v?x?x?x?x?3x?x?v123456???x1?x2?x3?x4?x5?3x6?v??x1?x2?x3?x4?x5?x6?1?x?0,(i?1,2,?,6)?i由?Ay?ve?6????yi?1,yj?0?i?1T?3y1?y2?y3?y4?y5?y6?v?y?3y?y?y?y?y?v23456?1?y1?y2?3y3?y4?y5?y6?v??y1?y2?y3?3y4?y5?y6?v?y?y?y?y?3y?y?v123456???y1?y2?y3?y4?y5?3y6?v??y1?y2?y3?y4?y5?y6?1?y?0,(j?1,2,?,6)?i我们假设各组不等式的6个不等式均成为等式，然后相加，得?6(x1?x2???x6)?6v?6(y1?y2???y6)?66?v?1?x?y?1??jj?j?1?j?1111111取x?y?(,,,,,)666666**由定理5可知，(x*,y*)为最优解作业：p152.5.9①(不用图解法)提示：用（5.5）及（5.6）式或（5.3a）式