管理运筹学课件第13章对策论.ppt
第13章 对策论,管理运筹学课件,2,2023/9/14,教学目标与要求,【教学目标】1.理解下列基本概念：矩阵对策，矩阵对策三要素，最优纯策略与最优混合策略，鞍点和对策值2.算法要求：(1)会用“超优原则”和“最大最小”原则求矩阵对策的最优纯策略(2)会用“线性规划”方法求矩阵对策的最优混合策略(3)了解纯策略和混合策略的纳什均衡求取。【知识结构】,管理运筹学课件,3,2023/9/14,管理运筹学课件,4,2023/9/14,管理运筹学课件,5,2023/9/14,本章主要内容,13.1 对策论的基本概念13.1.1 对策模型的基本要素13.1.2 对策问题的分类13.2 矩阵对策的纯策略优超原则最大最小原则13.3 矩阵对策的混合策略13.3.1 混合策略的概念13.3.2 图解法13.3.3 线性规划法13.4 纳什均衡13.4.1 纯策略纳什均衡的划线法13.4.2 混合策略纳什均衡的LP方法13.4 应用举例案例13-1 市场竞争策略案例13-2 对抗赛项目确定本章小结,管理运筹学课件,6,2023/9/14,13.1.1 对策模型的基本要素,1局中人局中人(players)是指参与竞争的各方，每方必须有独立的决策能力和承担风险的能力。(如:田忌、齐王）2策略集在对策问题中，局中人为了应对其他局中人的行动而采取的方案和手段称为该局中人的一个策略(strategy)。3赢得及赢得函数局中人采用不同策略对策时，各方总是有得或有失，统称赢得(payoff)或得益。,管理运筹学课件,7,2023/9/14,13.1.2 对策问题的分类,管理运筹学课件,8,2023/9/14,13.1.2 对策问题的分类,管理运筹学课件,9,2023/9/14,13.2 矩阵对策的纯策略,为求出对策模型的解，首先需要对双方的对策条件作如下的假设。(1)对策双方的行为是理智的，对策略的选择不存在任何侥幸心理。(2)局中人选取策略的目标是收益最大或损失最小。(3)局中人同时选取各自的行动策略，且不知道对方选取哪一个策略。(4)对策中的有关规定和要求，局中人是知道的。,管理运筹学课件,10,2023/9/14,超优原则,【例13.2】,第3行优超于第2行，第1行优超于第5行,第1列优超于第5列，第4列优超于第2列,第1行优于2、3行,最优纯策略（1,2）,管理运筹学课件,11,2023/9/14,【例13.3】某地区有甲、乙两家企业生产同种产品，采取相同的价格出售，为了提高市场份额，均采取做广告的方式扩大自己的销售量。甲和乙均有三种广告策略。甲企业所占的市场份额增加的百分数如下面矩阵A所示。,管理运筹学课件,12,2023/9/14,13.2.2 最大最小原则,【例13.4】,管理运筹学课件,13,2023/9/14,13.3.1 混合策略的概念,【例13.5】猜硬币游戏：甲、乙两个儿童玩猜硬币游戏，甲手中拿着一枚硬币，把硬币盖在桌子上，让儿童乙猜是正面向上还是反面向上。如若猜对甲给乙1元钱，猜错乙给甲1元钱。猜硬币游戏属于矩阵对策，儿童甲的策略有出正面向上(1)和出反面向上(2)，儿童乙的策略有猜正面向上(1)和猜反面向上(2)。,管理运筹学课件,14,2023/9/14,13.3.1 混合策略的概念,设甲出正面(1)的概率x,出反面(2)的概率1-x;乙猜正面(1)的概率y,猜反面(2)的概率1-y。则乙两个策略的期望值分别为:,当x0.5时，理性的儿童乙会选择猜正面;(3)当x=0.5时，儿童乙不论采取何种策略，平均赢得都是零。,乙的策略,同理甲的策略,最优混合策略,管理运筹学课件,15,2023/9/14,13.3.1 混合策略的概念,由于甲乙都是理智的，故,混合扩充：设有矩阵对策,混合扩充,管理运筹学课件,16,2023/9/14,13.3.1 混合策略的概念,当甲采取混合策略x,乙采取混合策略y,则称(x,y)为一个混合局势.,表示一个混合策略矩阵对策及G的一个混合扩充.,管理运筹学课件,17,2023/9/14,13.3.2 图解法,图解法求解矩阵对策，一般适用于赢得矩阵为 或 的对策问题，对于 和 都较大的对策问题就不适用了。下面通过例子来说明这种方法。,解 设甲的混合策略为x,(1-x),x0,1,则乙分别使用1,2,3时,甲赢得值:,步骤:(1)绘制x数轴,标出x取值范围0,1(2)x取0和1,确定三条直线端点,绘制三条甲赢得值直线(3)由于乙是理智的,甲的赢得值只能是最小的(粗线所示)(4)甲只能在最小中取最大,对应的策略为,最优对策值为V*=49/11,【例13.7】求解矩阵对策，其中,管理运筹学课件,18,2023/9/14,13.3.2 图解法,从图还可以看出局中人乙的最优混合策略为23的组合.,故1的概率为0.设2,3的概率为y,(1-y).由效率矩阵:,可知,当甲使用1,2,时,乙的损失值为:,由于甲是理智的,故乙取最大损失(粗线)乙会在最大损失中找出最小,即乙最优混合策略为:,y分别取0和1,绘制图形如下:,管理运筹学课件,19,2023/9/14,13.3.3 线性规划法,乙采取策略组合y1,yn时,是从利己主义出发的,会使自己的期望损失最小(也即甲的赢得最小)甲会使用某种策略组合x1,xm,使得在最小赢得的概率组合尽可能地大.因此有:,管理运筹学课件,20,2023/9/14,13.3.3 线性规划法,乙会使用某种策略组合y1,yn,使得最大损失的某种概率组合尽可能地小.因此有:,同理,甲采取策略组合x1,xm 时,也是从利己主义出发的,会使自己的期望赢得最大(也即乙的损失最大),管理运筹学课件,21,2023/9/14,综上所述,二人零和对策可以表述成一对对偶规划:,【例13.7】,解 写出一对对偶模型,解得:,求得最优混合局势:,管理运筹学课件,22,2023/9/14,13.4 纳什均衡,管理运筹学课件,23,2023/9/14,13.4 纳什均衡,表示成赢得矩阵:,如果某情况下无一参与者可以独自行动而增加收益，则此策略组合被称为纳什均衡点。“纳什均衡”，也叫非合作均衡，由诺贝尔经济学奖获得者美国普林斯顿大学约翰纳什提出。,“纳什均衡”描述的就是一种非合作博弈均衡，在现实中非合作的情况要比合作情况普遍。所以“纳什均衡”是对冯诺依曼和摩根斯坦的合作博弈理论的重大发展，甚至可以说是一场革命。纳什均衡也分为纯策略与混合策略.纯策略可采取“划线法”；混合策略可采取线性规划方法。,管理运筹学课件,24,2023/9/14,仍以囚徒困境为例，说明纯策略下纳什均衡的求取。（1）当李四选择坦白，张三也选择坦白，坐5年牢，否则将坐10年牢（a）；（2）当李四选择抵赖，张三还选择坦白，坐3月牢，否则会坐1年牢（b）；（3）当张三选择坦白，李四也选择坦白，坐5年牢，否则将坐10年牢（c）;（4）当张三选择抵赖，李四还选择坦白，坐3月牢，否则会坐1年牢（d）。可见，无论一方采取何种策略，另一方的最优策略均为坦白，故坦白是均衡点。任何一方偏这个均衡点都要受更多的损失。,13.4.1 纯策略纳什均衡的划线法,管理运筹学课件,25,2023/9/14,13.4.2 混合策略纳什均衡的LP方法,由于纳什均衡所解决的问题不是二人零和对策，故对策双方的赢得矩阵不是同一个矩阵，其LP模型也不是一对对偶问题。设甲、乙的赢得矩阵分别为A和B，混合策略概率分别为：,对于收益等赢得值，有收益最大化maxV(即min1/V)模型如下：,对于成本等损失值，有损失最小化minV(即max1/V)模型如下：,管理运筹学课件,26,2023/9/14,【例13.8】对下表（收益值）求取纳什均衡。,解 甲的收益矩阵 乙的收益矩阵,A的3、4行收益值不大于第1行，删除B的3、4列收益值不大于第1列，删除收益矩阵简化及使用概率如下：,乙的收益矩阵各元素+4，对甲、乙建立LP模型并求解如下：,，,管理运筹学课件,27,2023/9/14,案例13-1 市场竞争策略,管理运筹学课件,28,2023/9/14,案例13-2 对抗赛项目确定,管理运筹学课件,29,2023/9/14,管理运筹学课件,30,2023/9/14,解决方案 这是一个纳什均衡问题。在甲的收益矩阵中，第2行的收益值均不小于第1、3行，故是一个纯策略问题，即李参加仰泳比赛。由于甲是理智的，他会让李参加仰泳比赛，而乙对付甲的最优策略时，王参加3个项目比赛时的收益值分别为15、13、15。可见王参加仰泳和蛙泳成本是一样的，各以0.5的概率参加。决策建议 甲队李参加仰泳比赛；乙队王参加参加仰泳或蛙泳比赛。甲队得分12分，乙队得分15分。,管理运筹学课件,31,2023/9/14,本章小结,对策论是研究具有竞争性质的现象，并为参加者各方提供对策方法的数学理论。无论何种对策，构成一个对策现象的共同特征是具有三个基本要素：局中人、策略集和损益值。本章重点研究的是矩阵对策，又称为二人有限零和对策，是指两个局中人、每一局中人策略数量都是有限的且在任何一对策略组合下两个局中人的损益值之和始终为零的对策。通常矩阵对策表示为G=S1，S2，A在求解矩阵对策时，我们可以采取以下步骤：首先用严格下策反复消去法对赢得矩阵进行简化。判断对策是否存在鞍点，如若存在，可以用“最大最小”原则进行求解。如若不存在鞍点，说明存在最优混合策略。若简化后的矩阵为m2或2n阶，可以采取“图解法”求解。对于比较复杂的矩阵对策，可以采用“线性规划法”进行求解。纳什均衡是解决非零和的重要方法，与零和对策不同的是第一，要分别构造对策各方的收益矩阵第二，对策各方均以收益最大为目标第三，在利用超优原则化简时，以各自的收益矩阵进行比较各方案的收益值第四，对混合策略也以各自的收益矩阵建立LP模型。,
