非線形計画問題

質問

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*がどのような意味をもつか簡潔に述べよ。」
ところはわかりませんでした。

そこがわかる方がいらっしゃいましたら、ぜひご教授お願いします！

回答No.2

ur2c · ベストアンサー

> 簡単に説明していただけませんでしょうか。

最初の段落が簡単な説明です。

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
があります。

> 全部読んだんですけど、初心者なのでよくわかりませんでした。

具体的に「ここがわからん」と言ったほうが得です。「全部わかりませんでした」の言い訳が「専門外なので」や「初心者なので」だと、答えるだけむだか、と思ってしまいます。

お礼

ありがとうございます。

ご指摘のキーワードで検索していろいろと勉強させていただきました。

あとひとつだけ聞かせていただいてもいいですか。

制約条件式(x1+x2>=5)の右辺の値がσだけ増加したときの
目的関数の変化量を求めるところなんですが、

x1+x2>=5＋σ
2x1+x2>=7

でx1,x2を求めて、新たなx1,x2を目的関数に代入して目的関数の変化量を求めました。

結果は5σ^2-10σだったのですけど、これって合っているかどうか教えていただいてよろしいですか。

回答No.3

ur2c

> 結果は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 の係数符号は正のはずです。

回答No.1

ur2c

shadow price なんだ、とわかってもらいたいのでしょうね。

参考URL：

http://en.wikipedia.org/wiki/Shadow_price

お礼

ご回答ありがとうございます。

shadow priceてすか。
全部読んだんですけど、初心者なのでよくわかりませんでした。
簡単に説明していただけませんでしょうか。