非負の変数についての連立一次方程式または連立一次不等式を制約条件として，与えられた一次式の目的関数を最大あるいは最小にする問題を，最適化問題の中でも線形計画問題と呼ぶ．輸送問題，割当て問題等，現実に生ずる最適化問題の多くは，この問題に帰着できることが多い．その解は一般に，変数座標空間内での解許容領域としての凸多面体における端点群に存在する．これら端点群の中から最大あるいは最小点を求める効率的方法として，単体法（シンプレックス法）が知られている．