非線形計画問題

Question

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

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

ur2c · Accepted Answer

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

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

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://oshiete.goo.ne.jp/qa/5522445.html
があります。

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

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

ur2c · Answer

> 結果は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 · Answer

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

参考URL：http://en.wikipedia.org/wiki/Shadow_price

非線形計画問題

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

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

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

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング