Simplex Method

線形計画法（Linear Programming; LP）とは、一次不等式で表される制約条件の下で、一次関数の目的関数（コストや利益）を最小化または最大化する数理最適化手法です。

その幾何学的な意味は明確です。制約条件によって定義される多面体（Polytope：実行可能領域）の「頂点（Vertex）」を探索することに他なりません。LPの基本定理により、「最適解が存在するならば、それは必ず領域の頂点のいずれかにある」ことが保証されています。

シンプレックス法（単体法）は、この性質を利用し、ある頂点からスタートして、目的関数値が改善される隣接頂点へと次々に移動（ピボット演算）を繰り返すことで、有限回の手順で最適解に到達するアルゴリズムです。

$n$ 個の変数 $\boldsymbol{x} = (x_1, x_2, \dots, x_n)^T$ に対する線形計画問題の標準形は、以下のように記述されます。

目的関数（Objective Function）

（ここで $\boldsymbol{c}$ は利益係数ベクトル）

制約条件（Constraints）とスラック変数

シンプレックス法を適用するためには、不等式制約 $\boldsymbol{Ax} \le \boldsymbol{b}$ を等式制約に変換する必要があります。非負のスラック変数 $\boldsymbol{s} = (s_1, \dots, s_m)^T$ を導入し、以下のような連立一次方程式の形（正準形）に変形します。

1. 初期化（Initialization）： 実行可能基底解（通常は原点 $\boldsymbol{x}=0$）を見つけ、初期シンプレックス表（Tableau）を作成する。
2. 最適性判定（Optimality Test）： 目的関数の行（$Z$行）を見る。係数がすべて非負であれば、現在の解が最適解であるため終了する。
3. 入替変数の決定（Pivot Column）： 目的関数を最も改善させる変数（係数が最も負である変数）を選び、これを「入替変数」とする。
4. 離脱変数の決定（Pivot Row）： 制約条件を破らずにその方向にどれだけ進めるか、定数項と係数の比（Ratio）を計算する（最小比テスト）。比率が最小となる行の基底変数を「離脱変数」とする。
5. ピボット演算（Pivot Operation）： ガウスの消去法を用いて、選ばれたピボット要素を「1」に、それ以外の列要素を「0」にする。
6. ステップ2に戻る。

理論の理解を深めるため、以下の具体的な生産計画問題を解いてみましょう。

スラック変数 $s_1, s_2$ を導入して等式化し、表を作成します。
($Z - 4x_1 - 3x_2 = 0$ と変形)

判定： $Z$行に負の値があるため最適ではありません。$x_1$列（係数-4）を入替変数、$s_2$行（比率最小）を離脱変数とします。ピボットは 「2」 です。

ピボット行全体を2で割り、他の行から $x_1$ を消去（掃き出し法）します。

判定： $Z$行にまだ負の値（-1）があります。$x_2$列を入替変数、$s_1$行を離脱変数とします。次のピボットは 「0.5」 です。

同様に行列演算を行います。