,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,11,章 二人有限零和对策,第11章 二人有限零和对策,1,第,11,章 二人有限零和对策,11.1,基本概念,11.2,二人有限零和对策,的纯策略对策模型,11.3,二人有限零和对策,的混合策略对策模型,第11章 二人有限零和对策11.1基本概念,2,11.1,基本概念,一、对策现象与对策论,对策和对策论,对策：就是竞争或斗争中的决策,如：政治方面的阶级斗争，经济方面的劳资纠纷，市场竞争，原料竞争，投标竞争，外贸谈判，军备竞赛，各种体育比赛等,对策论：把各式各样的冲突现象抽象成一种数学模型，然后给出分析这些问题的方法和解。,11.1 基本概念一、对策现象与对策论对策和对策论,3,对策论数学角度,博弈论经济角度,.,对策论的历史,春秋战国时期孙子兵法,殷代围棋,19,世纪西方人把对策论应用于经济领域,对策论数学角度,4,40,年代中期对策论作为一种数学理论,1944,年，美籍匈牙利数学家纽曼,（,Neuman),经济学家曼格斯特,（,Morgenstern),对策论及其在经济管理中的应用,在,40,年代发展迅速，缘于二战中军事的需要，二战后又应用于其他领域。,40年代中期对策论作为一种数学理论,5,50,年代是对策论发展的鼎盛时期，纳什和夏普利等提出了讨价还价模型和合作对策的“核”的概念。,60年代，泽尔腾（1965）引入动态分析，提出“精练纳什均衡”概念。,海萨尼（1967-1968）则把不完全信息引入对策论的研究。,50年代是对策论发展的鼎盛时期，纳什和夏普利等提出了讨价还价,6,1,-1,0,1,0,-1,-1,1,0,A,石头,剪子,石头,剪子,布,布,赢,B,猜手,:,小孩,A,与,B,猜手,若规定赢 得,1,分，平得,0,分，输得,-1,分，则,A,的赢得可用右表来表示,。,齐王赛马：齐王与大将田忌赛马，各自的马都分为三,等，但齐王的同等马均强于田忌。孙膑给田忌出主意， 用下,-,上，上,-,中，中,-,下， 结果田忌胜出。,.,对策问题举例,下棋、打牌、体育比赛等。,1 -1 0 1 0 -1 -1 1 0A石头,7,4.,对策的分类,动态：是连续时间的动态对策，因此从上一状态到,另一状态的转移用微分描述,对策,零和：得失,二人：,静态： 非零和：得失零和,结盟：多人在一起交换策略非零和,多人零和,不结盟：多人在一起交换策略非零和,4.对策的分类,8,二,.,对策问题的组成（几个基本要素）,1.,局中人：,一局对策的参加者。,2.,策略：,局中人在一局对策中对付对手的一个行动方案。策略全体称为策论集。,S=s,1,s,2,s,m,局中人甲的策略集,D=d,1,d,2,d,n,局中人乙的策略集,3.,局势：,在一局对策中，每个局中人都选定一个策略后的各策略的组合。表示为（,S,i,D,j,).,4.,得失值（赢得函数）：,局中人选定某策略后相应的收益值。表示为,R,甲,（,s,i,d,j,),甲的收益,R,乙,（,s,i,d,j,),乙的收益,二.对策问题的组成（几个基本要素）,9,11.2,二人有限零和对策的纯策略对策模型,二人：指参加对策的局中人有个。,有限：指每个局中人的策略集为有限集。,零和：指在任一局势下，双方收益之和为。,11.2 二人有限零和对策的纯策略对策模型 二人：指参加对,10,M,一、纯策略对策模型矩阵对策,M一、纯策略对策模型矩阵对策,11,二、纯策略对策的解,1,、纯策略分析,例：今有甲、乙两厂生产同一种产品，它们都想通过内部改革挖掘，获得更多得市场份额。已知两厂分别都有三个策略措施。据预测，当双方采取不同的策略措施后两厂的市场占有份额变动情况如下所示。,二、纯策略对策的解,12,d,1,d,2,d,3,S,1,10,-1 3,S,2,12,10 -5,S,3,6 8 5,请你分析，理智情况下，甲、乙两厂最可能出现什么策略，最大收益是多少？,d1 d2 d3,13,d,1,d,2,d,3,S,1,10,-1 3,-1,A= S,2,12,10,-5,-5,S,3,6 8 5*,5*,12 10 5*,(s,3,d,3,),即为双方的最优策略，此时甲得,5,，乙失,5,。有唯一最优策略。,对甲而言，先想最坏，再想最好,则,s*=s,3,V,甲,=max min a,ij,对乙而言，先想最坏，再想最好,则,d*=d,3,V,乙,=min max a,ij,d1 d2 d3(s3,d,14,、纯策略对策的解,、纯策略对策的解,15,定理,1,：,定理1：,16,运筹学第十一章-二人有限零和对策剖析课件,17,例,只有一个鞍点,例,-2,-3,-4,-2,3,-6,8,3,8,7,例 只有一个鞍点例-2-3-4-2 3-68387,18,例,例,19,(3),优超原理,(3)优超原理,20,例,5,：,用优超原理求解下列对策,s1,s2,s3,s4,d1,d2,d3,d4,d1,d2,d3,d4,s1,s2,s3,s4,s3,s4,d1,d2,s1,s2,s3,s4,d1,d2,s3,s4,d1,s3,d1,故鞍点为（,s,3,d,1,),对策值为,例5： 用优超原理求解下列对策s1s2s3s4d1d2d3,21,练习先用优超原理简化矩阵，再求解。,练习先用优超原理简化矩阵，再求解。,22,11.3,二人有限零和对策的混合策略对策模型,一、基本概念,例：已知对策，；,A= 7 4 4*,3 6 3,7 6*,易知，在纯策略意义下无解。,11.3二人有限零和对策的混合策略对策模型一、基本概念,23,d,1,d,2,x,i,s,1,7,4 x,1,s,2,3,6,y,j,y,1,y,2,x,2,d1 d2 xi,24,当甲取,s,1,时，最少收益为,:min7x,1,y,1,4x,1,y,2,当乙取,d,1,时，最大损失为,:max7x,1,y,1,3x,2,y,1,则,(x*,y*),混合策略下的最优解,E(x*,y*),混合策略下的最优值,当甲取s1时，最少收益为:min7x1y1,4x1y2则,25,二人有限零和对策的混合策略对策模型：,G*=S*,D*;E,其中,:S*=X=(x,1,x,2,x,m,),T,x,i,=1,x,i,0,甲的混合策略集,D,*=y=(y,1,y,2,y,n,),T,y,j,=1,y,j,0,乙的混合策略集,E=E(X,Y)=, a,ij,x,i,y,j,甲的期望收益,乙的期望损失,二人有限零和对策的混合策略对策模型：,26,二、混合策略对策的解,、定义：如果,混合策略对策,G*=S*,D*;E,满足：,、定理：设,G*=(S*,D*;E),为混合对策，则,二、混合策略对策的解、定理：设G*=(S*,D*;E)为混,27,例： 求解下列对策,例： 求解下列对策,28,例：求解矩阵,d,1,d,2,d,3,S,1,10,-1 3,x,1,A= S,2,12 6 7 x,2,S,3,6 8 5 x,3,y,1,y,2,y,3,y(1)= 0,y(2)= 0.50000,y(3)= 0.50000,x(1)= 0,x(2)= 0.75000,x(3)= 0.25000,V,G,*= 6.50000,例：求解矩阵,29,案例企业建厂决策问题,某企业生产甲、乙两种家用电器据预测，若在某地建新厂则要投资,100,万元，每年可净收益,14,万元若将此款存入银行，则有万元利息此外，还有以下信息可供决策者参考：,（）在某地建新厂后，原厂房若不能售出，则要维修，每年将花费,3.2,万元因此，在某地建新厂后的净收益只能是,10.8,万元,（）据预测，今后年中，乙产品的需求量将下降（与进口无关）在此情况下，未被吸收的固定管理费用为,2.,万元，因此，建新,案例企业建厂决策问题,30,厂的净收益只能是,11.7,万元,（）在某地建新厂后，可增加销售额，经计算能多得,2.4,万元的收益，因此，净收益为,16.4,万元反之，若不建新厂将会损失,2.4,万元，扣除利息万元，净损失为,0.,万元,（）竞争者建厂若该企业不在此地建厂，则竞争者将在该地建厂，于是该企业在此地的销售额将被竞争者所占有，将损失,3.,万元，扣除利息万元，净损失,1.,万元,（）进口影响进口产品中对甲产品影响不大，但对乙产品销路的威胁极大若进口产品成功，将会占去的市场此时在该地建新厂不但无,厂的净收益只能是11.7万元,31,收益，反而损失,4.5,万元,根据以上信息，该企业的决策者应如何决策？,解：,原始,预算,（,d,1,),原厂,房未,出售,（,d,2,),需求,量下,降,（,d,3,),增加,销售,（,d,4,),竞争,者建,厂,（,d,5,),进口,影响,（,d,6,),建厂（,s,1,),不建厂,(s,2,),10.8,2,11.7,2,16.4,-0.4,14,-1.6,-4.5,2,收益，反而损失4.5万元原始原厂需求增加竞争进口建厂（s1,32,X=(0.16,0.84)T,Y=(0,0,0,0,0.29,0.71)T,V,G,=0.94,X=(0.16,0.84)T,33,案例,2,俾斯麦海的海空对抗,对策问题,一、相关背景资料,1943,年,2,月，第二次世界大战中的日本，在太平洋战区已处于明显的劣势。为扭转战局，日军统帅山本五十六大将统率下的一支舰队策划了一次军事行动：由集结地,南太平洋新不列颠群岛的拉包尔出发，穿过俾斯麦海，开往新几内亚的莱城，支援困守在那里的日军。山本五十六心中非常明白，在日本舰队穿过俾斯麦海的,3,天航程中，不可能躲开盟军的袭击，他要谋划的是尽可能减少损失。,当盟军获悉此情报以后，盟军统帅麦克阿瑟即命令他麾下的太平洋战区空军司令肯尼将军组织空中打击。,案例2俾斯麦海的海空对抗对策问题,34,日美双方的指挥官及参谋人员都进行了冷静与全面的谋划。,自然条件对于双方来说是已知的。基本情况是：,（,1,）从拉包尔到莱城的海上航线有南线和北线两条，通过时间均为,3,天。,（,2,）气象预报表明，未来,3,天中，北线阴雨，能见度差；而南线则天气晴好，能见度佳。,二、局势估计,局势,1,：,盟军侦察机重点搜索北线，日本舰队也恰好走北线。由于气候恶劣，能见度低以及轰炸机群在南线，因而盟军只能实施两天有效的轰炸。,局势,2,：,盟军侦察机重点搜索北线，而日本舰队走南线。由于发现晚，尽管盟军轰炸机群在南,日美双方的指挥官及参谋人员都进行了冷静与全面的谋划。,35,线，但有效轰炸也只有两天。,局势,3,：,盟军侦察机重点搜索南线，而日本舰队走北线。由于发现晚，盟军轰炸机群在南线，以及北线天气恶劣，故有效轰炸只能实施,1,天。,局势,4,：,盟军侦察机重点搜索南线，日本舰队也恰好走南线。此时，日军舰队被迅速发现，盟军轰炸机群所需航程很短，加之天气晴好，这将使盟军空军在,3,天中皆可实施有效轰炸。,三、历史情况,局势,1,成为事实。即肯尼将军命令盟军侦察机重点搜索北线；而山本五十六命令日本舰队取道北线航行。,线，但有效轰炸也只有两天。,36,盟军飞机在,1,天后发现日本舰队，基地在南线的盟军轰炸机群远程飞行，在恶劣天气中，实施了,2,天有效地轰炸，重创了日本舰队，但未能全歼。,四、数学模型,1,局中人：美日双方决策者,2,策略：美日双方各有两个策略：南线、北线,运筹学第十一章-二人有限零和对策剖析课件,37,3,支付与支付函数：,日军,北线 南线,盟军 北线,2 2,南线,1 3,= A,日军,北线 南线,盟军 北线,-2 -2,南线,-1 -3,= B,五、求解分析,（,1,）局中人,1,（盟军）希望获得的支付（赢得轰炸天数）尽可能多，但同时，他们也深知：,局中人,2,（日军）必然想方设法使自己的付出（被轰炸天数）尽可能少。,3 支付与支付函数：,38,（,2,）因此，盟军参谋部或肯尼将军在作选择时，首先要考虑：选择每个策略时至少能赢得多少，然后从中选取最有利的策略。具体来说：先对支付矩阵,A,各列求极小（至少赢得），然后，在对矩阵各列极小组成的集合中取极大（争取最佳）。于是有：,max min a,ij,max 2, 1,2,（,3,）对于日军参谋部或山本五十六大将，因居于被动地位，故首先考虑在对方每个策略中最多最多损失多少，在此前提下争取损失最小。具体来说：对同一支付矩阵,A,各行求极大（最多损失），然后，对矩阵各行极大组成的集合中取极小（争取最佳）。于是有：,min max a,ij,min 2,3 ,2,（2）因此，盟军参谋部或肯尼将军在作选择时，首先要考虑：选择,39,上述求解思想可概括为：“从最坏处着想，去争取最好的结果”。这是理性思考的表现。,此例中，恰有：,max min a,ij,min max aij ,2,这是实际对局的结果。,上述求解思想可概括为：“从最坏处着想，去争取最好的结果”。这,40,案例,3,中美贸易问题,对策问题,一、相关背景资料,1996,年,5,月,15,日，美国政府借口中国对知识产权保护不力，单方面宣布：对中国出口到美国的纺织品、服装及电子产品实施惩罚性关税，涉及产品金额达,30,亿美元，惩罚性税率达,100,，并于一个月后生效。,当晚，中国外经贸部发表公告，做出了强烈的反应。公告中表示：如果美国政府一意孤行，中国将实施反报复，并与美国贸易报复措施生效的同时生效。在公告中还列举了反报复清单，报复惩罚额相当。,案例3中美贸易问题对策问题,41,二、数学模型,1,局中人：中国、美国,2,我们可以用一些模拟的数据来写出该对策问题的赢得矩阵：,美国,报复 不报复,中国 报复 （,-50* , -50,） （,50* , -150,）,不报复（,-150, 50,） （,20 , 20,）,其中：姑且将双方报复的损失同假设为,50,亿元，双方不报复的收益均假设为,20,亿元，单方报复而另一方不报复，不报复方的损失极为,150,亿元（考虑牵连效应）。,二、数学模型,42,三、结果,这是一个二人非零和对策问题。按平衡偶理论可以得出：策略偶（报复 报复）为唯一的平衡偶。,事实发展是：双方都有允若，也有威胁。由于中方反报复力度相当，又在强化知识产权保护上作了承诺，因而，诱使美方考虑合作与不合作的得与失。双方经过,5,天的磋商，在知识产权问题上达成一致的同时，彼此宣布取消拟采取的贸易报复措施，避免了两败俱伤的结局，得到了好的结果。,由这个案例可以从定性的角度理解软对策的理念与特点。,三、结果,43,