Dynamic Programming... ケーキを3日掛けて食べるお話。

宿題でDynamic Programmingが出たのでもう一度w

前回はこっち。


前回はt=2で、２日掛けてケーキを食べ切ろうと言うお話だったんですが、今回はなんと３日です。

２日のケースと何が違うの〜？というと、最大化問題を２回解く所ですかね。

４日目のケーキの残量が０だとします。（３日で食べ切ると言う条件なので。）
よってx=0 where t=4

効用はケーキの消費量uの平方根を取ったものとします。

３日目の価値関数V_3に付いて考えます。

３日目の効用に次の日の価値観数V_4を含めて最大化を解きたい所ですが、4日目はケーキが残っていないのでV_4はゼロとなります。

そして、消費量u_3は自動的にその日までに残っていたケーキ残量x_3と同じになります。（食べ切っちゃうので。）

という事で、３日目は放置して２日目に行きます。

２日目の価値関数V_2は２日目の効用関数に3日目の価値関数V_3を含めた物になります。

そして、1日目の価値関数V_1は1日目の効用関数に2日目の価値関数V_2を含めた物になります。

V_2の最大化問題を解いてV_2を最大化させる解を関数として見つけ、その解をV_1に代入してV_1の最大化問題を解けば、全ての時間を通しての最適消費計画を見つけることができる訳です。






と、まぁこんな感じに解けちゃう訳です。

時間tが３から１０に増えたとしても同じプロセスを繰り返すだけでやっぱり解けます。
つまり、価値観数V_10から始めて、９回最大化問題を解けば最適計画が見つかります。
まぁt-1回最適化を解けと。そういうお話です。



いやぁ。解を関数として見つけるって結構めんどくせぇなって今まで思ってたんですけど、便利なんですね。