数学建模-对策论省名师优质课赛课获奖课件市赛课一等奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Operations Research,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,GAME THEORY对 策 论,第11章,第1页,5/1/2025,1,11 矩阵对策,6.1 引言,6.2 对策论基本概念,6.3 矩阵对策概念及模型,6.4 矩阵对策纯策略解（鞍点解）,6.5 矩阵对策混合策略解（mixed strategic solution）,6.6 矩阵对策解法,第2页,5/1/2025,2,Operations Research,6.1.1 何谓对策论（Game Theory）？,6.1.2 对策例子,6.1.3 对策论诞生与发展简况,6.1 引 言,第3页,5/1/2025,3,Operations Research,6.1.1 何谓对策论(Game Theory)？,定义：对策论亦称,竞赛论或博弈论,，是研究含有,斗争或竞争性质,现象数学理论和方法。,囚徒困境,局中人2,坦白,不坦白,局中人1,坦白,(-6,-6),(-1,-8),不坦白,(-8,-1),(-2,-2),第4页,5/1/2025,4,Operations Research,齐王赛马,决斗问题：神雕侠侣中武林盟主大会,6.1.2 对策例子,朱子柳,霍 都,郭 靖,达尔巴,郝大通,金轮法王,第5页,5/1/2025,5,Operations Research,6.1.3 对策论诞生与发展简况,早期工作,1912年E.Zermelo 关于集合论在象棋对策中应用,1921年E.Borel 引入最优策略,1928年J.V.Neumann证实了一些猜测,第6页,5/1/2025,6,Operations Research,6.1.3 对策论诞生与发展简况,产生标志,1944年J.V.Neumann和O.Morgenstern”对策论与经济行为”（Theory of Games and Economic Behavior）,发展成熟,Nash均衡、经济博奕论、信息不对称对策和广义对策,第7页,5/1/2025,7,Operations Research,6.2 对策论基本概念,6.2.1 局中人（Player）,6.2.2 策略（Strategy）,6.2.3 支付与支付函数,第8页,5/1/2025,8,Operations Research,6.2.1 局中人（Player）,1、局中人：,在一场竞争或斗争中决议者称为该局对策局中人,通常，一局对策含有两个或两个以上-决议者，普通用I表示局中人集合：,第9页,5/1/2025,9,Operations Research,6.2.1 局中人（Player）,2、对策分类：,依据局中人数量，可将对策分为,有限对策,无限对策(n2),对策,无限零和对策,无限非零和对策,有限零和对策,有限非零和对策,第10页,5/1/2025,10,Operations Research,6.2.2 策略（Strategy）,1、,策略与,策略集,局中人指导自己自始至终怎样行动一个方案，称为,策略,(Strategy),由全部策略组成集合，称为,策略集,(StrategySet),第11页,5/1/2025,11,Operations Research,6.2.2 策略（Strategy）,2、策略集元素：,对于局中人i,iI，都有自己策略集S,i,通常每一局中人策略集中最少应包含两个策略,对于例4包、剪、锤游戏。假设有两个局中人I=甲，乙，甲策略集为S,甲,=(包)、(剪)、(锤)=,a,1,、,a,2,、,a,3,;乙策略集为S,乙,=(包)、(剪)、(锤)=b,1,、b,2,、b,3,;,第12页,5/1/2025,12,Operations Research,6.2.3 支付与支付函数,1、局势：,各局中人所选定策略形成策略组,2、策略组,若s,i,是第i个局中人一个策略，则n个局中人策略组 s=(s,1,s,2,s,n,),就是一个,局势,。,第13页,5/1/2025,13,Operations Research,6.2.3 支付与支付函数,比如，对于包、剪、锤游戏。假设有两个局中人I=甲，乙，甲策略集为S,甲,=(包)、(剪)、(锤)=(a,1,)、(a,2,)、(a,3,);乙策略集为S,乙,=(包)、(剪)、(锤)=(b,1,)、(b,2,)、(b,3,);,则甲一个策略a,i,，和乙一个策略b,j,就组成一个局势s,ij,.,第14页,5/1/2025,14,Operations Research,6.2.3 支付与支付函数,3、赢得（支付）：,当每个局中人所采取策略确定后，他们就会得到对应收益或损失，称为局中人支付（Payoff）。,若甲一个策略,a,3,(锤)，乙一个策略,b,2,(剪)，则组成一个局势s,32,。在局势s,32,下，甲支付为：,乙支付,第15页,5/1/2025,15,Operations Research,6.2.3 支付与支付函数,4、支付（赢得）函数：,不一样策略会造成不一样支付，所以，支付是策略(,准确说应该是局势,)函数，称为支付函数(payoff function)。,对于例4，两人支付函数分别记为：,和,比如，对于策略,a,3,b,1,第16页,5/1/2025,16,Operations Research,6.2.3 支付与支付函数,5、零和对策和非零和对策,依据各局中人支付代数和是否为0，将对策分为零和对策和非零和对策(non-zero-sum games)。,若在任一局对策中，全体局中人支付总和为0，则该对策称为零和对策，不然称为非零和对策(non-zero-sum games)。,对于前例，显然为零和对策，因为,第17页,5/1/2025,17,Operations Research,6.2.3 支付与支付函数,6、对策分类,依据局中人数目和支付函数代数和,有限对策,n人对策(n2),对策,合作对策,非合作对策,第18页,5/1/2025,18,Operations Research,6.3 矩阵对策概念及模型,1、定义：两个人零和对策称为,矩阵对策,例，“包、剪、锤”游戏中，甲、乙双方各有三种不一样策略，分别为：,第19页,5/1/2025,19,Operations Research,6.3 矩阵对策概念及模型,甲支付情况以下表,1,(包),2,(剪),3,(锤),1,(包),0,-1,1,2,(剪),1,0,-1,3,(锤),-1,1,0,乙策略,甲支付,甲策略,表6.1,第20页,5/1/2025,20,Operations Research,6.3 矩阵对策概念及模型,齐王赛马,1,2,3,4,5,6,1,(,上中下),3,1,1,1,1,-1,2,(,上下中),1,3,1,1,-1,1,3,(,中上下),1,-1,3,1,1,1,4,(,中下上),-1,1,1,3,1,1,5,(,下中上),1,1,-1,1,3,1,6,(,下上中),1,1,1,-1,1,3,田忌策略,齐王赢得,齐王策略,上中下,上下中,中上下,中下上,下中上,下上中,第21页,5/1/2025,21,Operations Research,6.3 矩阵对策概念及模型,表6.1中数字用矩阵形式表示,A称为甲,支付矩阵,。显然，乙,支付矩阵,为-A。,所以，该对策可记为：,第22页,5/1/2025,22,Operations Research,6.3 矩阵对策概念及模型,2、矩阵对策模型,普通地，若局中人，策略集分别为：,为了与后面概念区分开来，我们称,i,为纯策略，,j,为,纯策略,，对于纯策略,i,j,组成策略偶(,i,j,)称为,纯局势,。,第23页,5/1/2025,23,Operations Research,6.3 矩阵对策概念及模型,若支付矩阵为：,ij,表示局势(,i,j,)下，局中人支付,则矩阵对策可记为,G,=,S,1,S,2,A,：即矩阵对策模型。,第24页,5/1/2025,24,Operations Research,6.4 矩阵对策纯策略解,6.4.1 矩阵对策纯策略解例解过程,6.4.2 矩阵对策纯策略解理论基础,6.4.3 矩阵对策纯策略解性质,第25页,5/1/2025,25,Operations Research,例5 设二人零和对策,G,=,S,1,S,2,A,，其中,6.4.1 矩阵对策纯策略解例解过程,而且局中支付矩阵为：,两位局中人都想自己支付最大化。,第26页,5/1/2025,26,Operations Research,6.4.1 矩阵对策纯策略解例解过程,这里我们认为局中人都是理智，从矩阵A进行逻辑推理可知：,假如局中人采取,3,作策略，虽有可能取得最大支付18，不过,局中人分析到这种心理，就会采取,3,策略，使不但得不到最大值18，反而取得很坏结果-8；,一样，局中人为了得到最大支付+12(即局中人支付-12)，会采取,2,作为策略,但局中人也会猜到这种心理,而采取,2,作策略，这么局中人只能得到-3。,第27页,5/1/2025,27,Operations Research,6.4.1 矩阵对策纯策略解例解过程,从以上分析能够看出，局中人选取最优策略时应该考虑到也是十分理智与精明，策略是要以支付最少为目标，所以不能存在任何侥幸心理。局中人也应作一样考虑。,对于局中人来说，应该是从最坏处着想向最好处努力。,第28页,5/1/2025,28,Operations Research,6.4.1 矩阵对策纯策略解例解过程,对局中人来讲，各策略最坏结果分别为：min-6,2,-7=-7,min5,3,6=3,min18,0,-8=-8,min-2,-12,7=-12,这些最坏情况中，最好结果是：,max-7,3,-8,-12=3,第29页,5/1/2025,29,Operations Research,6.4.1 矩阵对策纯策略解例解过程,一样，对局中人而言，各策略最坏结果分别为：,max-6,5,18,-2=18,max2,3,0,-12=3,max-7,6,-18,7=7,在这些最坏情况中，最好结果（损失最小）是,min18,3,7=3,第30页,5/1/2025,30,Operations Research,6.4.1 矩阵对策纯策略解例解过程,1,2,3,1,-6,2,-7,-7,2,5,3,6,3,3,18,0,-8,-8,4,-2,-12,7,-12,18,3,7,第31页,5/1/2025,31,Operations Research,6.4.1 矩阵对策纯策略解例解过程,课堂练习:求解对策 G=S,1,S,2,A,已知：,第32页,5/1/2025,32,Operations Research,定义1,对于矩阵对策G=S,1,S,2,A,假如存在纯局势,6.4.2 矩阵对策纯策略解理论基础,则称,局势,为对策G在纯策略中,解,。,亦称其为G,鞍点,(,saddle point):,(列中最大，行中最小),使得对任意,j,=1,，n,及任意,i,=1,m有：,第33页,5/1/2025,33,Operations Research,6.4.2 矩阵对策纯策略解理论基础,分别称为局中人，最优纯策略。称 为对策G,值(value),，记为,第34页,5/1/2025,34,Operations Research,6.4.2 矩阵对策纯策略解理论基础,定理1 矩阵对策G=S,1,S,2,A存在最优纯策略充分必要条件为：,第35页,5/1/2025,35,Operations Research,6.4.2 矩阵对策纯策略解理论基础,求对G解和值。,例6 已知 G=S,1,S,2,A，,其中,第36页,5/1/2025,36,Operations Research,6.4.2 矩阵对策纯策略解理论基础,1,2,3,4,1,8,6,8,6,6,2,1,3,4,-3,-3,3,9,6,7,6,6,4,-3,1,10,3,-3,9,6,10,6,6,解：依据A可得,第37页,5/1/2025,37,Operations Research,6.4.2 矩阵对策纯策略解理论基础,因为：,四个局势均为G鞍点，且,故知：,第38页,5/1/2025,38,Operations Research,6.4.3 矩阵对策纯策略解性质,从上例可知，对策解能够是不唯一，但对策值是唯一。对策解不唯一时，应满足下面两条性质：,1.,无差异性,：,若,与,是矩阵对策G两个解，则,即对策值相等，它们在矩阵中元素相同。,第39页,5/1/2025,39,Operations Research,6.4.3 矩阵对策纯策略解性质,2.可交换性,：若,与,是矩阵对策G两个解,则,与,也是对策解。,第40页,5/1/2025,40,Operations Research,6.4.3 矩阵对策纯策略解性质,是不是每一个矩阵对策都有纯策略解（鞍点）？,1,2,3,1,0,-1,1,-1,2,1,0,-1,-1,3,-1,1,0,-1,1,1,1,答案是否定。,第41页,5/1/2025,41,Operations Research,6.5 矩阵对策混合策略解,6.5.1 混合策略与混合扩充（mixed strategic solution）,6.5.2 解基本定理,第42页,5/1/2025,42,Operations Research,6.5.1 混合策略与混合扩充,1,2,1,3,6,3,2,5,4,4,5,6,1、问题提出,第43页,5/1/2025,43,Operations Research,6.5.1 混合策略与混合扩充,该对策问题表明不存在使对立双方到达,平衡局势,，所以，局中人采取任何一个纯策略，都有一定风险。所以，在这种情况下，局中人必须隐瞒自己选取策略意图。,第44页,5/1/2025,44,Operations Research,6.5.1 混合策略与混合扩充,2、问题处理方案设计,这时我们能够构想局中人随机地选取纯策略来进行对策。即在一局对策中，局中人以,概率,来选取纯策略,其中,满足,于是得到一个m维,概率,向量,第45页,5/1/2025,45,Operations Research,6.5.1 混合策略与混合扩充,一样对于局中人,有对应一个n维概率向量,满足,y,j,表示局中人选取纯策略,j,概率。,第46页,5/1/2025,46,Operations Research,6.5.1 混合策略与混合扩充,3、混合策略概念引入,定义:若给定一个矩阵对策G=S,1,S,2,A,其中,则我们把纯策略集对应概率向量：,与,分别称作局中人、混合策略，(X,Y)称为一个,混合局势,。,第47页,5/1/2025,47,Operations Research,6.5.1 混合策略与混合扩充,假如局中人选取策略为,局中人选取,因为两局中人分别选取策略,事件能够看成使相互独立,4、混合策略局中人支付,假如局中人选取策略为,第48页,5/1/2025,48,Operations Research,6.5.1 混合策略与混合扩充,就是局中人支付值。,所以局势(,i,，,j,)出现概率是,x,i,y,j,。从而知局中人支付,ij,概率是,x,i,y,j,。,于是，数学期望值：,第49页,5/1/2025,49,Operations Research,6.5.1 混合策略与混合扩充,令：,则称,为G,混合扩充,。,5、混合扩充,第50页,5/1/2025,50,Operations Research,6.5.1 混合策略与混合扩充,定义2,假如存在,满足:对任意,及,都有：,则称,为G（在混合策略下）,解,.,分别称为局中人、,最优,(混合),策略,.,称为对策G（在混合意义下）,值,，记为,第51页,5/1/2025,51,Operations Research,6.5.1 混合策略与混合扩充,例7,设,其中,求它解及值。,解：显然该问题无鞍点解。设局中人、混合策略分别为：,X=(x1,x2),Y=(y1,y2).则,第52页,5/1/2025,52,Operations Research,6.5.1 混合策略与混合扩充,则局中人支付数学期望为：,第53页,5/1/2025,53,Operations Research,6.5.1 混合策略与混合扩充,可见:当,第54页,5/1/2025,54,Operations Research,6.5.1 混合策略与混合扩充,显然,第55页,5/1/2025,55,Operations Research,6.5.1 混合策略与混合扩充,由定义1知：,分别是局中人、最优策略，且,第56页,5/1/2025,56,Operations Research,6.5.2 解基本定理,定理2 (基本定理),任意一个矩阵对策,其中,一定有解(在混合策略意义下),且假如G值是V,则以下两组不等式解是局中人,最优策略:,第57页,5/1/2025,57,Operations Research,6.5.2 解基本定理,（11-1）,（11-2）,第58页,5/1/2025,58,Operations Research,6.5.2 解基本定理,（1）若,则,（G值）,（2）若,则,（4）若,则,（3）若,则,可用例7验证,定理3,若 是对策G(同前)最优混合局势,则对某一个i或j来说：,第59页,5/1/2025,59,Operations Research,6.5.2 解基本定理,y,1,y,2,y,n,1,2,n,x,1,1,a,11,a,12,a,1n,V,1,x,2,2,a,21,a,22,a,2n,V,2,x,m,m,a,m1,a,m2,a,mn,V,m,V,1,V,2,V,n,V,V,第60页,5/1/2025,60,Operations Research,6.6 矩阵对策解法,6.6.1 图解法,6.6.2 优势法,6.6.3 简化计算法,6.6.4 线性规划解法,第61页,5/1/2025,61,Operations Research,6.6.1 图解法,例8,已知：,其中,求矩阵对策解和值。,第62页,5/1/2025,62,Operations Research,解:设局中人 混合策略为,(x,1-x),T,x0,1。,对局中人而言，他最少可能收入为局中,人选取,1,，,2,所确定两条直线(定理3知):,6.6.1 图解法,V,1,=5x+20(1-x)=20-15x,V,2,=35x+10(1-x)=25x+10,因为,x1,和,x2,一定大于0,在x处纵坐标中最小者.,局中人用“最大最小”标准选取自己策略,即:,第63页,5/1/2025,63,Operations Research,D点为极值点,D点坐标为：,即,最优混,合策略为：,E,D(1/4,16),V,V,1,=5x+20(1-x)=20-15x,V,2,=35x+10(1-x)=25x+10,x,F,从上图能够看出：,就是折线EDF.,第64页,5/1/2025,64,Operations Research,6.6.1 图解法,同理，对局中人而言有,V=5y+35(1-y)=35-30y,V=20y+10(1-y)=10+10y,最小最大点为:,即,最优解为：,对策值为：,第65页,5/1/2025,65,Operations Research,6.6.1 图解法,F,G(5/8,16),H,Y,V=5y+35(1-y)=35-30y,V=20y+10(1-y)=10+10y,第66页,5/1/2025,66,Operations Research,6.6.1 图解法,课堂练习p145-10.4-3：求解以下矩阵对策，已知赢得矩阵为：,第67页,5/1/2025,67,Operations Research,6.6.1 图解法,例9,已知：,其中,求对策解和值。,解：显然无鞍点，作混合扩充：,第68页,5/1/2025,68,Operations Research,6.6.1 图解法,对局中人而言，若选取,时，最小可能收入为以下四条直线在x处,纵坐标中最小者,v=2x+4(1-x)=4-2x (1),v=3x+(1-x)=2x+1 (2),v=x+6(1-x)=-5x+6 (3),v=5x (4),第69页,5/1/2025,69,Operations Research,6.6.1 图解法,从图上能够看出 B点坐标即为所求极值点.,A,B,(2),(3),(1),(4),B点坐标为:,即,最优解为,第70页,5/1/2025,70,Operations Research,6.6.1 图解法,同理可得：,v=2y,1,+3y,2,+y,3,+5y,4,(5),v=4y,1,+y,2,+6y,3,(6),由上节定理3求出最优解,将 分别代入方程(1)(4)得：,第71页,5/1/2025,71,Operations Research,6.6.1 图解法,定理3(4),定理3(2),定理3(2),定理3(4),第72页,5/1/2025,72,Operations Research,6.6.1 图解法,代入(5)、(6)得：,解之得：,故最优策略为,第73页,5/1/2025,73,Operations Research,6.6.2 优势法,对于普通矩阵对策,其中,定义3,若对固定i、k有,若对固定j和l，有,则称,优超,，记为,则称,优超,，记为,第74页,5/1/2025,74,Operations Research,6.6.2 优势法,(1),定理4,设G中某个,被其余,之一优超,由G可得,，其中,于是有,(2),中局中人最优策略就是G中,最优策略；,第75页,5/1/2025,75,Operations Research,6.6.2 优势法,若,是在,中最优解，则,为在G中最优解.,(3),第76页,5/1/2025,76,Operations Research,6.6.2 优势法,例10 已知某矩阵对策G支付矩阵为：,求解这个矩阵对策。,第77页,5/1/2025,77,Operations Research,6.6.2 优势法,解：,显然无鞍点，因为A阶数为,图解法失效。由定义可知,由定理1可将该问题简化为:,第78页,5/1/2025,78,Operations Research,6.6.2 优势法,可用图解法求得最优解和值分别为：,由,又可看出：,从,又可看出：,，所以得：,第79页,5/1/2025,79,Operations Research,6.6.2 优势法,即可得到对策G解为：,值为,V=5。,第80页,5/1/2025,80,Operations Research,6.6.3 简化计算法,定理5 若矩阵对策,其中d为常数，则G,1,与G,2,有相同解，且对策值相差一个常数d，即：,第81页,5/1/2025,81,Operations Research,6.6.3 简化计算法,推论1 若矩阵对策,其中k0为常数，则G,1,与G,2,有相同解,且,第82页,5/1/2025,82,Operations Research,6.6.3 简化计算法,例11 已知某矩阵对策G支付矩阵以下：,解：由推论1可取,得同解矩阵：,第83页,5/1/2025,83,Operations Research,6.6.3 简化计算法,由定理1可取d=-2，简化为：,由 v=4x+0(1-x)=4x,v=0 x+1(1-x)=1-x,则,由 v=4y+0(1-y)=4y,v=0y+1(1-y)=1-y,则,第84页,5/1/2025,84,Operations Research,6.6.3 简化计算法,原问题解为：,第85页,5/1/2025,85,Operations Research,6.6.4 线性规划解法,考虑普通问题：其中,其混合扩充为：,第86页,5/1/2025,86,Operations Research,6.6.4 线性规划解法,当局中人选定任一混合策略时,便确定了n个数：,因为局中人支付期望值为：,第87页,5/1/2025,87,Operations Research,6.6.4 线性规划解法,若矩阵对策值为,则由定理2可知(参见309陈说),第88页,5/1/2025,88,Operations Research,6.6.4 线性规划解法,不失普通，假设V0,令,定理 2第一组不等式,第89页,5/1/2025,89,Operations Research,6.6.4 线性规划解法,第90页,5/1/2025,90,Operations Research,6.6.4 线性规划解法,同理最优混合策略能够化归为：,值大于零矩阵对策求解能够转化成为求解一对互为对偶线性规划问题()和().,第91页,5/1/2025,91,Operations Research,6.6.4 线性规划解法,例12 设有一个矩阵对策，其局中人,支付矩阵为,求最优解及值。,第92页,5/1/2025,92,Operations Research,6.6.4 线性规划解法,解：显然无鞍点解，求解问题可化成两个互为对偶线性规划问题：,第93页,5/1/2025,93,Operations Research,6.6.4 线性规划解法,第94页,5/1/2025,94,Operations Research,6.6.4 线性规划解法,经过线性规划,(),或,(),可得：,第95页,5/1/2025,95,Operations Research,6.6.4 线性规划解法,即原问题得解为,值为:,第96页,5/1/2025,96,Operations Research,The,End,第11章 对 策 论,第97页,5/1/2025,97,Operations Research,