管理运筹学课件第13章对策论.ppt

《管理运筹学课件第13章对策论.ppt》由会员分享，可在线阅读，更多相关《管理运筹学课件第13章对策论.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第13章章 对策论对策论1/3/20231管理运筹学课件教学目标与要求教学目标与要求【教学目标】【教学目标】1.理解下列基本概念：矩阵对策，矩阵对策三要素，最优纯策略与最优混合策略，鞍点和对策值2.算法要求：(1)会用“超优原则”和“最大最小”原则求矩阵对策的最优纯策略(2)会用“线性规划”方法求矩阵对策的最优混合策略(3)了解纯策略和混合策略的纳什均衡求取。【知识结构】【知识结构】1/3/20232管理运筹学课件1/3/20233管理运筹学课件1/3/20234管理运筹学课件本章主要内容本章主要内容n13.1 对策论的基本概念对策论的基本概念n13.1.1 对策模型的基本要素对策模型的基本

2、要素n13.1.2 对策问题的分类对策问题的分类n13.2 矩阵对策的纯策略矩阵对策的纯策略n优超原则优超原则n最大最小原则最大最小原则n13.3 矩阵对策的混合策略矩阵对策的混合策略n13.3.1 混合策略的概念混合策略的概念n13.3.2 图解法图解法n13.3.3 线性规划法线性规划法n13.4 纳什均衡纳什均衡n13.4.1 纯策略纳什均衡的划线法纯策略纳什均衡的划线法n13.4.2 混合策略纳什均衡的混合策略纳什均衡的LP方法方法n13.4 应用举例应用举例n案例案例13-1 市场竞争策略市场竞争策略n案例案例13-2 对抗赛项目确定对抗赛项目确定n本章小结本章小结1/3/20235

3、管理运筹学课件13.1.1 对策模型的基本要素对策模型的基本要素1 1局中人局中人局中人(players)是指参与竞争的各方，每方必须有独立的决策能力和承担风险的能力。(如:田忌、齐王）2 2策略集策略集在对策问题中，局中人为了应对其他局中人的行动而采取的方案和手段称为该局中人的一个策略(strategy)。3 3赢得及赢得函数赢得及赢得函数局中人采用不同策略对策时，各方总是有得或有失，统称赢得(payoff)或得益。(上中下)(上下中)(中上下)(中下上)(下上中)(下中上)(上中下)3，-31，-11，-11，-1-1，11，-1(上下中)1，-13，-31，-11，-11，-1-1，1(

4、中上下)1，-1-1，13，-31，-11，-11，-1(中下上)-1，11，-11，-13，-31，-11，-1(下上中)1，-11，-11，-1-1，13，-31，-1(下中上)1，-11，-1-1，11，-11，-13，-31/3/20236管理运筹学课件13.1.2 对策问题的分类对策问题的分类n局中人之间是否允许合作？n策略选择是否与时间有关？n局中人多寡？n赢得值代数和是否为0？1/3/20237管理运筹学课件13.1.2 对策问题的分类对策问题的分类1/3/20238管理运筹学课件13.2 矩阵对策的纯策略矩阵对策的纯策略n为求出对策模型的解，首先需要对双方的对策条为求出对策模型

5、的解，首先需要对双方的对策条件作如下的假设。件作如下的假设。n(1)对策双方的行为是理智的，对策略的选择不对策双方的行为是理智的，对策略的选择不存在任何侥幸心理。存在任何侥幸心理。n(2)局中人选取策略的目标是收益最大或损失最局中人选取策略的目标是收益最大或损失最小。小。n(3)局中人同时选取各自的行动策略，且不知道局中人同时选取各自的行动策略，且不知道对方选取哪一个策略。对方选取哪一个策略。n(4)对策中的有关规定和要求，局中人是知道的。对策中的有关规定和要求，局中人是知道的。1/3/20239管理运筹学课件超优原则超优原则1 1对对 若恒有若恒有 则称则称 超优于超优于2 2对对 若恒有若

6、恒有 则称则称 超优于超优于【例【例13.2】第3行优超于第2行，第1行优超于第5行第1列优超于第5列，第4列优超于第2列 第1行优于2、3行 最优纯策略（1,2）1/3/202310管理运筹学课件【例13.3】某地区有甲、乙两家企业生产同种产品，采取相同的价格出售，为了提高市场份额，均采取做广告的方式扩大自己的销售量。甲和乙均有三种广告策略。甲企业所占的市场份额增加的百分数如下面矩阵A所示。1/3/202311管理运筹学课件13.2.2 最大最小原则最大最小原则【例【例13.4】1/3/202312管理运筹学课件13.3.1 混合策略的概念混合策略的概念【例例13.5】猜猜硬硬币币游游戏戏：

7、甲甲、乙乙两两个个儿儿童童玩玩猜猜硬硬币币游游戏戏，甲甲手手中中拿拿着着一一枚枚硬硬币币，把把硬硬币币盖盖在在桌桌子子上上，让让儿儿童童乙乙猜猜是是正正面面向向上上还还是是反反面面向向上上。如如若若猜猜对对甲甲给给乙乙1元元钱钱，猜猜错错乙乙给给甲甲1元元钱。钱。猜猜硬硬币币游游戏戏属属于于矩矩阵阵对对策策，儿儿童童甲甲的的策策略略有有出出正正面面向向上上(1)和和出出反反面面向向上上(2)，儿儿童童乙乙的的策策略略有有猜猜正正面面向向上上(1)和猜反面向上和猜反面向上(2)。1/3/202313管理运筹学课件13.3.1 混合策略的概念混合策略的概念设设甲甲出出正正面面(1)的的概概率率x,

8、出出反反面面(2)的的概概率率1-x;乙乙猜猜正正面面(1)的的概概率率y,猜反面猜反面(2)的概率的概率1-y。则乙两个策略的期望值分别为。则乙两个策略的期望值分别为:(1)当当x0.5时时，理性的儿童乙会选择，理性的儿童乙会选择猜正面猜正面;(3)当当x=0.5时，时，儿童乙不论采取何种策略，平均赢得都是零。，儿童乙不论采取何种策略，平均赢得都是零。乙的策略乙的策略同理甲的策略同理甲的策略最优混合策略最优混合策略1/3/202314管理运筹学课件13.3.1 混合策略的概念混合策略的概念由于甲乙都是理智的，故由于甲乙都是理智的，故混合扩充：设有矩阵对策混合扩充：设有矩阵对策混合扩充混合扩充

9、1/3/202315管理运筹学课件13.3.1 混合策略的概念混合策略的概念当甲采取混合策略x,乙采取混合策略y,则称(x,y)为一个混合局势混合局势.表示一个混合策略矩阵对策及G的一个混合扩充混合扩充.1/3/202316管理运筹学课件13.3.2 图解法图解法图图解解法法求求解解矩矩阵阵对对策策，一一般般适适用用于于赢赢得得矩矩阵阵为为 或或 的的对对策策问问题题，对对于于 和和 都都较较大大的的对对策策问问题题就就不不适适用用了了。下下面面通过例子来说明这种方法。通过例子来说明这种方法。解解 设设甲甲的的混混合合策策略略为为x,(1-x),x0,1,则则 乙乙 分分 别别 使使 用用1,

10、2,3时时,甲赢得值甲赢得值:0 1 x x*7 2 15 3 22 11 3步骤步骤:(1)绘制绘制x数轴数轴,标出标出x取值范围取值范围0,1(2)x取取0和和1,确确定定三三条条直直线线端端点点,绘绘制制三三条甲赢得值直线条甲赢得值直线(3)由由于于乙乙是是理理智智的的,甲甲的的赢赢得得值值只只能能是最小的是最小的(粗线所示粗线所示)(4)甲甲只只能能在在最最小小中中取取最最大大,对对应应的的策策略略为为 ,最最优优对对策策值值为为V*=49/11【例例13.7】求求解解矩矩阵阵对对策策 ，其中，其中1/3/202317管理运筹学课件13.3.2 图解法图解法0 1 x x*7 2 15

11、 3 22 11 3从从图图还还可可以以看看出出局局中中人人乙乙的的最最优优混合策略为混合策略为23的组合的组合.故故1的的概概率率为为0.设设2,3的的概概率率为为y,(1-y).由效率矩阵由效率矩阵:可可知知,当当甲甲使使用用1,2,时时,乙乙的的损失值为损失值为:由由于于甲甲是是理理智智的的,故故乙乙取取最最大大损损失失(粗线粗线)乙乙会会在在最最大大损损失失中中找找出出最最小小,即即乙最优混合策略为乙最优混合策略为:0 1 y y*3 111 5 2 2y分别取分别取0和和1,绘制图形如下绘制图形如下:1/3/202318管理运筹学课件13.3.3 线性规划法线性规划法乙乙采采取取策策

12、略略组组合合y1,yn时时,是是从从利利己己主主义义出出发发的的,会会使使自自己己的的期期望望损损失失最小最小(也即甲的赢得最小也即甲的赢得最小)甲甲会会使使用用某某种种策策略略组组合合x1,xm,使使得得在在最最小小赢赢得得的的概概率率组组合合尽尽可可能能地地大大.因此有因此有:1/3/202319管理运筹学课件13.3.3 线性规划法线性规划法乙乙会会使使用用某某种种策策略略组组合合y1,yn,使使得得最最大损失的某种概率组合尽可能地小大损失的某种概率组合尽可能地小.因此有因此有:同同 理理,甲甲 采采 取取 策策 略略 组组 合合x1,xm 时时,也也是是从从利利己己主主义义出出发发的的

13、,会会使使自自己己的的期期望望赢赢得得最最大大(也也即即乙乙的的损失最大损失最大)1/3/202320管理运筹学课件综综上上所所述述,二二人人零零和和对对策策可可以以表表述述成成一一对对对对偶偶规规划划:【例13.7】解解 写出一对对偶模型写出一对对偶模型解得解得:求得最优混合局势求得最优混合局势:1/3/202321管理运筹学课件13.4 纳什均衡纳什均衡1/3/202322管理运筹学课件13.4 纳什均衡纳什均衡表示成赢得矩阵表示成赢得矩阵:如果某情况下无一参与者可以独自行动而增加收如果某情况下无一参与者可以独自行动而增加收益，则此策略组合被称为纳什均衡点。益，则此策略组合被称为纳什均衡点

14、。“纳什均纳什均衡衡”，也叫非合作均衡，由诺贝尔经济学奖获得，也叫非合作均衡，由诺贝尔经济学奖获得者者美国普林斯顿大学约翰美国普林斯顿大学约翰纳什提出。纳什提出。“纳什均衡纳什均衡”描述的就是一种非合作博弈均衡，在现实中非合作的情描述的就是一种非合作博弈均衡，在现实中非合作的情况要比合作情况普遍。所以况要比合作情况普遍。所以“纳什均衡纳什均衡”是对冯是对冯诺依曼和摩根斯坦诺依曼和摩根斯坦的合作博弈理论的重大发展，甚至可以说是一场革命。的合作博弈理论的重大发展，甚至可以说是一场革命。纳什均衡也分为纯策略与混合策略纳什均衡也分为纯策略与混合策略.纯策略可采取纯策略可采取“划线法划线法”；混合；混合

15、策略可采取线性规划方法。策略可采取线性规划方法。1/3/202323管理运筹学课件仍以囚徒困境为例，说明纯策略下纳什均衡的求取。（1）当李四选择坦白，张三也选择坦白，坐5年牢，否则将坐10年牢（a）；（2）当李四选择抵赖，张三还选择坦白，坐3月牢，否则会坐1年牢（b）；（3）当张三选择坦白，李四也选择坦白，坐5年牢，否则将坐10年牢（c）;（4）当张三选择抵赖，李四还选择坦白，坐3月牢，否则会坐1年牢（d）。可见，无论一方采取何种策略，另一方的最优策略均为坦白，故坦白是均衡点。任何一方偏这个均衡点都要受更多的损失。13.4.1 纯策略纳什均衡的划线法纯策略纳什均衡的划线法1/3/202324管

16、理运筹学课件13.4.2 混合策略纳什均衡的混合策略纳什均衡的LP方法方法 由于纳什均衡所解决的问题不是二人零和对策，故对策双方的赢得矩阵由于纳什均衡所解决的问题不是二人零和对策，故对策双方的赢得矩阵不是同一个矩阵，其不是同一个矩阵，其LP模型也不是一对对偶问题。设甲、乙的赢得矩阵模型也不是一对对偶问题。设甲、乙的赢得矩阵分别为分别为A和和B，混合策略概率分别为：，混合策略概率分别为：对于收益等赢得值，有收益最大化对于收益等赢得值，有收益最大化maxV(即即min1/V)模型如下：模型如下：对于成本等损失值，有损失最小化对于成本等损失值，有损失最小化minV(即即max1/V)模型如下：模型如

17、下：1/3/202325管理运筹学课件【例【例13.8】对下表（收益值）求取纳】对下表（收益值）求取纳什均衡。什均衡。解解 甲的收益矩阵甲的收益矩阵 乙的收益矩阵乙的收益矩阵A的的3、4行收益值不大于第行收益值不大于第1行，删除行，删除B的的3、4列收益值不大于第列收益值不大于第1列，删除列，删除收益矩阵简化及使用概率如下：收益矩阵简化及使用概率如下：乙的收益矩阵各元素乙的收益矩阵各元素+4，对甲、，对甲、乙建立乙建立LP模型并求解如下：模型并求解如下：，1/3/202326管理运筹学课件案例案例13-1 市场竞争策略市场竞争策略1/3/202327管理运筹学课件案例案例13-2 对抗赛项目确

18、定对抗赛项目确定1/3/202328管理运筹学课件1/3/202329管理运筹学课件解决方案解决方案 这是一个纳什均衡问题。在甲的收益矩阵中，第2行的收益值均不小于第1、3行，故是一个纯策略问题，即李参加仰泳比赛。由于甲是理智的，他会让李参加仰泳比赛，而乙对付甲的最优策略时，王参加3个项目比赛时的收益值分别为15、13、15。可见王参加仰泳和蛙泳成本是一样的，各以0.5的概率参加。决决策策建建议议 甲队李参加仰泳比赛；乙队王参加参加仰泳或蛙泳比赛。甲队得分12分，乙队得分15分。1/3/202330管理运筹学课件本章小结本章小结对策论是研究具有竞争性质的现象，并为参加者各方提供对策方法的数学理

19、论。无论何种对策，构成一个对策现象的共同特征是具有三个基本要素：局中人、策略集和损益值。本章重点研究的是矩阵对策，又称为二人有限零和对策，是指两个局中人、每一局中人策略数量都是有限的且在任何一对策略组合下两个局中人的损益值之和始终为零的对策。通常矩阵对策表示为G=S1，S2，A在求解矩阵对策时，我们可以采取以下步骤：首先用严格下策反复消去法对赢得矩阵进行简化。判断对策是否存在鞍点，如若存在，可以用“最大最小”原则进行求解。如若不存在鞍点，说明存在最优混合策略。若简化后的矩阵为m2或2n阶，可以采取“图解法”求解。对于比较复杂的矩阵对策，可以采用“线性规划法”进行求解。纳什均衡是解决非零和的重要方法，与零和对策不同的是第一，要分别构造对策各方的收益矩阵第二，对策各方均以收益最大为目标第三，在利用超优原则化简时，以各自的收益矩阵进行比较各方案的收益值第四，对混合策略也以各自的收益矩阵建立LP模型。1/3/202331管理运筹学课件