ユーザ用ツール

サイト用ツール


動的計画法

dynamic programming

 線形計画を中心とする数理計画法は,非常に大規模な問題を妥当な労力で解くことができる点で実用性の高いものであるが,例えば目的関数や制約領域が凸でなくなると計算が非常に複雑になる欠点をも持っている.このような場合も問題の形によっては非常に簡単に解くことができるという点で,以下に述べる動的計画法は応用範囲の広いものである.次のような問題を考えてみよう.ある運送会社があって,その会社は毎月毎月送られてくる品物を蓄える一方,毎月毎月適当な量ずつ配達することが必要である.毎月送られてくる品物の量,at(t=1,2,…,N)は,あらかじめ定められており,また考慮期間の初めと終りの時点における在庫量S0SNも定められており,各時点における在庫量Stは上限値S,下限値Sであるとする.このような場合にt=1,2,…,NN期間における配送料の和を最小にするには毎月送り出配送量をいかに定めればよいか,ただし配送量は配送料xiの関数f(xi)で与えられるものとする.このような形の問題は,多段決定問題と呼ばれ,種々のシステムを取り扱う場合にしばしば遭遇する型である.多段決定問題をベルマンの最適性原理にもとづいて,関数漸化式をたて,これを解いていく方法を動的計画法と呼ぶ.