改訂単体法

改訂単体法（かいていたんたいほう、改訂シンプレックス法、英: 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}}}$

ただし A ∈ ℝ^m×n は制約行列であり、x ≥ 0 の下で Ax = b を満たすような解が少なくとも一つ存在し、A が行フルランクであると仮定する。もし、A がフルランクでない場合は、制約条件に冗長な制約式が存在するか、実行不可能な制約が含まれている。A がこのような場合であったとしても、前処理の段階で対処することができる。

線形計画問題では、KKT条件を満たす解が最適解となるための必要十分条件となる。線形計画問題に対するKKT条件は以下の通りである:

${\displaystyle {\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}}$

ただし λ および s は、それぞれ Ax = b、x ≥ 0 に対応するラグランジュ乗数（KKT乗数）である^[3]。また最下段の条件 s^T x = 0 は、s_ix_i = 0, i = 1, ..., n と等価な条件である。この条件は一般的に相補性条件（相補スラック条件）と呼ばれる。

線形計画の基本定理（英語版）から、実行可能多面体の頂点 x は、行列 A の列から選ばれた基底 B によって導かれる^{[注釈 1]}。Aが行フルランクであるとき、B は正則である。そして、A は一般性を失うことなく A = [B N] と分割できたと仮定すると、x は

${\displaystyle {\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}}$

と表される。ただし、x_B ≥ 0 である。また c および s はそれぞれ

${\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}}$

のように分割される。x_B ≥ 0 であることから相補性条件より s_B = 0 を満たさなければならない。このことから、最適性の条件は

${\displaystyle {\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}}$

と書き直される。これらの条件の下で

${\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}}$

ここで s_N ≥ 0 を満たしていれば、x は最適性の条件であるKKT条件を満たし、最適解であるといえる。

もし現在の解がKKT条件を満たしていない場合には、非基底変数の中で s_N < 0 に対応する x _N を制約条件（主実行可能性）が満たされるように基底変数と入れ替えるピボット操作を行う。退化していない場合は、ピボット操作によって目的関数値 c^Tx は厳密に減少する。したがって、線形計画問題が非退化仮定などの仮定の下では、制約条件が表す多面体の頂点が有限個であることから、改訂単体法はピボット操作の反復により最適解の頂点に到達する^[5]。

m < q ≤ n を満たし、s_q < 0 となる添字 q を選び、これを基底に入る変数の添字と呼ぶ。対応する行列 A の列 A_q が基底に移動され、x_q は 0 から増大される。このときの目的関数値の単位増加量は以下の通りである。

${\displaystyle {\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},}$

すなわち、x_q を 1 増加させると、目的関数値 c^Tx は −s_q 増加する^[6]。また、

${\displaystyle {\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},}$

であることから、x_B は、Δx_B = B⁻¹A_qx_q によって対応するように減少させる必要があり、これは変数の非負条件から x_B − Δx_B ≥ 0 を満たさなければならない。ここで、d = B⁻¹A_q とおく。

もし d ≤ 0 ならば x_q をどれだけ増加させても x_B − Δx_B ≥ 0 は非負のままである。この場合、c^Tx は任意に減少可能であることから、与えられた線形計画問題の実行可能領域は非有界^{[注釈 2]}である（最適解をもたない）。

そうでない場合は、基底から出る変数の添字として p = argmin_1≤i≤m {x_i/d_i | d_i > 0}

を選択する。この選択により、x_q を 0 から増加させながら、制約条件（主実行可能性）を満たしつつ A_p を 0 まで減少させることができる。結果としてピボット操作後の基底は A_q から A_p に置き換わる。

下記の線形計画問題

${\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}}$

が与えられたときに改訂単体法により最適解を求める。基底行列・非基底行列を

${\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}}$

としたとき、初期実行可能基底解は x = [0 0 0 10 15]^T であり、λ、S_N は

${\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}$

と求まる。

q = 3 を基底に入る変数の添字として選択する。すると、d = [1 3]^T となり、これは x₃ を 1 単位増加させると x₄ と x₅ がそれぞれ 1 と 3 減少することを意味する。したがって、x₃ を 5 まで増加させると、その時点で x₅ が 0 まで減少し、p = 5 が基底から出る変数の添字となる。

ピボット操作後では

${\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}}$

となり、

${\displaystyle {\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}$

が求まる。このとき s_N が非負であることから、x は最適性の条件（KKT条件）を満たし、最適解 x が求まった。

改訂単体法は単体法と同様に最適解を求めるため、入力の A , b , c によってはピボット操作を行ったときに目的関数値 c^Tx を改善することができない退化やピボット操作に求まる辞書が退化により何度も同一のものが表れる巡回現象が生じ得る。巡回が発生する場合では、 b の各成分に互いに異なる微小な値 ε を加える辞書式摂動法やBlandの最小添字規則に従ったピボット操作を行うことで巡回を防止し、有限回のピボット操作で最適解を求めることができる^[7]。

改訂単体法において、基底Bが2種類の方程式系を満たすものとする。

${\displaystyle {\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}}$

通常は B を反復ごとに因子分解するのではなく、LU分解された行列が直接更新される。その戦略として、Forrest−Tomlin 法や Bartels−Golub 法などが挙げられる。しかし、行列の更新にかかるデータの量や数値誤差がピボット操作を繰り返すごとに蓄積されるため、定期的な因子分解が必要となる^[1][8]。

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 ネットワークフロー (最大流問題) ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア

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

• 表示
• 編集

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

• 表示
• 編集