改訂単体法

ウィキペディア

改訂単体法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/11 08:37 UTC 版)

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

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

定式化

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

${\displaystyle {\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}}}$

Optimization computes maxima and minima.

非線形（制約付き）

一般	バリア関数 ペナルティ関数法
微分可能	ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法

凸最適化

凸最小化	切除平面法 簡約勾配法 劣勾配法 近接勾配法
線形 および 二次	内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法）
グラフ理論	最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法
ネットワークフロー (最大流問題)	ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法

メタヒューリスティクス

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

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

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

• 表示
• 編集

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

• 表示
• 編集