演習問題科目年月日（）時限施行採点学部学科年組番担当者

演習問題
演習 7 次の利得行列を持つ２人ゼロ和ゲームの最適混合戦略とゲーム値を求めよ．
HH
HH B
HH
A
A1
B1
B2
6
5
A2
2
8
1
=
u
+
u2
1
問 1. A が２つの戦略 A1 , A2 をとる確率を x1 , x2 = 0 (x1 + x2 = 1)，
B が２つの戦略 B1 , B2 をとる確率を y1 , y2 = 0 (y1 + y2 = 1) とする． y = (vu1 , vu2 ) = (
なる．
x = (x , x ), y = (y , y ) とおくとき，A の期待利得は
上の問題を以下の手順で解答せよ．
1
2
1
(1) B の立場で求める：定理 5 により，純粋戦略 i に対して
{
i = (1, 0) の場合， E(i, y) =
5v
uj = yj /v とおくと，y1 + y2 = 1 であるから
y1
y2
y1 + y2
1
u1 + u2 =
+
=
=
v
v
v
v


 w = u1 + u2 → 最大化

v → 最小化


u1 +
u2 5 1
y1 +
y2 5 v
⇒ 
u1 +
u2 5 1


y1 +
y2 5 v

 u = 0 (i = 1, 2)
i
yi = 0 (i = 1, 2)
という線形計画法の問題になる．
スラック変数
を導入して


u1
u1
+u2 →
+
u2 +
最大化
u1
+
=1
=1
u2 +
シンプレックス表で解く
cj →
↓ 基底変数
定数項 θ
=v
j = (0, 1) の場合， E(x, j) =
uj = xj /v とおくと，x1 + x2 = 1 であるから
5v
i = (0, 1) の場合， E(i, y) =



と
(2) A の立場で求める：定理 5 により，純粋戦略 j に対して
{
j = (1, 0) の場合， E(x, j) =
=v
問 2. v をゲーム値とする．





) であり，ゲーム値 v は
,
2
E(x, y) =






．したがって，B の最適戦略は
v=
u1 + u2 =
x1
x2
x1 + x2
1
+
=
=
v
v
v
v



w = u1 + u2 → 最小化



v → 最大化





u1 +
u2 = 1

x1 +
x2 = v
⇒ 
u1 +
u2 = 1



x1 +
x2 = v



 u = 0 (i = 1, 2)

 x = 0 (i = 1, 2)
i
i
という線形計画法の問題になる．
双対定理を利用して解く
主問題

w1 +





 制約条件：

双対問題

w2 → 最大化 
u1 + u2 → 最小化





 制約条件：
w1 +
w2 5
u1 +
u2 = 1






w1 +
w2 5
u1 +
u2 = 1








u1 = 0, u2 = 0
w1 = 0, w2 = 0
⇑
⇓
w
+
w
→
最大化
u
+
1 ) (
2
1 ) ( u)
2 → 最小化
(
)
( )
(
( )
⇐
w1
u1
5
=
w2
u2
第
以上の手続きで，双対問題を主問題に直して解く．その解法は，実
１
は変数が ui から wi に代わるだけで，B の解法のシンプレックス表
段
と全く同じものになる．したがって，(w1 , w2 ) = (
zj
cj − zj
最適解であり，目的関数の最大値は
第
双対問題の解(u1 , u2 ) を求める．
２
シンプレックス表第３段の zj の行の (z3 , z4 ) の値に等しいので
(
)
(u1 , u2 ) = (z3 , z4 ) =
,
段
zj
cj − zj
1
=
u1 + u2
最適戦略は x = (vu1 , vu2 ) = (
,
３
段
だから v =
u1 + u 2 =
第
zj
cj − zj
これより，(u1 , u2 ) = (
最大値は
．したがって，A の
) であり，ゲーム値 v は
となる．
,
) が最適解であり，目的関数の
である．u1 + u2 =
学部
先生氏名
(答) A の最適戦略は x = (
y=(
だから
年
科目
担当者
)が
,
である．
月
,
日（
学科 ), で，ゲーム値は
）
年 , B の最適戦略は
,
である．
時限施行
組
番
採
点

Download Report