線形計画法の目的関数の最大値の出し方

【制約条件式】
4x+2y≦160
3x+4y≦170
x≧0,y≧0

【目的関数】
Z=20x+15y

この目的関数の最大値は900なのですが、
その出し方がわかりません。

途中式を省かず、
上記以外の数字が出た場合は、それがどこから出たのか、なんであるのかという解説までお願いします。

No.3 ベストアンサー 回答者： genshisyounen 回答日時： 2012/12/22 19:41

4x+2y≦160・・・(1)

3x+4y≦170・・・(2)
x≧0・・・(3)
y≧0・・・(4)

(1)式、(2)式から、xだけの式、yだけの式を導くことを考える。

(1)×2ー(2)
(4x+2y)*2-(3x+4y)≦160*2-170
5x≦150
x≦30
(3)と併せると、0≦x≦30

(2)×4ー(1)×3
(3x+4y)*4-(4x+2y)*3≦170*4-160*3
10y≦200
y≦20
(4)と併せると、0≦y≦20

0≦x≦30、0≦y≦20の条件で、目的関数Z=20x+15yが最大になるのはx=30,y=20の時だから、
Z=20*30+15*20=900

考え方は、他の人のやり方が基本にはなると思いますが。

No.8 回答者： kamiyasiro 回答日時： 2012/12/23 11:17

回答者の皆さんは、zをx，y平面内に書きたがりますが、

そうではないので、
実務に応用できるように覚えておいて下さい。
zは、x，y平面に対して垂直方向にあるのです。

製品を設計することを考えてみましょう。
xという部品とyという部品を組み合わせますが、
これらの値が取りうる範囲をx，y平面で表しています。
これを設計空間といいます。
それらには、

4x+2y≦160
3x+4y≦170
x≧0,y≧0

という制約が掛っています。これを設計制約といいます。

一般的には、設計空間は、もっと変数が多く、
n次元ハイパーキュービック（超立方体）になっています。
超立方体の一部が切り取られるのが、設計制約です。
このときの最適化を「制約付き最適化」と言います。

目的関数zとは、設計した結果の製品特性値です。
本来は、「zは、x，y平面に対し、垂直」です。←ここが重要。
この目的関数を、設計の分野では応答曲面関数といい、
設計最適化の業務で重要な役割を果たします。

今、zは1次式ですから、平面方程式になっています。
ですから、x，y平面で設計値が取りうる四角形の各頂点のどれかが
zの最高点を与えるはずです。（内部には解が無い）
今回の回答は、4頂点を代入して求めればいいのです。
（ご質問の答え：4頂点（x，y）とzの値、
（0，0）：z＝0
（42.5，0）：z＝850
（0，40）：z＝600
（30，20）：z＝900

この性質は、解探索上重要な性質で、
解探索は、設計空間のハイパーキュービックの頂点から出発すれば、
効率的だということになります。
（たとえ、2次関数でも、1次関係が強ければ今回と同じ）
さらには、今回、解を与えた（30，20）が四角形として引っこんでいない
ということが、解を持つ重要な性質で、これを「凸性」と言います。

ところで、一般の製品設計では、
z、すなわち応答曲面関数は、1次関数になることは稀で、
通常は設計空間内のどこかで、最高パフォーマンスを出すはずで、
2次の関数で近似します。
このケースでは、設計空間の頂点から出発して、
・勾配法
・ダウンヒル・シンプレックス法
・遺伝的アルゴリズム
などの方法で解を探索します。

この回答へのお礼

お礼が遅くなってすみません。
回答ありがとうございました。

お礼日時：2012/12/27 18:12

No.7 回答者： genshisyounen 回答日時： 2012/12/23 06:48

No.６でグラフを添付しましたが、技術がないため、ほとんど判別できないものになってしまい、申し訳ありませんでした。

参考URLに同様のグラフ（「１．１ 図による解法」のグラフ）が有りましたので、これを参考にしてください。

4x+2y≦160・・・(1)
3x+4y≦170・・・(2)
x≧0・・・(3)
y≧0・・・(4)
この４つの式で表される範囲は、参考URLのグラフの斜線部に相当します。
赤線が目的関数です。
グラフの（2.3）の点が、問題の(30,20)に相当します。

参考URL：http://www.sist.ac.jp/~suganuma/kougi/other_lect …

No.6 回答者： genshisyounen 回答日時： 2012/12/23 00:00

この変形ぐらいはわかってほしいですが・・・・・・。

4x+2y≦160・・・(1)の変形の仕方。
4xを右辺に移す。
2y≦-4x+160
両辺を2で割る。
y≦-2x+80
3x+4y≦170・・・(2)の変形の仕方。
3xを右辺に移す。
4y≦-3x+170
両辺を4で割る。
y≦-(3/4)x+170/4

グラフも書いてみました。
真ん中の太線のグラフが目的関数です。

この回答へのお礼

何度も回答ありがとうございます。
図まで描いていただいて恐縮です。
何度も読み返し、思案した結果、やっと理解できました！
本当にありがとうございました！

お礼日時：2012/12/23 18:13

No.5 回答者： genshisyounen 回答日時： 2012/12/22 21:19

No.4の12行目に誤りがありました。

>目的関数Z=20x+15yを変型すると、y=-(4/3)x+D/15であり、・・・
↓
目的関数Z=20x+15yを変形すると、y=-(4/3)x+Z/15であり、・・・

No.4 回答者： genshisyounen 回答日時： 2012/12/22 21:07

補足します。

4x+2y≦160・・・(1)
3x+4y≦170・・・(2)
を変形すると、
y≦-2x+80・・・(1)’
y≦-(3/4)x+170/4・・・(2)'
であり、この２つの直線は第１象限で交差し、その交点が（30,20）になることがわかります。
（実際に図に書いて、考えてみてください。）
x≦30、y≦20は、(1)式、(2)式を同時に満たすx、yの範囲ですが、
気を付けなければいけないのは、（30,20）より右側（30<x≦40）ではy≦-2x+80の式でも可、（30,20）よりも左側（20<y≦170/4）では、y≦-(3/4)x+170/4の式でも可です。

目的関数Z=20x+15yを変型すると、y=-(4/3)x+D/15であり、傾きが-(4/3)で、(1)式よりも緩く、(2)式よりも急なので、（30,20）が目的関数の値が最大となります。
（目的関数の傾きによっては、こうはなりません。例えば、目的関数の傾きが(1)式よりも急な場合は、（0,40）が最大になります。）

この回答へのお礼

補足ありがとうございます。
最初の解説ではわかったのですが、補足を読むとなんだかわからなくなってしまいました。

変形するとなぜ
y≦-2x+80・・・(1)’
y≦-(3/4)x+170/4・・・(2)'
になるのでしょう？

変形の順序がわかりませんでした。

すみません。
正直、図の書き方も、読み方もわかりません…。

お礼日時：2012/12/22 22:18

No.2 回答者： naniwacchi 回答日時： 2012/12/22 19:22

こんばんわ。

点(x, y)の座標に対して 20x+ 15yの値は、
直線：20x+ 15y＝ zすなわち直線：y＝ -4/3*x+ z/15の
y切片である z/15を15倍したものとして与えられます。

点(x, y)は制約条件式として与えられた領域内を自由に移動できます。
その点から、傾き：-4/3の直線を引いたときの y切片を考えればよいわけです。

直線を平行移動させて、
y切片の値がもっとも大きくなるときを考えればよいことになります。

参考URL：http://oshiete.goo.ne.jp/qa/6222584.html

この回答へのお礼

お礼が遅くなってすみません。
回答ありがとうございました。

お礼日時：2012/12/27 18:11

No.1 回答者： spring135 回答日時： 2012/12/22 19:13

【制約条件式】

4x+2y≦160
3x+4y≦170
x≧0,y≧0
が示す範囲をxy平面上に描いてみてください。多角形となるでしょう。

その上にZ=20x+15yなる直線を描いてみて制約条件式を満たす点のうちｚが最大になる点を探せばよろしい。

こんな問題は多角形の頂点になることが自明です。

Z=20x+15yは傾きが一定だから直線を平行移動すればよいということが理解できるかどうかがポイントです。

この回答へのお礼

お礼が遅くなってすみません。
回答ありがとうございました。

お礼日時：2012/12/27 18:11