シンプレックス法
一般的な流れは以下のとおりである。
線型計画問題を制限標準型に変形する。 スラック変数を加え、標準型に変形する。制約条件のうち、不等式を含む物がなくなり、全て等式となる。 人工変数を加え、制限標準型に変形する。等式化された問題の目的関数を z とおく。z を最大化 (最小化) する線型計画問題にする。
ここまで行った作業を基にシンプレックス表 (Simplex Tableau、線型計画問題の係数を表にまとめたもの) を作成する。
式の数だけ基底変数を定める。目的関数zは必ず基底変数に選ばなければならない。
初期の基底変数から得られた連立方程式の解が最適かどうかを調べる。最適とみなすことができた場合は終了。終了しなかった場合は以下の作業をおこなう。
基底変数と非基底変数の組合せを変更する。 新たに基底変数にできそうな変数を非基底変数の中から選ぶ。複数存在する場合は、最も効果の高い変数を基底に選ぶ。(ピボット列の決定) 基底から追い出す変数を決める。増加限界 (定数項の値から新たに基底に入れる変数の係数を割ったもの) によって変数を決めることが多い。(ピボット行の決定) 新しい基底変数での連立方程式を解く。具体的にはピボットを中心に掃き出し法などで新たな実行可能解を求める。実行後は4.に戻り、同様の処理を繰り返す。