最適性原理#

読み: さいてきせいげんり
英名: 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)\) を解けば良いので，全探索をする場合の指数的に増大するツリーを回避することができる．