線形計画法の説き方 初級シスアド 平成16年度 午前問73改変

線形計画法の説き方についてです。
ある工場で製品A,Bを生産している。製品Aを1ｔ製造するのに、原料P,Qをそれぞれ4ｔ、9ｔ必要とし、製品Bについてもそれぞれ8ｔ、6ｔ必要とする。また、製品A,Bは1tあたりそれぞれ2万円、3万円の利益を生む。しかし、原料Pは40ｔ、Qは54ｔしかない。利益を最大にするにはどうしたらよいか。
制約条件　4x＋8y≦40→y≦-1/2x＋5
　　　　　9x＋6y≦54→y≦-3/2x＋9
　　　　　x≧0,y≧0
目的関数　2x+3y　　　　　　　　　答えxが3　yが4
ここまでは分かります。その下にグラフがあり、頂点のいずれかで利益が最大になります。となっていて、4つの頂点で目的関数に値を入れて答えを出しているのですが、このグラフはどうやって書くのですか。また、その答えが4つの頂点の中の、x、y軸に接していない頂点のxもしくはyの値の出し方も分かりません。
更に、制約条件の式を普通に解いても答えと同じx、yが出たのですが、これはたまたまでしょうか。
ちなみに数学が苦手なほうです。よろしくお願いします。

No.1 回答者： ktktkota 回答日時： 2006/11/24 14:43

バイトで数学の先生をしており、情報処理の資格をいくつか持っている者です。

目的関数の最大値を a とすると、2x+3y=a と書けますが、グラフを書くため、y=の形にすると、y=-2/3x+a/3です。
目的関数の傾きが -1/2x＋5 と -3/2x＋9 の中間、言い換えると、目的関数の傾き -0.67は -0.5と-1.5の中間なので、グラフを書いてみると、目的関数は２つの制約条件の式の間に線が書ける形になりますよね。だから、制約条件の式の交点が目的関数の最大値になるんですね。

aがもっとも大きくなるようにするには、目的関数 y=-2/3x+a/3 が y軸と交わる値、つまり a/3 をもっとも大きくするには、目的関数が制約条件の交点を通過しているときということです。

目的関数の傾きが２つの制約条件の傾きの間にない場合、片方の制約条件に依存することになり、問題としてつまらないので、目的関数の傾きは中間になるようにして、交点を通過したときに最大になるように、問題を作ってあるのだと思います。情報処理の線形計画法の試験では交点の場合しか出題されないと思いますよ。

グラフ書くとすぐわかるかと思うんですが、文章だとわかりにくいですね。。。

この回答へのお礼

首を長くして待っていたので、本当にありがたかったです。
が・・・ごめんなさい。ちょっと難しくて。
自分なりに質問した後もいろいろと調べて、解けるかも!?ぐらいにはなりました。ありがとうございました。

お礼日時：2006/11/27 12:48