この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

最適化・線形計画法の問題

難易度 4大学院入試の標準レベル大学数学最適化・線形計画法

実数 $x_{1}, x_{2}, x_{3}$ についての次の最適化問題を考える。
$maximize subject to F (x_{1}, x_{2}, x_{3}) = lo g (1 + x_{1}) + lo g (2 + x_{2}) + lo g (4 + x_{3}) x_{1} + x_{2} + x_{3} \leq 4, x_{1} \geq 0, x_{2} \geq 0, x_{3} \geq 0$
ただし $lo g$ は自然対数である。この問題の最大値を求めよ。

この問題で使うもの

凸計画と KKT 条件の十分性（説明と入口の問題）
KKT 条件（説明と入口の問題）

この問題を解けるようになるまで（79 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

目的関数の符号を変えて凸関数の最小化問題にし、KKT 条件を書きましょう。目的関数は狭義凸、制約は一次式なので、KKT 条件は最適性の必要十分条件です。

ヒント 2

和の制約の乗数を $λ$ とすると、 $λ > 0$ が示せます。 $ν = 1/ λ$ とおくと、 $x_{i} = max (0, ν - a_{i})$ （ $a_{1} = 1, a_{2} = 2, a_{3} = 4$ ）の形になります。

ヒント 3

$x_{1} + x_{2} + x_{3} = 4$ となる $ν$ を探します。 $ν = 2$ のとき和は $1$ 、 $ν = 4$ のとき和は $5$ なので、 $2 < ν < 4$ で $(ν - 1) + (ν - 2) = 4$ を解きます。

答えと解説

答えを見る

2 lo g 7

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

最小化問題に直して KKT 条件を使う。

問題の書き換えと KKT 条件の意味 $f (x) = - lo g (1 + x_{1}) - lo g (2 + x_{2}) - lo g (4 + x_{3})$ を、制約
$g_{0} (x) = x_{1} + x_{2} + x_{3} - 4 \leq 0, g_{i} (x) = - x_{i} \leq 0 (i = 1, 2, 3)$
のもとで最小化する。 $- lo g (a + t)$ は $t > - a$ で狭義凸なので $f$ は実行可能領域上で狭義凸であり、制約はすべて一次式である。よって KKT 条件は最適性の必要十分条件であり（一次制約なので制約想定が成り立つ）、最適解はただ 1 つである。

$a_{1} = 1, a_{2} = 2, a_{3} = 4$ とおく。乗数 $λ \geq 0$ （ $g_{0}$ に対応）、 $μ_{i} \geq 0$ （ $g_{i}$ に対応）を用いると、KKT 条件は
$- \frac{1}{a _{i} + x _{i}} + λ - μ_{i} = 0 (i = 1, 2, 3) (1)$
$λ (x_{1} + x_{2} + x_{3} - 4) = 0, μ_{i} x_{i} = 0 (2)$
と、実行可能性・ $λ, μ_{i} \geq 0$ である。

$λ > 0$ であること $λ = 0$ とすると $(1)$ より $μ_{i} = - \frac{1}{a _{i} + x _{i}} < 0$ となり矛盾。よって $λ > 0$ で、 $(2)$ より $x_{1} + x_{2} + x_{3} = 4$ 。

各 $x_{i}$ の形 $ν = \frac{1}{λ}$ とおく。
- $x_{i} > 0$ なら $μ_{i} = 0$ なので $(1)$ より $a_{i} + x_{i} = ν$ 、すなわち $x_{i} = ν - a_{i}$ （このとき $ν > a_{i}$ ）。
- $x_{i} = 0$ なら $μ_{i} = λ - \frac{1}{a _{i}} \geq 0$ 、すなわち $ν \leq a_{i}$ 。

どちらの場合も $x_{i} = max (0, ν - a_{i})$ と表せる。

$ν$ の決定 $S (ν) = max (0, ν - 1) + max (0, ν - 2) + max (0, ν - 4)$ は $ν$ について増加する。 $S (2) = 1 < 4$ , $S (4) = 3 + 2 = 5 > 4$ なので $2 < ν < 4$ であり、この範囲では $S (ν) = (ν - 1) + (ν - 2) = 2 ν - 3$ 。 $2 ν - 3 = 4$ より $ν = \frac{7}{2}$ 。

よって
$x_{1} = \frac{7}{2} - 1 = \frac{5}{2}, x_{2} = \frac{7}{2} - 2 = \frac{3}{2}, x_{3} = 0, λ = \frac{2}{7} .$
確認: $μ_{1} = μ_{2} = 0$ 、 $μ_{3} = λ - \frac{1}{4} = \frac{2}{7} - \frac{1}{4} = \frac{1}{28} \geq 0$ 、 $x_{1} + x_{2} + x_{3} = 4$ で、KKT 条件をすべて満たす。

最大値
$F = lo g \frac{7}{2} + lo g \frac{7}{2} + lo g 4 = lo g (\frac{49}{4} \cdot 4) = lo g 49 = 2 lo g 7.$

別解

$F$ は凹関数、制約は線形なので KKT 条件を満たす点が最大点。水位法で考える: $L = 1/ λ$ とおくと最適解は $x_{i} = max (L - a_{i}, 0)$ （ $a = (1, 2, 4)$ ）で、 $\sum x_{i} = 4$ 。

$x_{3} > 0$ と仮定すると $3 L - 7 = 4$ 、 $L = 11/3 < 4 = a_{3}$ で矛盾。よって $x_{3} = 0$ 。 $x_{1}, x_{2} > 0$ として $(L - 1) + (L - 2) = 4$ より $L = \frac{7}{2}$ 。 $x_{1} = \frac{5}{2}, x_{2} = \frac{3}{2}, x_{3} = 0$ 。 $x_{3} = 0$ の KKT 条件 $\frac{1}{4} \leq λ = \frac{2}{7}$ が成り立つ。

最大値: $F = lo g \frac{7}{2} + lo g \frac{7}{2} + lo g 4 = lo g (\frac{49}{4} \cdot 4) = lo g 49 = 2 lo g 7$ 。

検算: $(2, 2, 0)$ では $lo g 3 + lo g 4 + lo g 4 = lo g 48 < lo g 49$ 。 $(4/3, 4/3, 4/3)$ では $lo g \frac{7}{3} + lo g \frac{10}{3} + lo g \frac{16}{3} = lo g \frac{1120}{27} \approx lo g 41.5 < lo g 49$ 。答えは $2 lo g 7$ 。

最適化・線形計画法の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題