最適解の重要性② - 日々の想いに徒然草

monja2004-06-13

前回の最適解の重要性①(参考リンク)で
最適解について書いたけど、
今日はちょっとした実例を、
数式を出して説明しようと思う。
デルタ航空の1200万ドルの経費削減した話は、
次にまわします。

[問題背景]
さて、この四月から某省に入省した安月給のA君は
朝食を牛乳とシリアルだけで、何とか安く済ませたい。
でも、A君は牛乳とシリアルだけで
栄養失調にならないかどうかすごく不安である。
そこで図書館に行って、最低限朝食に必要な栄養素を調べたところ

タンパク質　ビタミンＤ　カルシウム

9グラム　 $\frac{1}{3}$ RDA 　 $\frac{1}{4}$ RDA

であるらしいことがわかった。
次にA君は、牛乳 $\frac{1}{2}$ カップとシリアル $\frac{1}{4}$ 袋
当たりのそれぞれの栄養含有量を調べたところ

　タンパク質　ビタミンＤ　カルシウム　値段

牛乳 $\frac{1}{2}$ カップ　3グラム　 $\frac{1}{15}$ RDA 　 $\frac{1}{6}$ RDA 　50円

シリアル $\frac{1}{4}$ 袋　2グラム　 $\frac{2}{15}$ RDA 　なし　65円

という事実を突き止めた。
さて、A君は「朝食に最低限必要な栄養素を取る」という条件の下で
できるだけ安上がりに牛乳とシリアルを食べる場合
どれだけの牛乳とだれだけのシリアルを食べればいいのか？

[問題の主目的]
とりあえず、牛乳 $\frac{1}{2}$ カップとシリアル $\frac{1}{4}$ 袋を一単位としよう。
ここで、 $x$ を摂取する牛乳の量
$y$ を摂取するシリアルの量とする。
今の問題の主目的は、
「どれだけ朝食(牛乳＆シリアル)の値段を安く出来るか？」って事だよね？
朝食の値段を $z$ として
これを数式で表すと $z=50x+65y$ 。
つまり、この $z$ の値の最小化という事と
その時の $x$ と $y$ の値を求めたいってことが、問題の主目的になる。

[問題の条件]
そして、問題条件としてまず
「朝食の最低限必要な栄養素を取る」って事なので
①　 $3x+2y\geq9$ ……タンパク質は9グラム以上
②　 $\frac{1}{15}x+\frac{2}{15}y\geq\frac{1}{3}$ ……ビタミンＤは $\frac{1}{3}$ RDA以上
③　 $\frac{1}{6}x\geq\frac{1}{4}$ ……カルシウムは $\frac{1}{4}$ RDA以上
の3個の条件がある。

さらにA君は、
牛乳の入れすぎでシリアルがびしょびしょになるのを避けたいし
逆に牛乳が少なくてシリアルがぱさぱさしすぎるのも避けたい。
ということで、牛乳1カップあたり
シリアルは $\frac{1}{6}$ 袋以上1袋以下という条件を付け加えた。
④　 $2x\leq\frac{4}{6}y$ ……牛乳1カップあたりシリアルは $\frac{1}{6}$ 袋以上
⑤　 $2x\geq4y$ ……牛乳1カップあたりシリアルは1袋以下
と、新たに2つの条件を付け加える。

さらにもう一つ加える条件がある。
A君は牛乳とシリアルを「食べる」のであって、
「吐き出す」ことを考えなくても良いので
$x$ も $y$ も正の数という事を条件に付けておこう。
⑥　 $x\geq0$
⑦　 $y\geq0$

この７つが主目的を解く上での問題条件となる。

[問題の定式化]

最小化	$z$	=	$50x$	+	$65y$
条件	$3x$	+	$2y$	$\geq$	9	①
	$\frac{1}{15}x$	+	$\frac{2}{15}y$	$\geq$	$\frac{1}{3}$	②
	$\frac{1}{6}x$			$\geq$	$\frac{1}{4}$	③
	$2x$			$\leq$	$\frac{4}{6}y$	④
	$2x$			$\geq$	$4y$	⑤
	$x$			$\geq$	0	⑥
			$y$	$\geq$	0	⑦

ふぅ、これだけ書くのは結構大変だったなぁ……。(笑)
さて、これで問題の定式化も終わったな。
あとは①〜⑦の条件式を満たしながら、
どれだけ $z$ の値を小さくできるかなんだけど
とりあえず、①〜⑦の条件を $x$ $y$ 平面上に表したのが上の図です。
青い領域が、７つの条件を全て満たす領域ってことだね。

[zの最小化]
さて、ここで条件をすべて満たしながら
最小になる $z$ を探さなきゃいけないんだけど
$z=50x+65y$ と青い領域の中に、共有点のあるところが
条件を満たしていることになる。
そこで、共有点のあるギリギリのところまで
$z$ の値を少しずつ下げてみる。(上図参照)
すると、 $z$ =197.5より小さくすると
ちょうど $z=50x+65y$ と青い領域に、共有点がなくなるよね？
そう、この $x=2$ と $y=1.5$ という時が
全ての条件を満たす一番安い朝食費ということになり
その値段は、 $z$ =197.5円ということになる。

これが実際の例における最適解の導出例なんだけど
問題の規模が大きくなるにつれて、かなりのおいしい話になったりする。
今の例は、たかだが数百円単位の話だけど
これが数千万とか数億単位になると、
最適解を出すだけで、今までやっていた時よりも
何百万とか何千万とかの経費削減ができたりするんだから
経営者には必須の学問だと思うよ。

タンパク質	ビタミンＤ	カルシウム
9グラム	$\frac{1}{3}$ RDA	$\frac{1}{4}$ RDA

	タンパク質	ビタミンＤ	カルシウム	値段
牛乳 $\frac{1}{2}$ カップ	3グラム	$\frac{1}{15}$ RDA	$\frac{1}{6}$ RDA	50円
シリアル $\frac{1}{4}$ 袋	2グラム	$\frac{2}{15}$ RDA	なし	65円