線形計画問題#

読み: せんけいけいかくもんだい
英名: Linear Programming Problem
別名: LP

目的関数および制約条件に関する式が全て線形であるような最適化問題のことを線形計画問題（あるいは英語の頭文字をとって LP 問題）と呼ぶ．なお，linear programming という語について「線形計画法」という意味ではなく「線形計画問題」という意味で使われていることもある．このため，線形計画問題のことを単に LP と呼ぶこともある．

生産計画問題やダイエット問題などが線形計画問題の代表例として知られている．また，線形計画問題の解法としては，単体法や内点法が良く知られている．なお，一次方程式に対する解法の分類になぞらえると，単体法は直接法に，内点法は反復法に相当する．

線形計画問題を扱う際には，多くの場合次のような標準形と呼ばれる形式に変換する．

(72)#\[\begin{split}\begin{array}{ll} \min & c^\top x \\ \mathrm{s.t.} & Ax = b \\ & x \ge 0 \end{array}\end{split}\]

ただし，\(A \in \mathbb{R}^{m \times n}\)，\(b \in \mathbb{R}^m\)，\(c \in \mathbb{R}^n\) は定数であり，\(x \in \mathbb{R}^n\) は変数であるものとする．