シンプレックス法を雑に理解した

わかる人には当たり前で、わからない人には多分わからない駄文だが、将来の自分には有用と判断して公開

参考文献

シンプレックス法でも勉強しようとググっていくつかのページを見たけど、東工大の水野研が公開しているPDFのテキストが一番わかりやすかった

1. 標準形への変形

二次関数のグラフを描画したいときには平方完成するように、線形計画法では解きたい課題を 標準形 に変形することが第一歩。標準形はざっくり以下の形:

• 登場する変数が 全て非負
• 目的関数の 最小化 がミッション
• その他の制約は全て 等式制約 (不等式制約はない)

一般の線形計画問題を標準形になんとか変形する必要がある。そのためのテクニックは以下:

• テク: 非負制約の導入
  • x に非負制約がない場合、u, v という非負変数を用いて x = u - v として x を消去
  • 変数を 1 へらして 2 増やすので見た目にはちょっと複雑になったように見える
• テク: 最大化問題を最小化問題に変換
  • 目的関数の符号を逆転させる
• テク: 不等式制約の除去
  • スラック変数の導入
  • x + y <= 3 ならスラック変数 z を導入して、 x + y + z = 3, z は非負とする
  • x + y >= 3 なら -x -y <= -3 と変形して -x -y + z = -3, z は非負 とする

以降の章は、解きたい課題が標準形であることを前提とする。

2. 概念の理解

2-1. 基底解

変数の数 N に対して、等式制約の数は M しかないので、N = M でない限り、変数は一意に決まらない（だからこそ最適化問題になる）。例えば 「N - M 個の変数を全部 0 にしてしまって、残りの M 個の変数を M 個の等式制約で一意に決める」、といった変数の決め方で全変数値を決めることは可能であり、そのようにして決めた変数の組を基底解という。基底解の各変数値が運よく全て非負であったら、（最適かどうかは別として）制約をすべて満たしている。これを実行可能基底解と呼ぶ。さらにもっと運が良くて、その実行可能基底解が、目的関数を最小化するような最適な変数の組み合わせだった場合、最適実行可能基底解という。

注:

• 基底解は（どの変数を 0 にするかという任意性があるので）、複数ある
• M 個の等式制約が独立、すなわち、ランクが M であることを仮定している

2-2. 数学の力

超強力な定理「最適解があるなら最適実行可能基底解が存在する」がというのがある。つまり、「（有限個の）基底解をしらみつぶしに調べれば、最適解に到達できる」ということが言える。こうなるとなんか解けそうな気がしてくる。

あと必要なのは以下であり、それらについても理論が確立されている

• 基底解の最適性判別の方法
  • 補足: なくてもいいけど、ないと本当に全ての基底解を巡らなければいけなくなる。
• 基底解の巡り方
  • 補足: いい感じに次に処理する基底解を見つける方法
• 実行可能基底解の作り方
  • 補足: 基底解だけを作りたいなら、適当に N - M 個を 0 にすればいいんだけど、後述するように、シンプレックス法では実行可能基底解がほしい。実行可能基底解が得られれは上述の巡り方で芋づる式に基底解を巡れる。これは二段階シンプレックス法に対応。

2-3. 基底形式表現

基底解を求める場合は、「N - M 個の変数値(非基底変数)をすべて 0 にしてのこりの M 個の変数値(基底変数)を決める」ということを行ったけど、そうじゃなく、「N - M 個の非基底変数をすべて定数だと思って M 個の基底変数の値を決め」、「そのあとに全ての非基底変数の値に 0 を代入する」と考えよう。このように 0 に評価するのを後にすることにより、非基底変数の、目的関数や基底変数への寄与分を定量評価できる。このように、線形計画問題を、非基底変数による寄与を明確にした形に変形した形式を基底形式表現とか、辞書と呼ぶ。

辞書が求まると基底解の最適性を判別できる。つまり、もし目的関数における非基底変数による寄与分がすべてプラスだったとすれば、非基底変数をすべて0 以外にしてはまずい、ということがわかり、この実行可能基底解が最適であることがわかる。そうでなく、もし目的関数における非基底変数の寄与分にマイナスの項があった場合、その非基底変数 x を 0 にするよりも、正の値にした方が目的関数の値を減らすことが可能であると判断できる。つまり、 「x を非基底変数にしたのは間違いで、現在の基底変数のうちどれか一つ y と入れ替えた新しい基底解にするべきだった」と判断できる。

さて、辞書を求める方法は明快だが若干計算量が多い。上述の通り、複数の基底解を計算するにあたり複数の辞書を求める必要があるのだが、その構成順は「辞書」⇒「基底変数と非基底変数からひとつずつ変数を抜き出し入れ替えた基底での辞書」というようによく似た基底解に対する辞書が必要になる。こういった漸化的な辞書の構成法だと計算量が少なくて済むのでアルゴリズムに取り入れたい。

3. 主シンプレックス法

以上の準備があれば、シンプレックス法の理解はできたも同然。以下の手順

• 手順1. 実行可能基底解をもつ基底変数の組み合わせ（とその辞書）を何とか一つ見つける
• 手順2. 目的関数に対してマイナスの寄与を果たす非基底変数を見つける(x と名付ける)
  • なければ最適解を見つけた！ということなので即時終了
• 手順3. x をプラスにしたときに値が減る基底変数 y を見つける
  • 全ての基底変数値が増えるなら（いくらでも x を大きくできるので）非有界となり解なしと判断。即時終了
• 手順4. x と y を入れ替えた基底解に対応する辞書を求めて、手順2 に戻る

3-1. 二段階シンプレックス法

主シンプレックス法の 手順1. でいきなり手詰まりになることがある。つまり、実行可能な基底解がなかなか見つからない場合がある。そこで、実行可能な基底解を求めるための一連の手続きが知られている。その手続きは、主問題をちょっと変更した線形計画問題をシンプレックス法で解くというものだ。つまり、全体を通じてみると二回シンプレックス法を解くように見えるので二段階シンプレックス法と呼ぶんだと思う。

一段目の線形計画問題は以下のように作られる。

• 追加で新たに人工変数を M個導入し、目的関数を人工変数の総和とする
• M 個の等式制約の左辺を少し修正（一つの人工変数を足す）

上記で得られた標準形の線形計画問題では、容易に人工変数全てを非基底変数として選択した際の辞書が得られるので、シンプレックス法を使って解ける。解く前から最適解は 0 だと知っているので（なぜなら目的関数は非負である人工変数の総和だから）、もし計算結果が 0 でないなら、そもそも主問題がおかしかった（実行不能）ということで終了できる。予想通り 0 であった場合、その時の非人工変数の値の組み合わせが、元の問題の実行可能解となる（一見すると驚きだが簡単に証明できる）

3-2. 無限ループ

基底解の個数は有限なのだけど、主シンプレックス法の手順では、基底解全部を巡れずに同じ基底解を繰り返し調べてしまう可能性がある。ただ、「すべての実行可能基底解で基底変数の値が正である (0 でない)」という非退化条件 が成立する場合無限ループは起こらない。

4. 主要トピック

シンプレックス法は十分一般的・汎用的ではあるが、それでもなお個別のケースごとに考慮せねばならない留意事項がある

4-1. ピボット規則

シンプレックス法の実装において（ある程度）任意性があるのは、「どの非基底変数とどの基底変数を入れ替えるのかを選択する規則」であり、これをピボット規則と呼ぶ。ピボット規則の実装を取り換えると、最適解を見つけるまでの実行速度が変わったり、無限ループを回避できたりする。主に以下に上げるピボット規則がある:

• 最小係数規則 (Dantzig の規則)
• 最良改善規則 (最小目的関数規則)
• 最小添え字規則(Bland の規則)
• ランダム規則

4-2. 無限ループ回避

前章でも触れたが、退化がある場合実行時に無限ループが発生しうる。実際上はレアケースらしいが、理論上無限ループを回避するための方法があることが重要。ピボット規則として最小添え字規則を採用すると無限ループが回避できる。