線形計画問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』

線型計画問題 (せんけいけいかくもんだい、Linear Programming Problem) とは、最適化問題において、目的関数が線型関数で、なおかつ線型関数の等式と不等式で制約条件が記述できる問題である。

・線形計画法

行列やベクトルを用いて表現すると、行列Aとベクトルb,cが与えられたとき、制約条件Ax=b, x≥0をみたしつつc^Txを最小化するベクトルxを求める問題のことである。

上の問題は次のように記述できる。

<math>

\begin{matrix}

\min &:& c^T x \\
\mbox{sub.to} &:& Ax = b \\
& & x \ge 0

\end{matrix} </math>

最大化問題や制約条件に線形不等式を含む問題も、容易に上記の形式に変換できる。

この問題を解くアルゴリズムとしては、1947年にG.B. Danzigが提案したシンプレックス法（単体法）がよく知られている。このアルゴリズムは、実用上は高速だが、Danzig が提唱したもの（ピボット規則）は理論的には多項式時間アルゴリズムではない。多項式時間で解が得られるピボット規則の存在性は、現在も未解決問題である。単体法という名前は、Danzig が提案した特殊な図解法においては，アルゴリズムの進行に従って単体が下に落ちていくように見えることに由来する。

その後、1979年、L.G. Khachiyanが初めての多項式時間アルゴリズムである楕円体法を提案する。さらに、1984年、N. Karmarkarは内点法というアルゴリズムを提案し、大規模な問題に対してはシンプレックス法よりも高速であると主張した。