線形計画問題とは、制約条件及び目的関数が線形式で表現されている最適化問題のことである。線形計画法（Linear Programming）とは線形計画問題を解くための手法の１つである。

線形計画問題の標準形

　「対象となる式が全て線形」というだけでは様々な形態が考えられ、それぞれに論じたり処理したりすることは煩雑なので、以下のような標準形に変換して議論を行うのが普通である。

　すなわち、

1. 最小化すべき目的関数が与えられていること。
2. 全ての決定変数に非負条件が課せられていること。
3. 制約条件が等式で表されていること。

を満たす必要がある。これを満たしていなければ、以下のような手順で標準形のに変換することができる。

目的関数を最大化する問題の場合

　目的関数の符号を反転させた式を新たな目的関数とすればよい。

決定変数に非負条件が課せられていない場合

　正確に言えば「決定変数が負の値をとる場合もある」問題の場合。その（負になるかもしれない）変数を、非負の２つの新変数の差として定義しなおすとよい。

制約条件に不等式が含まれている場合

　仮に下式のように不等号で条件が与えられていたとする。�煤i式）≧（値）という形式であったなら両辺の符号を反転させればよいので、一般に�煤i式）≦（値）という形式としてよい。

　このとき、不等号の左辺は右辺よりも値が小さいことを意味しているので、その差をλ_j（≧０）とすると次式のように記述することができる。

　この変数λ_jをスラック変数（slack variable）と言う。

Updated : 2007/02/21