線型計画問題

線型計画問題 (せんけいけいかくもんだい、英語：linear programming problem) とは、最適化問題において、目的関数が線型関数で、なおかつ線型関数の等式と不等式で制約条件が記述できる問題である。この問題を解く手法を線型計画法という。

数学的表現

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

線型計画問題は次のように記述できる。

${\displaystyle {\begin{matrix}{\text{maximize}}&c^{T}x\\{\text{subject to}}&Ax\leq b\\&x\geq 0\end{matrix}}}$

これを標準型といい、制約条件に線型不等式を含む問題も、スラック変数を加えることで、容易に上記の標準型に変換できる。最大化問題の場合は、目的関数の符号を反転させれば最小化問題となる。

アルゴリズム

この問題を解くアルゴリズムとしては、1947年にジョージ・ダンツィーグが提案したシンプレックス法（単体法）がよく知られている。このアルゴリズムは、実用上は高速であり、ほとんど常に変数の数・制約条件の数の大きい方のオーダーの反復回数で解が求まる。しかし、Dantzig が提唱したもの（ピボット規則）は理論的には多項式時間アルゴリズムではない。常に多項式時間で解が得られるピボット規則の存在性は、現在も未解決問題である。単体法という名前は、Dantzigが提案した特殊な図解法においては、アルゴリズムの進行に従って単体が下に落ちていくように見えることに由来する。

その後、1979年、Leonid Khachiyanが初めての多項式時間アルゴリズムである楕円体法（英語版）を提案する。さらに、1984年、ナレンドラ・カーマーカー（Narendra Karmarkar）はより効率の良いカーマーカー法を提案し、大規模な問題に対してはシンプレックス法よりも高速であると主張した。現代においては、カーマーカー法に触発された汎用の内点法で十分に高速に解ける。

関連項目

• 双対問題