線型計画問題

線型計画問題（せんけいけいかくもんだい、（英: linear programming problem）とは、最適化問題において、目的関数が線型関数で、なおかつ線型関数の等式と不等式で制約条件が記述できる問題である。線形最適化問題（せんけいさいてきかもんだい、（英: linear optimization problem）とも。

線型計画問題を解く手法を線型計画法（線形最適化）という。

定義

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

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

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

標準形

線型計画問題における標準形（ひょうじゅんけい、（英: standard form）は目的関数・等式制約・非負制約による問題の表現である。

線型計画問題の制約には一次不等式を利用できる。この不等式はスラック変数（英語版）を用いて等式制約と非負制約のペアに分解できる。また変数は負の値を取れる。これは正負部分へ分割することで非負条件が付いた変数のペアに分解できる（参考: split variable）。

${\boldsymbol {c}},{\boldsymbol {b}}$ を定数ベクトル、 ${\boldsymbol {x}}$ を変数ベクトル、 $A$ を行列とする。線型計画問題を次の形式、

標準形

${\begin{matrix}{\text{maximize}}&{\boldsymbol {c}}^{T}{\boldsymbol {x}}\\{\text{subject to}}&A{\boldsymbol {x}}={\boldsymbol {b}}\ (\geq {\boldsymbol {0}})\\&{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{matrix}}$

で表したもの、すなわち目的関数・等式制約・非負制約による問題の表現が標準形である。

解法

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

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

定義

標準形

解法

関連項目