Mac用プロットライブラリ-13「はみ出し問題と線形計画法」

前回のはみ出し問題は、線形計画問題と見なすことができるところまでわかった。もともとそれほど複雑な問題ではないし、自分で線形計画法を実装するのもボケ防止になるので、勉強しようと思ってインターネット上で解説を探してみると、結構ヒットする（Googleで「線形計画法+シンプレックス」で検索）。読んでみて何となくわかった気がしてきた。

ここではお勉強の過程をそのまま書いておくことにする。どうしてもまわりくどい書き方だったり同じことを何度も書いたりしてるが、それは思考の過程を踏んでいるせいで、整理されたものを見たければいっぱい出ている本なり解説サイトなりを参照すればよい。

また、なるべく線形代数のことばを使って書くことにした。線形計画法を解説しているサイトを見ると、表を使ったり、線形計画法独特の省略法があったりして僕みたいな慣れていない人間にはピンとこないところがあった。歳のせいか、数字がいっぱい並んだ表を見るともうそこで思考が止まってしまう。線形代数は多項式Fittingなどの問題で慣れ親しんでいるのでそこを出発点にした。

ところで、LAPACKには線形計画問題のための関数が用意されていて、MacOS X10.2以降には標準でインストールされている（本体は/System/Library/Frameworks/Accelerate.frameworkの中にlibLAPACK.dylibとして、普通のインストール先の/usr/lib/liblapack.*はそこへのシンボリックリンクになってる）らしい。でも僕はもうLAPACKは使ってないし（LAPACKが必要なほど大きな行列演算は、もうあまりしない）、LAPACKは大きなライブラリなので、このためだけにLAPACKをメモリにロードしなければいけないのはちとつらい（MacOSXって使ってない共有ライブラリは追い出されるの？それともページアウトするだけ？）。自分で実装する前に、お勉強しよう。

線形計画法

ってなんじゃいな

具体的な問題の例は解説サイトにいっぱいあるけど、例えば原料と製品がそれぞれ複数あって売り上げを最大化する、原料AとBから製品XとYが作れるけどどう配分すれば一番儲かるか、とか経費を最小化するには、とかそういう問題。原料の総使用量に上限があって、製品の量を変数にして総使用量を超えないと言う条件を不等式で、売り上げを評価関数として考える。これらはすべて線形な式になっているとする。こういった問題の解を見つけようと言うのが線形計画法。

N個の変数に対するM個の1次の不等式で表現された制約条件をすべて満足する領域は、N次元空間内の凸多角形の内部になる（もちろん、問題設定によってはある方向に無限にのびる開領域になる場合もある）。

例えば

例として変数が三つの場合を考える。変数の値の組は3次元空間の1点で表されることになる。1次のある制約条件を満たす領域は、その3次元空間の中で、平面で区切られた空間のどちらか一方（不等号の向きで決まる）になる。制約条件ごとに平面で区切られた空間ができて、すべての制約条件を満たすということはその空間のANDをとることになって、すなわち凸多面体の内部ということになる。

評価関数も1次多項式であれば、そのとり得る値によって平行移動する平面になる。係数が変化しなければこの面の法線は評価関数の値によらず一定なので、その評価関数の値が異なる平面群のうち、さっきの凸多面体と交差して、かつ評価関数の値が最大（あるいは最小）になるものを選べばよい。

凸多面体が評価関数の平面と平行な面を持っていなければ、最適解はその凸多面体の頂点のどれかひとつ、ということになる（平行な面があるということは評価関数と係数の比が同じの条件式があるということで、評価関数の値そのものを制限することになる。そういう問題はまずありえないだろう）。イメージとしては図-1みたいな感じ。

この図では一番上にある評価関数平面が、一番極値に近い、ということになる。

変数が三つの場合はこんなイメージでおっけーでしょう。これを一般のN次元にしたとしても、条件式も評価関数も変数に対して線形だから関数そのものが極値を持たないので、極値は端っこにしかこないことは自明で、評価関数が最大（小）になる頂点を探すアルゴリズムを実装すればいい、ということになる。

続きはまたこんどにするけど、この調子では整理がすむまでずいぶんかかるな。