《运筹学》胡运权清华版-12-02矩阵对策基本定理.ppt

(1) VG2 VG1
(2) T (G1) T (G2 )
16
定理9——
设G1={S1,S2;A} 为一矩阵对策，且 A=-AT，则
(1) VG 0 (2) T1(G) T2 (G)
其中T1(G) 和T2(G)分别为局中人I和II 的最优策略集。
17
max
xS1*
w
x S1* xi 1, xi 0
i
6
综上，局中人I的问题——
max w
aij xi w j 1,2...n
i
xi 1
i xi 0
线性规划问题I
7
同理分析局中人II
理性假设下，局中人II选取混合策略 y*的目标是使
v2
min
yS
* 2
max
xS1*
E(x,
y)
若y固定，局中人I采用纯策略x=αi， 则局中人II的期望损失
E(i, y) aij y j (12.15)
j 8
若y固定，局中人I采用任意一个混 合策略x时，由（12.17）
max E(x, y) max
xS1*
xS1*
i
E(i, y)xi v

易知 v max E(i, y) i
即 E(i, y) v i
9
由（12.15） E(i, y) v i
aij y j v i 1,2...m
j
局中人II的目标是
v2
min
yS2*
max
xS1*
E(x,
y)
min
yS2*
v
y
S
* 2
y j 1, y j 0
j
10
综上，局中人II的问题——
min v
aij y j v
j
y j 1
j
j
E(x, j) aij xi (12.16)
i
2
进一步
E(x, y)
aij xi y j aij y j xi
ij
ij
E(i, y)xi i
(12.17)
E(x, y)
aij xi y j aij xi y j
ij
ji
E(x, j) y j j
(12.18)
min E(x, y) min
yS
* 2
yS
* 2
E(x, j) y j w
j
易知 w min E(x, j) j
即 E(x, j) w j
5
由（12.16） E(x, j) w j
aij xi w j 1,2...n
i
局中人I的目标是
v1
max
xS1*
min
yS
* 2
E(x,
y)
y
j
0
i 1,2...m
线性规划问题II
11
• 问1：上述两个线性规划问题关系？ 互为对偶问题
•问2：上述两个线性规划问题解的情况？
易知 x (1,0,....0), w min a1j | j 1,2...n
是问题I的一个可行解
y (1,0,....0), v maxai1 | i 1,2...m
i
14
定理7——
设有两个矩阵对策G1={S1,S2;A1}和 G2={S1,S2;A2}，其中
A1 =(aij)， A2 =(aij＋L)， 则
(1) VG2 VG1 L (2) T (G1) T (G2 )
15
定理8——
设有两个矩阵对策G1={S1,S2;A}和 G2={S1,S2;αA}，其中 α>0为任意常数， 则
是问题II的一个可行解
12
因此两个问题都有可行解，根据对 偶理论，这两个问题都有最优解，且目 标值相等 max w=min v。
v1
max
xS1*
min
yS2*
E(x,
y)
max
xS1*
w
v2
min
yS2*
max
xS1*
E(x,
y)
min
yS2*
v
所以max min E(x, y) min max E(x, y)
四、矩阵对策基本定理
定理5——
矩阵对策G={S1,S2;A} 在混合 策略意义下必定有解。
1
现引入记号：
i——αi，局中人I的纯策略 j——βj，局中人II的纯策略 E( i,y)——局中人I取纯策略αi时的赢得值 E( x,j)——局中人II取纯策略βj时的赢得值
则
E(i, y) aij y j (12.15)
xS1* yS2*
yS2* xS1*
即矩阵对策在混合策略意义下必定有解。 13
五、矩阵对策若干性质
定理6—— 互补松弛性定理
设（x*,y*）是G的解，v=VG ，则
(1) xi* 0
aij
y
* j
v
j
(2) y*j 0 aij xi* v
i
(3)
aij
y
*
j
v
xi*
0
j
(4)
aij xi* v y*j 0
3
矩阵对策基本定理证明分析——
理性假设下，局中人I选取混合策略 x*的目标是使
v1
max
xS1*
min
yS
* 2
E(x,
y)
若x固定，局中人II采用纯策略y=βj， 则局中人I的期望收益
E(x, j) aij xi (12.16)
i 4
若x固定，局中人II采用任意一个混 合策略y时，由（12.18）