（第2回）解答pdf ファイル - 一橋大学商学部・大学院商学研究科

計画数学 I
第２回練習問題解答
2012 年 12 月 26 日，高岡浩一郎∗
【このファイルは７頁分です．
】
問 1 の解説
[答え]
最適解は x∗ =
(
√1 ,
10
− √210 , z
)
, ただし第３成分は |z| ≤
√1
2
ならば何でも良い．
以下に２通りの解法を示す．
解法その１
図形的考察で解く方法．この問題の実現可能領域は，円柱の上面と下面にふくらみを持たせたよ
うな形をした立体である．円柱軸を軸とした回転体になっている．目的関数に x3 が入っていない
ことから，最適解の集合は円柱の側面上に伸びた線分（円柱軸と平行）である．最適解の第１成分
✷
と第２成分を求める方法は，事実上２変数問題である．
解法その２
Kuhn-Tucker 条件を用いる方法．
f (x)
g1 (x)
g2 (x)
:= x1 − 2x2 ,
:= x21 + x22 + x23 ,
:= x21 + x22 ,
b1 := 1,
b2 := 12 ,
と定義すると
Max f (x)
s.t.
gi (x) ≤ bi ,
i = 1, 2
という問題になる．ここで f は線型なので凹，また gi はすべて凸なので，Kuhn-Tucker 条件を
満たす x が（講義の定理 13.3 より）最適解になる．x ∈ R3 が Kuhn-Tucker 条件を満たすとは

∂L
(1.1)

 ∂x1 = 1 − 2 λ1 x1 − 2 λ2 x1 = 0,
∂L
= −2 − 2 λ1 x2 − 2 λ2 x2 = 0,
(1.2)
∂x

 ∂L2
=
−2 λ1 x3
= 0,
(1.3)
∂x3
および

2
2
2

 1 − x1 − x2 − x3 ≥ 0, (2.1.1)
λ1 ≥ 0,
(2.1.2)


少なくとも一方がゼロ (2.1.3)
∗ 一橋大学大学院商学研究科．E-mail:





[email protected]
1
1
2
− x21 − x22 ≥ 0,
λ2 ≥ 0,
少なくとも一方がゼロ
(2.2.1)
(2.2.2)
(2.2.3)
となるような λ ∈ R2 が存在することである．λ1 > 0 の場合，(1.3) より x3 = 0 となり，また
(2.1.1) において等号が成立する．さらに，それら２つの性質から
x21 + x22 = 1
も言えることになる．しかしこれは (2.2.1) と矛盾．ゆえに，λ1 = 0 である．
もし λ2 もゼロだとすると (1.1) と矛盾するので，λ2 > 0. ゆえに，(2.2.1) において等号が成
立することになる．また，(1.1) (1.2) より
x1 =
1
> 0,
2λ2
x2 = −
1
< 0
λ2
である．以上から，Kuhn-Tucker 条件を満たす x が求まる．x3 については (2.1.1) のみが関係す
✷
るので，一意には決まらない．
問 2 の解説
[答え]
最適解は x∗ =
(
√1 ,
30
− √230 ,
√5
30
)
Kuhn-Tucker 条件を用いる．
f (x)
g1 (x)
g2 (x)
:= x1 − 2x2 + 5x3 ,
:= x21 + x22 + x23 ,
:= x21 + x22 ,
b1 := 1,
b2 := 12 ,
と定義すると
Max f (x)
gi (x) ≤ bi ,
s.t.
i = 1, 2
という問題になる．ここで f は線型なので凹，また gi はすべて凸なので，Kuhn-Tucker 条件を
満たす x が（講義の定理 13.3 より）最適解になる．x ∈ R3 が Kuhn-Tucker 条件を満たすとは

∂L

= 0,
(1.1)
 ∂x1 = 1 − 2 λ1 x1 − 2 λ2 x1
∂L
=
−2
−
2
λ
x
−
2
λ
x
=
0,
(1.2)
1 2
2 2
∂x

 ∂L2
= 5 − 2 λ1 x3
= 0,
(1.3)
∂x3
および




2
2
2

 1 − x1 − x2 − x3 ≥ 0, (2.1.1)
λ1 ≥ 0,
(2.1.2)


少なくとも一方がゼロ (2.1.3)
− x21 − x22 ≥ 0,
λ2 ≥ 0,


少なくとも一方がゼロ
1
2
(2.2.1)
(2.2.2)
(2.2.3)
となるような λ ∈ R2 が存在することである．(1.3) より λ1 = 0 は不適なので， λ1 > 0 である．
ゆえに (2.1.1) において等号が成立する．また，(1.1) (1.2) より，x2 = −2x1 となる．
λ2 > 0 の場合は，さらに (2.2.1) においても等号が成立する．ゆえに
( 1
2
1 )
x = √ , −√ , √
10
10
2
となるが，ここから λ1 と λ2 の値を求めようとすると，後者の値が負になってしまう．よって
λ2 = 0 である．また，(1.1) (1.2) (1.3) より
x1 =
1
> 0,
2λ1
x2 = −
1
< 0,
λ1
x3 =
5
> 0
2λ1
なので，これと (2.1.1) より Kuhn-Tucker 条件を満たす x が求まる．
2
✷
問 3 の解説
[答え]
[注 ]
最適解は x∗ =
(
0,
6
5
)
制約式が無ければ， x = ( −2, 2
)
の時に目的関数は最大値をとります．第１象限の中で
その点から（ある意味で）最も近い点が本問の最適解であると言えるので，最適解の第１成分がゼ
ロになることは納得できるのではないでしょうか？
[解説]
Kuhn-Tucker 条件を考える．
f (x) := −x21 − 4x1 x2 − 5x22 + 4x1 + 12x2 − 40,
g1 (x) := −x1 ,
b1 := 0,
g2 (x) := −x2 ,
b2 := 0,
と定義すると
Max f (x)
s.t.
gi (x) ≤ bi ,
i = 1, 2
という問題になる．ここで f (x) = −(x1 + 2x2 )2 − x22 + 4x1 + 12x2 − 40 は（線型関数も含め）い
くつかの凹関数の和の形になっているので凹，また gi はすべて線型だから凸なので，Kuhn-Tucker
条件を満たす x が（講義の定理 13.3 より）最適解になる．x ∈ R3 が Kuhn-Tucker 条件を満たす
とは
{
∂L
∂x1
∂L
∂x2
=
=
−2x1 − 4x2 + 4 + λ1
−4x1 − 10x2 + 12 + λ2
= 0,
= 0,
(1.1)
(1.2)
および


 x1 ≥ 0,
λ1 ≥ 0,


少なくとも一方がゼロ


(2.2.1)
 x2 ≥ 0,
λ2 ≥ 0,
(2.2.2)


少なくとも一方がゼロ (2.2.3)
(2.1.1)
(2.1.2)
(2.1.3)
となるような λ ∈ R2 が存在することである．ここで λ2 > 0 と仮定すると，x2 = 0 となるので
(1.1) から
4 + λ1
≥ 2
2
となり，(2.1.3) から λ1 = 0 である．これと (1.1) より x1 = 2 となるが，(1.2) に代入すると λ2
が負になってしまうので矛盾．ゆえに λ2 = 0 である．ここでさらに λ1 = 0 も仮定すると (1.1)
(1.2) から x1 = −2 となり (2.1.1) と矛盾するので，λ1 > 0 そして (2.1.3) から x1 = 0 である．
x1 =
✷
問 4 の解説
[答え]
最適解は x∗ =
(
± 21 , 0,
1
8
)
以下に２通りの解法を示す．
3
解法その１
この問題に限った特殊な話だが，目的関数と第１制約式を良く見ると，最適解に対しては第１制
約式 2x3 ≤ x21 + x22 において明らかに等号成立なので，問題を
Max − x41 +
x2
x21
− 2
2
2
s.t.
x21 + x22 ≤ 4
という２変数問題に帰着させると便利である．目的関数は
(
1
x2
1 )2
+
− 2
− x21 −
4
16
2
と書き直せるので，制約式が無い場合は x1 = ± 12 , x2 = 0 が最適解になるが，これは制約式も満
✷
たしているので，本問の最適解でもある．
解法その２
Kuhn-Tucker 条件を用いる方法．
f (x) := −x41 − x22 + x3 ,
g1 (x) := −x21 − x22 + 2x3 ,
g2 (x) := x21 + x22 ,
b1 := 0,
b2 := 4,
と定義すると，x ∈ R3 が Kuhn-Tucker 条件を満たすとは

∂L
3

 ∂x1 = −4x1 + 2 λ1 x1 − 2 λ2 x1 = 0,
∂L
= −2x2 + 2 λ1 x2 − 2 λ2 x2 = 0,
∂x

 ∂L2
= 1 − 2 λ1
= 0,
∂x3
(1.1)
(1.2)
(1.3)
および


 −g1 (x) ≥ 0,
λ1 ≥ 0,


少なくとも一方がゼロ


(2.2.1)
 4 − g2 (x) ≥ 0,
λ2 ≥ 0,
(2.2.2)


少なくとも一方がゼロ (2.2.3)
(2.1.1)
(2.1.2)
(2.1.3)
となるような λ ∈ R2 が存在することである．まず (1.3) より λ1 =
1
2
なので，以下の２性質が
成立する：
• 式 (1.2) より (−2 + 1 − 2λ2 ) x2 = 0, ゆえに x2 = 0.
(∗)
• 式 (2.1.3) より g1 (x) = 0, つまり 2x3 = x21 + x22 . 上の (∗) もあわせて考えると
2x3 = x21
(∗∗)
そして λ2 がゼロか正かで場合分けする．
λ2 > 0 のとき，(2.2.1) で等号成立，つまり x21 + x22 = 4 である．これと (∗) より x1 = ±2 と
なるし，(∗∗) より x3 = 2 である．しかしここから (1.1) を用いて λ2 の値を求めると負になって
しまい，矛盾．
4
一方 λ2 = 0 のとき，(1.1) より
−4x31 + x1 = 0,
x1 = 0, ±
つまり
である．よって Kuhn-Tucker 条件を満たす点は
 
0
 
および
 0 
1
2


± 12


 0 
1
8
0
の，計３つである．それぞれの点に対して目的関数の値を計算し，比較することによって，答えを
✷
得る．
[注] この問題では g1 が凸関数ではないので定理 13.3 の仮定が満たされず，したがって KuhnTucker 条件を満たす点が自動的に最適解になることは保証されていません．実際，原点は KuhnTucker 条件を満たしますが，最適解ではありません．
問 5 の解説
[答え]
最適解は x∗i =
m
pi α i
i = 1, 2, 3.
[解説]
f (x) =
α2 α3
1
xα
1 x2 x3
g1 (x)
=
−x1
g2 (x)
=
−x2
g3 (x)
=
−x3
g4 (x)
=
p1 x1 + p2 x2 + p3 x3
と定義し，Kuhn-Tucker 条件を考える．計算の際には，以下の事実に注意して進むとスムーズに
進むと思われる：gi のどれか１つでも値がゼロの時は目的関数の値もゼロになるので，そこでは
明らかに最大値を取り得ない．このことから，最適解においては λ1 = λ2 = λ3 = 0 になる．✷
問 6 の解説
[答え]
(i)
(ii)
最適解は c∗0 = K,
c∗j = 0,
j = 1, · · · , 4.
最適解は
(
c∗j
=
)
9 2j
10
∑4 ( 9 )2i
i=0 10
[ (i) の解説 ]
5
K
(i) の答えはぐっとにらめば明らかだが，以下に Kuhn-Tucker 条件を用いて解いてみる．この
問題は
4 (
∑
9 )j
cj 【変数ベクトルは c ∈ R5 】
10
j=0
Max
{
cj
j=0 cj
∑4
s.t.
≥
≤
0,
K
j = 0, 1, · · · , 4,
と定式化される．
f (c)
gj (c)
g5 (c)
(
∑4
:=
j=0
)
9 j
cj ,
10
:= −cj ,
∑4
:=
j=0 cj ,
bj := 0, (j = 0, 1, · · · , 4)
b5 := K,
と定義すると
Max f (c)
s.t.
gi (c) ≤ bi ,
i = 0, 1, · · · , 5
という問題になる．ここで f は線型なので凹，また gi もすべて線型なので凸だから，Kuhn-Tucker
条件を満たす c が（講義の定理 13.3 より）最適解になる．c ∈ R5 が Kuhn-Tucker 条件を満たす
とは，各 j = 0, 1, · · · , 4 に対して
( 9 )j
∂L
=
+ λj − λ5 = 0,
∂cj
10
および


(2.j.1)
 cj ≥ 0,
λj ≥ 0,
(2.j.2)


少なくとも一方がゼロ (2.j.3)
が成り立ち，かつ

∑4

(2.5.1)
 K − j=0 cj ≥ 0,
λ5 ≥ 0,
(2.5.2)


少なくとも一方がゼロ (2.5.3)
(1.j)
も満たすような λ = ( λ0 , λ1 , · · · , λ5 )
∈ R6 が存在することである．まず式 (1.j) から，λ5
は明らかに正なので，(2.5.3) から，(2.5.1) において等号が成立する．また，各 j = 1, · · · , 4 に対
しては
λj
( 9 )j
【式 (1.j) より】
10
=
λ5 −
>
λ5 − 1 【 j ≥ 1 より】
=
λ0 【式 (1.0) より】
≥
0, 【式 (2.0.1) より】
つまり j = 1, · · · , 4 に対しては λj > 0 なので，(2.j.1) において等号が成立する．以上の議論か
✷
ら答えが導かれる．
6
[ (ii) の解説 ]
Kuhn-Tucker 条件を用いた解法．この問題は
Max c∈R5
4 (
∑
9 )j √
cj
10
j=0
{
≥ 0,
≤ K
cj
j=0 cj
∑4
s.t.
j = 0, 1, · · · , 4,
と定式化される．
f (c)
:=
(
∑4
j=0
)
9 j
10
√
cj ,
gj (c) := −cj ,
∑4
g5 (c) :=
j=0 cj ,
bj := 0, (j = 0, 1, · · · , 4)
b5 := K,
と定義すると
Max f (c)
s.t.
gi (c) ≤ bi ,
i = 0, 1, · · · , 5
という問題になる．c ∈ R5 が Kuhn-Tucker 条件を満たすとは，各 j = 0, 1, · · · , 4 に対して
( 9 )j 1
∂L
=
√ + λj − λ5 = 0,
∂cj
10 2 cj
および


(2.j.1)
 cj ≥ 0,
λj ≥ 0,
(2.j.2)


少なくとも一方がゼロ (2.j.3)
が成り立ち，かつ

∑4

(2.5.1)
 K − j=0 cj ≥ 0,
λ5 ≥ 0,
(2.5.2)


少なくとも一方がゼロ (2.5.3)
(1.j)
も満たすような λ = ( λ0 , λ1 , · · · , λ5 )
∈ R6 が存在することである．まず式 (1.j) から，λ5
は明らかに正なので，(2.5.3) から，(2.5.1) において等号が成立する．また各 j = 0, · · · , 4 に対
して，cj = 0 は (1.j) と矛盾するので，cj > 0. ゆえに，(2.j.3) より λj = 0 となり，さらに (1.j)
から
{
cj =
}2
1 ( 9 )j
2λ5 10
✷
が成立する．以上の議論から答えが導かれる．
7

Download Report