Mac用プロットライブラリ-15「線形計画問題の行列表現」

くそー、まだ梅雨じゃないのに雨が降ってなんにもできない。
自転車はもちろん、しばらく布団を外に干してない。
土日ぐらい気を利かして晴れろよ、ばかやろー。

ということで暇なので、プロットのはみ出し問題を解決するための線形計画法のお勉強の続き。

行列表現と標準形

標準形に変形した結果、問題はN(>n)個の変数に対するM(>m)個の等式の条件とすべての変数に対する非負制約のもとでの評価関数の最小化と言う問題になる。

この標準形に変形された問題を、行列のかっこうに書き直すと

の制約のもとで

を最小にするxを求める、ということになる。ここでa.bはベクトルaとbの内積である。

こう書くと連立1次方程式みたいだけどスラック変数のせいで条件式の数だけ変数が増えているので式-11は変数の数の方が方程式の数より多い不定の方程式になっている。

スラック変数を含めた変数の数がN個で、条件式の数がM個であるとする。ということは行列AはN>MのM×N行列（横長）ということになる。

従ってこれは、N次元空間内の式-11で決まるM次元部分空間の内部で、少なくともN-M個の座標（変数）が0になっていて残りは正の点（これはもとの問題のn次元空間内の凸多角形の頂点にそのまま対応する）のうちから評価関数を最小にするものを選ぶ、という問題になる。

そう考えると、直感的には何となく

1. M次元部分空間の内部で、少なくともN-M個の座標（変数）が0になっている点をなんでもいいから見つける
2. 0でない変数を0にして（そのとき0だった変数は0でなくなる）評価関数が小さくなるものを探す
3. そうやって0の変数を入れ替えて評価関数が最小のものを探す

としたらいいかな、と言う気がしてくる。どうやらこれがシンプレックス法の考え方らしい。

シンプレックス法のための前準備

この問題に対してまず、Aの独立な列（縦方向）ベクトルをM個取り出して、それを行列Aの前の方に並べ余った縦ベクトルをその後ろに並べた行列を作る。条件式にひとつづつスラック変数が含まれている（少なくともM個あってその要素は0ではない）ので、これは常に可能である。もちろん、それに従ってベクトルxとcも要素の順番を入れ替えて番号を振り直しておく。つまり順番を入れ替えたあとの行列Aを、

と分解する。

さらに、ここで解ベクトルも二つに分解する。

さらに評価関数の係数cも同様に

とすると、評価関数zは

と分解できる。 また、それぞれ分解したベクトルの0でない成分を抜き出した短いベクトルを

と書くとxUとcUはM次元ベクトル、xVとcVはN-M次元ベクトルであるが 式-18の評価関数zは

と書ける。 また、このUの0でないM×M小行列をBとする。つまり

ついでにVの0でない(N-M)×M小行列をNとしておく。つまりこれも

ごちゃごちゃと書いてきたが、ようするにこれらの小行列と短いベクトルを使えば式-11は

の条件の下で

を最小にする問題に変形できる。 これだけだとなーんにも変わっとらんがな、と思うけど実はこの変形は役に立つ。 長くなったので続きは別稿にしよう。