最適性原理を使った例

最適性原理

　動的計画法において、ベルマンの最適性原理というものがあります。
　最適性原理とは、次のようなものです。

　　「最適政策は、最初の状態や決定が何であっても、それ以後の決定は最初の決定によって生じた状態に関して、最適政策になるように構成しなければならない」

　これは、ある時点における最適政策はそれ以後の任意の最適政策と整合的でなければならないということを意味しています。言い方を変えれば、ある時点での決定は、それ以前の状態を所与として、それ以後の決定は最適政策を構成していくというものです。

　ただこれでは、どうもイメージがつきにくい感じがします。

　そこで、最適性原理を使い、問題を解く方法について、例を挙げたいと思います。
　教科書によっては、最短経路問題を使って、例を挙げていることがありますが、ここでは数式の違うモデルで説明します。

例

問題

　ある工場で、XとYという2つの製品を作っており、それらを製造するための設備が18台あります。

　XとYに使われる設備の台数をそれぞれ$x$、$y$とします。ただし、1期間に製品を製造すると設備も使えなくなるものが出てき、X製品を製造すると、設備の1/3が、Y製品を製造すると、設備の2/3のみが使え続けれるとします。

　各期に製造した製品を販売し、1期間に$6x+5y$の利益があります。このとき、それぞれの製品の製造にどれだけの設備を割り当てていけば、3期間製造したときの最大の利益はどうなるでしょうか。

解法

　この問題を解くために、3期から後ろ向きに、毎期の利益が最大になるように考えていきます。
　なぜ、後ろ向きに解いていくかといえば、最適性原理から、

　　3期：3期の利益を最大化
　　2期：2期と3期（最大化済）の利益を最大化
　　1期：1期・2期（最大化済）・3期（最大化済）の利益を最大化

を行えばいいからです。

　これを具体的に見ていきます。

3期
　各期における使用される設備の合計を$n_i$、XとYの製造に使われる設備の数を$x_i \, , \, y_i$とすると、

　　$n_3 = x_3 + y_3$

となります。そして、各期の利益を$\pi_i$とすると、

　　$\pi_3 = 6x_3 + 5y_3$

を最大化することになります。

　この利益$\pi_3$について、上記の設備数の式を代入すると、

　　$\pi_3 = 6x_i + 5y_i = 6x_i + 5(n_3 \, – \, x_3) = x_3 + 5 n_3$

となります。この式から、できるだけ$x_3$を多くしたほうがいいのですが、$0 \leq x_3 \leq n_3$なので、$x_3 = n_3$から、

　　$\pi_3 = 6 x_3 = 6 n_3$

を得ることができます。
　すなわち、3期においては、残っている設備をすべてXの製造に割り当てるのが、最も利益が大きくなる状態になります。

2期
　まずは、2期に利用される設備の数と2期における利益はそれぞれ

　　$n_2 = x_2 + y_2$

　　$\pi_2 = 6x_2 + 5y_2$

となります。

　ところで、2期に使用した設備については、3期に使えなくなるものが出てくるので、

　　$\dfrac{1}{3}x_2 + \dfrac{2}{3}y_2= n_3$

が成立します。

　上記の式を使って、2期では、$pi_2 + \pi_3$を最大化します。

　　$\pi_2 + \pi_3 = (6x_2 + 5y_2) + 6 n_3 = (6x_2 + 5y_2) + (2x_2 + 4y_2) = 8x_2 + 9y_2 = 9n_2 \, – \, x_2$

　この式から、できるだけ$x_2$を少なくしたほうがいいのですが、$0 \leq x_2 \leq n_2$なので、$x_2 = 0$であり、$y_2 = n_2$となるので、

　　$\pi_2 + \pi_3 = 9 y_2 = 9 n_2$

となります。

1期
　2期と同様に考えて、1期においても、利用される設備数と利益などの式はそれぞれ

　　$18 = x_1 + y_1$

　　$\pi_1 = 6x_1 + 5y_1$

　　$\dfrac{1}{3}x_1 + \dfrac{2}{3}y_1= n_2$

となります。なお、初期には18台の設備があるので、$n_1 =18$となっています。

　そして、1期においては、2期における最大化した利益を用いて、次のような利益を最大化します。

　　$\pi_1 + \pi_2 + \pi_3 = (6x_1 + 5y_1) + 9n_2$

　この式を整理すると、

　　$\pi_1 + \pi_2 + \pi_3 = 198 \, – \, x_1$

を得ることができ、$x_1=0$（$y_1 = 18$）としたとき、利益は最大になります。

まとめ
　以上から、1期の値を2期・3期に代入していくと、次のようになります。

参考

　　西村清彦『経済学のための最適化理論入門』

　　杉山昌平『動的計画法』