単体法の解決手順

由凸集的定理知，線形計画の最適解は必ず基底可行解であり、基底可行解は必ず凸集合の頂点上に存在します。そして、線形計画問題の可行領域は凸集合であり、可行領域は可行解の集合です。したがって、最適解を求めるためには、基底可行解を見つける必要があります。

これがなぜ線形計画の手順が次のようになるのかの理由です：基底を見つける - 基底解を求める - 基底可行解であるかを検証する - 最適解であるかを検証する - 最適解でない場合は反復（基底変換）。

最初に、線形計画問題を標準的な数学モデルに変換します。
次に、初期基底を見つけ、それが可行基底であるかを検証します。
- 基底を見つける：係数行列の最大ランクの正方部分行列（ $m \times m$ 次）を見つけます。
- 基底解を求める：非基底変数を 0 に設定すると、制約方程式は $m \times m$ 次の連立一次方程式となり、必ず一意の解が存在します。現在の制約方程式を解くと、基底解が得られます。
- 基底可行解であるかを検証する：基底解のすべての基底変数が非負の制約を満たす場合、その基底解は基底可行解です。
最適解であるかを検証する：
- すべての $σ_j ≤ 0$ の場合、現在の解が最適解です。
- すべての $σ_j ≤ 0$ であり、少なくとも 1 つの $σ_j = 0$ が存在する場合、無数の最適解があります。
- $σ_j > 0$ が存在し、対応する非基底変数 $x_j$ のすべての係数 $a_{ij} <0$ である場合、最適解は存在しません。
- $σ_j > 0$ が存在し、対応する非基底変数 $x_j$ の係数の中に少なくとも 1 つの $a_{ij} >0$ が存在する場合、反復を続けることができます。
反復を続ける場合は、基底変換を行います。
- 入れ替える変数を決定します：最大の正数 $σ_j$ を持つ非基底変数 $x_j$ を選択し、入れ替える変数とします。
- 出す変数を決定します：最小の正数 $θ_j=\frac{b_i}{a_{ij}}$ を持つ $i$ に対応する基底変数 $x_i$ を選択し、出す変数とします。
- 基底変換： $x_j=θ，x_i=0$ とし、新しい基底変数の係数行列 $B$ を単位行列に変換し、新しい基底を得ます。
- 再度検証：新しい基底に対して「基底解を求める - 基底可行解であるかを検証する - 最適解であるかを検証する...」を行い、反復ができなくなるまで続けます。

$σ_j$ は基底変換後の目的関数の変動量です（すべての $σ_j≤ 0$ は現在の選択肢よりも良い選択肢がないことを意味します）。
$θ$ は非基底変数の最小の正数の値です。