Mac用プロットライブラリ-14「シンプレックス法」

前回の続き。線形計画問題を解くアルゴリズムの「シンプレックス法」のお勉強。

シンプレックス法

そのアルゴリズムの一つとしてシンプレックス法と言うのがあるらしい。これはある頂点から始めて評価関数の値が大きく（あるいは小さく）なる方向に頂点をたどっていくというもの。イメージとしてはわかりやすい。でも頂点を探すのってどうするの？

ということでさらにいろんなサイトに教えを乞うてみる。
前回描いた図のようなイメージだと、ある頂点から評価関数の値が大きくなる方向の稜線にそって次の頂点に向かうのがわかりやすいけど、実際のアルゴリズムでは稜線を探すのは大変なので変数をひとつずつ（座標軸にそって）変えていって次の頂点にたどり着く、ということをやる。

それと、やはり計算機向けにするために行列で表現しておく方がいい。そうすればLAPACKのような線形計算のライブラリも使えることになる。僕は使わないけどね。

問題の形式的な統一

行列で書いて、線形計算の手法を使いやすくするために、まず問題の形式をそろえてしまう。それは n個の変数xiの線形結合の制約条件

あるいは

がm個あるもとで評価関数z

を最小化、あるいは最大化する(x1,..., xn)の組を求めると言う問題に対して

• 最小化問題にする
• 変数変換を行って、非負の変数だけにする
• さらに新しい変数を導入して不等号の条件式を等号にする

ということを行う。

最小化問題にするというのは、最大化問題には評価関数の符号を反転するだけ。問題が線形なので意味は同じになる。べつに最大化問題にそろえたとしても後の議論はところどころ符号が反転するだけで全く同じになる。

後の二つに対してはスラック変数と言うのを導入する。

• 非負制約のある変数はそのまま
• 制約のない変数xは、変数を一つ増やして
  
  
  
  とする
• 変数に対するほかの制約（非正制約とか、あるかどうか知らないけど）も同じようにする
• 不等式の制約条件
  
  
  
  は、さらに変数を増やして
  
  
  
  とする。逆の不等式
  
  
  
  には
  
  
  
  

などとする。この追加した変数をスラック変数と呼ぶらしい。ようするに制約条件を揃えて、変数が非負であると言う制約だけにする。こうすることで問題の形式を統一しておく。変数を増やして何が面白いのか、とも感じるけど、ことのほか便利であることが後でわかる。

続きはあしたにしよ。