改訂単体法

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

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

定式化

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

{\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 \in ℝ m \times n$ は制約行列であり、 $x \geq 0$ の下で $Ax = b$ を満たすような解が少なくとも一つ存在し、 $A$ が行フルランクであると仮定する。もし、 $A$ がフルランクでない場合は、制約条件に冗長な制約式が存在するか、実行不可能な制約が含まれている。 $A$ がこのような場合であったとしても、前処理の段階で対処することができる。

アルゴリズム

最適性の条件

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

{\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 \geq 0$ に対応するラグランジュ乗数（KKT乗数）である^[3]。また最下段の条件 $s T x = 0$ は、 $s i x i = 0$ , $i = 1, ..., n$ と等価な条件である。この条件は一般的に相補性条件（相補スラック条件）と呼ばれる。

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

{\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 \geq 0$ である。また $c$ および $s$ はそれぞれ

{\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 \geq 0$ であることから相補性条件より $s B = 0$ を満たさなければならない。このことから、最適性の条件は

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

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

{\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 \geq 0$ を満たしていれば、 $x$ は最適性の条件であるKKT条件を満たし、最適解であるといえる。

ピボット操作

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

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

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

すなわち、 $x q$ を 1 増加させると、目的関数値 $c T x$ は $- s q$ 増加する^[6]。また、

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

であることから、 $x B$ は、 $Δ x B = B -1 A q x q$ によって対応するように減少させる必要があり、これは変数の非負条件から $x B - Δ x B \geq 0$ を満たさなければならない。ここで、 $d = B -1 A q$ とおく。

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

そうでない場合は、基底から出る変数の添字として $p = argmin 1\leq i \leq m {x i / d i | d i > 0}$

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

具体例

下記の線形計画問題

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

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

{\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$ は

{\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 3$ を 1 単位増加させると $x 4$ と $x 5$ がそれぞれ 1 と 3 減少することを意味する。したがって、 $x 3$ を 5 まで増加させると、その時点で $x 5$ が 0 まで減少し、 $p = 5$ が基底から出る変数の添字となる。

ピボット操作後では

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

となり、

{\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 T x$ を改善することができない退化やピボット操作に求まる辞書が退化により何度も同一のものが表れる巡回現象が生じ得る。巡回が発生する場合では、 $b$ の各成分に互いに異なる微小な値 $ε$ を加える辞書式摂動法やBlandの最小添字規則に従ったピボット操作を行うことで巡回を防止し、有限回のピボット操作で最適解を求めることができる^[7]。

基底表現

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

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

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