最適化問題【optimization problem】

概要

最適化問題（optimization problem）とは、ある関数を特定の条件下で最大あるいは最小とする解を求める問題。現実の何らかの問題について望ましさを表す関数を定義し、最も望ましい状態になるのはいつかを調べる問題である。

例えば、関数 ƒ（x） = x²-2x+3 について x>0 における最小値を求める、といったように定式化できる問題を指す。このとき、対象となる関数を「目的関数」、変数について課される条件を「制約条件」あるいは「制約関数」という。

この例では x=1 のとき ƒ（x）=2 となり最小となる。ƒ（x）=2 をこの問題における最適値と呼び、これを与える x=1 を最適解という。最大を求める問題と最小を求める問題を区別して、最大値および最大解、最小値および最小解と呼び分ける場合もある。

変数が連続的に変化するような関数の最適値を求める問題は「連続最適化問題」と呼ばれ、目的関数が一次式で表される線形計画問題などが含まれる。一方、変数が離散的な値しか取らないような問題は「離散最適化問題」あるいは「組み合わせ最適化問題」と呼ばれ、情報科学の有名な問題である最短経路問題、ナップサック問題、巡回セールスマン問題、エイトクイーン問題などはこちらに含まれる。

(2023.11.21更新)