この記事での学習内容 基本情報 応用情報
最適化問題とは何か、線形計画法、PERT、最短経路問題などの考え方を理解する。
用語例： 動的計画法
最適化問題
制約のある中で、目的とする関数（目的関数）の解が最大（あるいは最小）となる値を求める問題を最適化問題といいます。
目的関数や制約関数によって幾つかの種類にわけられます。
線形計画法（LP法）
目的関数と制約関数が一次式（直線）で表現できる問題です。線形計画問題の中には、生産などで原材料の使用量などの制約のある中から、最大限の製品をいくつ作れるかを求める、線形計画法などがあります。
非線形計画法
目的関数あるいは制約関数が一次式でない場合の問題です。ニュートン法などの開放があります。
動的計画法
動的計画法は、問題全体を細かい部分問題に分割し、分割された問題の最適解を解いていくことによって、これらの結果を集めて全体の解を導く方法です。
例：最短経路問題。PERTのクリティカルパスを求めるのは動的計画法の一種。