非線形計画問題に関する質問

質問

非線形計画問題に関する質問
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かなとは思いますが、乗数の意味がわかりません。

回答No.1

stomachman

λは未定乗数でしょう。カルッシュ・クーン・タッカーの方法を用いたのだと思います。機械的にやれば
　　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)ということも生じます。線形計画法では解は必ず制約条件の境界線上にある訳ですが、非線形計画法の場合にはそうとは限らないわけです。