トップ > 数理計画用語集 > 最適性原理

数理計画用語集

最適性原理

読み:さいてきせいげんり
英名:Principle of Optimality
関連動的計画法多段階決定過程

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

集合equation,非負整数変数equation(equation),equationについての関数equation(equation),非負整数equationを与えると次の資源配分問題が定まる.

equation

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

いま,活動equationequation,資源をequationに制限した場合の資源配分問題equation(equationequation)を定めると,equationについて,

equation

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

equation,(equation)

equation,(equation) ,(equation)

が得られる.なお,最終段階であるequationが元問題の最適解となることに注意する.上式は各段階equation(equation)について,任意のequation(equation)について定まる問題equation最適解としてequation(equation)をもつならば,問題equationでもequation(equation)が最適解となることを主張している.

なお,最適解を得るにはequation個の問題equationを解けば良いので,全探索をする場合の指数的に増大するツリーを回避することができる.