最適化概要

最適化問題の基本形

どのような最適化問題であっても、以下の形に整理される。

目的関数:$f(\boldsymbol{x}) \rightarrow min, or / max$
制約条件:$\boldsymbol{x} \in \boldsymbol{S}$

$\boldsymbol{x}$はn次元実ベクトル,$f:\mathbb{R}^n \rightarrow \mathbb{R}$の実数値関数,制約条件を満たす$\boldsymbol{x}$を実行可能解,その集まり$\boldsymbol{S} \subset \mathbb{R}^n$を実行可能領域,実行可能領域で目的関数を最大(あるいは最小)となるものを最適解という。

大分類

  1. 線形計画問題:目的関数および制約条件が変数の1次式である問題
  2. 非線形計画問題:目的関数あるいは制約条件が変数の非線形関係である問題
  3. ネットワーク計画問題:多くは線形計画問題だが、ネットワーク構造を利用することで効率的なアルゴリズムが構成できるもの
  4. 組み合わせ計画問題:変数として離散変数(全整数,混合整数),0-1変数をとることもある(論理的制約条件を表現)

同じ問題を数学的に等価に複数の問題としてモデル化できるが、扱いやすい問題を選ぶ