線型計画問題
行列やベクトルを用いて表現すると、行列Aとベクトルb,cが与えられたとき、制約条件Ax≤b, x≥0をみたしつつcxを最大化するベクトルxを求める問題のことである。
線型計画問題は次のように記述できる。
maximize c T x subject to A x ≤ b x ≥ 0 {\displaystyle {\begin{matrix}{\text{maximize}}&c^{T}x\\{\text{subject to}}&Ax\leq b\\&x\geq 0\end{matrix}}}
これを標準型といい、制約条件に線型不等式を含む問題も、スラック変数を加えることで、容易に上記の標準型に変換できる。最大化問題の場合は、目的関数の符号を反転させれば最小化問題となる。