スライド 1

親の仕送り問題
<マルコフ決定過程>
問題設定
 春から下宿生活をすることになったK君。
 4月から親の仕送りを受ける。
 収入・支出のデータをもとに、できるだけ親の
負担の少ない仕送り計画を設定する。
 収入例
: 仕送り、バイト代、奨学金 etc
 支出例 : 生活費、家賃、授業料 etc
授業料の支払い以外を確率的に変動するも
のとみなす。
 学生ローン:
c(x,y)
金利 100rL%/週
上限 10万円
:
学生ローンの金利負担分
 第t月の月初めの預金残高(Xt)に応じて
その月の仕送り額(Yt)を決定し、
第1週末までに送ってもらう。
→Xt所与のもとで、Ytの確率分布が示される
(マルコフ決定過程)。
授業料をふくめた家計負担の期待値(5.1
2)
∞
t=1
Σ[ E { Yt} / (1+r)4t-3
+ E { c(Xt、Yt)} / (1+r)4t-3 ]
+200,000 / (1+r) +…
線形計画問題

(5.13)
最小化
∞
Σ[ E {Yt} / (1+r)4t-3
t=1
+ E { c(Xt、Yt)} / (1+r)4t-3 ]
 条件
Yt ; Xt 所与のもとである確率分布
として与えられる
 β=(1+r)-4
 cij =
yj + c( xi, yj)
∞
 zij =
 Pijk
Σ(1+ r )³ ・βt・P { Xt = xi, Yt = yj }
t=1
= P { Xt+1= xk| Xt = xi , Yt = yj }
1ij{ Xt,Yt } = 1, Xt = xi, Yt = yj のとき
0, それ以外
(目的関数の変形)
∞
= Σ Σ Σ(1+r)³・βt・cij
t=1 i∈I j∈Ji
・ P { Xt= xi ,Yt = yj }
= Σ Σ cij・ zij
i∈I j∈Jk
(5.15)
 Σzkj
jJk
∞
= Σ Σ(1+r) ³ ・βt・P { X t= xk , Y t= yj }
jJk t=1
-1
=Σ Σ・β・Pijk ・ z ij+ (1+r) ・ P{ X 1= xk }
iI
jJi
よって
Σz kjー ΣΣβ・P ijk・ zij
(5.17)
iI jJi
iI
= (1+r)-1, xk = 0 のとき (kI)
0
それ以外
線形計画問題(5.18)
 最小化
Σ Σ cij ・ zij
iI jJi
 条件
Σ zkj ー Σ Σ β・ Pijk ・ zij
iI jJi
jJk
-1
= (1+r) , xk= 0 のとき
0
それ以外
zij0, jJi, II
⇒最適解{zij*|jJi, iI}
( k  I)
定理
 実行可能基底解の中から最適解が選ばれる

問題(5.18)の最適解は、定常かつ純粋な仕
送り計画 Yt = F*(Xt) に対応。

Yt = F*(Xt)のもとでの {Xt|t1}の
①推移確率
Pik*=P{Xt+1=xk|Xt=xi,Yt=F*(xi)}
②状態確率
πi*(t)=P{Xt=xi}
→πk*(t+I)=Σπi*(t)・Pik*
iI
(5.20)
 t→∞
πk*=Σπi*・Pik* ,kI
Σπi*=1
iI
(5.21)
預金残高の定常分布
0.9
0.8
0.7
0.6
0.5
定常確率
0.4
0.3
0.2
0.1
0
rL
0.001
0.01
0.1
-100 -80 -60 -40 -20
預金残高(千円)
0
20
40
= F*(Xt)のもとでの {Yt|t1}の
状態確率
 Yt
9)
ρj*(t)=P{F*(Xt)=yj}=P{XtF*-1(yj)} (5.1
仕送り額の定常分布{ ρj* }は(5.21)より
iA
*
ρj =Σπi*
(5.22)
*
j
( Aj*={iI|xiF*-1(yj)
)
仕送り額の定常分布
0.9
0.8
0.7
0.6
0.5
定常確率
0.4
0.3
0.2
0.1
0
rL
0.001
0.01
0.1
0
20
40
60
仕送り金額(千円)
80
100
問題の最適解
rL
0.001
(xi, yj)
(0,0)
(-20,000,
(-30,000,
(-40,000,
(-50,000,
(-60,000,
(-70,000,
(-80,000,
(-90,000,
10,000)
0)
20,000)
30,000)
40,000)
40,000)
40,000)
70,000)
zij
0.999
0.829
5.329
168.396
5.307
28.116
1.066
33.679
1.061
(-100,000, 90,000)
0.01
0.1
(30,000,
(0,
(-10,000,
(40,000,
(0,
20,000)
50,000)
60,000)
20,000)
60,000)
5.591
207.814
0.999
41.562
207.814
42.561