2 :v2 3x5(1x)52x
203.0:2v.23021 11x2(1x) 9x2
步骤:
(1)绘制x数轴,标出x取值范围[0,1]
(2)x取0和1,确定三条直线端点,绘制三 条甲赢得值直线
(3)由于乙是理智的,甲的赢得值只能是 最小的(粗线所示)
(4)甲只能在最小中取最大,对应的策略 为 X * ( 3 , 8 ) ,最优对策值为V*=49/11
同 理 可 定 义 局 中 人 乙 的 混 合 策 略 与 混 合 策 略 集 .
当甲采取混合策略x,乙采取混合策略y,则称(x,y)为一个混合局势.
G*S1*,S2*,E 表示一个混合策略矩阵对策及G的一个混合扩充.
20.02.2021
课件
17
13.3.2 图解法
图解法求解矩阵对策，一般
适用于赢得矩阵为 或 的对
20.02.2021
课件
6
13.1.1 对策模型的基本要素
1．局中人
局中人(players)是指参与竞争的各方，每方必须有独立的决策能力和承 担风险的能力。(如:田忌、齐王）
2．策略集
在对策问题中，局中人为了应对其他局中人的行动而采取的方案和手段 称为该局中人的一个策略(strategy)。
3．赢得及赢得函数
5
2
4
5
2
4
m
ax
2
max 6 3 4 2
最 优 纯 策 略 (3,4)
20.02.2021
min2
课件
13
13.3.1 混合策略的概念
【例13.5】 猜硬币游戏：甲、乙两个儿童玩猜硬币游戏， 甲手中拿着一枚硬币，把硬币盖在桌子上，让儿童乙猜是 正面向上还是反面向上。如若猜对甲给乙1元钱，猜错乙给 甲1元钱。
设甲出正面(α1)的概率x,出反面(α2)的概率1-x;乙猜正面(β1)的概率y,猜反 面(β2)的概率1-y。则乙两个策略的期望值分别为:
E 1 1 x ( 1 )(1 x) 2 x 1 E 2 ( 1 ) x 1 (1 x ) 1 2 x
令 E1 E2,可 得 x0.5
(1) 当x<0.5时，E1 E2，理性的儿童乙会选择猜反面;
max 5 1 4
min1
20.02.2021
课件
12
13.2.2 最大最小原则
1
A 1
a11
m am1
max
n min
a1n
max
ars
amn
如果ars ahk,则该值所对 应的策略为最优纯策略
min ahk
【例13.4】
m in
2 3 4 4 4
A
6
4
2
4 3 3
2 3 2
m
则 m 维 概 率 向 量 x ( x 1 ,. . . ,x m ) T , x i 1 ,x i 0 称 为 甲 的 一 个 混 合 策 略 i 1
则 m 维 称 S 1 * x ( x 1 ,...,x m ) T |i m 1 x i 1 ,x i 0 称 为 甲 的 混 合 策 略 集
混合扩充：设有矩阵对策 GS1,S2,A混合扩充 G*S1*,S2*,E
S
* 2
y1
S
* 1
S2
1
S1
yn 甲 各 方 案 最 n 小 期 望 赢 得
n
甲至少期望赢得
x 1 1 a11
A
x m m am1
a1n
amn
m i n a 1 j y j
m
j1
n
i n a m j y j
管理运筹学课件第13章对策论
单击此处添加副标题内容
第13章 对策论
教学目标与要求
【教学目标】 1. 理解下列基本概念： 矩阵对策，矩阵对策三要素，最优纯策略与最优混合策略，鞍点和对策值 2. 算法要求： (1) 会用“超优原则”和“最大最小”原则求矩阵对策的最优纯策略 (2) 会用“线性规划”方法求矩阵对策的最优混合策略 (3) 了解纯策略和混合策略的纳什均衡求取。 【知识结构】
课件 V
j
y
j
≥
0
i 1, 2, j 1, 2,
,m ,n
20
13.3.3 线性规划法
同理,甲采取策略组合 x1,…,xm 时,也是从利己主 义出发的,会使自己的期望 赢得最大(也即乙的损失最 大)
y1
yn
x1 a11
A
xm a m1
m
max ai1xi
i1
a1n
a mn
m
ainxi
1 1 6
A1 3 5
4 1
0 4 2 1 3
第1列优超于 第5列，第4列 优超于第2列
1
1 6
A2
3
5
3 5 1 .5
4 1 3
4
4
4
第1行优于 2、3行
0
A3 1
2 3 4 5
4 5 4 6.5
5 1.5 4
9
3 3 0 8
1
2
3
6 4 5
20.02.2021
最优纯策略（α1,β2）
20.02.2021
课件
10
13.2.1超优原则
1．对 r , s 若恒有arj asj 则称 r 超优于 s 2．对 h , k 若恒有aih aik 则称 h 超优于 k
【例13.2】
第3行优超
6
1
A5
1
4 2 5 3
5 0 1.5 3
4 3 4 0
6 .5
7
9
8
于第2行， 第1行优超 于第5行
0
y* 1 y
由于甲是理智的,故乙取最大损
2 3 11
A 7 5
2
失(粗线)
乙会在最大损失中找出最小,即 乙最优混合策略为:
可知,当甲使用α1,α2,时,乙的损失
2值0.02为.202:1
课件
Y * (0, 9 , 2 ) 11 11 19
13.3.3 线性规划法
y1
x1 a11
A
xm a m1
局中人采用不同策略对策时，各方总是有得或有失，统称赢得(payoff)或
得益。
1
2
3
4
5
6
(1 上中下) (2 上下中) (3 中上下) (4 中下上) (5 下上中) (6 下中上)
(上中下) 3，-3 1，-1 1，-1 -1，1 1，-1 1，-1
(上下中) 1，-1 3，-3 -1，1 1，-1 1，-1 1，-1
yn
m in
甲至少期望赢得
n
a1n a 1 j y j
a mn
j 1 n
a
mjy
j
max
min
X S1*
Y
S
* 2
m i 1
n
aij xi y j
j 1
V
j 1
乙采取策略组合y1,…,yn时,是从利己主义出发的,会使自己的期望损失最 小(也即甲的赢得最小)
甲会使用某种策略组合x1,…,xm,使得在最小赢得的概率组合尽可能地大.
基本概念：三要素，分类
对
二人零和纯策略：超优原则、maxmin 和 minmax 原则
策
论
二人零和混合策略：图解法（2 行或 2 列收益矩阵）
LP 方法（一般情况）
20.02.2021
纳什均衡（非零和）：纯策略（划线法） 混合策略（LP 方法）
课件
3
20.02.2021
课件
4
20.02.2021
(中上下) 1，-1 1，-1 3，-3 1，-1 1，-1 -1，1
(中下上) 1，-1 1，-1 1，-1 3，-3 -1，1 1，-1
(下上中) -1，1 1，-1 1，-1 1，-1 3，-3 1，-1
(下中上) 1，-1 -1，1 1，-1 1，-1 1，-1 3，-3
20.02.2021
课件
5
本章主要内容
13.1 对策论的基本概念 13.1.1 对策模型的基本要素 13.1.2 对策问题的分类 13.2 矩阵对策的纯策略 13.2.1优超原则 13.2.2最大最小原则 13.3 矩阵对策的混合策略 13.3.1 混合策略的概念 13.3.2 图解法 13.3.3 线性规划法 13.4 纳什均衡 13.4.1 纯策略纳什均衡的划线法 13.4.2 混合策略纳什均衡的LP方法 13.4 应用举例 案例13-1 市场竞争策略 案例13-2 对抗赛项目确定 本章小结
11 11
11
7 β1
5 β2
β3
3
2
2
课0 件
x*
1 x 18
13.3.2 图解法
从图还可以看出局中人乙的最 优混合策略为β2β3的组合.
11
1:v33y11(1y)118y 2:v45y2(1y)23y
y分别取0和1,绘制图形如下:
7 β1 5 β2
11 α1
β3
3
5
2
2
α2
3
0
x*
2 1x
故β1的概率为0.设β2,β3的概率为 y,(1-y).由效率矩阵:
猜硬币游戏属于矩阵对策，儿童甲的策略有出正面向上(α1)
和出反面向上(α2)，儿童乙的策略有猜正面向上(β1)和猜反
面向上(β2)。
m in
1
A
1
1 1
1
1
m ax
1
max 1 1
m in 1
m jinm a ixaij m jinm a ixaij