この記事での学習内容 基本情報 応用情報

最適化問題とは何か、線形計画法、PERT、最短経路問題などの考え方を理解する。

用語例： 動的計画法

最適化問題

制約のある中で、目的とする関数（目的関数）の解が最大（あるいは最小）となる値を求める問題を最適化問題といいます。

目的関数や制約関数によって幾つかの種類にわけられます。

線形計画法（LP法）

目的関数と制約関数が一次式（直線）で表現できる問題です。線形計画問題の中には、生産などで原材料の使用量などの制約のある中から、最大限の製品をいくつ作れるかを求める、線形計画法などがあります。

非線形計画法

目的関数あるいは制約関数が一次式でない場合の問題です。ニュートン法などの開放があります。

動的計画法

動的計画法は、問題全体を細かい部分問題に分割し、分割された問題の最適解を解いていくことによって、これらの結果を集めて全体の解を導く方法です。

例：最短経路問題。PERTのクリティカルパスを求めるのは動的計画法の一種。