線形計画問題

【せんけいけいかくもんだい (linear programming problem)】

最適化問題(数理計画問題)

${\mbox{max.}}f(x)\ \,$ (あるいは, $\min .\ f(x)\,$)

${\mbox{s.t.}}x=(x_{1},x_{2},\ldots ,x_{n})\in F,\,$

において, 目的関数 $f\,$ が線形であり, かつ, 実行可能集合 $F\,$ が線形等式と線形不等式を用いて表現されている問題.この問題への定式化, および, 解法を含めて線形計画と呼ぶ.