[管理学]93第十五章 对策论.ppt

第十五章 对策论,第十五章 对策论,15.1 对策论的基本概念 15.2 矩阵对策的最优纯策略 15.3 矩阵对策的混合策略 15.4 求解矩阵对策中的计算技巧(自学) 15.5 两人有限非零和对策(自学),引言,在日常生活中，经常可以看到一些具有相互斗争或竞争性质的行为，如下棋、打牌、体育比赛等。还有企业间的竞争、军队或国家间的战争、政治斗争等，都具有对抗的性质。在这类行为中，各方具有不同的目标和利益。为实现自己的目标和利益，各方必须考虑对手可能采取的行动方案，并力图选择对自己最为有利或最为合理的行动方案。 这种具有竞争或对抗性质的行为称为对策行为。这种研究对策的理论与方法,叫做对策论,也叫博弈论（Game Theory）,对策论是运筹学的重要分支，最早研究的问题是对抗或竞争中的各方所应采取的策略以及由此得到的结果，并给出策略优劣的分析。研究方法是：先构造出所论冲突的数学模型，然后用数学方法加以分析、比较、计算。对策论诞生于1927年，由大数学家冯诺伊曼创立。冯诺伊曼认识到经济与政治中的某些决策条件在数学上与某些策略对策等价，所以从分析这些对策中所学到的东西可以直接应用于现实生活中的决策。,引言,冯诺伊曼 (1903-1957),对策论是研究具有斗争性质现象的数学理论和方法，它是运筹学的一个重要分支。最早的运筹学思想可以追溯到战国时期的齐王赛马，近年来运筹学思想普遍运用到经济学中，用于解释一些经济现象和做出最好的经济决策。事实上，经济学和对策 论的研究模式都是强调个人理性，在给定的约束条件下追求效用最大化，1994年诺贝尔经济学奖授予了三位博奕论专家：纳什(Nash)、塞尔腾(Selten)和豪尔沙尼(Harsanyi)，其中最重要的原因之一是他们在非合作博奕论方面作出了突出的贡献。,引言,我国战国时期的“田忌齐王赛马”就是典型的对策行为,齐王：上、 中、 下 田忌：上、 中、 下,齐王：上、 中、 下 田忌：上、 中、 下,齐王3:0取胜,田忌2:1取胜,对策问题各种各样，所以对策模型也千差万别，但本质上都包括三个基本要素： 局中人、策略集、赢得函数 (1)局中人 （Player）： 在一个对策行为中，有权决定自己行动方案的对策参加者,称为局中人。局中人可以是人，也可以是集团，如齐王赛马的齐王和田忌分别都是局中人；在人与自然的斗争中，人和自然都是局中人。通常用I表示局中人集合，如果有n个局中人，则I=1,2,n。一般要求一个对策中至少有两个局中人。局中人总是被假定是聪明且有理智的。, 15.1 对策论的基本概念,(2)策略集 （Strategy）：对策中可供局中人选择的一个实际可行的完整的行动方案，称为一个（纯）策略； 一个局中人全体策略构成的集合，称为此局中人的策略集。参加对策的每一局中人iI的策略集记为Si。一般每一局中人的策略集中至少应包括两个（纯）策略。 如田忌齐王赛马中，若用（上、中、下）表示以上马、中马、下马依次参赛，就是一个纯策略。 齐王与田忌的策略集中，各自都有六个纯策略： S1=(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、上、中),(下、中、上) S2=(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、上、中),(下、中、上), 15.1 对策论的基本概念,(3)赢得函数 （支付函数 Score）： 局势：对策中，每一局中人所选定策略形成的策略组合称一个局势。 设局中人1从自己的策略集S1=1,2 ,m中选定策略i，局中人2从自己的策略集S2=1, 2 , n选定策略j，则S=(i, j)就构成两人对策中的一个局势。 在n个对策中，设si表示第i局中人的一个策略，则n个局中人的策略组合形成的局势为S=(s1,s2,sn)。 赢得函数：当一个局势S出现后，各局中人都有自己的结果（得失），记为Hi(S)，它表示第i局中人的赢得（支付）值。显然Hi(S)是局势S的函数,称为局中人i的赢得函数。, 15.1 对策论的基本概念,例如在“齐王赛马”中，局中人集合I=1,2； 齐王的策略集用S1=1,6表示 田忌的策略集用S2=1,6表示。 假定每胜一局赢得1分，输一局得-1分 如在1=(上、中、下)，1=(上、中、下)构成的局势 S=1, 1下 ： 齐王的赢得为H1(S)=3 田忌的赢得为H2(S)=-3,3 1 1 1 1 -1 1 3 1 1 -1 1 1 -1 3 1 1 1 -1 1 1 3 1 1 1 1 1 -1 3 1 1 1 -1 1 1 3,2 (上 下 中),3 (中 上 下),4 (中 下上),5 (下中上),1 (上 中 下),6 (下上中),1 (上 中 下),2 (上 下 中),3 (中 上 下),4 (中 下上),5 (下上 中),6 (下 中上),齐王的赢得矩阵为,齐王的策略,田忌的策略,对策行为的分类,纯策略对策 混合策略对策,两人有限零和对策,本章研究对象 两人有限零和对策(即矩阵对策),2个局中人； 每个局中人策略集的策略数目都是有限的; 每一局势的对策都有确定的益损值； 同一局势的两个局中人的益损值之和为零, 15.2 矩阵对策的最优纯策略,一、矩阵对策问题数学模型的建立 两人有限零和对策(矩阵对策)的数学模型为： =,;S1,S2,A 其中表示第一个居中人， 表示第二个居中人；S1=1,2,m，S2=1, 2, , n分别为局中人和的策略集，A=(aij)mxn为局中人的赢得矩阵，由于假定对策的结果为零和，所以局中人的羸得矩阵为-A。,“田忌齐王赛马”对策问题的数学模型如下： = ,; S1,S2; A 表示齐王 表示田忌 S1=1,6表示齐王的策略集合; S2=1,6表示田忌的策略集合 其中i，i (上、中、下),(上、下、中),(中、上、下), (中、下、上),(下、上、中),(下、中、上) A表示齐王的赢得矩阵,例题一,例题二,某单位采购员在秋天决定冬季取暖用煤的储量问题。已知在正常的冬季气温条件下要消耗15吨煤，在较暖与较冷的气温条件下要消耗10吨和20吨。假定冬季的煤价随天气寒冷程度而有所变化，在较暖、正常、较冷的气候条件下每吨煤价分别为10元、15元、20元，又设秋季时煤价为每吨10元。在没有关于当年冬季准确的气象预报的条件下，秋季储煤多少吨能使单位的支出量少？建立该问题的对策数学模型。,例题二,解：将该问题看成对策问题,其数学模型为： = ,;S1,S2;A 其中表示采购员 表示冬天的天气 S1表示采购员在秋季购买煤的数量S1 =10, 15 ,20 S2表示冬季气候状况S2=较暖、正常、较冷 A表示采购员购煤的支出费用,例题二,-100 -175 -300 -150 -150 -250 -200 -200 -200,10吨 15吨 20吨,较暖 正常 较冷,A=,冬季单价: 10 15 20,秋季单价: 10元,课堂练习,甲、乙双方谈判签订一项合同，甲方的最后要价是25万元，而乙方的出价是20万元，谈判陷于僵局，为了打破僵局，双方约定，再各报一个价（必须报整数价格），以下述价格成交：谁让步多，取谁出的价，如果双方让步相同，则取双方报价的中间值，问甲、乙双方应如何报价？最后的成交价是多少？(写出此对策问题的三要素或者说建立该问题的数学模型),解： 将该问题看成对策问题,其数学模型为: = ,;S1,S2;A 其中表示甲方 表示乙方 S1表示甲方报价，分别为 S1=1, 2,3 ,4=21，22，23，24 S2表示乙方报价，分别为 S2=1, 2, 3 , 4 =21，22，23，24 A表示成交价格矩阵（见下页）,21 21 21 22.5 22 22 22.5 24 23 22.5 23 24 22.5 22 23 24,21 22 23 24,甲25,乙20,1 2 3 4,4 3 2 1,21 22 23 24,差价,A=,二、矩阵对策在纯策略下有解的解法,解法的基本思想是： 双方都立足在最不利的情况下争取最好的结果 最大最小原则,例题一,甲、乙双方谈判签订一项合同，甲方的最后要价是25万元，而乙方的出价是20万元，谈判陷于僵局，为了打破僵局，双方约定，再各报一个价（必须报整数价格），以下述价格成交：谁让步多，取谁出的价，如果双方让步相同，则取双方报价的中间值，问甲、乙双方应如何报价？最后的成交价是多少？ 写出此对策问题的三要素或者说建立该问题的数学模型； 该对策问题是否存在纯策略意义下的平衡解，如果存在，解为多少？,21 21 21 22.5 22 22 22.5 24 23 22.5 23 24 22.5 22 23 24,21 22 22.5 22,23 22.5 23 24,甲方25,乙方20,max,max,min,min,22.5,22.5,21 22 23 24,（2）所以该对策问题存在纯策略意义下的平衡解. 甲方报价23万元,乙方报价22万元 最后的成交价格是22.5万元,A=,21 22 23 24,例题二,某单位采购员在秋天决定冬季取暖用煤的储量问题。已知在正常的冬季气温条件下要消耗15吨煤，在较暖与较冷的气温条件下要消耗10吨和20吨。假定冬季的煤价随天气寒冷程度而有所变化，在较暖、正常、较冷的气候条件下每吨煤价分别为10元、15元、20元，又设秋季时煤价为每吨10元。在没有关于当年冬季准确的气象预报的条件下，秋季储煤多少吨能使单位的支出量少？ 写出此对策问题的三要素或者说建立该问题的数学模型； 该对策问题是否存在纯策略意义下的平衡解，如果存在，解为多少？,-100 -175 -300 -150 -150 -250 -200 -200 -200,10吨 15吨 20吨,较暖 正常 较冷,A=,（2）可见该对策问题存在纯策略意义下的平衡解. 采购员秋季购买20吨煤最稳妥 花费的费用为200万元,-100 -150 -200,max,max,min,-200,-200,-300 -250 -200,min,a11 a12 . a1j . a1n a21 a22 . a2j . a2n ai1 ai2 . aij . ain am1 am2 . amj . amn,a1c a2e aij amd,ak1 ah2 . aij . atn,方,方,max,max,min,min,A=,理论总结,可见居中人的赢得v1=maxminaij,居中人 的损失v2=minmaxaij,当v1=v2时,该点称为鞍点即为纯策略意义下的平衡解; 通常在具有鞍点的对策问题中,称为该矩阵对策具有纯策略意义下的平衡解, 1 2 i m, 1 2 . j . n,最优解为( i， j) 最优值为aij,v1,v2,课堂练习,P368 1、2,该矩阵对策在纯策略下无解。也就是说用最大最小原则来选取各自的纯策略都不会是稳定的，此时求解矩阵对策的混合策略,15.3 矩阵对策的混合策略,在具有鞍点的矩阵对策中,居中人的赢得v1=maxminaij,居中人 的损失v2=minmaxaij且v1=v2。但一般情况下却总有v1不等于v2 例如,9 7 2 8,A=,9 8,max,max,min,7,8,7 2,min,在上述双方都不能固定采用任何一个纯策略下，必须随机地选取自己的各个纯策略，使双方捉摸不到自己使用的策略，以求得自己的期望赢得最大（或期望损失最小）。,例如,9 7 2 8,1 2,1 2,x1 x2 ,y1 y2 ,方,方,假设x1 ，x2分别表示方选取1，2纯策略的概率，y1 y2 分别表示方选取1，2纯策略的概率，即为混合策略,9 7 2 8,9x1+2x2v 7x1+8x2v,x1 x2,局中人使用1的概率为x1 ，使用2的概率为x2 ，则 x1 + x2 =1 当局中人使用1策略时，局中人的平均赢得为： 9x1 +2x2 假设局中人期望赢得的平均值为V，此时 9x1 +2x2 V 同理当局中人 使用2策略时，局中人的平均赢得为： 7x1 +8x2 7x1 +8x2 V,求解最优混合策略的思路,1 2,1 2,此时应该,minZ=x1+x2 9x1+2x21 7x1+8x21 x1,x2 0,令x1 = x1 / V ， x2 = x2 / V 9x1 +2x2 V变为9x1+2x2 1 7x1+8x2 V变为7x1+8x2 1 又因为x1 + x2 =1所以x1+ x2=1/ V 对来说，期望V值越大越好，也就是说期望1/ V的值越小越好，于是建立起求的最优混合策略的线性规划数学模型：,求解最优混合策略的思路,9x1+2x2v 7x1+8x2v,9 7 2 8,9y1+7y2v 2y1+8y2 v,y1 y2,局中人 使用 的概率为y1 ，使用2的概率为y2 ，则 y1 + y2 =1 当局中人使用1策略时，局中人 的平均损失为： 9y1 +7y2 假设局中人期望赢得的平均值为V，此时 9y1 +7y2 V 同理当局中人 使用2策略时，局中人 的平均损失为： 2y1 +8y2 2y1 +8y2 V,同理求解的最优混合策略,1 2,1 2,此时应该,maxW=y1+y2 9y1+7y2 1 2y1+8y2 1 y1,y2 0,令y1 = y1 / V ， y2 = y2 / V 9y1 +7y2 V变为9y1+7y2 1 2y1+8y2 V变为2y1+8y2 1 又因为y1 +y2 =1所以y1+ y2=1/ V 对来说，期望V值越小越好，也就是说期望1/ V的值越大越好，于是建立起求的最优混合策略的线性规划数学模型：,同理求解的最优混合策略,9y1+7y2v 2y1+8y2 v,minZ=x1+x2 9x1+2x21 7x1+8x21 x1,x2 0,maxW=y1+y2 9y1+7y21 2y1+8y21 y1,y2 0,x1 x2 ,y1 y2 ,又令,总之,令x1 ，x2分别表示方选取1，2纯策略的概率 y1 ，y2分别表示方选取1，2纯策略的概率,则：,可见是一组互为对偶的对称性线性规划问题,x1 = x1 / v x2 = x2 / v y1 = y1 / v y2 = y2 /v,a11 a12 . a1j . a1n a21 a22 . a2j . a2n ai1 ai2 . aij . ain am1 am2 . amj . amn,x1 x2 xi xm,y1 y2 . yj . yn,方,方,A=,理论总结,如果是不具有鞍点的对策问题,求解该矩阵对策最优混合策略的解,令x1 ，x2xm 分别表示方选取1， 2m纯策略的概率; y1 ，y2 yn 分别表示方选取1，2 n纯策略的概率，则x1 + x2 +.+ xm =1, y1 + y2 +.+ yn =1, 1 2 i m, 1 2 . j . n,a11 x1 + a21 x2 +.+ am1 xm v a12 x1 + a22 x2 +.+ am2 xm v a1n x1 + a2n x2 +.+ amn xm v x1,x2 , , xm 0,假设局中人期望赢得的平均值为V （v0），则：,a11 y1 + a12 y2 +. +a1n yn v a21 y1 + a22 y2 +.+ a2n yn v am1 y1 + am2 y2 +.+ amn yn v y1,y2 , , yn 0,居中人,居中人,作如下变换,令xi = xi / V yj = yj / V 则：,minZ= x1 + x2 +.+ xm a11 x1 + a21 x2 +.+ am1 xm 1 a12 x1 + a22 x2 +.+ am2 xm 1 a1n x1 + a2n x2 +.+ amn xm 1 x1,x2 , , xm 0,maxW= y1 + y2 +. + yn a11 y1 + a12 y2 +. +a1n yn 1 a21 y1 + a22 y2 +.+ a2n yn 1 am1 y1 + am2 y2 +.+ amn yn 1 y1,y2 , , yn 0,一组互为对偶的对称性线性规划问题,居中人,居中人,最优混合策略的求解,利用单纯型法求出x1,x2 , , xm 后，根据 x1+x2 + + xm =1/v，得出v 再由xi = xi / v，即xi = v xi得xi （i=1,2,m）即方选取各纯策略的概率，也就是居中人的最优混合策略 利用最终单纯型表的检验数得出y1,y2 , , yn 后，再由yj = yj / v，即yj = vyj得yj (j=1,2,n)即方选取各纯策略的概率，也就是居中人 的最优混合策略 二者具有相同的最优值，即1/v,对策问题的题型,写出此对策问题的三要素(或建立此对策问题的数学模型)； 该对策问题是否存在纯策略意义下的平衡解,如果存在,给出问题的最优策略?如果不存在,请将此对策问题对策双方的最优混合策略表示为一个互为对偶的线性规划模型 该对策问题是否存在鞍点,如果存在,给出问题的最优策略?如果不存在,请将此对策问题对策双方的最优混合策略表示为一个互为对偶的线性规划模型 已知甲方的最优混合策略为(0.8, 0.2, 0 ),请采用对偶性质求出乙方的最优混合策略及甲方的期望决策值. 求对策问题对策双方的混合策略(单纯形法),1、写出此对策问题的数学模型； 2、此对策问题是否存在纯策略意义下的平衡解？如果存在，求此纯策略意义下的平衡解；如果不存在，请将此对策问题对策双方的最优混合策略表示为一个互为对偶的线性规划模型,现有两家企业相互竞争同一产品市场，企业A有4个销售渠道，企业B有5个销售渠道。已经算出当双方采取不同的策略时，A方所能获得的利润：,综合练习题目,解：1、对策问题的数学模型如下： = ,;S1,S2;A 其中表示企业A 表示企业B S1表示企业A的销售渠道，S1=1, 2,3 ,4 S2表示企业B的销售渠道，S2=1, 2, 3 , 4, 5 A表示企业A所能获得的利润：,-3 2 2 1 1 1 -3 -1 2 0 -2 4 3 3 2 3 -1 5 4 1,A=,A=, 1 2 3 4,1 2 3 4 5,-3 2 2 1 1 1 -3 -1 2 0 -2 4 3 3 2 3 -1 5 4 1,2、,-3 -3 -2 -1,3 4 5 4 2,max,max,min,min,-1,2,可见v1=maxminaij=-1, v2=minmaxaij=2,因为v1不等于v2，所以该对策问题不存在鞍点即原问题不具有纯策略意义下的平衡解，需要求解最优混合策略的解,x1 x2 x3 x4,y1 y2 y3 y4 y5,A=, 1 2 3 4,1 2 3 4 5,-3 2 2 1 1 1 -3 -1 2 0 -2 4 3 3 2 3 -1 5 4 1,令x1 ，x2，x3 ，x4分别表示企业A选取1，2 ，3 ，4 纯策略的概率; y1， y2 ， y3 ， y4 ， y5 分别表示企业B选取1，2 ,3 ，4 ,5纯策略的概率,假设企业A期望获得的平均利润为V 令x i = xi / V (i=1,2,3,4) yj = yj / V (j=1,2,3,4,5),minZ= x1 + x2 +x3 + x4 -3 x1 + x2 -2x3 + 3x4 1 2 x1 -3x2 +4x3- x4 1 2 x1 - x2 +3x3+5x4 1 x1 +2x2 +3x3+4x4 1 x1 +2 x3 +x4 1 x1,x2 , x3 , x4 0,maxW= y1 + y2 +y3 + y4 + y5 3 y1 + 2 y2 + 2 y3 +1 y4 + y5 1 y1 -3 y2 - y3 +2y4 1 -2y1 + 4 y2 + 3 y3 +3 y4 + 2y5 1 3 y1 - y2 + 5 y3 +4y4 + y5 1 y1,y2 , y3 , y4,y5 0,企业A,企业B,对策双方的最优混合策略表示为如下一个互为对偶的线性规划模型：,课后作业,P268 1、 2、3、4,谢 谢！,本章结束,以下自学,在矩阵对策G=S1,S2,A,S1= 1,2 ,3 ,4 ,S2= 1, 2 ,3中，关于局中人1某个混合策略的意义，有以下解释，其中正确的是,(A)交替使用每一个纯策略； (B)使用某一个纯策略的概率； (C)使用每一个纯策略i,(i=1,2,3,4)的概率所构成的概率向量； (D)各纯策略的线性组合,二、矩阵对策在纯策略下有解的解法,解：,1.解法的思想： 双方都立足在不利的情况下争取最好的结果最大最小原则。 例 求解矩阵对策 =S1,S2;A，其中:,例题一,甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看成一种策略，双方各选一种策略参赛，比赛共赛三局，规定每局胜者得1分，输者得-1分,S1=1，2 ，3 分别表示甲队三种不同的阵容 S1=1，2 ，3 分别表示乙队三种不同的阵容 根据以往比赛得分资料，可得甲队的赢得矩阵为A，如下所示：,试问这次比赛各队应采用哪种阵容上场最为稳妥。,A =,A =,min 1 -3 -1,max 3 1 3,max1,min 1,所以这次比赛甲队应采用1阵容上场，乙队应采用2阵容上场最为稳妥。,例题一,甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看成一种策略，双方各选一种策略参赛，比赛共赛三局，规定每局胜者得1分，输者得-1分,S1=1，2 ，3 分别表示甲队三种不同的阵容 S2=1，2 ，3 分别表示乙队三种不同的阵容 根据以往比赛得分资料，可得甲队的赢得矩阵为A，如下所示：,试问这次比赛各队应采用哪种阵容上场最为稳妥。,A =,二、在纯策略下有解的矩阵对策的解法,解：,1.解法的思想： 双方都立足在不利的情况下争取最好的结果最大最小原则。 例 求解矩阵对策 =S1,S2;A，其中:,3.方法步骤： 上例求解过程可简单的表述如下：,其步骤是： 第一步：分别确定A各行中的最小值，并在该数字上加圈表示；,2.在矩阵对策中， 若 成立，则称ai*j*为对策的值，记为V=ai*j*。称使上式成立的纯局势(i*,j*)为对策在纯策略下的解（亦称均衡局势）。i*和j*分别称为局中人和的最优纯策略。,第二步：分别确定A各列中的最大值，并在该数字上加框表示；,第三步：若A中的某元素同时被圈和框住，则该元素即为对策的值，该元素所在的行和列对应的策略则分别为局中人和的最优纯策略，并由最优纯策略组成了对策的解。 因此上例对策的值V=2，对策的解为(2,2)，2,2分别是局中人和的最优纯策略。 在纯策略下有解的矩阵对策中，值ai*j*既是所在行的最小值，又是所在列的最大值，称其为鞍点。所以这类矩阵对策又称为有鞍点的对策。这个事实可推广到一般，即 在纯策略下矩阵对策 =S1,S2;A有解的充要条件是：存在纯局势(i*,j*)，使得对于一切的i=1,2m,j=1,2n均有,aij*ai*j*ai*j,矩阵对策的解可以不唯一。,例2 求下列矩阵对策的解,在此例中,对策的解不唯一.当解不唯一时,解之间的关系具有如下性质:,(1)无差别性:即若(i1,j1),和(i2,j2) 是对策的两个解，则,（2）可交换性：即若(i1,j1),和(i2,j2) 是对策的两个解，则(i1,j2),和(i2,j1) 也是对策的两个解。,一、混合策略和混合局势,（X，Y）称为混合局势。,二、混合扩充和混合策略下的解 当X，Y由局中人1和局中人2分别独立决定以后，纯局势 以概率xiyj出现，于是局中人1在混合策略下赢得的数学期望为,n,在纯策略下矩阵对策的解是混合策略下矩阵对策解的特殊情况。 三、基本定理（不加证明） （1）在混合扩充下，任何矩阵对策必有解； （2）在混合策略下，(X*,Y*)是对策解的充要条件是：,类似于纯策略的情况，若,则称E（X*，Y*）为对策 的值，称（X*，Y*）为对策 在混合策略下的解，X*和Y*分别为局中人1和局中人2的最优混合策略。,其等价形式是:,作为应用，给出（2）的另一等价形式： （3）(X*,Y*)为对策的解的充要条件是存在数v，使X*,Y*分别是下面两个不等式组的解：,n,其中v为对策的值。作如下变换，（设v0）,可见是一组互为对偶的对称性线性规划问题,（1）,（2）,四、矩阵对策的混合策略的解法,其中v为对策的值。作如下变换，（设v0）,于是不等式组（1）和（2）变为等价的互为对偶线性规划问题,1、LP法,n,应当指出，在未求解(P)和(D)之前，V的正负是未知的。当V =v0时，可以v0或v0，此时建立的LP模型(P)和(D)可用单纯形法求解，且X*0,Y*0,（2）若A=(aij)mxn中含有负元素时，则有可能出现v0，由此则可能出现无解，这与基本定理相矛盾。此时，可根据下述定理进行处理： 定理：设对策 =S，S；A和对策 =S，S；A，其中A=(aij)mxn，A=(aij+k)mxn,k为任一常数，则 与 的解相同，且V=Vk。,其方法是先对含有负元素的A加上正数k,k=-minaij，构成一个新的赢得矩阵A，再用LP法进行求解，所得的解就是原对策的解， 但V=Vk。,2、2n对策的解法,(1) 22对策的公式法,由于在纯策略下无解的22对策，其最优混合策略(x1*,x2*)0，(y1*,y2*)0，所以由LP对偶理论中的互补松驰性定理知，基本定理(3)的两组不等式均可取等式。即,由A建立的两个互为对偶的线性规划模型如下：,有唯一解：,例3 求解下列矩阵对策=S1，S2；A,解：（1）这是一个无鞍点的矩阵对策。,（2）是一个有鞍点的矩阵对策，用鞍点法求得对策的解为(2*,1*)，对策值为V =2,(2) 2n对策的代数解法： 对2n对策，可先将2n对策转化为Cn2个22子对策，再利用22对策的公式法，分别求出各子对策的值，最后从中解出2n对策的解，其步骤如下： 第一步：由2n阶矩阵A分别写出Cn2个22阶子矩阵Ai； 第二步：分别求出各Ai相应子对策的值V i； 第三步：取V =minV i= V k,1kN，其中N=Cn2,Ak是由A中的两列所构成； 第四步：求出Ak相应子对策V k的解X(o)、Y(o)，取X*=Xo，同时在Y(o)中添加n2个0分量在对应列的位置上，构成Y*，则(X*Y*)就是原2n对策的解。,解：（1）对应于A的三个子对策的赢得矩阵为,（2）分别求以A1，A2，A3为赢得矩阵的相应子对策的值 VA1=21/5，VA2=119/23，VA3=7 （3）取V=minVA1， VA2， VA3= min21/5，119/23，7=21/5 （4）用公式法求V=21/5对应的子策略A1的解,由于A1是由A的第一、二列组成，则局中的选择第三列的概率为0。,（5）因此原矩阵对策的解为：X*=（3/5，2/5），Y*=（7/15，8/15，0）， V=21/5,3、迭代法 对于赢得矩阵阶数较高的矩阵对策，除了可用线性规划求解外，还可用以下的迭代法求解。 迭代法的基本思想是：两个局中人反复进行多局对策，在每一局中各局中人都根据在此以前的各局对策中可能赢得的总和，在自己的纯策略中选取一个使自己累计所得最多（或损失最少）的纯策略。在多局对策后，当迭代的结果双方达到一定的满意程度时，迭代结束。此时用局中人纯策略在已进行的各局对策中出现的频率分布作为最优混合策略中概率分布的一个近似。 因此，迭代法是一种求解矩阵对策的近似解法。,例11 试用迭代法求解以下矩阵对策,解：对于第一个局中人,对于第二个局中人,对于第一个局中人,对于第二个局中人,对于第一个局中人,对于第二个局中人,局中人的最优混合策略,局中人的最优混合策略,对策值V=(2/3+4/3)/2=1, 5.4 求解矩阵对策中的计算技巧,1、 用优超原则简化赢得矩阵 例,优超原则：在A=(aij)mxn中 (1)若第k行与第l行的各元素均有 akjalj (j=1,2n) 则称局中人的纯策略k优超于纯策略l，此时在最优混合策略中必有Xl*=0。（即可在A中删去第l行）。 (2)若第p列与第q列的各元素均有 aipaiq (i=1,2m) 则称局中人的纯策略p优超于纯策略q，此时在最优混合策略中必有yq*=0（即可在A中删去第q列）,值得指出的是，对于A中的纯策略i1(或j1)不为纯策略i2im(或j2jm)所优超。但被它们的凸组合所优超，即,此时，同样可在A删去第i1行(或第j1列)，对策的解不变。 2、若两个矩阵对策 1=S,S,A1， 2=S,S,A2且满足A1=A2+k(k为任一常数)，则V1=V2+k，且它们有相同的解。 3、若两个矩阵对策 1和 2满足A1=kA2(k为任一常数)，则V 1=kV 2，且它们有相同的解。 4、设A为n阶对角矩阵（即主对角线上的元素为a11,a22ann，其余元素均为0）。若a11,a22ann符号相同，则,例 两小孩猜扑克牌花色，游戏规定：由甲小孩每次从4种花色的牌中拿出一张牌给乙小孩猜，猜对花色，甲付给乙小石子三个；猜不对，乙付给甲一个石子，试求游戏的解。 解 据题意，该游戏可归结为矩阵模型G=S甲,S乙,A，其中甲小孩的赢得,显然该对策无鞍点，为简化计算，对A中各元素减1，得,即甲、乙两小孩应以1/4的概率出（或猜）各种花色的牌，互不吃亏。,“齐王赛马”的羸得矩阵满足上述条件，故由此可得,X*=Y*=(1/6,1/6,1/6,1/6)，且VG=6/6=1。,对于矩阵对策，该选用哪种方法进行求解？一般可按以下顺序进行考虑： 1首先，用最大最小原则试求鞍点。若无，则考虑以下方法； 2若A为特殊矩阵，则可选用上述4,5给出的结论，直接求解； 3对33阶以上的赢得矩阵A，试用优超法将A降阶 4对2n对策，可转化为Cn2个22对策，分别用公式法求解，并从中求出原对策的解； 5以上方法均不可行时，则可用LP法或迭代法求解。,15.5 两人有限非零和对策,在许多对策问题中，对策双方的得失之和并不等于零，即局中人一方的得并不等于另一方得失，这就是两人有限非零和对策。如两家企业竞争某种商品的市场占有率，当他们采取某些策略时，有可能产生双赢的结果。,一、两人有限非零和对策的数学模型 例18 甲、乙两家面包店在市场竞争中，各自都在考虑是否要降价，如果两家都降价，则各家可得3百元的利润，如果都不降价，则各家可得利润5百元，如果一家降价，另一家不降，则降价的一家可得利润6百元，不降价的一家由于剩余损坏等原因而亏损4百元，问双方应如何选择行动较为合理？,依题意，把上述问题表述成如下表格：,这个问题的数学模型可表示为：,一般地，两人有限零和对策的数学模型可表示为,随着A,B的确定，两人有限非零和对策也就确定，因此两人有限非零和对策又称为双矩阵对策。特别，当A=-B时，双矩阵对策就是矩阵对策。 在上述这个竞争对策中，两家面包店在没有互通信息非合作情况下，各自都有两种策略的选择，降价或不降价。显然，双方最好策略的选择都是降价，即（1，1）。 因为选择降价至少可以得到3百元的利润，如果选择不降价，则可能由于对方降价而蒙受4百元的损失。当然，在两店互通信息，进行合作的情况下，双方采取不降价的策略，各自都能得到5百元的利润。 例19 设想一个垄断企业已占领市场（称为在位者），另一个企业很想进入市场（称为进入者）。在位者想保持其垄断地位，就要阻绕进入者进入。假定进入者进入之前在位者的垄断利润为300，进入后两者的利润合为100（各得50），进入成本为10。试分析两者的最佳策略。,根据题意，可得如下表格：,对于这个对策问题，经过分析容易得到（1， 1）（进入，默许）和（2， 2）（不进入，斗争）是双方选择的最好的局势。,二、非合作两人对策的解法 在这里所讨论的两人有限非零和对策中，假定对策双方都了解对方的纯策略集和赢得函数，但不合作，并且局中人在选择自己的策略时不知道对方的选择。 （1）非合作两人对策的解