改訂単体法とは？わかりやすく解説

改訂単体法（かいていたんたいほう、改訂シンプレックス法、英: Revised simplex method）とは、数理最適化に関するアルゴリズムの一種である。1954年にジョージ・ダンツィーグ・ウィリアム・オーチャード・ヘイズ（ドイツ語版）によって考案された線形計画問題を解くための解法であり、同じく線形計画法のアルゴリズムとして知られる単体法に工夫を施した解法である^[1]。

改訂単体法は反復法に分類され、線形計画問題のある一つの解を初期の解として、反復ごとに解を改善しながら最適解を得るアルゴリズムであるが、反復ごとに得られる解を初期の入力値で表される行列の連立方程式を解くことで得る。これは反復ごとに直前の反復で得た辞書と呼ばれる変数の状態を表した数式により解を更新する単体法とは反復解の生成方法が異なっている。解の更新を行列形式により行うことで行列の疎な構造を利用した効率の良い実行が可能となる^[2]^[3]。