最適性原理

最適性原理#

  • 読み: さいてきせいげんり

  • 英名: Principle of Optimality

多段階決定過程における決定段階を \(1,\ldots,n\) とし,各段階における問題群を \(A_i \ (i = 1,\ldots,n)\) とする.\(i<j\) を満たす任意の決定段階 \(i,j\) に対して,問題 \(P \ (\in A_j)\) の最適解は,問題 \(P\) の決定に影響を与える問題 \(Q \ (\in A_i)\) においても最適解となることを最適性原理と言う.以下に資源配分問題の例を紹介する.

集合 \(I=\{ 1,\ldots,n \}\),非負整数変数 \(x_i \ (i \in I)\)\(x_i\) についての関数 \(g(x_i) \ (i \in I)\),非負整数 \(a\) を与えると次の資源配分問題が定まる.

(52)#\[\max \left\{ \sum_{i=1}^n{g(x_i)} \middle| \sum_{i=1}^n{x_i \le a} \right\}\]

集合 \(I\) の要素は活動,\(g(x_i) \ (i \in I)\) は利得,\(a\) は資源,\(x_i \ (i \in I)\) は配分と呼ばれ,資源と利得を考慮して各活動に対する配分を決定する問題である.

いま,活動 \(i \in I\)\(i \le k\),資源を \(x\) に制限した場合の資源配分問題 \(f_k(x) \ (0 \le x \le a, \ k = 1,\ldots,n)\) を定めると,\(k = 2,\ldots,n\) について,

(53)#\[\begin{split}\begin{array}{lll} f_k(x) &=& \max{\left\{ \sum_{i=1}^k{g(x_i)} \middle| \sum_{i=1}^k{x_i \le x} \right\}} \\ &=& \max{\left\{g(x_k) + \max{\left\{ \sum_{i=1}^{k-1}{g(x_i)} \middle| \sum_{i=1}^{k-1}{x_i \le a-x_k} \right\}} \middle| 0 \le x_k \le a\right\}} \\ &=& \max{\left\{g(x_k) + f_{k-1}{(a-x_k)} \middle| 0 \le x_k \le a\right\}} \end{array}\end{split}\]

が導かれる.これより,帰納的な構成によって次の多段階決定過程,

(54)#\[\begin{split}\begin{array}{l} f_1(x) = g(x), \ (0 \le x \le a) \\ f_k(x) = \max{\left\{ g(x_k) + f_{k-1}(x-x_k) \middle| 0 \le x_k \le x \right\}}, \ (0 \le x \le a), \ (k=2,\ldots,n) \end{array}\end{split}\]

が得られる.なお,最終段階である \(f_n(a)\) が元問題の最適解となることに注意する.上式は各段階 \(k \ (=2,\ldots,n)\) について,任意の \(x \ (0 \le x \le a)\) について定まる問題 \(f_k(x)\) が最適解として \(x_i \ (i=1,\ldots,k)\) をもつならば,問題 \(f_{k-1}(x-x_k)\) でも \(x_i \ (i=1,\ldots,k-1)\) が最適解となることを主張している.

なお,最適解を得るには \((a+1) \cdot n\) 個の問題 \(f_k(x)\) を解けば良いので,全探索をする場合の指数的に増大するツリーを回避することができる.

関連