• 締切済み

数理計画

今、自分でモデルを作り数理計画法を用いて解くということをしています。自分の作ったモデルが min ax1+bx2 s.t. x1+x2<c or x1+x2=0 上のように制約条件の中に「or(もしくは)」が入るものになってしまった(実際に作ったものはもっと複雑ですが簡単にすると上のような感じです)のですがこういったものは線形計画と呼べるのでしょうか?また解くことは可能でしょうか?

みんなの回答

  • pori_boy
  • ベストアンサー率60% (18/30)
回答No.2

こんにちは このような問題は線形計画と呼べません。 解くことが可能かというと、No.1さんのようにすれば (この例だと)2つの問題を解けばOKです。 ただし、注意すべき点として、orが複数入ると とかなければならない問題の数が指数的に増えます。 ので、もっと複雑なものというのが解けるかどうかは 問題の構造によるという答えになると思います。 例えば、難しい問題として有名な0-1整数計画問題は x1=0 or x1=1, x2=0 or x2=1, ... xk=0 or xk=1 という制約が入ってくると思いますが、この場合 2^k個の問題を解いて、その中で一番良いものを 採用する、という必要がでてきますね。

回答No.1

制約条件のどちらかを満たせばいいので >min ax1+bx2 >s.t. x1+x2<c or x1+x2=0 を min ax1+bx2 s.t. x1+x2<c と min ax1+bx2 s.t. x1+x2=0 の2つの数理計画問題にして、それぞれの解のうち ax1+bx2 の小さい方を取ればいいので、線形計画問題に出来ます。問題が複雑になっても同様です。

関連するQ&A

  • 線形代数 線形写像 質問

    線形写像の定義は、 f(ax1+bx2)=af(x1)+bf(x2)を満たすです。 (1)f(x)=2x+1が線形写像でないことを示せ。 f(ax1+bx2)=af(x1)+bf(x2)より、 f(ax1+bx2)=2(x1+x2)+1=2(x1)+2(x2)+1 af(x1)+bf(x2)=(2(x1)+1)+(2(x2)+1) よって、f(ax1+bx2)≠af(x1)+bf(x2) とありました。 正しいでしょうか? f(ax1+bx2)=af(x1)+bf(x2)より、 f(ax1+bx2)=2(ax1+bx2)+1=2(ax1)+2(bx2)+1 af(x1)+bf(x2)=(2a(x1)+1)+(2b(x2)+1) よって、f(ax1+bx2)≠af(x1)+bf(x2) では間違いでしょうか? f(x)=2x+1における、2がaやbを表しているのでしょうか? (2)f(x)=2(x+1)が線形写像でないことを示せ。 についてですが、f(x)=2x+2とすれば、示せるのですが、 f(x)=2(x+1)でも(1)の手順で示せるのでしょうか? 以上、ご回答よろしくお願い致します。

  • つぎの数理計画問題を解いてください。

    つぎの数理計画問題を解いてください。 max ax + (1-a)y subject to 2x + y ≦ 3 x + y ≦ 2 x≧0, y≧0 (1) この問題に対するKuhn-Tucker条件を示せ。 (2) (x, y) = (1, 1) が最適解となるaの区間を示せ。 よろしくお願いします。

  • 数理計画法の双対問題の解法について

    私は現在、以下のような問題に取り組んでおります。 問題:次の線形計画問題の双対問題を解け。 minimize: z = 2x1+3x2+8x3 2x1+2x2+6x3 ≥ 6 x1+2x2+4x3 ≥ 4 x1,x2,x3 ≥ 0 私はこの双対問題のシンプレックス表を用いて解く方法が分かりません。 どなたか解答・解説をお願いします。

  • 最適化の問題に詳しい方

    お世話になっております。 Let x0 and x1 be solution of min tcx+c0 s.t. Ax≦a, Bx=b, x≧0 Show that all points on the line with end points x0 and x1 are solutions. (A:m×n matrix, a,b,c∈R^n, B:k×n matrix) 訳せば 「x0とx1を min tcx+c0 s.t. Ax≦a, Bx=b, x≧0 の解とする時、終点をx0とx1とする線上の全ての点が解を示せ」 これはどうやって示せばいいのでしょうか? tは転置行列の意味だと思います。 x_0とx_1がAx≦a,Bx=b,x≧0を満たしていて、tcx0=tcx1ならば点λx0+(1-λ)x1も Ax≦a,Bx=b,x≧0を満たしていて、同じ最適値(?)を持つ事をいいのかと思いますが この手の問題になれてらっしゃる方,お教え下さい。

  • 線形計画法について

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

  • 線形計画問題の標準形

    現在大学で線形計画法を学んでいるのですが,実際に数字を用いて問題を解く事にはなれてきたのですが,証明問題などになるとどの様に回答を行えば良いか回答に繋がるプロセス分かりません. どの様なプロセスで回答をすれば良いかなにかアドバイスがございましたらよろしくお願いします.以下が現在回答に困っている問題ですのでよろしくお願いします. 線形計画法の標準形 目的関数:c^T x →最小 制約条件:Ax =b x≧0 m<nとなる自然数.x ∈ R^n, c ∈ R^n, b ∈ R^mであり,Aはm*n実行列で,rankA = m とし b ≠ 0 とする. 問題1.線形計画問題の制約条件を満たすxのなす集合を実行可能領域Fで表し,Fが空集合でないときFが凸集合であることを示しなさい. Fが凸集合とは x,x' ∈ F ⇒tx + (1 - t)x' ∈ F (∀t ∈ [0,1]) が成立するときをいう. 問題2.Au = b を満たすベクトル u ≠ 0 が存在する事を示せ. 問題3.Ax = 0 を満たすxのなす R^n の線形部分空間はAの核と呼ばれkerAと表す.Ax = bを満たすxのなす R^n の部分集合を J で表すとき J = { x ∈ R^n | x = u + v, v ∈ kerA} となる事を示せ.ただしuは問題2で存在を示したベクトルである.

  • 線形計画

    線形計画の双対問題についてわからないところがあるので教えてください。 http://home.hiroshima-u.ac.jp/~kato/b_mp1/MP1_12_20061219_an...双対問題' の(2)の問題の解答のところなんですけど 最初に標準形に変換するときなんでわざわざX2=X2+ - X2- としているのでしょう? 普通にX3を追加して=にしMAXの符号を変えてMINにすればいいのではないでしょうか? またここではX2を1行目のようにしてますがこれはX1ではいけないのでしょうか? わかりにくい質問かと思いますが教えてください。

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

    線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。 問題は、以下のとおりです。 (線形計画法とシャドウ価格) 次の線形計画法の解、各制約のシャドウ価格を求めなさい。 制約条件 2x+y≦7, x+3y≦6, x≧0,y≧0 のもとで、目的関数 Z=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が負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり2番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。

  • 線形計画問題

    線形計画問題をシンプレックス法で解きたいのですが、よくわかりません。シンプレックス表を作成して解こうとしているのですが、流れがよく分からず解けないのです…。問題をそのまま載せてしまいますが、自分では色々資料を見て考えたつもりです。 分かる方いらっしゃいましたら、どうかよろしくお願いします。 w=x+2y+5z→min s.t. 3x+4y+z≧8 x+2y+4z≧9 x≧0,y≧0,z≧0