93 对策论课件

《93 对策论课件》由会员分享，可在线阅读，更多相关《93 对策论课件（87页珍藏版）》请在装配图网上搜索。

1、 15.1 对策论的基本概念对策论的基本概念 15.2 矩阵对策的最优纯策略矩阵对策的最优纯策略 15.3 矩阵对策的混合策略矩阵对策的混合策略 15.4 求解矩阵对策中的计算技巧求解矩阵对策中的计算技巧(自自学学) 15.5 两人有限非零和对策两人有限非零和对策(自学自学) 在日常生活中，经常可以看到一些具有相互斗争在日常生活中，经常可以看到一些具有相互斗争或竞争性质的行为，如下棋、打牌、体育比赛等。还或竞争性质的行为，如下棋、打牌、体育比赛等。还有企业间的竞争、军队或国家间的战争、政治斗争等，有企业间的竞争、军队或国家间的战争、政治斗争等，都具有对抗的性质。在这类行为中，各方具有不同的都具

2、有对抗的性质。在这类行为中，各方具有不同的目标和利益。为实现自己的目标和利益，各方必须考目标和利益。为实现自己的目标和利益，各方必须考虑对手可能采取的行动方案，并力图选择对自己最为虑对手可能采取的行动方案，并力图选择对自己最为有利或最为合理的行动方案。有利或最为合理的行动方案。 这种具有竞争或对抗这种具有竞争或对抗性质的行为称为性质的行为称为对策行为对策行为。这种研究对策的理论与方。这种研究对策的理论与方法法, ,叫做对策论叫做对策论, ,也叫博弈论（也叫博弈论（Game TheoryGame Theory） 对策论是运筹学的重要分支，最早研究对策论是运筹学的重要分支，最早研究的问题是对抗或竞

3、争中的各方所应采取的问题是对抗或竞争中的各方所应采取的策略以及由此得到的结果，并给出策的策略以及由此得到的结果，并给出策略优劣的分析。研究方法是：先构造出略优劣的分析。研究方法是：先构造出所论冲突的数学模型，然后用数学方法所论冲突的数学模型，然后用数学方法加以分析、比较、计算。对策论诞生于加以分析、比较、计算。对策论诞生于1927年，由大数学家冯年，由大数学家冯诺伊曼创立。诺伊曼创立。冯冯诺伊曼认识到经济与政治中的某些决诺伊曼认识到经济与政治中的某些决策条件在数学上与某些策略对策等价，策条件在数学上与某些策略对策等价，所以从分析这些对策中所学到的东西可所以从分析这些对策中所学到的东西可以直接应

4、用于现实生活中的决策。以直接应用于现实生活中的决策。 对策论是研究具有斗争性质现象的数学理论和对策论是研究具有斗争性质现象的数学理论和方法，它是运筹学的一个重要分支。最早的运筹学方法，它是运筹学的一个重要分支。最早的运筹学思想可以追溯到战国时期的齐王赛马，近年来运筹思想可以追溯到战国时期的齐王赛马，近年来运筹学思想普遍运用到经济学中，用于解释一些经济现学思想普遍运用到经济学中，用于解释一些经济现象和做出最好的经济决策。事实上，经济学和对策象和做出最好的经济决策。事实上，经济学和对策 论的研究模式都是强调个人理性，在给定的约束条论的研究模式都是强调个人理性，在给定的约束条件下追求效用最大化，件下

5、追求效用最大化，1994年诺贝尔经济学奖授予年诺贝尔经济学奖授予了三位博奕论专家：纳什了三位博奕论专家：纳什(Nash)、塞尔腾、塞尔腾(Selten)和豪尔沙尼和豪尔沙尼(Harsanyi)，其中最重要的原因之一是，其中最重要的原因之一是他们在非合作博奕论方面作出了突出的贡献。他们在非合作博奕论方面作出了突出的贡献。我国战国时期的我国战国时期的“田忌齐王赛马田忌齐王赛马”就是典型的对策行为就是典型的对策行为齐王齐王3:0取胜取胜田忌田忌2:1取胜取胜 对策问题各种各样，所以对策模型也千差万别，但对策问题各种各样，所以对策模型也千差万别，但本质上都包括本质上都包括三个基本要素三个基本要素： 局

6、中人、策略集、赢得函数局中人、策略集、赢得函数 (1) (1)局中人局中人 （Player）： 在一个对策行为中，有在一个对策行为中，有权决定自己行动方案的对策参加者权决定自己行动方案的对策参加者, ,称为局中人。局中称为局中人。局中人可以是人，也可以是集团，如齐王赛马的齐王和田人可以是人，也可以是集团，如齐王赛马的齐王和田忌分别都是局中人；在人与自然的斗争中，人和自然忌分别都是局中人；在人与自然的斗争中，人和自然都是局中人。通常用都是局中人。通常用I I表示局中人集合，如果有表示局中人集合，如果有n n个局个局中人，则中人，则I=1,2,nI=1,2,n。一般要求一个对策中至少有两。一般要求

7、一个对策中至少有两个局中人。局中人总是被假定是聪明且有理智的。个局中人。局中人总是被假定是聪明且有理智的。 15.1 对策论的基本概念对策论的基本概念 (2)(2)策略集策略集 （Strategy）：对策中可供局中人选择对策中可供局中人选择的一个实际可行的完整的行动方案，称为一个（纯）的一个实际可行的完整的行动方案，称为一个（纯）策略策略； 一个局中人全体策略构成的集合，称为此局中一个局中人全体策略构成的集合，称为此局中人的人的策略集策略集。参加对策的每一局中人。参加对策的每一局中人i i I I的策略集记为的策略集记为S Si。一般每一局中人的策略集中至少应包括两个（纯）。一般每一局中人的策

8、略集中至少应包括两个（纯）策略。策略。 如如田忌齐王赛马田忌齐王赛马中，若用（上、中、下）表中，若用（上、中、下）表示以上马、中马、下马依次参赛，就是一个纯策略。示以上马、中马、下马依次参赛，就是一个纯策略。 齐王与田忌的策略集中，各自都有齐王与田忌的策略集中，各自都有六个纯策略六个纯策略： S1=(S1=(上、中、下上、中、下),(),(上、下、中上、下、中),(),(中、上、中、上、下下),(),(中、下、上中、下、上),(),(下、上、中下、上、中),(),(下、中、上下、中、上) ) S2=( S2=(上、中、下上、中、下),(),(上、下、中上、下、中),(),(中、上、中、上、下下

9、),(),(中、下、上中、下、上),(),(下、上、中下、上、中),(),(下、中、上下、中、上) ) 15.1 对策论的基本概念对策论的基本概念(3)(3)赢得函数赢得函数 （支付函数支付函数 Score）： 局势：局势：对策中，每一局中人所选定策略形成的策略对策中，每一局中人所选定策略形成的策略组合称一个局势。组合称一个局势。 设局中人设局中人1 1从自己的策略集从自己的策略集S S1= 1, , 2 , , m 中选定中选定策略策略 i，局中人，局中人2 2从自己的策略集从自己的策略集S S2= 1, , 2 , , n 选定选定策略策略 j，则，则S=(S=( i, , j) )就构成

10、两人对策中的一个局势。就构成两人对策中的一个局势。 在在n n个对策中，设个对策中，设s si表示第表示第i i局中人的一个策略，则局中人的一个策略，则n n个局中人的策略组合形成的局势为个局中人的策略组合形成的局势为S=(sS=(s1,s,s2,s,sn) )。 赢得函数：赢得函数：当一个局势当一个局势S S出现后，各局中人都有自己出现后，各局中人都有自己的结果（得失），记为的结果（得失），记为H Hi(S)(S)，它表示第，它表示第i i局中人的赢得局中人的赢得（支付）值。显然（支付）值。显然H Hi(S)(S)是局势是局势S的函数的函数, ,称为局中人称为局中人i i的的赢赢得函数得函数

11、。 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 -11 3 1 1 -1 11 -1 3 1 1 1-1 1 1 3 1 11

12、1 1 -1 3 11 1 -1 1 1 32(上 下 中)3(中 上 下)4(中 下上)5(下中上)1(上 中 下)6(下上中)1(上 中 下)2(上 下 中)3(中 上 下)4(中 下上)5(下上 中)6(下 中上)齐齐王的王的赢赢得矩得矩阵为阵为齐王的策略田忌的策略对策动态对策静态对策结盟对策不结盟对策联合对策合作对策无限策略对策有限策略对策二人多人零 和非零和零 和非零和同有限对策纯策略对策混合策略对策两人有限零和对策两人有限零和对策 2个局中人；个局中人； 每个局中人策略集的策略数目都是有限的每个局中人策略集的策略数目都是有限的; 每一局势的对策都有确定的益损值；每一局势的对策都有确

13、定的益损值； 同一局势的两个局中人的益损值之和为零同一局势的两个局中人的益损值之和为零 15.2 矩阵对策的最优纯策略矩阵对策的最优纯策略一、矩阵对策问题数学模型的建立一、矩阵对策问题数学模型的建立两人有限零和对策两人有限零和对策(矩阵对策矩阵对策)的数学模型为：的数学模型为：=,;S1,S2,A 其中其中表示第一个居中人，表示第一个居中人， 表示第二表示第二个居中人；个居中人；S1= 1, 2, m，S2= 1, 2, , n分别为局中人分别为局中人和和的策略集，的策略集，A=(aij)mxn为局中人为局中人的赢得矩阵，由于假定对策的结的赢得矩阵，由于假定对策的结果为零和，所以局中人果为零和

14、，所以局中人的羸得矩阵为的羸得矩阵为-A。311-11113-111111311-11113-11-1111311-11113A=“田忌齐王赛马田忌齐王赛马”对策问题的数学模型如下对策问题的数学模型如下： = ,; S1,S2; A 表示齐王表示齐王 表示田忌表示田忌 S1= 1, 6表示齐王的策略集合表示齐王的策略集合; S2= 1, 6表示田忌的策略集合表示田忌的策略集合 其中其中 i， i (上、中、下上、中、下),(上、下、中上、下、中),(中、上、下中、上、下), (中、下、上中、下、上),(下、上、中下、上、中),(下、中、上下、中、上) A表示齐王的赢得矩阵表示齐王的赢得矩阵 某

15、单位采购员在秋天决定冬季取暖用煤的储某单位采购员在秋天决定冬季取暖用煤的储量问题。已知在正常的冬季气温条件下要消量问题。已知在正常的冬季气温条件下要消耗耗15吨煤，在较暖与较冷的气温条件下要消吨煤，在较暖与较冷的气温条件下要消耗耗10吨和吨和20吨。假定冬季的煤价随天气寒冷吨。假定冬季的煤价随天气寒冷程度而有所变化，在较暖、正常、较冷的气程度而有所变化，在较暖、正常、较冷的气候条件下每吨煤价分别为候条件下每吨煤价分别为10元、元、15元、元、20元，元，又设秋季时煤价为每吨又设秋季时煤价为每吨10元。在没有关于当元。在没有关于当年冬季准确的气象预报的条件下，秋季储煤年冬季准确的气象预报的条件下

16、，秋季储煤多少吨能使单位的支出量少？建立该问题的多少吨能使单位的支出量少？建立该问题的对策数学模型。对策数学模型。解：解：将该问题看成将该问题看成对策问题对策问题,其数学模型为：其数学模型为： = ,;S1,S2;A其中其中表示采购员表示采购员 表示冬天的天气表示冬天的天气 S1表示采购员在秋季购买煤的数量表示采购员在秋季购买煤的数量S1 =10, 15 ,20 S2表示冬季气候状况表示冬季气候状况S2-100 -175 -300-150 -150 -250-200 -200 -20010吨15吨20吨较暖 正常 较冷A=冬季单价冬季单价: 10 15 20秋季单价秋季单价: 10元元甲、乙双

17、方谈判签订一项合同，甲方甲、乙双方谈判签订一项合同，甲方的最后要价是的最后要价是25万元，而乙方的出价万元，而乙方的出价是是20万元，谈判陷于僵局，为了打破万元，谈判陷于僵局，为了打破僵局，双方约定，再各报一个价（必僵局，双方约定，再各报一个价（必须报整数价格），以下述价格成交：须报整数价格），以下述价格成交：谁让步多，取谁出的价，如果双方让谁让步多，取谁出的价，如果双方让步相同，则取双方报价的中间值，问步相同，则取双方报价的中间值，问甲、乙双方应如何报价？最后的成交甲、乙双方应如何报价？最后的成交价是多少？价是多少？(写出此对策问题的三要素写出此对策问题的三要素或者说建立该问题的数学模型或者

18、说建立该问题的数学模型) 解解： 将该问题看成将该问题看成对策问题对策问题,其数学模型为其数学模型为:= ,;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 2421222324甲25 乙20 1 2 3 4 4321

19、21 22 23 24 差价差价A= 解法的基本思想是：解法的基本思想是：双方都立足在最不利的情况下争取双方都立足在最不利的情况下争取最好的结果最好的结果最大最小原则最大最小原则甲、乙双方谈判签订一项合同，甲方的最甲、乙双方谈判签订一项合同，甲方的最后要价是后要价是25万元，而乙方的出价是万元，而乙方的出价是20万元，万元，谈判陷于僵局，为了打破僵局，双方约定，谈判陷于僵局，为了打破僵局，双方约定，再各报一个价（必须报整数价格），以下再各报一个价（必须报整数价格），以下述价格成交：谁让步多，取谁出的价，如述价格成交：谁让步多，取谁出的价，如果双方让步相同，则取双方报价的中间值，果双方让步相同，

20、则取双方报价的中间值，问甲、乙双方应如何报价？最后的成交价问甲、乙双方应如何报价？最后的成交价是多少？是多少？写出此对策问题的三要素或者说建立写出此对策问题的三要素或者说建立该问题的数学模型；该问题的数学模型； 该对策问题是否存在纯策略意义下的该对策问题是否存在纯策略意义下的平衡解，如果存在，解为多少？平衡解，如果存在，解为多少？ 21 21 21 22.5 22 22 22.5 24 23 22.5 23 24 22.5 22 23 24212222.522 23 22.5 23 24 甲方甲方25 乙方乙方20 maxmaxminmin22.522.5 21 22 23 24 （2）所以该

21、对策问题存在纯策略意义下的平衡解）所以该对策问题存在纯策略意义下的平衡解. 甲方报价甲方报价23万元万元,乙方报价乙方报价22万元万元 最后的成交价格是最后的成交价格是22.5万元万元A= 21222324某单位采购员在秋天决定冬季取暖用煤的储量问题。某单位采购员在秋天决定冬季取暖用煤的储量问题。已知在正常的冬季气温条件下要消耗已知在正常的冬季气温条件下要消耗15吨煤，在较吨煤，在较暖与较冷的气温条件下要消耗暖与较冷的气温条件下要消耗10吨和吨和20吨。假定冬吨。假定冬季的煤价随天气寒冷程度而有所变化，在较暖、正常、季的煤价随天气寒冷程度而有所变化，在较暖、正常、较冷的气候条件下每吨煤价分别为

22、较冷的气候条件下每吨煤价分别为10元、元、15元、元、20元，又设秋季时煤价为每吨元，又设秋季时煤价为每吨10元。在没有关于当年元。在没有关于当年冬季准确的气象预报的条件下，秋季储煤多少吨能使冬季准确的气象预报的条件下，秋季储煤多少吨能使单位的支出量少？单位的支出量少？ 写出此对策问题的三要素或者说建立该问题的写出此对策问题的三要素或者说建立该问题的数学模型；数学模型；该对策问题是否存在纯策略意义下的平衡解，该对策问题是否存在纯策略意义下的平衡解，如果存在，解为多少？如果存在，解为多少？-100 -175 -300-150 -150 -250-200 -200 -20010吨15吨20吨较暖

23、正常 较冷A=（2）可见该对策问题存在纯策略意义下的平衡解）可见该对策问题存在纯策略意义下的平衡解. 采购员秋季购买采购员秋季购买20吨煤最稳妥吨煤最稳妥 花费的费用为花费的费用为200万元万元 -100 -150 -200 maxmaxmin-200-200-300-250-200min a11 a12 . a1j . a1n a21 a22 . a2j . a2n ai1 ai2 . aij . ain am1 am2 . amj . amna1ca2e aij amd ak1 ah2 . aij . atn 方方方方maxmaxminminA= 可见居中人可见居中人的赢得的赢得v1=ma

24、xminaij,居中人居中人 的损失的损失v2=minmaxaij,当当v1=v2时时,该点称为鞍点即为纯策略意义下的平衡解该点称为鞍点即为纯策略意义下的平衡解; 通常在具有通常在具有鞍点鞍点的对策问题中的对策问题中,称为该矩阵对策具有称为该矩阵对策具有纯策略纯策略意义下的意义下的平衡解平衡解 1 2 i m 1 2 . j . n 最优解为最优解为( i， j)最优值为最优值为aijv1v2P368 1、2 该矩阵对策在纯策略下无解。也就是说用最大最小原则该矩阵对策在纯策略下无解。也就是说用最大最小原则来选取各自的纯策略都不会是稳定的，此时求解矩阵对策来选取各自的纯策略都不会是稳定的，此时求

25、解矩阵对策的混合策略的混合策略15.3 矩阵对策的混合策略矩阵对策的混合策略在具有鞍点的矩阵对策中在具有鞍点的矩阵对策中,居中人居中人的赢得的赢得v1=maxminaij,居中人居中人 的损失的损失v2=minmaxaij且且v1=v2。但一般情况下却总有。但一般情况下却总有v1不等于不等于v2例如例如9 72 8A= 9 8 maxmaxmin7872min 在上述双方都不能固定采用任何一个纯策在上述双方都不能固定采用任何一个纯策略下，必须随机地选取自己的各个纯策略，略下，必须随机地选取自己的各个纯策略，使双方捉摸不到自己使用的策略，以求得自使双方捉摸不到自己使用的策略，以求得自己的期望赢得

26、最大（或期望损失最小）。己的期望赢得最大（或期望损失最小）。9 72 8121 2x1x2 y1 y2 方方方方假设假设x1 ，x2分别表示分别表示方选取方选取1，2纯策略的概率，纯策略的概率，y1 y2 分别表示分别表示方选取方选取1，2纯策略的概率，即为混合策略纯策略的概率，即为混合策略9 72 89x1+2x2v7x1+8x2vx1x2局中人局中人使用使用1的概率为的概率为x1 ，使用，使用2的概率为的概率为x2 ，则，则x1 + x2 =1当局中人当局中人使用使用1策略时，局中人策略时，局中人的平均赢得为：的平均赢得为： 9x1 +2x2 假设局中人假设局中人期望赢得的平均值为期望赢得

27、的平均值为V，此时，此时9x1 +2x2 V同理当局中人同理当局中人 使用使用2策略时，局中人策略时，局中人的平均赢得为：的平均赢得为：7x1 +8x2 7x1 +8x2 V求解最优混合策略的思路求解最优混合策略的思路121 2此时应该此时应该minZ=x1+x29x1+2x217x1+8x21x1,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/

28、V的值越小越好，于是建立起求的值越小越好，于是建立起求的最优混合策略的线性规划数学模型：的最优混合策略的线性规划数学模型：St.求解最优混合策略的思路求解最优混合策略的思路9x1+2x2v7x1+8x2v9 72 89y1+7y2v2y1+8y2 vy1 y2局中人局中人 使用使用 的概率为的概率为y1 ，使用，使用2的概率为的概率为y2 ，则，则y1 + y2 =1当局中人当局中人使用使用1策略时，局中人策略时，局中人 的平均损失为：的平均损失为： 9y1 +7y2 假设局中人假设局中人期望赢得的平均值为期望赢得的平均值为V，此时，此时9y1 +7y2 V同理当局中人同理当局中人 使用使用2

29、策略时，局中人策略时，局中人 的平均损失为：的平均损失为： 2y1 +8y2 2y1 +8y2 V同理求解同理求解的最优混合策略的最优混合策略121 2此时应该此时应该maxW=y1+y29y1+7y2 12y1+8y2 1y1,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的值越大越好，于是建立起求的值越大越好，于是建立起求的最优混合策略的线性

30、规划数学模型：的最优混合策略的线性规划数学模型：St.同理求解同理求解的最优混合策略的最优混合策略9y1+7y2v2y1+8y2 v9 72 8minZ=x1+x29x1+2x217x1+8x21x1,x2 0St.maxW=y1+y29y1+7y212y1+8y21y1,y2 0St.x1x2 y1 y2 又令又令总之总之令令x1 ，x2分别表示分别表示方选取方选取1，2纯策略的概率纯策略的概率 y1 ，y2分别表示分别表示方选取方选取1，2纯策略的概率纯策略的概率则：则：可见是一组互为对偶的对称性线性规划问题可见是一组互为对偶的对称性线性规划问题x1 = x1 / v x2 = x2 /

31、vy1 = y1 / v y2 = y2 /v a11 a12 . a1j . a1n a21 a22 . a2j . a2n ai1 ai2 . aij . ain am1 am2 . amj . amnx1x2 xixm y1 y2 . yj . yn 方方方方A= 如果是不具有如果是不具有鞍点鞍点的对策问题的对策问题,求解该矩阵对策最优混合求解该矩阵对策最优混合策略策略的的解解令令x1 ，x2xm 分别表示分别表示方选取方选取1， 2m纯策略的概纯策略的概率率; y1 ，y2 yn 分别表示分别表示方选取方选取1，2 n纯策略的概纯策略的概率，则率，则x1 + x2 +.+ xm =1,

32、 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居中人居中人居中人居中人作如下变换

33、作如下变换令令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一组互为对偶一组互为对偶的对称性线性的

34、对称性线性规划问题规划问题居居中中人人居居中中人人 利用单纯型法求出利用单纯型法求出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)即即方选取各纯策略的概率，也就是居中人方选取各纯策略的概率，也就

35、是居中人 的最优的最优混合策略混合策略 二者具有相同的最优值，即二者具有相同的最优值，即1/v写出此对策问题的三要素写出此对策问题的三要素(或建立此对策问题的数学模型或建立此对策问题的数学模型)；该对策问题是否存在该对策问题是否存在纯策略意义下的平衡解纯策略意义下的平衡解,如果存在如果存在,给出给出问题的最优策略问题的最优策略?如果不存在如果不存在,请将此对策问题对策双方的请将此对策问题对策双方的最优混合策略表示为一个互为对偶的线性规划模型最优混合策略表示为一个互为对偶的线性规划模型该对策问题是否存在该对策问题是否存在鞍点鞍点,如果存在如果存在,给出问题的最优策略给出问题的最优策略?如果不存在

36、如果不存在,请将此对策问题对策双方的最优混合策略表示请将此对策问题对策双方的最优混合策略表示为一个互为对偶的线性规划模型为一个互为对偶的线性规划模型已知甲方的最优混合策略为已知甲方的最优混合策略为(0.8, 0.2, 0 ),请采用对偶性质求请采用对偶性质求出乙方的最优混合策略及甲方的期望决策值出乙方的最优混合策略及甲方的期望决策值.求对策问题对策求对策问题对策双方双方的混合策略的混合策略(单纯形法单纯形法) 1、写出此对策问题的数学模型；、写出此对策问题的数学模型； 2、此对策问题是否存在纯策略意义下的平衡解？如果存在，求、此对策问题是否存在纯策略意义下的平衡解？如果存在，求此纯策略意义下的

37、平衡解；如果不存在，请将此对策问题对此纯策略意义下的平衡解；如果不存在，请将此对策问题对策双方的最优混合策略表示为一个互为对偶的线性规划模型策双方的最优混合策略表示为一个互为对偶的线性规划模型现有两家企业相互竞争同一产品市场，企业现有两家企业相互竞争同一产品市场，企业A有有4个销售渠道，个销售渠道，企业企业B有有5个销售渠道。已经算出当双方采取不同的策略时，个销售渠道。已经算出当双方采取不同的策略时，A方所能获得的利润：方所能获得的利润：123451-3221121-3-1203-2433243-1541综合练习题目综合练习题目解：解：1、对策问题的数学模型如下：、对策问题的数学模型如下：=

38、,;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 1A= A= 1 234 1 2 3 4 5 -3 2 2 1 1 1 -3 -1 2 0 -2 4 3 3 2 3 -1 5 4 12、-3-3-2-1 3 4 5 4 2maxmaxminmin-12可见可见v1=maxmina

39、ij=-1, v2=minmaxaij=2,因为因为v1不等于不等于v2，所以该，所以该对策问题不存在鞍点即原问题不具有纯策略意义下的平衡解，需要对策问题不存在鞍点即原问题不具有纯策略意义下的平衡解，需要求解最优混合策略的解求解最优混合策略的解x1x2x3x4 y1 y2 y3 y4 y5A= 1 234 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选

40、取选取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

41、 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对策双方的最优混对策双方的最优混合策略表示为如下合策略表示为如下一个互为对偶的线一个互为对偶的线性规划模型：性规划模型：在矩阵对策G=S1,S2,A,S1= 1,2 ,3 ,4 ,S2= 1, 2 ,3中，关于局中人1某个混合策略的意义，有以下解释，其中正确的是(A)交替使用每一个纯策略；(B)使用某一个纯策略的概率；(C)使用每一个纯策略i,(i=

42、1,2,3,4)的概率所构成的概率向量；(D)各纯策略的线性组合 5033416423817A解：2min*jija1.解法的思想解法的思想：双方都立足在双方都立足在不利的情况下争取最好的结果不利的情况下争取最好的结果最大最小原则。最大最小原则。例例 求解矩阵对策求解矩阵对策 =S1,S2;A，其中，其中: ijjamin321 2max33285033416423817*4321 jiia iijamax 16 2 5 甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看成一种策略，双方各选一种策略参赛，比赛共赛三局，规定每局胜者得1分，输者得-1分

43、S1=1，2 ，3 分别表示甲队三种不同的阵容 S1=1，2 ，3 分别表示乙队三种不同的阵容 根据以往比赛得分资料，可得甲队的赢得矩阵为A，如下所示：试问这次比赛各队应采用哪种阵容上场最为稳妥。1 1 1 -1 -3 1 3 -1 3A =1 1 1 -1 -3 1 3 -1 3A =min1-3-1max 3 1 3max1min11maxminminmax12aaaijijijji1minmax1ijjiaV1maxmin2ijijaV所以这次比赛甲队应采用1阵容上场，乙队应采用2阵容上场最为稳妥。试问这次比赛各队应采用哪种阵容上场最为稳妥。1 1 1 -1 -3 1 3 -1 3A =

44、 5033416423817A解：2min*jija1.解法的思想解法的思想：双方都立足在双方都立足在不利的情况下争取最好的结果不利的情况下争取最好的结果最大最小原则。最大最小原则。例例 求解矩阵对策求解矩阵对策 =S1,S2;A，其中，其中: ijjamin321 2max33285033416423817*4321 jiia iijamax 16 2 5 5033416423817A 3.方法步骤：方法步骤：上例求解过程可简单的表述如下：其步骤是：第一步：分别确定A各行中的最小值，并在该数字上加圈表示； 2.在矩阵对策中在矩阵对策中， 若成立，则称ai*j*为对策的值，记为V=ai*j*。

45、称使上式成立的纯局势(i*,j*)为对策在纯策略下的解（亦称均衡局势）。i*和j*分别称为局中人和的最优纯策略。*maxminminmaxjiijijijjiaaa第二步：分别确定A各列中的最大值，并在该数字上加框表示； 第三步：若第三步：若A中的某元素同时被圈和框住，则该元素即中的某元素同时被圈和框住，则该元素即为对策的值，该元素所在的行和列对应的策略则分别为局为对策的值，该元素所在的行和列对应的策略则分别为局中人中人和和的最优纯策略，并由最优纯策略组成了对策的的最优纯策略，并由最优纯策略组成了对策的解。解。 因此上例对策的值因此上例对策的值V=2，对策的解为，对策的解为( 2, 2)， 2

46、, 2分别分别是局中人是局中人和和的最优纯策略。的最优纯策略。 在纯策略下有解的矩阵对策中，值在纯策略下有解的矩阵对策中，值ai*j*既是所在行的最既是所在行的最小值，又是所在列的最大值，称其为鞍点。所以这类矩阵小值，又是所在列的最大值，称其为鞍点。所以这类矩阵对策又称为有鞍点的对策。这个事实可推广到一般，即对策又称为有鞍点的对策。这个事实可推广到一般，即 在纯策略下矩阵对策在纯策略下矩阵对策 =S1,S2;A有解的充要条件是：有解的充要条件是：存在纯局势存在纯局势( i*, j*)，使得对于一切的，使得对于一切的i=1,2m,j=1,2n均均有有aij* ai*j* ai*j矩阵对策的解可以

47、不唯一。矩阵对策的解可以不唯一。例2 求下列矩阵对策的解1238372046454546A在此例中,对策的解不唯一.当解不唯一时,解之间的关系具有如下性质:(1)无差别性无差别性:即若(i1,j1),和(i2,j2) 是对策的两个解，则 aajiji*2*2*1*1（2）可交换性：）可交换性：即若(i1,j1),和(i2,j2) 是对策的两个解，则(i1,j2),和(i2,j1) 也是对策的两个解。 一、混合策略和混合局势一、混合策略和混合局势 .,21Y,X1; 0|Y, 1; 0|X),(Y),(X,A;,SSyySxxSyyyxxxSS*2*1m1ijj*2m1iii*1n21m2121

48、简称策略的混合策略和局中人分别称为局中人对任意令设给定一般地（X，Y）称为混合局势。二、混合扩充和混合策略下的解二、混合扩充和混合策略下的解当X，Y由局中人1和局中人2分别独立决定以后，纯局势 以概率xiyj出现，于是局中人1在混合策略下赢得的数学期望为),ji( m1in1jTjiijYyxaXA)Y,X(E的混合扩充为原对策则称E;,SS*2*1*n 在纯策略下矩阵对策的解是混合策略下矩阵对策解的特殊情况。 三、基本定理（不加证明）三、基本定理（不加证明） （1）在混合扩充下，任何矩阵对策必有解； （2）在混合策略下，(X*,Y*)是对策解的充要条件是：类似于纯策略的情况，若)(E)Y,X

49、(E)Y,X(EY,Xmaxminminmax*XYYXSSSS*1*2*2*1则称E（X*，Y*）为对策 的值，称（X*，Y*）为对策 在混合策略下的解，X*和Y*分别为局中人1和局中人2的最优混合策略。E(X,Y*)E(X*,Y*)E(X*,Y)其等价形式是:),(E),(E),(Ej*iXYXY 作为应用，给出（2）的另一等价形式： （3）(X*,Y*)为对策的解的充要条件是存在数v，使X*,Y*分别是下面两个不等式组的解：n其中v为对策的值。作如下变换，（设v0）v,vyyxxjjii01zmin)p(xxaxim1iiijm1ii01wmax)D(yyayjn1ijijn1jj可见是

50、一组互为对偶的对称性线性规划问题)m,.,2 , 1i (0 x1x)n,.,1j (vxaim1iim1iiij（1）),.,2 , 1(01),.,2 , 1(11njyymivyainjimjjij（2）四、矩阵对策的混合策略的解法四、矩阵对策的混合策略的解法其中v为对策的值。作如下变换，（设v0）v,vyyxxjjii于是不等式组（1）和（2）变为等价的互为对偶线性规划问题01zmin)p(xxaxim1iiijm1ii01wmax)D(yyayjn1ijijn1jj 1、LP法n 应当指出，在未求解(P)和(D)之前，V的正负是未知的。当V =v0时，可以v0或v0，此时，此时建立的

51、建立的LP模型模型(P)和和(D)可用单纯形法求解，且可用单纯形法求解，且X* 0,Y* 0 （2）若）若A=(aij)mxn中含有负元素时，则有可能出现中含有负元素时，则有可能出现v 0，由此则可能出现无解，这与基本定理相矛盾。此时，可根由此则可能出现无解，这与基本定理相矛盾。此时，可根据下述定理进行处理：据下述定理进行处理： 定理：设对策 =S，S；A和对策 =S，S；A，其中A=(aij)mxn，A=(aij+k)mxn,k为任一常数，则 与 的解相同，且V=Vk。 其方法是先对含有负元素的A加上正数k,k=-minaij，构成一个新的赢得矩阵A，再用LP法进行求解，所得的解就是原对策的

52、解， 但V=Vk。赢得矩阵形为nnaaaaaa2222111211.,.,的对策称为 2n对策。2、2n对策的解法 (1) 22对策的公式法 由于在纯策略下无解的22对策，其最优混合策略(x1*,x2*)0，(y1*,y2*)0，所以由LP对偶理论中的互补松驰性定理知，基本定理(3)的两组不等式均可取等式。即由A建立的两个互为对偶的线性规划模型如下：0,vv)P(v1zminxxxaxaxaxa212221122211110,vv)D(v1wmaxyyyayayaya21222112221111 (1) 121221112221111xxvxaxavxaxa(2)121222121212111

53、yyvyayavyaya有唯一解：)()()(211222111211*2211222112122*1aaaaaaxaaaaaax )()()()(211222112111*2211222111222*1aaaaaayaaaaaay )()(2112221122211211aaaaaaaavVG例3 求解下列矩阵对策=S1，S2；A3201A)2(1131A) 1 (解：（1）这是一个无鞍点的矩阵对策。316)3()1(11,316)1(1,326)3(1,326)3(1,316)1(16)31()11(Vyyxx*2*1*2*1（2）是一个有鞍点的矩阵对策，用鞍点法求得对策的解为(2*,1*

54、)，对策值为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对策的解。例 已知赢得矩阵为2091371A试用代数法求解此

55、对策。解：（1）对应于A的三个子对策的赢得矩阵为20137291310971AAA321（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的解158,15752,53yyxx02010201由于A1是由A的第一、二列组成，则局中的选择第三列的概率为0。（5）因此原矩阵对策的解为：X*=（3/5，2/5），Y*=（7/15，8/15，0）， V=21/5例例11 试用迭代法求解以下矩阵对策试用迭代法求解以下

56、矩阵对策 121130202A解：对于第一个局中人解：对于第一个局中人 1 1 2 3对于第二个局中人对于第二个局中人 2 1 2 3对于第一个局中人对于第一个局中人对于第二个局中人对于第二个局中人 1 1 2 3 2 2 1 2 3 1对于第一个局中人对于第一个局中人对于第二个局中人对于第二个局中人 1 1 2 3 2 2 2 1 2 3 1 1局中人局中人的最的最优混合策略优混合策略 03231X/ 03132Y/ 局中人局中人的最的最优混合策略优混合策略对策值对策值V=(2/3+4/3)/2=11、 用优超原则简化赢得矩阵用优超原则简化赢得矩阵例388065786485937852050

57、3043A优超原则：在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)所优超。但被它们的凸组合所优超，即miiimmiii2332211,. (或) njjimmjjj2332211,. 此时，同样可在A删去第i1行(或第j1列)

58、，对策的解不变。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符号相同，则符号相同，则nnaaaYX,.,2211* 且 VG=。其中111i

59、anij 例 两小孩猜扑克牌花色，游戏规定：由甲小孩每次从4种花色的牌中拿出一张牌给乙小孩猜，猜对花色，甲付给乙小石子三个；猜不对，乙付给甲一个石子，试求游戏的解。 解 据题意，该游戏可归结为矩阵模型G=S甲,S乙,A，其中甲小孩的赢得3111131111311113A矩阵显然该对策无鞍点，为简化计算，对A中各元素减1，得4000040000400004A于是有014141414111GV,且=-1， X*=Y*=(1/4,1/4,1/4,1/4)。 即甲、乙两小孩应以1/4的概率出（或猜）各种花色的牌，互不吃亏。5.设 A 为 n 阶 矩 阵 。 若 njijniijnibanjba11),

60、.,2, 1(),.,2, 1(, 则 X*=Y*=(1/n,1/n,1/n,1/n)， 且 VG=b/n。 “齐王赛马”的羸得矩阵满足上述条件，故由此可得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 两人

61、有限非零和对策两人有限非零和对策 在许多对策问题中，对策双方的得失之和并不等于零在许多对策问题中，对策双方的得失之和并不等于零，即局中人一方的得并不等于另一方得失，这就是两人有，即局中人一方的得并不等于另一方得失，这就是两人有限非零和对策。如两家企业竞争某种商品的市场占有率，限非零和对策。如两家企业竞争某种商品的市场占有率，当他们采取某些策略时，有可能产生双赢的结果。当他们采取某些策略时，有可能产生双赢的结果。一、两人有限非零和对策的数学模型一、两人有限非零和对策的数学模型例例18 甲、乙两家面包店在市场竞争中，各自都在考虑是甲、乙两家面包店在市场竞争中，各自都在考虑是否要降价，如果两家都降价

62、，则各家可得否要降价，如果两家都降价，则各家可得3百元的利润，如百元的利润，如果都不降价，则各家可得利润果都不降价，则各家可得利润5百元，如果一家降价，另一百元，如果一家降价，另一家不降，则降价的一家可得利润家不降，则降价的一家可得利润6百元，不降价的一家由于百元，不降价的一家由于剩余损坏等原因而亏损剩余损坏等原因而亏损4百元，问双方应如何选择行动较为百元，问双方应如何选择行动较为合理？合理？依题意，把上述问题表述成如下表格：这个问题的数学模型可表示为：的赢得矩阵。为局中人的赢得矩阵为局中人其中25643B,15463A,)B,A( ;,21221121SSSS一般地，两人有限零和对策的数学模

63、型可表示为为其赢得矩阵。的纯策略集，为局中人的赢得矩阵；为局中人的纯策略集，为局中人其中B2,1A1,),B,A( ;,n212m21121SSSS随着A,B的确定，两人有限非零和对策也就确定，因此两人有限非零和对策又称为双矩阵对策。特别，当A=-B时，双矩阵对策就是矩阵对策。 在上述这个竞争对策中，两家面包店在没有互通信息非合作情况下，各自都有两种策略的选择，降价或不降价。显然，双方最好策略的选择都是降价，即（1，1）。因为选择降价至少可以得到3百元的利润，如果选择不降价，则可能由于对方降价而蒙受4百元的损失。当然，在两店互通信息，进行合作的情况下，双方采取不降价的策略，各自都能得到5百元的

64、利润。 例19 设想一个垄断企业已占领市场（称为在位者），另一个企业很想进入市场（称为进入者）。在位者想保持其垄断地位，就要阻绕进入者进入。假定进入者进入之前在位者的垄断利润为300，进入后两者的利润合为100（各得50），进入成本为10。试分析两者的最佳策略。 根据题意，可得如下表格：对于这个对策问题，经过分析容易得到（1， 1）（进入，默许）和（2， 2）（不进入，斗争）是双方选择的最好的局势。二、非合作两人对策的解法二、非合作两人对策的解法 在这里所讨论的两人有限非零和对策中，假定对策双方都了解对方的纯策略集和赢得函数，但不合作，并且局中人在选择自己的策略时不知道对方的选择。（1）非合作

65、两人对策的解纳什均衡一般地，对于非合作两人对策S1,S2;(A,B),如果i*S1, j*S2分别是局中人1和2的最优纯策略，则称局势(i*, j*)是一个纳什均衡.求非合作两人对策的纳什均衡解的步骤如下：1、在双矩阵对策（A,B)表中，对于矩阵A的每列，分别找出赢得最大的数字，并在其下划一横线；2、在双矩阵对策（A,B)表中，对于矩阵B的每行，分别找出赢得最大的数字，并在其下划一横线；3、如果表中某格的数字下面都被划上横线，则此格对应于两个局中人相应策略的组合就是一个（纯策略下的）纳什均衡。否则，该对策不存在纯策略下的纳什均衡。例如：，（2）混合策略纳什均衡 上面所介绍的非合作两人有限对策是

66、在纯策略下有解的对策问题，其特点是纳什均衡中的策略是每一个局中人的一个完整策略。但是有些对策并不存在纯策略下的纳什均衡，如下例： 例20 局中人是政府和一个流浪汉，流浪汉有两个策略：寻找工作或游荡；政府也有两个策略：救济或不救济。政府帮助流浪汉的前提是后者必须试图寻找工作；否则，前者不予帮助；而流浪汉只有在得不到救济时才会寻找工作。下表给出了对策的赢得双矩阵：因此，在这个对策问题中，没有一个纯局势可以构成纯策略下的纳什均衡。为求得纳什均衡，必须对矩阵加以扩充 设A,B分别为局中人1和2的赢得矩阵，且皆为mn矩阵，局中人1，2的混合策略集为：1,0|xm1iii*1xxs1,0|Yn1iii*2yys如果一个混合策略组合（X*,Y*）同时满足YXYXYXYT*T*T*T*BB,AXA则称策略组合局势（ X*,Y*）是一个混合策略纳什均衡。 对于上述例题，假定政府以概率x选择救济，以概率1-x选择不救济，即政府的混合策略为(x,1-x)，流浪汉以概率y选择寻找工作，以概率1-y选择游荡，即流浪汉的混合策略为(y,1-y)。那么政府的期望赢得函数为：yxxy5y1y0113)x1 ,x(XA