运筹学第十一章二人有限零和对策课件.ppt

《运筹学第十一章二人有限零和对策课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第十一章二人有限零和对策课件.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学第十一章二人有限零和对策第1页，此课件共40页哦第第11章章 二人有限零和对策二人有限零和对策u11.1基本概念基本概念u11.2二人有限零和对策二人有限零和对策的纯策略对策模型的纯策略对策模型u 11.3二人有限零和对策二人有限零和对策的混合策略对策模型的混合策略对策模型第2页，此课件共40页哦11.1 基本概念基本概念一、对策现象与对策论一、对策现象与对策论1.对策和对策论对策和对策论对策：就是竞争或斗争中的决策对策：就是竞争或斗争中的决策如：政治方面的阶级斗争，经济方面的劳资纠纷，市场如：政治方面的阶级斗争，经济方面的劳资纠纷，市场竞争，原料竞争，投标竞争，外贸谈判，军备竞赛，竞争

2、，原料竞争，投标竞争，外贸谈判，军备竞赛，各种体育比赛等各种体育比赛等对策论：把各式各样的冲突现象抽象成一种数对策论：把各式各样的冲突现象抽象成一种数学模型，然后给出分析这些问题的方法和解。学模型，然后给出分析这些问题的方法和解。第3页，此课件共40页哦对策论数学角度对策论数学角度博弈论经济角度博弈论经济角度.对策论的历史对策论的历史n春秋战国时期孙子兵法春秋战国时期孙子兵法n殷代围棋殷代围棋n19世纪西方人把对策论应用于经济领域世纪西方人把对策论应用于经济领域第4页，此课件共40页哦n40年代中期对策论作为一种数学理论年代中期对策论作为一种数学理论1944年，美籍匈牙利数学家纽曼年，美籍匈牙

3、利数学家纽曼 （Neuman)经济学家曼格斯特经济学家曼格斯特（Morgenstern)对策论及其在经济管理中的应用对策论及其在经济管理中的应用n在在40年代发展迅速，缘于二战中军事的需要，年代发展迅速，缘于二战中军事的需要，二战后又应用于其他领域。二战后又应用于其他领域。第5页，此课件共40页哦n50年代是对策论发展的鼎盛时期，纳什和年代是对策论发展的鼎盛时期，纳什和夏普利等提出了讨价还价模型和合作对策的夏普利等提出了讨价还价模型和合作对策的“核核”的概念。的概念。n60年代，泽尔腾（年代，泽尔腾（1965）引入动态分析，）引入动态分析，提出提出“精练纳什均衡精练纳什均衡”概念。概念。海萨尼

4、海萨尼（1967-1968）则把不完全信息引入对策论的研）则把不完全信息引入对策论的研究。究。第6页，此课件共40页哦 1-1 0 1 0-1-1 1 0A石头剪子石头 剪子布布赢B猜手猜手:小孩小孩A与与B猜手猜手,若若规定赢规定赢 得得1分，平分，平得得0分，输得分，输得-1分，则分，则 A的赢得可用右表来表的赢得可用右表来表示示。齐王赛马：齐王与大将田忌赛马，各自的齐王赛马：齐王与大将田忌赛马，各自的马都分为三马都分为三 等，但齐王的同等马均强于等，但齐王的同等马均强于田忌。孙膑给田忌出主意，田忌。孙膑给田忌出主意，用下用下-上，上，上上-中，中中，中-下，下，结果田忌胜出。结果田忌胜出

5、。.对策问题举例对策问题举例下棋、打牌、体育比赛等。下棋、打牌、体育比赛等。第7页，此课件共40页哦4.对策的分类对策的分类动态：是连续时间的动态对策，因此从上一状态到动态：是连续时间的动态对策，因此从上一状态到另一状态的转移用微分描述另一状态的转移用微分描述对策对策零和：得失零和：得失二人：二人：静态：静态：非零和：得失非零和：得失零和零和结盟：多人在一起交换策略非零和结盟：多人在一起交换策略非零和多人零和多人零和不结盟：多人在一起交换策略非零和不结盟：多人在一起交换策略非零和第8页，此课件共40页哦二二.对策问题的组成（几个基本要素）对策问题的组成（几个基本要素）1.局中人：局中人：一局对

6、策的参加者。一局对策的参加者。2.策略：策略：局中人在一局对策中对付对手的一个行动方案。局中人在一局对策中对付对手的一个行动方案。策略全体称为策论集。策略全体称为策论集。S=s1,s2,sm局中人甲的策略集局中人甲的策略集D=d1,d2,dn局中人乙的策略集局中人乙的策略集3.局势：局势：在一局对策中，每个局中人都选定一个策略后的在一局对策中，每个局中人都选定一个策略后的各策略的组合。表示为（各策略的组合。表示为（Si,Dj).4.得失值（赢得函数）：得失值（赢得函数）：局中人选定某策略后相应的收益局中人选定某策略后相应的收益值。表示为值。表示为R甲甲（si,dj)甲的收益甲的收益 R乙乙（s

7、i,dj)乙的收益乙的收益第9页，此课件共40页哦11.2 二人有限零和对策的纯策略对策模型二人有限零和对策的纯策略对策模型 二人：指参加对策的局中人有个。二人：指参加对策的局中人有个。有限：指每个局中人的策略集为有限集。有限：指每个局中人的策略集为有限集。零和：指在任一局势下，双方收益之和为。零和：指在任一局势下，双方收益之和为。第10页，此课件共40页哦M一、纯策略对策模型矩阵对策第11页，此课件共40页哦二、纯策略对策的解二、纯策略对策的解1、纯策略分析、纯策略分析例：今有甲、乙两厂生产同一种产品，它们都想例：今有甲、乙两厂生产同一种产品，它们都想通过内部改革挖掘，获得更多得市场份额。已

8、知两通过内部改革挖掘，获得更多得市场份额。已知两厂分别都有三个策略措施。据预测，当双方采取不厂分别都有三个策略措施。据预测，当双方采取不同的策略措施后两厂的市场占有份额变动情况如下同的策略措施后两厂的市场占有份额变动情况如下所示。所示。第12页，此课件共40页哦d1 d2 d3 S1 10 -1 3S2 12 10 -5 S3 6 8 5 请你分析，理智情况下，甲、乙两厂最请你分析，理智情况下，甲、乙两厂最可能出现什么策略，最大收益是多少？可能出现什么策略，最大收益是多少？第13页，此课件共40页哦d1 d2 d3 S1 10 -1 3 -1 A=S2 12 10 -5 -5 S3 6 8 5

9、*5*12 10 5*(s3,d3)即为双方的最优策略，此时甲得即为双方的最优策略，此时甲得5，乙失，乙失5。有唯一。有唯一最优策略。最优策略。对甲而言，先想最坏，再想最好对甲而言，先想最坏，再想最好则则s*=s3,V甲甲=max min aij 对乙而言，先想最坏，再想最好对乙而言，先想最坏，再想最好则则d*=d3,V乙乙=min max aij第14页，此课件共40页哦、纯策略对策的解第15页，此课件共40页哦定理1：第16页，此课件共40页哦第17页，此课件共40页哦例例 只有一个鞍点例-2-3-4-2 3-68387第18页，此课件共40页哦例例第19页，此课件共40页哦(3)优超原理

10、优超原理第20页，此课件共40页哦例5：用优超原理求解下列对策s1s2s3s4d1 d2d3 d4d1 d2d3 d4s1s2s3s4s3s4d1 d2s1s2s3s4d1 d2s3s4d1s3d1故鞍点为（s3,d1)对策值为第21页，此课件共40页哦练习先用优超原理简化矩阵，再求解。练习先用优超原理简化矩阵，再求解。第22页，此课件共40页哦11.3二人有限零和对策的混合策略对策模型二人有限零和对策的混合策略对策模型一、基本概念一、基本概念例：已知对策，；例：已知对策，；A=7 4 4*3 6 3 7 6*易知，在纯策略意义下无解。易知，在纯策略意义下无解。第23页，此课件共40页哦d1

11、d2 xi s1 7 4 x1 s2 3 6 yj y1 y2 x2第24页，此课件共40页哦当甲取s1时，最少收益为:min7x1y1,4x1y2当乙取d1时，最大损失为:max7x1y1,3x2y1则(x*,y*)混合策略下的最优解E(x*,y*)混合策略下的最优值第25页，此课件共40页哦u二人有限零和对策的混合策略对策模型：二人有限零和对策的混合策略对策模型：G*=S*,D*;E 其中:S*=X=(x1,x2,xm)T xi=1,xi0甲的混合策略集甲的混合策略集 D*=y=(y1,y2,yn)T yj=1,yj0 乙的混合策略集乙的混合策略集 E=E(X,Y)=aijxiyj 甲的期

12、望收益甲的期望收益 乙的期望损失乙的期望损失第26页，此课件共40页哦二、混合策略对策的解二、混合策略对策的解、定义：如果、定义：如果混合策略对策混合策略对策G*=S*,D*;E满足：、定理：设G*=(S*,D*;E)为混合对策，则第27页，此课件共40页哦例：求解下列对策第28页，此课件共40页哦例：求解矩阵 d1 d2 d3 S1 10 -1 3x1 A=S2 12 6 7 x2 S3 6 8 5 x3 y1 y2 y3 y(1)=0 y(2)=0.50000 y(3)=0.50000 x(1)=0 x(2)=0.75000 x(3)=0.25000 VG*=6.50000 第29页，此课

13、件共40页哦案例企业建厂决策问题案例企业建厂决策问题 某企业生产甲、乙两种家用电器据预测，若在某地建新厂则要投资100万元，每年可净收益14万元若将此款存入银行，则有万元利息此外，还有以下信息可供决策者参考：（）在某地建新厂后，原厂房若不能售出，则要维修，每年将花费3.2万元因此，在某地建新厂后的净收益只能是10.8万元（）据预测，今后年中，乙产品的需求量将下降（与进口无关）在此情况下，未被吸收的固定管理费用为2.万元，因此，建新第30页，此课件共40页哦厂的净收益只能是11.7万元（）在某地建新厂后，可增加销售额，经计算能多得2.4万元的收益，因此，净收益为16.4万元反之，若不建新厂将会损

14、失2.4万元，扣除利息万元，净损失为0.万元（）竞争者建厂若该企业不在此地建厂，则竞争者将在该地建厂，于是该企业在此地的销售额将被竞争者所占有，将损失3.万元，扣除利息万元，净损失1.万元（）进口影响进口产品中对甲产品影响不大，但对乙产品销路的威胁极大若进口产品成功，将会占去的市场此时在该地建新厂不但无第31页，此课件共40页哦收益，反而损失4.5万元根据以上信息，该企业的决策者应如何决策？解：原始预算（d1)原厂房未出售（d2)需求量下降（d3)增加销售（d4)竞争者建厂（d5)进口影响（d6)建厂（s1)不建厂(s2)10.8211.7216.4-0.414-1.6-4.52第32页，此课

15、件共40页哦X=(0.16,0.84)TY=(0,0,0,0,0.29,0.71)TVG=0.94第33页，此课件共40页哦案例案例2俾斯麦海的海空对抗俾斯麦海的海空对抗对策问题对策问题一、相关背景资料一、相关背景资料 1943年2月，第二次世界大战中的日本，在太平洋战区已处于明显的劣势。为扭转战局，日军统帅山本五十六大将统率下的一支舰队策划了一次军事行动：由集结地南太平洋新不列颠群岛的拉包尔出发，穿过俾斯麦海，开往新几内亚的莱城，支援困守在那里的日军。山本五十六心中非常明白，在日本舰队穿过俾斯麦海的3天航程中，不可能躲开盟军的袭击，他要谋划的是尽可能减少损失。当盟军获悉此情报以后，盟军统帅麦

16、克阿瑟即命令他麾下的太平洋战区空军司令肯尼将军组织空中打击。第34页，此课件共40页哦日美双方的指挥官及参谋人员都进行了冷静与全面的谋划。自然条件对于双方来说是已知的。基本情况是：（1）从拉包尔到莱城的海上航线有南线和北线两条，通过时间均为3天。（2）气象预报表明，未来3天中，北线阴雨，能见度差；而南线则天气晴好，能见度佳。二、局势估计二、局势估计 局势1：盟军侦察机重点搜索北线，日本舰队也恰好走北线。由于气候恶劣，能见度低以及轰炸机群在南线，因而盟军只能实施两天有效的轰炸。局势2：盟军侦察机重点搜索北线，而日本舰队走南线。由于发现晚，尽管盟军轰炸机群在南第35页，此课件共40页哦线，但有效轰

17、炸也只有两天。局势3：盟军侦察机重点搜索南线，而日本舰队走北线。由于发现晚，盟军轰炸机群在南线，以及北线天气恶劣，故有效轰炸只能实施1天。局势4：盟军侦察机重点搜索南线，日本舰队也恰好走南线。此时，日军舰队被迅速发现，盟军轰炸机群所需航程很短，加之天气晴好，这将使盟军空军在3天中皆可实施有效轰炸。三、历史情况三、历史情况 局势1成为事实。即肯尼将军命令盟军侦察机重点搜索北线；而山本五十六命令日本舰队取道北线航行。第36页，此课件共40页哦盟军飞机在1天后发现日本舰队，基地在南线的盟军轰炸机群远程飞行，在恶劣天气中，实施了2天有效地轰炸，重创了日本舰队，但未能全歼。四、数学模型四、数学模型 1

18、局中人：美日双方决策者 2 策略：美日双方各有两个策略：南线、北线第37页，此课件共40页哦3 支付与支付函数：日军 北线 南线 盟军 北线 2 2 南线 1 3 =A 日军 北线 南线 盟军 北线 -2 -2 南线 -1 -3 =B五、求解分析五、求解分析（1）局中人1（盟军）希望获得的支付（赢得轰炸天数）尽可能多，但同时，他们也深知：局中人2（日军）必然想方设法使自己的付出（被轰炸天数）尽可能少。第38页，此课件共40页哦（2）因此，盟军参谋部或肯尼将军在作选择时，首先要考虑：选择每个策略时至少能赢得多少，然后从中选取最有利的策略。具体来说：先对支付矩阵A各列求极小（至少赢得），然后，在对矩阵各列极小组成的集合中取极大（争取最佳）。于是有：max min aij max 2,1 2（3）对于日军参谋部或山本五十六大将，因居于被动地位，故首先考虑在对方每个策略中最多最多损失多少，在此前提下争取损失最小。具体来说：对同一支付矩阵A各行求极大（最多损失），然后，对矩阵各行极大组成的集合中取极小（争取最佳）。于是有：min max aij min 2,3 2 第39页，此课件共40页哦上述求解思想可概括为：“从最坏处着想，去争取最好的结果”。这是理性思考的表现。此例中，恰有：max min aij min max aij 2 这是实际对局的结果。第40页，此课件共40页哦