改訂単体法

ウィキペディア

改訂単体法

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

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

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

定式化

これ以降では、線形計画問題が下記のような標準形として与えられているものとして説明を行う。

${\begin{array}{rl}{\text{Minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{s.t.}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}$

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

非線形（制約付き）

凸最適化

組合せ最適化

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• 群知能（ACO・PSO）
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア （一覧）