線型計画問題のソースを表示

{{出典の明記|date=2011年11月}}
'''線型計画問題''' (せんけいけいかくもんだい、{{lang-en-short|linear programming problem}}) とは、[[最適化問題]]において、目的関数が[[線型関数]]で、なおかつ線型関数の等式と[[不等式]]で制約条件が記述できる問題である。この問題を解く手法を[[線型計画法]]という。

== 数学的表現 ==
行列やベクトルを用いて表現すると、[[行列 (数学)|行列]]''A''と[[数ベクトル空間|ベクトル]]''b'',''c''が与えられたとき、制約条件''Ax&le;b'', ''x&ge;0''をみたしつつ''c<sup>T</sup>x''を最大化するベクトル''x''を求める問題のことである。

線型計画問題は次のように記述できる。
:<math>
\begin{matrix}
 \text{maximize} & c^T x \\
 \text{subject to} & Ax \le b \\
 & x \ge 0
\end{matrix}
</math>

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

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

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

== 関連項目 ==
*[[双対問題]]

{{主要な最適化問題の分類}}
{{最適化アルゴリズム}}

{{DEFAULTSORT:せんけいけいかくもんたい}}
[[Category:最適化]]
[[Category:オペレーションズリサーチ]]
[[Category:数学の問題]]
[[Category:数学に関する記事]]