改訂単体法

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

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

定式化

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

$\begin{array}{cc}\text{Minimize}& {𝒄}^{\mathrm{T}}𝒙\\ \text{s.t.}& 𝑨𝒙=𝒃,𝒙\ge 0\end{array}$

ただし テンプレート:Math は制約行列であり、テンプレート:Math の下で テンプレート:Math を満たすような解が少なくとも一つ存在し、テンプレート:Math が行フルランクであると仮定する。もし、テンプレート:Math がフルランクでない場合は、制約条件に冗長な制約式が存在するか、実行不可能な制約が含まれている。テンプレート:Math がこのような場合であったとしても、前処理の段階で対処することができる。

アルゴリズム

最適性の条件

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

$\begin{array}{cc}𝑨𝒙& =𝒃,\\ {𝑨}^{\mathrm{T}}\mathit{\lambda }+𝒔& =𝒄,\\ 𝒙& \ge 0,\\ 𝒔& \ge 0,\\ {𝒔}^{\mathrm{T}}𝒙& =0\end{array}$

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

テンプレート:仮リンクから、実行可能多面体の頂点 テンプレート:Math は、行列 テンプレート:Math の列から選ばれた基底 テンプレート:Math によって導かれるテンプレート:Efn。テンプレート:Mathが行フルランクであるとき、テンプレート:Math は正則である。そして、テンプレート:Math は一般性を失うことなく テンプレート:Math と分割できたと仮定すると、テンプレート:Math は

$𝒙=\left[\begin{array}{c}{𝒙}_{𝑩}\\ {𝒙}_{𝑵}\end{array}\right]=\left[\begin{array}{c}{𝑩}^{-1}𝒃\\ 0\end{array}\right]$

と表される。ただし、テンプレート:Math である。また テンプレート:Math および テンプレート:Math はそれぞれ

$\begin{array}{cc}𝒄& =\left[\begin{array}{c}{𝒄}_{𝑩}\\ {𝒄}_{𝑵}\end{array}\right],\\ 𝒔& =\left[\begin{array}{c}{𝒔}_{𝑩}\\ {𝒔}_{𝑵}\end{array}\right].\end{array}$

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

$\begin{array}{cc}{𝑩}^{\mathrm{T}}\mathit{\lambda }& ={𝒄}_{𝑩},\\ {𝑵}^{\mathrm{T}}\mathit{\lambda }+{𝒔}_{𝑵}& ={𝒄}_{𝑵},\end{array}$

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

$\begin{array}{cc}\mathit{\lambda }& =({𝑩}^{\mathrm{T}}{)}^{-1}{𝒄}_{𝑩},\\ {𝒔}_{𝑵}& ={𝒄}_{𝑵}-{𝑵}^{\mathrm{T}}\mathit{\lambda }.\end{array}$

ここで テンプレート:Math を満たしていれば、テンプレート:Math は最適性の条件であるKKT条件を満たし、最適解であるといえる。

ピボット操作

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

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

$\frac{\partial ({𝒄}^{\mathrm{T}}𝒙)}{\partial x_q}=s_q,$

すなわち、テンプレート:Math を 1 増加させると、目的関数値 テンプレート:Math は テンプレート:Math 増加するテンプレート:Sfn。また、

$𝑩{𝒙}_{𝑩}+{𝑨}_q{x}_q=𝒃,$

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

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

そうでない場合は、基底から出る変数の添字として テンプレート:Math

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

具体例

下記の線形計画問題

$\begin{array}{cc}𝒄& ={\left[\begin{array}{ccccc}-2& -3& -4& 0& 0\end{array}\right]}^{\mathrm{T}},\\ 𝑨& =\left[\begin{array}{ccccc}3& 2& 1& 1& 0\\ 2& 5& 3& 0& 1\end{array}\right],\\ 𝒃& =\left[\begin{array}{c}10\\ 15\end{array}\right].\end{array}$

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

$\begin{array}{cc}𝑩& =\left[\begin{array}{cc}{𝑨}_4& {𝑨}_5\end{array}\right],\\ 𝑵& =\left[\begin{array}{ccc}{𝑨}_1& {𝑨}_2& {𝑨}_3\end{array}\right]\end{array}$

としたとき、初期実行可能基底解は テンプレート:Math であり、テンプレート:Math、テンプレート:Math は

$\begin{array}{cc}\mathit{\lambda }& ={\left[\begin{array}{cc}0& 0\end{array}\right]}^{\mathrm{T}},\\ {𝒔}_{𝑵}& ={\left[\begin{array}{ccc}-2& -3& -4\end{array}\right]}^{\mathrm{T}}.\end{array}$

と求まる。

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

ピボット操作後では

$\begin{array}{cc}𝑩& =\left[\begin{array}{cc}{𝑨}_3& {𝑨}_4\end{array}\right],\\ 𝑵& =\left[\begin{array}{ccc}{𝑨}_1& {𝑨}_2& {𝑨}_5\end{array}\right].\end{array}$

となり、

$\begin{array}{cc}𝒙& ={\left[\begin{array}{ccccc}0& 0& 5& 5& 0\end{array}\right]}^{\mathrm{T}},\\ \mathit{\lambda }& ={\left[\begin{array}{cc}0& -4/3\end{array}\right]}^{\mathrm{T}},\\ {𝒔}_{𝑵}& ={\left[\begin{array}{ccc}2/3& 11/3& 4/3\end{array}\right]}^{\mathrm{T}}.\end{array}$

が求まる。このとき テンプレート:Math が非負であることから、テンプレート:Math は最適性の条件（KKT条件）を満たし、最適解 テンプレート:Math が求まった。

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

退化

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

基底表現

改訂単体法において、基底テンプレート:Mathが2種類の方程式系を満たすものとする。

$\begin{array}{cc}𝑩𝒛& =𝒚,\\ {𝑩}^{\mathrm{T}}𝒛& =𝒚.\end{array}$

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

脚注

参考文献

• テンプレート:Cite book
• テンプレート:Cite thesis
• テンプレート:Cite book