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

S={s1,s2,……,sm}—局中人甲的策略集 D={d1,d2,……,dn}—局中人乙的策略集 3.局势：在一局对策中，每个局中人都选定一个策略 后的各策略的组合。表示为（Si,Dj). 4.得失值（赢得函数）：局中人选定某策略后相应的 收益值。表示为 R甲（si,dj)—甲的收益 R乙（si,dj)—乙的收益
３.对策问题举例 ①下棋、打牌、体育比赛等。
② 齐王赛马：齐王与大将田忌赛马，各自的 马都分为三 等，但齐王的同等马均强于 田忌。孙膑给田忌出主意， 用下----上 ，上----中，中----下， 赢 B 石头 剪子 布 A 结果田忌胜出。 石头 0 1 -1 ③猜手:小孩A与B猜手, 剪子 -1 1 0 若规定赢 得1分， 布 0 1 -1 平得0分，输得 -1分， 则 A的赢得可用右表来 表示。
8 5 7
5
(3)优超原理
若A中第i, k 行有aij akj , j 1 记si 记d j sk (可在S中取消sk ) 若A中第j, l列有aij ail , i 1 dl (可在D中取消d k )
n 称si 优超于sk 。 m 称d j 优超于dl 。
例5： 用优超原理求解下列对策
4 1 3 1
s1 s2 s3 s4 d1
d1 1 -1 2 0
d2 0 4 s3 2 s3 4
'
s1
s2
d1 d2 s3 2 2 d1 0 4 s4
d2
d1 s3 2 s3 s4 0
s3 （2）
s1 1 s2 -1 A s3 2 s4 0
d1 d2 d3 d4 s1 s2 s3 s4
1 -1 2 0 0 4 2 4 3 0 2 1 4 1 d1 3 d 1 1
s4
d3 d4
d1 d2 d3 d4
0 4 2 4 3 0 2 1
a1n a11 A＝ 为甲的支付矩阵 a a mn m1 其中aij为甲的得（也是乙的失），乙的得即为-aij。
M
故称G （S ,D,A）为纯策略对策模型(矩阵对策)
二、纯策略对策的解 1、纯策略分析
例１：今有甲、乙两厂生产同一种产品，它们 都想通过内部改革挖掘，获得更多得市场份额。 已知两厂分别都有三个策略措施。据预测，当 双方采取不同的策略措施后两厂的市场占有份 额变动情况如下所示。
A
故鞍点为（s3,d1) 对策值为ＶＧ＊＝２
练习
先用优超原理简化矩阵，再求解。
A
2 2 5 6
3 1 9 8
4 3 1 3
5 4 0 6
6 0 3 4
11.3二人有限零和对策的混合策略对策模型
一、基本概念 例：已知对策Ｇ＝｛Ｓ，Ｄ；Ａ｝
A= 7
3
4
6
4*
3
7
S1 Ａ＝S2 S3
d1 d2 10 -1 12 10 6 8
d3 3 -5 5
请你分析，理智情况下，甲、乙两 厂最可能出现什么策略，最大收益 是多少？
分析 :甲 : 当然想出s2
d1 d2 d3 S1 10 -1 3 -1 乙:当然想出d3 A= S2 12 10 -5 -5 S3 6 8 5* 5* 12 10 5* 对甲而言，先想最坏，再想最好． 则s*=s3,V甲＝５=max min aij 对乙而言，先想最坏，再想最好． 则d*=d3,V乙＝５=min max aij (s3,d3)即为双方的最优策略，此时甲得5，乙失5。有 唯一最优策略。
则(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
甲选 max min aij si* j i 即理智局中人的选择 max aij d j* 乙选 min j i
２、纯策略对策的解
(1) 对策G的解和值：使得aij* ai* j* ai* j 的(si* , d j* )称为 G的解，si* 与d j* 分别是 甲,乙的最优纯策略，ai* j* 称为G的值，记为VG 。
11.2 二人有限零和对策的纯策略对策模型 二人：指参加对策的局中人有２个。
有限：指每个局中人的策略集为有限集。
零和：指在任一局势下，双方收益之和为０ 。
一、纯策略对策模型－矩阵对策
设二人有限零和对策问题的局中人为甲和乙 S {s1，s2， D {d1，d 2， ,sm }为甲的策略集 ,d n }为乙的策略集
VG 3 ( si* , d j* ) ( s2 , d 2 )
8
例３
3
8
7
只有一个鞍点
0 2 2 -3 5 4 3 2 3 4 -4 -2
min max aij 2
j i
m下无解
在40年代发展迅速，缘于二战中军事的需 要，二战后又应用于其他领域。
50年代是对策论发展的鼎盛时期，纳什 和夏普利等提出了讨价还价模型和合作 对策的“核”的概念。 60年代，泽尔腾（1965）引入动态分析 ，提出“精练纳什均衡”概念。海萨尼 （1967-1968）则把不完全信息引入对策 论的研究。
(2)鞍点：若局势（si*，d j*）对应的 ai* j*＝max min aij＝min max aij
i j j i
则称（si*，d j*）为鞍点。
分析上例中的a33，它就满足ai3 a33 a3 j
定理1： G在纯策略中有解(si* , d j* )(si* , d j* )是鞍点
4 1 d1 3 d 1 1
s4
0 4 s3 2 s3 4
s1 2
s2
2 d1 d2 0 4
2 s3 0
j
（2）
i
A'
j
对于A' min max aij max min aij 2,即对策解是（s3 , d1）VG 2。
d1 10 12 6 y1
d2 -1 6 8 y2
d3 3 x1 7 x2 5 x3 y3
［案例１］企业建厂决策问题
某企业生产甲、乙两种家用电器．据预测， 若在某地建新厂则要投资100万元，每年可净收益 14万元．若将此款存入银行，则有２万元利 息．此外，还有以下信息可供决策者参考：
（１）在某地建新厂后，原厂房若不能售出，则 要维修，每年将花费3.2万元．因此，在某地建新 厂后的净收益只能是10.8万元．
－甲的期望收益 －乙的期望损失
二、混合策略对策的解 １、定义：如果混合策略对策
x y
G*={S*,D*;E}满足：
E (x* , y* ) max E (x, y ) min E (x, y ) 则称x , y 分别为局中人甲、乙的最优混合策略. (x , y )为对策G *的最优解。 VG * =E（x* ,y* )为对策G *的最优值。
4.对策的分类
动态：是连续时间的动态对策，因此从上一状态到
另一状态的转移用微分描述
对策 零和：得＋失＝０ 二人： 静态： 非零和：得＋失≠０ 零和
结盟：多人在一起交换策略
多人 不结盟：多人在一起交换策略 和
非零和
零和 非零
二.对策问题的组成（几个基本要素） 1.局中人：一局对策的参加者。
2.策略：局中人在一局对策中对付对手的一个行动方 案。策略全体称为策论集。
i j
aij p( si ) p(d j )
i j
aij xi y j
i j
当甲取s1时，最少收益为:min{7x1y1,4x1y2}
当乙取d1时，最大损失为:max{7x1y1,3x2y1}
甲选 max min E ( X , Y ) xi* j i 即理智局中人的选择 max E(X,Y) y j* 乙选 min j i
6*
易知，Ｇ在纯策略意义下无解。
记 xi p( si ) 0 xi 1(i 1, 2) yi p(di ) 0 yi 1(i 1, 2)
d1 s1 7 s2 3 yj y1 d2 4 6 y2 xi x1 x2
x
i 1 2 i 1
2
i
1 1
y
i
E ( X , Y ) aij p( si , d j )
（２）据预测，今后１０年中，乙产品的需求量 将下降５％（与进口无关）．在此情况下，未被 吸收的固定管理费用为2.３万元，因此，建新
厂的净收益只能是11.7万元．
5
4
2
例４
6 1 8 0
5 6 5 5 -1 4 2 -1 5 7 5 5 2 6 2 0
VG 5 ( si* , d j* ) ( s1 , d 2 ), ( s1 , d 4 ), ( s3 , d 2 ), ( s3 , d 4 ) 鞍点不唯一,但值唯一。
２、定理：设G*=(S*,D*;E)为混合对策，则
* * * *
E( x, y ) E( x , y ) E( x , y)
* * * *
例６： 求解下列对策
1 -1 A 2 0 1 -1 2 0 0 4 2 4 3 0 2 1 0 4 2 4 3 0 2 1 4 1 3 1 1 d3 -1 d4 2 0
i 1,
,m
j 1,