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

凸最適化・組合せ最適化の問題

難易度 3大学院入試の専門科目の標準レベル大学院数学凸最適化・組合せ最適化

$x = (x_{1}, x_{2}, x_{3}, x_{4}) \in {0, 1}^{4}$ を変数とする次の 0-1 ナップサック問題 $(P)$ を考える。
$(P) maximize 7 x_{1} + 5 x_{2} + 4 x_{3} + 3 x_{4} subject to 5 x_{1} + 4 x_{2} + 3 x_{3} + 2 x_{4} \leq 9, x \in {0, 1}^{4} .$
$(P)$ の最適値を $p^{*}$ とする。不等式制約だけに乗数 $λ \geq 0$ を導入してラグランジュ関数
$L (x, λ) = 7 x_{1} + 5 x_{2} + 4 x_{3} + 3 x_{4} + λ (9 - 5 x_{1} - 4 x_{2} - 3 x_{3} - 2 x_{4})$
を定め、双対関数を $g (λ) = max_{x \in {0, 1}^{4}} L (x, λ)$ 、双対問題の最適値を $d^{*} = min_{λ \geq 0} g (λ)$ とする。双対ギャップ $d^{*} - p^{*}$ を求めよ。

この問題で使うもの

非凸・整数の問題の双対ギャップ（説明と入口の問題）
ラグランジュ双対関数と弱双対性（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

主問題は小さいので実行可能な部分集合を列挙して $p^{*}$ を求め、双対関数は $x_{i}$ ごとに分離して最大化する。

ヒント 2

$g (λ) = 9 λ + \sum_{i} max (0, c_{i} - λ a_{i})$ は凸な区分線形関数で、折れ点は $c_{i} / a_{i}$ 。傾き $9 - \sum_{c_{i} / a_{i} > λ} a_{i}$ の符号が変わる点を探す。

ヒント 3

$p^{*} = 12$ である。また $g$ の傾きは $\frac{5}{4} < λ < \frac{4}{3}$ で $- 1$ 、 $\frac{4}{3} < λ < \frac{7}{5}$ で $2$ なので、最小点は $λ = \frac{4}{3}$ 。

答えと解説

答えを見る

\frac{2}{3}

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

解説を読む

主問題の最適値 $p^{*}$ . 重さ $(5, 4, 3, 2)$ の合計が $9$ 以下となる部分集合を調べる。 $4$ 個すべては重さ $14$ 、 $3$ 個の組では ${1, 2, 3} : 12, {1, 2, 4} : 11, {1, 3, 4} : 10$ がいずれも不適で、 ${2, 3, 4}$ は重さ $9$ 、価値 $5 + 4 + 3 = 12$ 。 $2$ 個の組では ${1, 2}$ （重さ $9$ 、価値 $12$ ）、 ${1, 3}$ （ $8$ , $11$ ）、 ${1, 4}$ （ $7$ , $10$ ）、 ${2, 3}$ （ $7$ , $9$ ）、 ${2, 4}$ （ $6$ , $8$ ）、 ${3, 4}$ （ $5$ , $7$ ）。 $1$ 個以下では価値は $7$ 以下。よって $p^{*} = 12$ 。

双対関数. $L (x, λ) = 9 λ + \sum_{i} (c_{i} - λ a_{i}) x_{i}$ （ $c = (7, 5, 4, 3)$ , $a = (5, 4, 3, 2)$ ）は $x_{i}$ ごとに分離するので、各 $x_{i} \in {0, 1}$ について独立に最大化して
$g (λ) = 9 λ + max (0, 7 - 5 λ) + max (0, 5 - 4 λ) + max (0, 4 - 3 λ) + max (0, 3 - 2 λ) .$
これは区分的に線形な凸関数で、折れ点は $c_{i} / a_{i}$ すなわち $\frac{5}{4}, \frac{4}{3}, \frac{7}{5}, \frac{3}{2}$ である。 $λ$ における傾きは $9 - \sum_{i : c_{i} / a_{i} > λ} a_{i}$ である。
- $\frac{5}{4} < λ < \frac{4}{3}$ ： $c_{i} / a_{i} > λ$ となるのは $i = 1, 3, 4$ で、傾きは $9 - (5 + 3 + 2) = - 1 < 0$ 。
- $\frac{4}{3} < λ < \frac{7}{5}$ ： $i = 1, 4$ で、傾きは $9 - (5 + 2) = 2 > 0$ 。

凸関数の傾きが負から正に変わるので、最小は $λ^{*} = \frac{4}{3}$ でとられる：
$g (\frac{4}{3}) = 12 + (7 - \frac{20}{3}) + 0 + (4 - 4) + (3 - \frac{8}{3}) = 12 + \frac{1}{3} + \frac{1}{3} = \frac{38}{3} .$
よって $d^{*} = \frac{38}{3}$ 。（確認：この値は線形計画緩和の値に一致する。価値/重さの比の大きい順に $x_{4} = 1, x_{1} = 1$ とし、残り容量 $2$ に $x_{3} = \frac{2}{3}$ を入れると $3 + 7 + \frac{8}{3} = \frac{38}{3}$ 。 ${0, 1}^{4}$ を区間 $[0, 1]^{4}$ に置き換えても $L$ の最大値は変わらないため、ラグランジュ双対は LP 緩和の双対と一致する。）

双対ギャップ. 弱双対性より $d^{*} \geq p^{*}$ であり、
$d^{*} - p^{*} = \frac{38}{3} - 12 = \frac{2}{3} .$
主問題が整数制約をもち凸でないため強双対性は成り立たず、正のギャップが生じる。

別解

最適値 $p^{*}$ :重さの合計が 9 以下になる組合せを調べる。
- 3 個以上を選ぶ場合、実行可能なのは ${2, 3, 4}$ (重さ 9、価値 12)のみ。ほかの 3 個の組は重さが 10 以上、4 個すべてなら重さ 14 で不可能。
- 2 個を選ぶ場合、 ${1, 2}$ は重さ 9 で価値 12、 ${1, 3}$ は価値 11、 ${1, 4}$ は価値 10、そのほかはさらに小さい。

よって $p^{*} = 12$ 。

双対関数: $g (λ) = 9 λ + \sum_{i} max (0, v_{i} - λ w_{i})$ 。これは $λ$ の区分線形凸関数で、折れ点は $v_{i} / w_{i} = 7/5, 5/4, 4/3, 3/2$ である。

双対問題の値は、 $x \in [0, 1]^{4}$ に緩和した LP 緩和の最適値に等しい。比 $v_{i} / w_{i}$ の大きい順(項目 4、1、3、2)に詰めると、項目 4(重さ 2)と項目 1(重さ 5)で重さ 7、残り容量 2 に項目 3 を $2/3$ 入れる。値は $3 + 7 + \frac{2}{3} \cdot 4 = \frac{38}{3}$ となる。

検算: $λ = 4/3$ のとき $g = 12 + (7 - \frac{20}{3}) + 0 + 0 + (3 - \frac{8}{3}) = 12 + \frac{1}{3} + \frac{1}{3} = \frac{38}{3}$ 。項目 3 の寄与は $4 - 4 = 0$ 、項目 2 の寄与は $5 - \frac{16}{3} < 0$ なので 0。

これより $d^{*} = 38/3$ 。

双対ギャップ: $d^{*} - p^{*} = \frac{38}{3} - 12 = \frac{2}{3}$ 。

凸最適化・組合せ最適化の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題