运筹学第十一章二人有限零和对策

第11章二人有限零和对策第11章二人有限零和对策11.1基本概念11.2二人有限零和对策的纯策略对策模型

11.3二人有限零和对策的混合策略对策模型11.1基本概念一、对策现象与对策论对策和对策论对策：就是竞争或斗争中的决策．如：政治方面的阶级斗争，经济方面的劳资纠纷，市场竞争，原料竞争，投标竞争，外贸谈判，军备竞赛，各种体育比赛等．对策论：把各式各样的冲突现象抽象成一种数学模型，然后给出分析这些问题的方法和解。对策论－数学角度博弈论－经济角度２.对策论的历史春秋战国时期－孙子兵法殷代－围棋19世纪－西方人把对策论应用于经济领域40年代中期－对策论作为一种数学理论1944年，美籍匈牙利数学家－纽曼（Neuman)经济学家－曼格斯特（Morgenstern)

《对策论及其在经济管理中的应用》在40年代发展迅速，缘于二战中军事的需要，二战后又应用于其他领域。50年代是对策论发展的鼎盛时期，纳什和夏普利等提出了讨价还价模型和合作对策的“核”的概念。60年代，泽尔腾（1965）引入动态分析，提出“精练纳什均衡”概念。海萨尼（1967-1968）则把不完全信息引入对策论的研究。1-1010-1-110A石头剪子石头剪子布布赢B猜手:小孩A与B猜手,若规定赢得1分，平得0分，输得-1分，则A的赢得可用右表来表示。

③齐王赛马：齐王与大将田忌赛马，各自的马都分为三

等，但齐王的同等马均强于田忌。孙膑给田忌出主意，用下----上，上----中，中----下，结果田忌胜出。②３.对策问题举例①下棋、打牌、体育比赛等。4.对策的分类

动态：是连续时间的动态对策，因此从上一状态到另一状态的转移用微分描述对策零和：得＋失＝０二人：静态：非零和：得＋失≠０零和结盟：多人在一起交换策略非零和多人零和不结盟：多人在一起交换策略非零和

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

R乙（si,dj)—乙的收益11.2二人有限零和对策的纯策略对策模型

二人：指参加对策的局中人有２个。有限：指每个局中人的策略集为有限集。零和：指在任一局势下，双方收益之和为０。M一、纯策略对策模型－矩阵对策二、纯策略对策的解1、纯策略分析例１：今有甲、乙两厂生产同一种产品，它们都想通过内部改革挖掘，获得更多得市场份额。已知两厂分别都有三个策略措施。据预测，当双方采取不同的策略措施后两厂的市场占有份额变动情况如下所示。

d1d2d3S110

-13Ａ＝S212

10-5S3685请你分析，理智情况下，甲、乙两厂最可能出现什么策略，最大收益是多少？

d1d2d3S110

-13-1

A=S2

12

10-5

-5S3685*5*

12105*(s3,d3)即为双方的最优策略，此时甲得5，乙失5。有唯一最优策略。对甲而言，先想最坏，再想最好．则s*=s3,V甲＝５=maxminaij

对乙而言，先想最坏，再想最好．则d*=d3,V乙＝５=minmaxaij２、纯策略对策的解定理1：例２

只有一个鞍点例３-2-3-4-23-68387例４(3)优超原理例5：用优超原理求解下列对策s1s2s3s4d1d2d3d4d1d2d3d4s1s2s3s4s3s4d1d2s1s2s3s4d1d2s3s4d1s3d1故鞍点为（s3,d1)对策值为ＶＧ＊＝２练习先用优超原理简化矩阵，再求解。11.3二人有限零和对策的混合策略对策模型一、基本概念例：已知对策Ｇ＝｛Ｓ，Ｄ；Ａ｝

A=744*36376*易知，Ｇ在纯策略意义下无解。

d1d2xis17

4x1s23

6

yjy1y2x2

当甲取s1时，最少收益为:min{7x1y1,4x1y2}当乙取d1时，最大损失为:max{7x1y1,3x2y1}则(x*,y*)－混合策略下的最优解

E(x*,y*)－混合策略下的最优值二人有限零和对策的混合策略对策模型：

G*={S*,D*;E}

其中:S*={X=(x1,x2,…,xm)T

∑xi=1,xi≥0}

－甲的混合策略集D*={y=(y1,y2,…,yn)T∑yj=1,yj≥0}

－乙的混合策略集E=E(X,Y)=∑∑aijxiyj

－甲的期望收益－乙的期望损失二、混合策略对策的解１、定义：如果混合策略对策

G*={S*,D*;E}满足：２、定理：设G*=(S*,D*;E)为混合对策，则例６：求解下列对策例７：求解矩阵

d1d2d3

S110

-13

x1A=S21267x2S3685x3y1y2y3y(1)=0y(2)=0.50000y(3)=0.50000x(1)=0x(2)=0.75000x(3)=0.25000VG*=6.50000

［案例１］企业建厂决策问题某企业生产甲、乙两种家用电器．据预测，若在某地建新厂则要投资100万元，每年可净收益14万元．若将此款存入银行，则有２万元利息．此外，还有以下信息可供决策者参考：（１）在某地建新厂后，原厂房若不能售出，则要维修，每年将花费3.2万元．因此，在某地建新厂后的净收益只能是10.8万元．（２）据预测，今后１０年中，乙产品的需求量将下降５％（与进口无关）．在此情况下，未被吸收的固定管理费用为2.３万元，因此，建新厂的净收益只能是11.7万元．（３）在某地建新厂后，可增加销售额，经计算能多得2.4万元的收益，因此，净收益为16.4万元．反之，若不建新厂将会损失2.4万元，扣除利息２万元，净损失为0.４万元．（４）竞争者建厂．若该企业不在此地建厂，则竞争者将在该地建厂，于是该企业在此地的销售额将被竞争者所占有，将损失3.６万元，扣除利息２万元，净损失1.６万元．（５）进口影响．进口产品中对甲产品影响不大，但对乙产品销路的威胁极大．若进口产品成功，将会占去８０％的市场．此时在该地建新厂不但无收益，反而损失4.5万元．根据以上信息，该企业的决策者应如何决策？解：原始预算（d1)原厂房未出售（d2)需求量下降（d3)增加销售（d4)竞争者建厂（d5)进口影响（d6)建厂（s1)不建厂(s2)１４２10.8211.7216.4-0.414-1.6-4.52X=(0.16,0.84)TY=(0,0,0,0,0.29,0.71)TVG=0.94［案例2］俾斯麦海的海空对抗——对策问题一、相关背景资料

1943年2月，第二次世界大战中的日本，在太平洋战区已处于明显的劣势。为扭转战局，日军统帅山本五十六大将统率下的一支舰队策划了一次军事行动：由集结地——南太平洋新不列颠群岛的拉包尔出发，穿过俾斯麦海，开往新几内亚的莱城，支援困守在那里的日军。山本五十六心中非常明白，在日本舰队穿过俾斯麦海的3天航程中，不可能躲开盟军的袭击，他要谋划的是尽可能减少损失。当盟军获悉此情报以后，盟军统帅麦克阿瑟即命令他麾下的太平洋战区空军司令肯尼将军组织空中打击。

日美双方的指挥官及参谋人员都进行了冷静与全面的谋划。自然条件对于双方来说是已知的。基本情况是：

（1）从拉包尔到莱城的海上航线有南线和北线两条，通过时间均为3天。（2）气象预报表明，未来3天中，北线阴雨，能见度差；而南线则天气晴好，能见度佳。二、局势估计

局势1：盟军侦察机重点搜索北线，日本舰队也恰好走北线。由于气候恶劣，能见度低以及轰炸机群在南线，因而盟军只能实施两天有效的轰炸。

局势2：盟军侦察机重点搜索北线，而日本舰队走南线。由于发现晚，尽管盟军轰炸机群在南线，但有效轰炸也只有两天。

局势3：盟军侦察机重点搜索南线，而日本舰队走北线。由于发现晚，盟军轰炸机群在南线，以及北线天气恶劣，故有效轰炸只能实施1天。

局势4：盟军侦察机重点搜索南线，日本舰队也恰好走南线。此时，日军舰队被迅速发现，盟军轰炸机群所需航程很短，加之天气晴好，这将使盟军空军在3天中皆可实施有效轰炸。三、历史情况局势1成为事实。即肯尼将军命令盟军侦察机重点搜索北线；而山本五十六命令日本舰队取道北线航行。

盟军飞机在1天后发现日本舰队，基地在南线的盟军轰炸机群远程飞行，在恶劣天气中，实施了2天有效地轰炸，重创了日本舰队，但未能全歼。四、数学模型

1局中人：美日双方决策者

2策略：美日双方各有两个策略：南线、北线3支付与支付函数：日军北线南线盟军北线22

南线13=A

日军北线南线盟军北线-2-2

南线-1-3=B五、求解分析（1）局中人1（盟军）希望获得的支付（赢得轰炸天数）尽可能多，但同时，他们也深知：局中人2（日军）必然想方设法使自己的付出（被轰炸天数）尽可能少。

（2）因此，盟军参谋部或肯尼将军在作选择时，首先要考虑：选择每个策略时至少能赢得多少，然后从中选取最有利的策略。具体来说：先对支付矩阵A各列求极小（至少赢得），然后，在对矩阵各列极小组成的集合中取极大（争取最佳）。于是有：

maxmin{aij}＝max{2,1}＝2（3）对于日军参谋部或山本五十六大将，因居于被动地位，故首先考虑在对方每个策略中最多最多损失多少，在此前提下争取损失最小。具体来说：对同一支付矩阵A各行求极大（最多损失），然后，对矩阵各行极大组成的集合中取极小（争取最佳）。于是有：

minmax{aij}＝min{2,3}＝2

上述求解思想可概括为：“从最坏处着想，去争取最好的结果”。这是理性思考的表现。此例中，恰有：

maxmin{aij}＝minmax{aij}＝2

这是实际对局的结果。［案例3］中美贸易问题——对策问题一、相关背景资料

1996年5月15日，美国政府借口中国对知识产权保护不力，单方面宣布：对中国出口到