• ベストアンサー

線形計画法について

線形計画問題で、 制約条件: x1+4x2+x3≦2 x2+x2+2x3≦3 x1,x2,x3≧0 目的関数: max(5x1+8x2+6x3) という問題がでたのですが、 ご覧の通り3変数の問題なのですが図式解法を用いて解けという指定なのです。 2変数ならすんなりできたのですが、3変数となると上手くいきません。 どなたかわかる方いたら是非ご教授願います。

質問者が選んだベストアンサー

  • ベストアンサー
回答No.1

3次元の図を描けばいいのでしょうが、かなり描きにくいと思います。 それで、2次元の図を描いてみるといいと思います。 次の2通りの方法があります。 (1) x3 = 0 , 0.1 , 0.2 , 0.3 , … の場合について、    x1x2平面上で図を描く (2) 制約条件の構造からすると x1>0,x2>0,x3>0 の部分に端点はないので、    x1 = 0 として x2x3平面上で図を描き、    x2 = 0 として x1x3平面上で図を描き、    x3 = 0 として x1x2平面上で図を描く これでやってみてわからなければ、またお尋ね下さい。

SpawnCS
質問者

お礼

有難うございます。 (2)がイメージしやすいのでそちらでやってみようと思います。

関連する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を求めます。

  • 非線形計画問題

    min f(x1,x2)=(x1-1)^2+x2^2 subject to x1+x2>=5 2x1+x2>=7 (計画変数x1,x2は非負) (1)KKT条件を示し、最適解x1*,x2*を求め、目的関数の最小値を示せ。 (2)最適解x1*,x2*が存在する鞍点において、制約条件式(x1+x2>=5)の右辺の値がσだけ増加したときの 目的関数の変化量を求めよ。また、このような変化量に対して、λ1*,λ2*がどのような意味をもつか簡潔に述べよ。 という問題です」。 (1)はノーマルな解法で解いたら, x1*=2,x2*=3,目的関数の最小値は10でした。 (2)については変化量を求めたら、5σ^2-10σでした。 ですが、「このような変化量に対して、λ1*,λ2*がどのような意味をもつか簡潔に述べよ。」 ところはわかりませんでした。 そこがわかる方がいらっしゃいましたら、ぜひご教授お願いします!

  • 線形計画問題

    最近線形計画法について独学で勉強を始めたのですが いくつかの書籍を調べてもどうしても分からない点が あったのでこの場を利用させて頂きます。 頭を悩めていますのは制約条件が特殊なためです。 問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が 分母にきているのです。目的関数で分母に変数を 持つものは分数計画問題といるのを拝見した事が あるのですが上記のような例は探し方が悪いのか 見つける事ができていません。 実行可能領域は非有界ですが最小化問題のため 上記の例であると2変数なのでグラフにプロットする 事でおよそですが解は見つかりました。 しかし実際の問題は10変数以上の問題となっています ので解が求められません。 その後も実行可能領域を多面体で近似すれば良いのか 等の考察を繰り返しましたが問題が複雑になりお手上げ の状態です。 ちゃんとした解法があるのならお教え頂けるか書籍の 案内をして頂きたいです。宜しくお願いします。

  • 線形計画法の解について!

    線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。 問題は、以下のとおりです。 (線形計画法とシャドウ価格) 次の線形計画法の解、各制約のシャドウ価格を求めなさい。 制約条件 2x+y≦7, x+3y≦6, x≧0,y≧0 のもとで、目的関数 Z=x+y を最大化せよ。

  • 非線形計画法について

    非線形計画法を現在勉強しています。 1. どういうときに線形でどういうときに非線形となるのか良く分かりません。 例えば、ある従属変数yを線形関数f=Σcx で表したいときにパラメータcの絶対値の和が定数bより小さくなるという制約のもとで、yとfの二乗誤差を最小化するパラメータcを求める問題を考えます。 この場合、制約条件はcについて線形ですが、最小化したいのは、yとfの二乗誤差なのでこの場合は非線形ということになるのでしょうか?それとも関数fはcに関して線形関数なので、線形計画法で解くことになるのでしょうか? 2. 以下のサイトで勉強しているのですが、このサイトにある楕円型の等高線はおそらく、従属変数yと目的関数fの誤差を表しているのだと思うのですが、なぜ「楕円」になるのですか?二乗誤差を考えるのならば、「円」になるのではと疑問で仕方ありません。 http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/nonlinear/nonlinear.htm#2.2 疑問が晴れずにもやもやしています。 回答もしくはアドバイス、よろしくお願いします。

  • 変数数40万の0-1変数線形計画問題を解きたい

    0-1変数線形計画問題を解きたいです。目的関数および制約条件は1次関数(線形)です。 ただし、変数数が40万ほどあるのですが、 こういった問題を解くことはできますか? 出来たらMATLABのライセンスがあるのでMATLABで解きたいです。(Global Optimazation ToolBoxおよびOptimazation ToolBoxのライセンスあり。) もしくは、gruobiやNuoptのようなソフトを使えば解けるものでしょうか? ご知見ございましたら、よろしくお願いいたします。

  • 非線形計画法 主-双対問題

    次のような制約付き最小化問題を考えています。 目的関数は非線形です。 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が負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり2番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。

  • 線形問題

    線形計画問題で質問です。 max 3x[1]+2x[2]+2y 制約条件 x[1]+x[2]+2y≦6 2x[1]+x[2]+y≦10 x[2]+y≦3 x[1],x[2],y≧0 これの最適解と最適値を求めたいのですが どう計算していけばいいのか困っています。 まずは制約領域を書こうとしたのですが、変数が3つで、3次元になり それをどう使うのか、それとも変数を減らすことがいいのかと

  • 線形計画問題

    最大化 z = x_1 + 2x_2 + 3x_3 制約条件  x_1 + x_2+ 2x_3 ≦ 12 3x_1 + 2x_2+ x_3 ≦ 12 x_1,x_2,x_3 ≧ 0 という線形計画問題の最適解とその求め方をお教えいただけますでしょうか? (変数が2つなら、高校数学の範囲でわかるのですが・・・)

  • 経営科学の線形計画法、教えてください

    線形計画法のシンプレックス法で、問題を解くために不等式であらわされた制約条件式を、わざわざ余裕変数を用いて等式条件にするのはどうしてですか?