線形計画法

線形計画問題とは, 線形不等式系を満たす変数の組のうちで線形関数を最小(または最大)にするものを求める問題である. 線形計画問題の記述能力は高く, 入手可能な資源を用いて利潤が最大となるよう各製品の生産量を決める生産計画, 各製品を各消費地まで最小費用で運搬する輸送計画, 最短の日数で工事を完了させる日程計画など, 現実世界における多くの最適化問題が線形計画問題として直接的にモデル化される．また, 組合せ最適化問題を解くための基本的な道具としても線形計画法は重要な役割を担っている. 線形計画問題に対する解法としては, 1947年にDantzigによって提案された単体法が, 改良を重ねつつ, 長いこと主流を占めていた. しかし, 1984年には, Karmarkarによって, 全く異なるアルゴリズムが提案され, 内点法と総称される一群の新たなアルゴリズムが登場した. 計算複雑度の観点からは, 線形計画問題に対する強多項式時間解法の開発が主要な未解決問題とされている.