====== 多段配分問題 ======
==== multistage allocation problem ====

{{tag>..c17}}

　多段決定問題の一つで，有限の資源を部門や年次に配分することによって得られる総利益を最大化するような配分方法を求める問題である．最適性の原理に基づいた動的計画法を適用することにより解くことができる．最も基本的な問題とは，配分を\({x_1},{x_2}, \cdots ,{x_N}\left( {{x_i} \ge 0} \right)\)とし，総量//x<sub>T</sub>//に関して\(\sum\limits_{i = 1}^N {{x_i} = {x_T}} \)の制約の下で，総利益\(\sum\limits_{i = 1}^N {{g_i}\left( {{x_i}} \right)} \)を最大化する配分\(x_1^*,x_2^*, \cdots ,x_N^*\)を求めよというものである(ただし，//g<sub>i</sub>//(//x<sub>i</sub>//)は//i//への配分による利益)．部分問題の最適配分量の定式化から，段階的に最適配分量の系列を求めることができる．


~~NOCACHE~~