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

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

難易度 3期末試験の応用レベル大学数学最適化・線形計画法

実数 $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

目的関数は凹関数で制約は 1 次式なので、KKT 条件を満たす点が最適解になります。各制約に乗数を付けて KKT 条件を書きましょう。

ヒント 2

$x_{i} > 0$ のときは $\frac{1}{c _{i} + x _{i}} = λ$ （ $c_{1} = 1, c_{2} = 2, c_{3} = 4$ ）、 $x_{i} = 0$ のときは $\frac{1}{c _{i}} \leq λ$ となります。 $ν = \frac{1}{λ}$ とおくと $x_{i} = max (0, ν - c_{i})$ と書けます（水位を決めるイメージです）。

ヒント 3

$λ > 0$ なので $x_{1} + x_{2} + x_{3} = 4$ です。 $x_{3} = 0$ と仮定して $(ν - 1) + (ν - 2) = 4$ を解き、得られた $ν$ が $ν \leq 4$ を満たすか確かめましょう。

答えと解説

答えを見る

2 lo g 7

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

解説を読む

凸計画であることの確認 最小化問題 $minimize - f$ として考える。 $- lo g (c + x)$ は $x > - c$ で 2 階導関数が $\frac{1}{( c + x ) ^{2}} > 0$ なので凸であり、 $- f$ は凸関数の和で凸である。制約はすべて 1 次式で、たとえば $(x_{1}, x_{2}, x_{3}) = (1, 1, 1)$ はすべての不等式を等号なしで満たす（スレーター条件）。したがって KKT 条件は最適性の必要十分条件である。また実行可能領域は有界閉集合なので最大値は存在する。

KKT 条件 乗数 $λ \geq 0$ （制約 $x_{1} + x_{2} + x_{3} \leq 4$ ）、 $μ_{i} \geq 0$ （制約 $x_{i} \geq 0$ ）を用いると、KKT 条件は
$\frac{1}{1 + x _{1}} = λ - μ_{1}, \frac{1}{2 + x _{2}} = λ - μ_{2}, \frac{1}{4 + x _{3}} = λ - μ_{3},$
$λ (4 - x_{1} - x_{2} - x_{3}) = 0, μ_{i} x_{i} = 0 (i = 1, 2, 3)$
と実行可能性である。

$\frac{1}{1 + x _{1}} > 0$ より $λ \geq μ_{1} + \frac{1}{1 + x _{1}} > 0$ なので、相補性から $x_{1} + x_{2} + x_{3} = 4$ 。

各 $i$ について、 $x_{i} > 0$ なら $μ_{i} = 0$ で $\frac{1}{c _{i} + x _{i}} = λ$ 、すなわち $x_{i} = \frac{1}{λ} - c_{i}$ （ $c_{1} = 1, c_{2} = 2, c_{3} = 4$ ）。 $x_{i} = 0$ なら $\frac{1}{c _{i}} = λ - μ_{i} \leq λ$ 、すなわち $\frac{1}{λ} \leq c_{i}$ 。まとめて $ν = \frac{1}{λ}$ とおくと
$x_{i} = max (0, ν - c_{i})$
である。

$ν$ の決定 $ν \leq 4$ と仮定すると $x_{3} = 0$ 、 $x_{1} = ν - 1$ 、 $x_{2} = ν - 2$ （ $ν \geq 2$ のとき）で、
$(ν - 1) + (ν - 2) = 4 ⟹ ν = \frac{7}{2} .$
これは $2 \leq ν \leq 4$ を満たすので矛盾はない。よって
$x_{1} = \frac{5}{2}, x_{2} = \frac{3}{2}, x_{3} = 0, λ = \frac{2}{7}, μ_{1} = μ_{2} = 0, μ_{3} = λ - \frac{1}{4} = \frac{1}{28} \geq 0$
で KKT 条件がすべて満たされる。（ $ν$ を大きくすると $\sum x_{i}$ は単調に増えるので、 $\sum x_{i} = 4$ となる $ν$ はこれだけである。）

最大値
$f (\frac{5}{2}, \frac{3}{2}, 0) = 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 条件が最大の十分条件になる。ラグランジュ乗数 $λ \geq 0$ （ $x_{1} + x_{2} + x_{3} \leq 4$ 用）、 $μ_{i} \geq 0$ （ $x_{i} \geq 0$ 用）として、 $\frac{1}{a _{i} + x _{i}} = λ - μ_{i}$ （ $a = (1, 2, 4)$ ）。 $x_{i} > 0$ なら $a_{i} + x_{i} = 1/ λ$ 、 $x_{i} = 0$ なら $a_{i} \geq 1/ λ$ 。

水位 $L = 1/ λ$ とおくと $x_{i} = max (L - a_{i}, 0)$ で、和が 4 になる $L$ を求める。 $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 = 7/2$ 。 $x_{1} = 5/2, x_{2} = 3/2, x_{3} = 0$ （ $x_{3} = 0$ の条件 $a_{3} = 4 \geq L = 7/2$ を満たす）。

最大値は $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$ 。

検算: $x_{3}$ に微小量を回すと、限界効用 $1/4$ は他の $1/ L = 2/7$ より小さいので得にならない。たとえば $(2, 2, 0)$ では $lo g 3 + lo g 4 + lo g 4 = lo g 48 < lo g 49$ 、 $(5/2, 1, 1/2)$ では $lo g 3.5 + lo g 3 + lo g 4.5 = lo g 47.25 < lo g 49$ 。答えは $2 lo g 7$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題