改訂単体法

**改訂単体法**（かいていたんたいほう、**改訂シンプレックス法**、）とは、数理最適化に関するアルゴリズムの一種である。1954年にジョージ・ダンツィーグ・によって考案された線形計画問題を解くための解法であり、同じく線形計画法のアルゴリズムとして知られる単体法に工夫を施した解法である。

改訂単体法は反復法に分類され、線形計画問題のある一つの解を初期の解として、反復ごとに解を改善しながら最適解を得るアルゴリズムであるが、反復ごとに得られる解を初期の入力値で表される行列の連立方程式を解くことで得る。これは反復ごとに直前の反復で得た辞書と呼ばれる変数の状態を表した数式により解を更新する単体法とは反復解の生成方法が異なっている。解の更新を行列形式により行うことで行列の疎な構造を利用した効率の良い実行が可能となる。

## 定式化
今、下記の線形計画問題が与えられているとする。

:
ただし  は制約行列であり、 の下で  を満たすような解が少なくとも一つ存在し、 が行フルランクであると仮定する。もし、 がフルランクでない場合は、制約条件に冗長な制約が存在するか、線形計画問題が実行不可能の可能性がある。 がこのような場合であったとしても、前処理の段階で対処することができる。

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

:

ただし  および  は、それぞれ 、 に対応するラグランジュ乗数（KKT乗数）である。また（）の条件  は、,  と等価である。この条件は一般的に相補性条件（相補スラック条件）と呼ばれる。

線形計画法の基本定理から、実行可能多面体の頂点  は、行列  の列から選ばれた基底  によって導かれる。が行フルランクであるとき、 は正則である。そして、 は一般性を失うことなく  と分割できたと仮定すると、 は

:
\boldsymbol{x} =
\begin{bmatrix}
\boldsymbol{x_B} \\
\boldsymbol{x_N}
\end{bmatrix} =
\begin{bmatrix}
\boldsymbol{B}^{-1} \boldsymbol{b} \\
\boldsymbol{0}
\end{bmatrix}


と表される。ただし、 である。また  および  はそれぞれ

:
\begin{align}
\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{align}


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

:
\begin{align}
\boldsymbol{B}^{\mathrm{T}} \boldsymbol{\lambda} & = \boldsymbol{c_B}, \\
\boldsymbol{N}^{\mathrm{T}} \boldsymbol{\lambda} + \boldsymbol{s_N} & = \boldsymbol{c_N},
\end{align}


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

:
\begin{align}
\boldsymbol{\lambda} & = (\boldsymbol{B}^{\mathrm{T}})^{-1} \boldsymbol{c_B}, \\
\boldsymbol{s_N} & = \boldsymbol{c_N} - \boldsymbol{N}^{\mathrm{T}} \boldsymbol{\lambda}.
\end{align}


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

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

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

:\frac{\partial (\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x})}{\partial x_q} = s_q,

すなわち、 を 1 増加させると、目的関数値  は  増加する。また、

:\boldsymbol{B x_B} + \boldsymbol{A}_q x_q = \boldsymbol{b},

であることから、 は、 によって対応するように減少させる必要があり、これは変数の非負条件から  を満たさなければならない。ここで、 とおく。

もし  ならば  をどれだけ増加させても  は非負のままである。この場合、 は任意に減少可能であることから、与えられた線形計画問題の実行可能領域は非有界である（最適解をもたない）。

そうでない場合は、基底から出る変数の添字として

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

## 具体例
下記の線形計画問題

:
\begin{align}
\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{align}


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

:
\begin{align}
\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{align}


としたとき、初期実行可能基底解は  であり、、 は

:
\begin{align}
\boldsymbol{\lambda} & =
\begin{bmatrix}
0 & 0
\end{bmatrix}^{\mathrm{T}}, \\
\boldsymbol{s_N} & =
\begin{bmatrix}
-2 & -3 & -4
\end{bmatrix}^{\mathrm{T}}.
\end{align}


と求まる。

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

ピボット操作後では

:
\begin{align}
\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{align}


となり、

:
\begin{align}
\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{align}


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

## 実用上で起こり得る問題点
### 退化

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

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

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


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

## 脚注

### 注釈

### 出典

## 参考文献

* 
* 
* 
* 

## 関連項目
* 線形計画法
* 単体法

## 外部リンク
* 改訂単体法 - 数理最適化用語集