スポンサーサイト

--年--月--日 --:--

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

線形計画問題の幾何的な意味

2008年09月23日 00:05

久々の更新。。
もうちょっと更新できたら良いんですけど、家につくのは日付が変わってからなので気力が湧きませんでした。
気長に見てくださってる方、ありがとうございます。
忙しいのもやっと落ち着いたのでぼちぼち更新していきます。
次からは矢継ぎ早に更新できるといいなぁ。

ちなみに、ノートPC買いました!
HPのtx2505っていうやつなんですけど、13万ぐらいでタブレットPCのメモリ4GB積んだやつを買えちゃうんですね。すごい安くなったもんだなぁ。

ただ、このノートPC、ものすごい発熱なのがタマに傷ですが・・・。
個人的には結構満足かも。
キーボードも打ちやすいし、画面も見やすいし。いいこと尽くめです。


さて、今回も線形計画法のこと書きます。
本当はそろそろ線形相補性問題に入りたいんだけど。。
もうちょっと理解を深めるということで、違った角度からの話をしたいと思います。


前回までお話した線形計画問題とシンプレックス法。
数学的には、制約を定義しその制約内で最小値(もしくは最大値)を求めるものでした。

ここでの制約というのは ax > b という単純な線形式ですよね。
最大値の場合は不等号が逆(<)になります。

これを具現化してみると。。。
実は多角形の領域に囲まれた部分の問題になります。

制約式の ax > b という部分は ax を x 軸、b を y 軸とみなせば、 ax = b であらわされた直線の上領域に当たるわけです。
ax < b なら下の領域ですね。
ということは、制約式が増えるごとに制約式を満たす領域が限定されていくのがわかります。
もちろん、これは「答えに影響するような制約式」の場合だけの話です。

1次の制約式により限定された領域というのは多角形に他なりません。
しかも凸多角形です(無限遠線で区切られた領域で凹む場所なんて出来るわけないので)

問題が凸多角形上のことだとわかったことで、元に戻ってみます。
この領域内でのある関数との最大値(最小値)というのは、どこかの頂点になりそうです。

前回のシンプレックス法での適応時に、「基底を求め、それを最大限まで増やす」という項目があったかと思います。
これは、この制約式で囲まれた領域(多角形)の辺を目的関数に沿った方向に他の辺とぶつかるまで辿るという行為になります。


スケジューリングの最適化や人員配置の問題が、いつの間にか多角形の問題に変わってるのが面白いですよね。
最適化問題を幾何的に解くことも出来るわけです。
そういうわけで、最適化問題とグラフ理論というのは親和性の強い問題なわけですね。


スポンサーサイト


最近の記事


上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。