改訂単体法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/11 08:37 UTC 版)
改訂単体法（かいていたんたいほう、改訂シンプレックス法、英: Revised simplex method）とは、数理最適化において、ジョージ・ダンツィーグによって考案された線形計画問題に対する単体法に工夫を施した解法である。
改訂単体法は（シンプレックス表を用いた）単体法と同様の手順で実行可能基底解と呼ばれる線形計画問題の最適解となり得る解を求めていくが、実行可能基底解の生成方法が異なっている。基底変数の組み合わせを表現する辞書（基底形式表現）を表したシンプレックス表を用いる代わりに、基底変数に対応する制約式の係数を要素とする行列を生成していく。線形計画問題を行列形式として表現することで行列の疎な構造を利用して効率良く解くことができる[1][2]。
定式化
これ以降では、線形計画問題が下記のような標準形として与えられているものとして説明を行う。
Optimization computes maxima and minima.
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) | |||||
|---|---|---|---|---|---|
| グラフ理論 |
| ||||
| ネットワークフロー (最大流問題) |
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |
 | この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。 |
