B.2.1 単体法
単体法(simplex method)は，実行可能領域を構成する頂点（基底解）を反復的に移動しながら，目的関数値を改善していく手法です．
その歴史は古く，1940 年代に George B. Dantzig によって考案されて以来，理論解析，アルゴリズムの改良，そして産業界の実問題への適用を通じて，今日まで幅広く発展してきました．歴史的背景については，Dantzig の Origins of the Simplex Method（1990）に詳述されています．同論文では，線形計画法の黎明期における数学者・経済学者の貢献や単体法の起源が，著者自身の直感的理解とともに述べられています．
単体法の概要
単体法では係数行列から基底（基底行列）を選び，これに対応する基底解を定めます．基底を選ぶことは，実行可能領域における頂点を選択することに相当します．
選んだ初期基底が制約条件を満たさない場合には，フェーズ 1と呼ばれる手続きを実行し，制約を満たす基底へ移動させます．実行可能な基底が得られた時点で，単体法はフェーズ 2に移行します。
フェーズ 2 では，目的関数値を改善できる方向をもつ非基底変数を選び，それを基底に組み入れることで隣接する頂点へと移動します．この基底の入れ替え操作をピボット（pivot）と呼びます．
具体的には，以下の処理を 1 回の反復（iteration）として実行します．
- プライシング（pricing）
非基底変数の中から，目的関数値を改善できる変数（入る変数）を選択する． - 比率判定（ratio test）
選択した変数を基底に入れた際，制約条件を満たしたまま値を増加させられる限界を調べ，基底から除外すべき変数（出る変数）を決定する． - ピボット操作（pivot）
基底の入れ替え（更新）を行い，現在の基底解を次の頂点へと移動させる．
これらの手順を，改善が見込めなくなる（最適性の条件が満たされる）まで繰り返すことで，最適解に到達します．凸多面体の辺を伝って頂点を順に移動するという性質から，単体法は幾何学的な解釈が容易であり，多くの実問題に対して実用的な計算性能を示すことが知られています．
実装における構造的性質の利用
単体法が今日においても広く利用され，多くの応用分野で高い有効性を保っている背景には，数理的な構造を巧みに利用した実装技術があります．代表的なものとして，実務上の最適化問題が持つ以下の性質が挙げられます．
- スパース性（sparsity）
多くの線形計画問題では制約行列が疎であり，この性質を利用することで，プライシングや基底更新といった主要操作の計算負荷を大きく削減できます． - ハイパースパース性（hyper-sparsity）
プライシングや前進代入・後退代入などの計算で，実際に参照・更新される非ゼロ要素がごく少数に限られる現象です．これに対応した専用アルゴリズムにより，さらなる高速化が可能となります． - 基底の近三角性（near-triangularity）
基底行列は行・列の並べ替えによって「ほぼ三角行列」の形に変換できることが多く，この構造により LU 分解や連立方程式の求解を数値的安定性を保ちつつ高速に実行できます．
これらの構造的性質を最大限に活かすことで，単体法は理論的な最悪計算量とは対照的に，実務上の多くの問題に対して高い計算性能を発揮します．
上に戻る