非線形計画問題の解法と変化量に対するλ1*,λ2*の意味について
- 非線形計画問題の最適解を求めるためにはKKT条件を用いることができます。KKT条件を満たす最適解x1*,x2*はx1*=2,x2*=3となり、目的関数の最小値は10です。
- 鞍点において、制約条件式(x1+x2>=5)の右辺の値がσだけ増加した場合、目的関数の変化量は5σ^2-10σとなります。λ1*,λ2*はこの変化量に対して制約条件式の感度を示す係数であり、具体的な意味は問題文からはわかりません。
- ベストアンサー
非線形計画問題
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*がどのような意味をもつか簡潔に述べよ。」 ところはわかりませんでした。 そこがわかる方がいらっしゃいましたら、ぜひご教授お願いします！
- nanakoxzb
- お礼率84% (90/107)
- 数学・算数
- 回答数3
- ありがとう数2
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
> 簡単に説明していただけませんでしょうか。 最初の段落が簡単な説明です。 the shadow price is the instantaneous change, per unit of the constraint, in the objective value of the optimal solution of an optimization problem obtained by relaxing the constraint. もし英語がだめなら、「シャドープライス」とか「潜在価格」とかで引けば日本語の説明もあります。（まとはずれなのも出て来ますので注意） また、関連する質問に「なぜ、双対問題（双対性）を考えるのですか？」 http://okwave.jp/qa/q5522445.html があります。 > 全部読んだんですけど、初心者なのでよくわかりませんでした。 具体的に「ここがわからん」と言ったほうが得です。「全部わかりませんでした」の言い訳が「専門外なので」や「初心者なので」だと、答えるだけむだか、と思ってしまいます。
その他の回答 (2)
- ur2c
- ベストアンサー率63% (264/416)
> 結果は5σ^2-10σだったのですけど、これって合っているかどうか教えて ちゃんと計算はしてませんけど、ちがってるように見えます。 書きやすいように (x, y, s) := (x1, x2, σ) とします。 最小化問題なので、目的関数 f を支出と思うことにします。すると 5 =< x + y は「合計で最低 5 単位は税金みたいな義務として払え」という制約です。5 - (x + y) が未納。 5 を 5 + s になおして 0 < s なら「もっと払え」です。それは x,y を選択して節約する余地が減り、支出 f が増える方向に働きます。（最適点でこの制約が効いてなければ支出は不変ですけど、問題 (2) の題意から、効いてるはずです。）ところが「結果」の 5 s^2 - 10 s は「税が s だけ増えると、その 10 倍ほど支出が減る」と言ってます。 潜在価格の意味から、その最適点における値を 0 =< k として、変化量は k s + O(s^2) の形になるはずです。ただ、Lagrange 関数は g = 0 を制約として f + k g と書いてもいいし f - k g と書いてもいいので、符号には気をつけないと。具体化して意味を考えるとき、混乱します。（私も混乱してるかも。） 結局、「結果」の s の係数符号は正のはずです。
- ur2c
- ベストアンサー率63% (264/416)
shadow price なんだ、とわかってもらいたいのでしょうね。
お礼
ご回答ありがとうございます。 shadow priceてすか。 全部読んだんですけど、初心者なのでよくわかりませんでした。 簡単に説明していただけませんでしょうか。
関連するQ&A
- 非線形計画問題に関する質問
非線形計画問題に関する質問 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かなとは思いますが、乗数の意味がわかりません。
- 締切済み
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 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が負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
- 締切済み
- 数学・算数
- 非線形の最適化問題の質問です。
「制約条件：2x+y≦3、x+y≦2、x,y≧0のとき、alogx + (1-a)logy を最大化する解(x,y)を求めよ」という最適化問題の解が(x,y) = (1,1)となるようなaの範囲を求めよ。 という問題なのですが、これは目的関数に(-1)をかけて最小化問題とし、キューン・タッカー条件を用いて解けばよいのでしょうか？ キューン・タッカー条件を用いて解いてみると、a = 2λ1 + λ2 かつ 1-a = λ1 + λ2 で、λ1、λ2≧0より0≦a≦1という範囲があっけなく出てきたのですが…本当にこれで合っているのか不安です。 図形的に考えてみようとも思いましたが、目的関数が複雑すぎて断念しました。 どなたかこの問題の正しい解法を教えて頂けないでしょうか？ どうぞよろしくお願いします。
- ベストアンサー
- 数学・算数
- 【至急】線形計画問題について、ヒントをください！
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 としていいのかが分かりません。 ≦ や ≧ ではなく、= が制約関数に含まれていると、標準形ではどの様に変形すれば宜しいのでしょうか？ どなたか教えてください。また、理由もお聞かせ頂けると幸いです。
- 締切済み
- 数学・算数
- 線形計画問題
最近線形計画法について独学で勉強を始めたのですが いくつかの書籍を調べてもどうしても分からない点が あったのでこの場を利用させて頂きます。 頭を悩めていますのは制約条件が特殊なためです。 問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が 分母にきているのです。目的関数で分母に変数を 持つものは分数計画問題といるのを拝見した事が あるのですが上記のような例は探し方が悪いのか 見つける事ができていません。 実行可能領域は非有界ですが最小化問題のため 上記の例であると2変数なのでグラフにプロットする 事でおよそですが解は見つかりました。 しかし実際の問題は10変数以上の問題となっています ので解が求められません。 その後も実行可能領域を多面体で近似すれば良いのか 等の考察を繰り返しましたが問題が複雑になりお手上げ の状態です。 ちゃんとした解法があるのならお教え頂けるか書籍の 案内をして頂きたいです。宜しくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画問題について教えてください。
この線形計画問題で、条件を１）と２）で変えたときに 最適解がどう違うのでしょうか？教えてください。 最大化：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式は必要だと思います。 問題のミスでしょうか？ どなたか教えてください。
- ベストアンサー
- 数学・算数
- ＫＫＴ条件について教えてください。
ＫＫＴ条件はどのようなものかわかるのですが、具体的な数値例がわかりません。 以下の2次計画問題のＫＫＴ条件を教えて下さい。 最小化：x1^2+x2^2 (x1の2乗＋x2の2乗) 条件：x1+2x2=1 ,x1≧0,x2≧0
- ベストアンサー
- 数学・算数
- 線形計画法の解法について！
線形計画法の解き方が判らなくて困っています。 判らないこと 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を求めます。
- ベストアンサー
- 数学・算数
お礼
ありがとうございます。 ご指摘のキーワードで検索していろいろと勉強させていただきました。 あとひとつだけ聞かせていただいてもいいですか。 制約条件式(x1+x2>=5)の右辺の値がσだけ増加したときの 目的関数の変化量を求めるところなんですが、 x1+x2>=5＋σ 2x1+x2>=7 でx1,x2を求めて、新たなx1,x2を目的関数に代入して目的関数の変化量を求めました。 結果は5σ^2-10σだったのですけど、これって合っているかどうか教えていただいてよろしいですか。