- 締切済み
非線形計画問題に関する質問
非線形計画問題に関する質問 minimize f(x1,x2)=(x1-1)^2+x2^2 subject to x1+x2≧5 (1) 2x1+x2≧7 x1≧0 x2≧0 (1)の右辺の値がδだけ増加した時の目的関数の変化量と、この変化量に 対して乗数λ1,λ2はどのような意味を持つか述べよ という問題です。 最適値は(x1,x2)=(3,2)で乗数は(λ1,λ2)=(4,0) というところまで求めました。 変化量はδ^2/2かなとは思いますが、乗数の意味がわかりません。
- takah715ro
- お礼率0% (0/1)
- 数学・算数
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- stomachman
- ベストアンサー率57% (1014/1775)
λは未定乗数でしょう。カルッシュ・クーン・タッカーの方法を用いたのだと思います。機械的にやれば L= f(x1,x2) + λ1(5-(x1+x2)) + λ2(7-(2x1+x2)) + λ3(-x1) + λ4(-x2) として ∂L/∂x1 = 0, ∂L/∂x2 = 0 λ1(5-(x1+x2)) = 0 λ2(7-(2x1+x2)) = 0 λ3x1 = 0 λ4x2 = 0 x1+x2≧5, 2x1+x2≧7, x1≧0, x2≧0 λ1≧0, λ2≧0, λ3≧0, λ4≧0 を全て満たすようにする訳です。が、手抜きでしょうか、x1≧0, x2≧0に関する未定乗数λ3, λ4はナシにしたのですね。 さて、この問題は他にも解き方があります。というのは、目的関数は(1,0)と(x1,x2)の距離の２乗になっているから、これは「(x1,x2)平面上で、4つの不等式を全て満たす点のうち(1,0)に最も近い点は？」という問題だと解釈できます。 そこで、(1)式の不等号を等号に置き換えたもの (x1+x2=5) を表す直線Lと、2つ目の不等式で決まる (2x1+x2=7) の直線Mをグラフに描いてみて下さい。するとこの場合、解(すなわち(1,0)に最も近い点)が直線L上にあることは一目瞭然かと思います。 ところで、λ1(5-(x1+x2))=0 であってしかも λ1≠0 だ、ということは解が (5-(x1+x2))=0 を満たすということですから、つまりλ1≠0は解が直線L上にあることを示しています。 また、λ2=0だということは、(7-2x1+x2) は必ずしも0ではない。これは解が直線M上にない（か、あってもMとLの交点上である）ってことです。 という訳で、λ1,λ2は「それぞれに対応する制約条件の境界線(L, M)の上に解があるかどうか」を示しているんですね。 ここで(1)式の右辺をδだけ変化させると、直線Lが動きます。もしδが微小であれば、解はやはりL上にあって、その位置がLの動きにつれてちょっとだけ動くわけですが、δが大きくなってくると、λ1=0, λ2≠0ということが生じる。すなわち解がL上ではなく、M上にある、という状態になった訳です。Lをもっと動かすと（あるいは直線Mも動かすと）解がL上にもM上にもない（λ1=0, λ2=0）という状態になって直線x1=0やx2=0の上に行く(λ3やλ4が0でなくなる）かも知れません。検討してみて下さい。 さらに直線x1=0やx2=0も動かしてみれば、解がどの直線上にもない(λ1～λ4がすべて0)ということも生じます。線形計画法では解は必ず制約条件の境界線上にある訳ですが、非線形計画法の場合にはそうとは限らないわけです。
関連するQ&A
- 非線形計画問題
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*がどのような意味をもつか簡潔に述べよ。」 ところはわかりませんでした。 そこがわかる方がいらっしゃいましたら、ぜひご教授お願いします！
- ベストアンサー
- 数学・算数
- 線形計画問題の双対問題について疑問
線形計画問題の双対問題について疑問 主問題 minimize 2x1 + 5x2 sublect to 3x1 + x2 <=3 2x1 + x2 >=5 x1, x2>=0 の双対問題はどうなるのですか？ たとえば、 主問題 minimize 2x1 + 5x2 sublect to 3x1 + x2 >=3 2x1 + x2 >=5 x1, x2>=0 なら、 双対問題 maximaize 3y1 + 5y2 sublect to 3y1 + 2y2 <=2 y1 + y2 <=5 y1, y2>=0 となるということはわかるんですが・・・・ よろしくお願いします。
- 締切済み
- その他（学問・教育）
- 【至急】線形計画問題について、ヒントをください！
maximize 7x1 + 4x2 + 2x3 subject to 3x1 + 3x2 + x3 ≦ 36 .................. 2x1 + x2 + x3 = 18 .................. x1,x2,x3≦0 . この問題の最適解と最適値を求めたいのですが、、まず標準形の線形計画問題に変形する段階で、 2x1 + x2 + x3 = 18 と、 = がでできてしまい、 subject to 3x1 + 3x2 + x3 + x4 = 36 ................... 2x1 + x2 + x3 + x5 = 18 ................... x1,x2,x3,x4,x5≦0 としていいのか、 subject to 3x1 + 3x2 + x3 + x4 = 36 ................... 2x1 + x2 + x3 = 18 ................... x1,x2,x3,x4≦0 としていいのかが分かりません。 ≦ や ≧ ではなく、= が制約関数に含まれていると、標準形ではどの様に変形すれば宜しいのでしょうか？ どなたか教えてください。また、理由もお聞かせ頂けると幸いです。
- 締切済み
- 数学・算数
- 線形計画問題について教えてください。
この線形計画問題で、条件を１）と２）で変えたときに 最適解がどう違うのでしょうか？教えてください。 最大化：X1+2X2-X3+3X4+X5+2X6 条件：2X1+X2+3X3+X4+4X5+3X6≦7 １）0≦Xj≦1,j=1,2,3,4,5,6 ２）Xj∈{0,1},j=1,2,3,4,5,6
- ベストアンサー
- 数学・算数
- 至急お願いします！線形計画問題についてです。
maximize 7x1 + 4x2 + 2x3 subject to 3x1 + 3x2 + x3 ≦ 36 .................. 2x1 + x2 + x3 = 18 .................. x1,x2,x3≦0 この問題を2段階法により解けという問題なのですが、x1,x2,x3と3変数も出てきているのに、制約関数が2式のみって、解くことができないですよね？3変数であれば最低でも3式は必要だと思います。 問題のミスでしょうか？ どなたか教えてください。
- ベストアンサー
- 数学・算数
- 数理計画法の双対問題の解法について
私は現在、以下のような問題に取り組んでおります。 問題：次の線形計画問題の双対問題を解け。 minimize: z = 2x1+3x2+8x3 2x1+2x2+6x3 ≥ 6 x1+2x2+4x3 ≥ 4 x1,x2,x3 ≥ 0 私はこの双対問題のシンプレックス表を用いて解く方法が分かりません。 どなたか解答・解説をお願いします。
- 締切済み
- 数学・算数
- 線形計画法の問題です
線形計画法の問題です 問題 ・原料PとQから3種類の製品A、B、Cを生産している。 ・製品Aを生産するのに、原料Pを1トン、原料Qを2トン必要 ・製品Bを生産するのに、原料Pを1トン、原料Qを3トン必要 ・製品Cを生産するのに、原料Pを2トン、原料Qを4トン必要 ・原料Pの使用可能量は10トン、原料Qの使用可能量は28トン ・製品A、B、Cの1トン当たりの利益は、30万円、20万円、４０万円 ・市場調査の結果、製品Aの需要量は、製品Bの需要量を2トンより多く上回ることはない 問1．利益を最大化する問題を線形計画問題として定式化せよ 問2．最大利益とその時の各製品の生産量 問3．原料Pの最大使用可能量が1トン減った場合、最大利益がどのように変化するか 問4．原料Qの最大使用可能量が1トン減った場合、最大利益がどのように変化するか 答１．目的関数 30x1+20x2+40x3 → MAX 制約条件 x1+x2+2x3<=10 2x1+3x2+4x3<=28 答2．最大利益 300万円 製品A 10トン 製品B 0トン 製品C 0トン 答3．最大利益は-30万円 答４．最大利益は変化しない となってしまいます。 たぶん、『・市場調査の結果・・・』を制約式に入れていないため、変な答えになっていると思います。 どなたか、模範解答を教えてください。
- ベストアンサー
- 数学・算数
- 【至急!!】線形計画問題教えてください。
次の問題を双対シンプレックス法により解け。 minimize 15x1+7x2+12x3 sub to x1x+2x+x3≧1 3x1+x2+x3≧2 x1,x2,x3≧0 双対シンプレックス法での解き方がいまいち分かりません。 双対シンプレックス法での解き方が分かる方教えてください(>_<)
- ベストアンサー
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 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が負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
- 締切済み
- 数学・算数
