- ベストアンサー
線形計画法の目的関数の最大値の出し方
- みんなの回答 （8）
- 専門家の回答
質問者が選んだベストアンサー
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 考え方は、他の人のやり方が基本にはなると思いますが。
その他の回答 (7)
- kamiyasiro
- ベストアンサー率54% (222/411)
回答者の皆さんは、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次の関数で近似します。 このケースでは、設計空間の頂点から出発して、 ・勾配法 ・ダウンヒル・シンプレックス法 ・遺伝的アルゴリズム などの方法で解を探索します。
- genshisyounen
- ベストアンサー率73% (38/52)
No.６でグラフを添付しましたが、技術がないため、ほとんど判別できないものになってしまい、申し訳ありませんでした。 参考URLに同様のグラフ（「１．１ 図による解法」のグラフ）が有りましたので、これを参考にしてください。 4x+2y≦160・・・(1) 3x+4y≦170・・・(2) x≧0・・・(3) y≧0・・・(4) この４つの式で表される範囲は、参考URLのグラフの斜線部に相当します。 赤線が目的関数です。 グラフの（2.3）の点が、問題の(30,20)に相当します。
- genshisyounen
- ベストアンサー率73% (38/52)
この変形ぐらいはわかってほしいですが・・・・・・。 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 グラフも書いてみました。 真ん中の太線のグラフが目的関数です。
お礼
何度も回答ありがとうございます。 図まで描いていただいて恐縮です。 何度も読み返し、思案した結果、やっと理解できました！ 本当にありがとうございました！
- genshisyounen
- ベストアンサー率73% (38/52)
No.4の12行目に誤りがありました。 >目的関数Z=20x+15yを変型すると、y=-(4/3)x+D/15であり、・・・ ↓ 目的関数Z=20x+15yを変形すると、y=-(4/3)x+Z/15であり、・・・
- genshisyounen
- ベストアンサー率73% (38/52)
補足します。 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)' になるのでしょう？ 変形の順序がわかりませんでした。 すみません。 正直、図の書き方も、読み方もわかりません…。
- naniwacchi
- ベストアンサー率47% (942/1970)
こんばんわ。 点(x, y)の座標に対して 20x+ 15yの値は、 直線：20x+ 15y＝ zすなわち直線：y＝ -4/3*x+ z/15の y切片である z/15を15倍したものとして与えられます。 点(x, y)は制約条件式として与えられた領域内を自由に移動できます。 その点から、傾き：-4/3の直線を引いたときの y切片を考えればよいわけです。 直線を平行移動させて、 y切片の値がもっとも大きくなるときを考えればよいことになります。
お礼
お礼が遅くなってすみません。 回答ありがとうございました。
- spring135
- ベストアンサー率44% (1487/3332)
【制約条件式】 4x+2y≦160 3x+4y≦170 x≧0,y≧0 が示す範囲をxy平面上に描いてみてください。多角形となるでしょう。 その上にZ=20x+15yなる直線を描いてみて制約条件式を満たす点のうちｚが最大になる点を探せばよろしい。 こんな問題は多角形の頂点になることが自明です。 Z=20x+15yは傾きが一定だから直線を平行移動すればよいということが理解できるかどうかがポイントです。
お礼
お礼が遅くなってすみません。 回答ありがとうございました。
関連するQ&A
- 線形計画法の解法について！
線形計画法の解き方が判らなくて困っています。 判らないこと 1.制約条件の式と計算値 2.目的関数の式と目的値 線形計画法は変数と制約条件と目的関数が与えられます。 制約条件を満足し、目的関数が最大（最小）となる変数を求めます。 線形計画法の例 変数 x y 制約条件 (A) 10x + 4y ≦ 360 (B) 4x + 5y ≦ 200 (C) 2x + 10y ≦ 300 (D) x ≧ 0 (E) y ≧ 0 目的関数 M = 7x+12y A,B,C,D,Eの条件を満足し目的関数(M)が最大となる変数x,yを求めます。
- ベストアンサー
- 数学・算数
- 線形計画法の解について！
線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。 問題は、以下のとおりです。 （線形計画法とシャドウ価格） 次の線形計画法の解、各制約のシャドウ価格を求めなさい。 制約条件 2x＋y≦7, x＋3y≦6, x≧0,y≧0 のもとで、目的関数 Z＝x＋y を最大化せよ。
- ベストアンサー
- 数学・算数
- 線形計画法の説き方 初級シスアド 平成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が出たのですが、これはたまたまでしょうか。 ちなみに数学が苦手なほうです。よろしくお願いします。
- 締切済み
- 情報処理技術者
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 min x1^2+x2^2 s.t. -x1-x2+4<=0 x1>=0 x2>=0 この問題の場合最適解は(x1,x2)=(2,2)であり、その時の目的関数値は8となります。 次に次式のような双対問題を考えます。 g(x)=-x1-x2+4とおき 双対関数 φ(u)=inf{x1^2+x2^2+u*(-x1-x2+4) : x1>=0 , x2>=0} =inf{x1^2-u*x1 : x1>=0}+inf{x2-2-u*x2 : x2>=0}+4*u 上記においてもしu>=0であれば、x1=x2=(u/2). （なぜなら、x1^2-u*x1をx1で微分するとx1=u/2となる。） u<0であるならばx1=x2-0であることに注目しますと。 φ(u)=-(1/2)*u^2+4*u for u>=0 =4u for u<0 となります． 双対関数がu>0の場合は最大がu=4であることに注目すると、その時の目的関数は8であり、主問題と双対問題の最適な目的関数値は一緒となります。 次に主問題を次のように制約を増やした最小化問題を考えます。 min x1^2+x2^2 s.t. -x1-x2+4<=0 -2*x1-3*x2<=0 x1>=0 x2>=0 これの最適解は上記の問題と同じにならないといけないのですが、 例えば、ラグランジュ関数F(x1,x2,λ1,λ2)を次のようにおき各変数で偏微分して最適解を求めると（λ：ラグランジュ乗数）、 F(x1,x2,λ1,λ2)=x1^2+x2^2+λ1*(-x1-x2+4)+λ2*(-2*x1-3*x2) 最適解はx1=12, x2=-8であり、その時の目的関数は208となり、前問と異なった解が得られました。 この原因は明確であり、ラグランジュ関数の中の各制約式が、偏微分して解を得ることで不等式制約ではなく等式制約とみなされたためです。 偏微分して解を求めなければいいのですが、どうしても偏微分でかいを求めたいために、、前門で示した双対問題を導入しましたが、結果は双対問題のほうでも偏微分するので一緒でした。 しかし、双対問題で得られた解。つまりuは主問題のλに相当し、KKT条件より必ず正である必要があるので、双対問題を解き、uが負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
- 締切済み
- 数学・算数
- ２次関数の最大・最小
問： 次の条件に適するように、定数ａの値を求めよ。 （１）関数y=x^2-4x+a (1<=x<=5)の最大値が６である。 （２）関数y=-x^2+3x+a (-3<=x<=1)の最大値が４である。 （３）関数y=-x^2-4x+aの最大値が、関数y=x^2-4xの最小値と一致する。 答： （１）a=1 （２）a=2 （３）a=-8 解説して下さい！
- ベストアンサー
- 数学・算数
- 線形計画法？の問題が解けません
カロリー タンパク質 製品Ａ 270 kcal 8 g 製品Ｂ 165 kcal 16 g それぞれ１００ｇにつき という成分表が与えられています。 これだけで、１日あたりの栄養を 2500 kcal、 タンパク質を 100 g 確保したい。 総重量を最小にするにはどうしたらよいか。 という問題なのですけどわかりません。 求める重量を製品Ａは x 製品Ｂは y とおいて 目的関数 P = x + y 制約式 270x + 165y >= 2500 8x + 16y >= 100 として、グラフで許容領域を書いて求めようと考えたのですが、できませんでした。 まず、グラフが書けませんでした。 割り切れない数値でごちゃごちゃしてしまいました。 それで、この答え（できれば計算式も）を教えてくれませんか。 お願いします。
- ベストアンサー
- 数学・算数
お礼
お礼が遅くなってすみません。 回答ありがとうございました。