改訂単体法

ウィキペディア

改訂単体法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/14 07:23 UTC 版)

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

改訂単体法は（シンプレックス表を用いた）単体法と同様の手順で実行可能基底解と呼ばれる線形計画問題の最適解となり得る解を求めていくが、実行可能基底解の生成方法が異なっている。基底変数の組合せを表現する辞書（基底形式表現）を表したシンプレックス表を用いる代わりに、基底変数に対応する制約の係数を要素とする行列を生成していく。行列形式を用いて線形計画問題を解くことにより行列の疎な構造を利用した効率の良い解法の実行が可能となる。

定式化

今、下記の線形計画問題が与えられているとする。

$\min$ 最適化問題では極大・極小値をとる解について求める。