2009年07月15日

数理計画問題とその応用

情報科学や経済学の学問分野ではメジャーなんだけど、「数理計画問題」と呼ばれるものがある。この学問分野、一言でいうと「与えられた複数の条件式の下で、目的とする値を最大化(最小化)する」という事を探求するのだけど、これは現代の経済や企業経営において非常に役に立つ話なんですよ。
実際に大手の企業は、物流や人員配置等を数理計画問題として解いてコスト削減を実施しているらしい。

さて、今日はこの数理計画問題の中でも、わりと簡単な「線形計画問題(条件式の中に、二乗以上のべき乗変数を含まない)」について、例と共に説明していこう。



さて、まずはこの線形計画問題を説明する上での背景話として、俺の大学時代の貧乏話(半分フィクション)を出すとしよう。(笑)

当時俺は朝食を作るのがめんどくさくてしょうがなかった。ただ、昼食も夕食もろくな物を食べていなかったので、栄養失調が心配で何かしら朝食を食べる必要は感じていた。とりあえずシリアルと牛乳を買って来て、これを朝食にしようと思ったのだが、どれだけ食べれば朝食に必要な栄養素を摂取する事ができるかと思い、栄養士である友達に聞いたところ、たんぱく質を9グラム、ビタミンDを1/3RDA、カルシウムを1/4RDAを摂取する必要のある事がわかった。(ちなみに、RDAは1日の必要摂取量)そして実際に、牛乳とシリアルにどれだけその栄養素が含まれているのを調べてみると、以下の通りである事がわかった。

【牛乳(1/2カップ)】
値段:50円
タンパク質:3グラム
ビタミンD:1/15RDA
カルシウム:1/6RDA

【シリアル(1/4袋)】
値段:65円
タンパク質:2グラム
ビタミンD:2/15RDA
カルシウム:なし

ここで俺は「どうせなら一日の朝食に必要最低限の栄養素を摂取しつつ、朝食費用をできるだけ少なくしたいな」と考えたわけですよ。しかも、「牛乳を混ぜ過ぎてシリアルをびしょびしょにしたくない」「逆に、牛乳が少なすぎてぼそぼそのシリアルにしたくない」という多少わがままな条件まで付けることにしました。

さて、今までの話はつまるところ
○一日の朝食に必要最低限の栄養素を摂取する
○牛乳を混ぜ過ぎてシリアルをびしょびしょにしたくない
○牛乳が少なすぎぼそぼそのシリアルにしたくない
の三つの条件を満たしながら、朝食代を最も少なくするために、牛乳とシリアルをどの程度の割合で混ぜるべきか?という問題にまとめる事ができる。


ここで一旦、この問題を定式化してみよう。牛乳1/2カップとシリアル1/4袋をそれぞれ一単位として(x,y)とする。そして朝食一食分の費用をzとすると、以下のようにこの問題を定式化できる。
breakfast-model.jpg

今は変数がxとyしかないので、非常に簡単な問題なんだよね。なぜなら、xy平面に@〜Fの条件式を図示すると以下の領域になる。
linear-plan-probrem.jpg
今考えなければいけないのは、この領域内においてzを最小にする具体的な(x,y)の値を求めるわけだ。z=50x+65yであるので、この直線が上記の水色の領域に触れていて、さらにzが一番小さくなるところというと、↓の箇所になる時でしょうか。
linear-plan-probrem_answer.jpg
この結果より、7つの条件式を満たして朝食費用を最小化するx,yが算出できるわけです。

ちなみに、この問題の場合はわりと楽に答えが出るんだけど、変数の数が3個以上になると、図に書くのも面倒だし、人間の手で解くにはもうかなりしんどいわけですよ。さらに、4変数になると図に書けないので、おそらく人間には解けないわけだ。ただし、この手の線形計画問題に対しては変数の数がいくつになろうが、「シンプレックス法」というコンピュータで解ける万能な計算方法がある。このシンプレックス法を、初めてコストダウンに適用した企業が、米国のデルタ航空だったのだけど、航空機と乗務員のスケジューリングに関して変数の数が1700万、条件式は800本の線形計画問題を解いて年間1000万ドル以上のコスト削減が図られたんだよね。いやいや、やっぱ規模の大きいことになると、人間が適当に決めるよりも数式に従う方が無難って事だな。(笑)


シンプレックス法(1947年発案)については、かなり数学チックな話になるのでここでは説明しないけど、自動でこういう問題が普通のPCで解けるんだから、すごい世の中になったよなぁ……。(笑)



今日のエントリーで、「なるほど」「ふむふむ」「面白い」などと思ってくれた方で、一票を頂ける方は是非ともお願いします。↓
人気ブログランキングへ
posted by きらっち at 20:12| Comment(2) | TrackBack(0) | 科学
この記事へのコメント
経済学、統計処理、貿易、外交あらゆる部門にお詳しくて、作曲もなさるし、きらっちさんは本当に一人でブログ書いているのですか。スゴイ。
Posted by ゆきちゃん at 2009年07月15日 21:06
>ゆきちゃんさん
いやいや、きらっちが二人も三人もいるわけじゃないですよ。(笑)
大学時代はコンピュータ専攻だったし、他の分野は専門外なんですよ。素人視点で書いてるだけです。(笑)
Posted by きらっち at 2009年07月16日 19:20
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/30565954

この記事へのトラックバック