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

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

難易度 2大学院の講義の演習問題レベル大学院数学凸最適化・組合せ最適化

$x = (x_{1}, x_{2}, x_{3}, x_{4}) \in R^{4}$ とし、整数計画問題（0-1 ナップサック問題）
$maximize c^{⊤} x subject to 2 x_{1} + 3 x_{2} + 4 x_{3} + 5 x_{4} \leq 7, x \in {0, 1}^{4}$
の線形計画緩和の実行可能領域
$P = {x \in R^{4} 2 x_{1} + 3 x_{2} + 4 x_{3} + 5 x_{4} \leq 7, 0 \leq x_{i} \leq 1 (i = 1, 2, 3, 4)}$
を考える。凸多面体 $P$ の頂点の個数を求めよ。

この問題で使うもの

多面体の頂点（基底解）（説明と入口の問題）
整数計画の線形計画緩和と整数性（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

頂点では一次独立な $4$ 本の不等式が等号で成り立つ。ナップサック制約 $2 x_{1} + 3 x_{2} + 4 x_{3} + 5 x_{4} \leq 7$ が等号かどうかで場合分けしよう。

ヒント 2

ナップサック制約が等号でない頂点は ${0, 1}^{4}$ の点である。等号の場合の非整数頂点は、 $1$ つの座標 $x_{j}$ だけが $0 < x_{j} < 1$ で、残りが $0$ か $1$ に固定された点になる。 $x_{i} = 1$ となる添字の集合を $S$ とすると、条件は $7 - a_{j} < w (S) < 7$ である。

ヒント 3

整数頂点は、重み $2, 3, 4, 5$ の品物から総重量 $7$ 以下で選ぶ選び方の数で、 $9$ 個ある。あとは $j = 1, 2, 3, 4$ のそれぞれについて、条件 $7 - a_{j} < w (S) < 7$ を満たす $S$ を数えればよい。

答えと解説

答えを見る

17

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

解説を読む

$a = (2, 3, 4, 5)$ 、 $b = 7$ とおく。 $P$ は $R^{4}$ 内の多面体で、不等式は $a^{⊤} x \leq b$ と $0 \leq x_{i} \leq 1$ （計 $9$ 本）である。点 $x \in P$ が頂点であることは、 $x$ で等号が成り立つ不等式の係数ベクトルの中に一次独立なものが $4$ 本あることと同値である。各 $i$ について $x_{i} \geq 0$ と $x_{i} \leq 1$ が同時に等号になることはないので、等号の成り立つ境界制約 $x_{i} \in {0, 1}$ は座標ごとに高々 $1$ 本である。

(1) ナップサック制約が等号でない場合。 一次独立な $4$ 本はすべて境界制約から選ぶしかないので、 $x_{1}, \dots, x_{4}$ がすべて $0$ または $1$ である。逆に、 $a^{⊤} x \leq 7$ を満たす ${0, 1}^{4}$ の点は立方体 $[0, 1]^{4}$ の頂点であり、 $P \subset [0, 1]^{4}$ に含まれるから $P$ の頂点でもある（等号 $a^{⊤} x = 7$ の場合もここで数える）。重みが $2, 3, 4, 5$ の品物から総重量 $7$ 以下で選ぶ選び方を数える。
- 何も選ばない： $1$ 通り
- $1$ 個選ぶ： $4$ 通り
- $2$ 個選ぶ： $2 + 3 = 5$ , $2 + 4 = 6$ , $2 + 5 = 7$ , $3 + 4 = 7$ の $4$ 通り（ $3 + 5 = 8$ , $4 + 5 = 9$ は不可）
- $3$ 個以上選ぶ：最小でも $2 + 3 + 4 = 9 > 7$ なので不可

よって整数頂点は $1 + 4 + 4 = 9$ 個である。

(2) 非整数の頂点。 ナップサック制約が等号 $a^{⊤} x = 7$ で、境界制約の等号が $3$ 本の場合である。このとき、ちょうど $1$ つの座標 $x_{j}$ が $0 < x_{j} < 1$ を満たし、残りの $3$ 座標は $0$ か $1$ に固定される。 $a_{j} \neq = 0$ なので、 $a$ と残り $3$ 本の座標ベクトル $e_{i}$ $(i \neq = j)$ は一次独立であり、この点は確かに頂点である。 $x_{i} = 1$ となる添字の集合を $S \subseteq {1, 2, 3, 4} ∖ {j}$ 、その重みの和を $w (S)$ とすると、 $x_{j} = \frac{7 - w ( S )}{a _{j}}$ が $0 < x_{j} < 1$ を満たす条件は
$7 - a_{j} < w (S) < 7$
である。 $j$ ごとに数える。
- $j = 1$ （ $a_{1} = 2$ ）： $S \subseteq {2, 3, 4}$ の重み和は $0, 3, 4, 5, 7, 8, 9, 12$ 。 $5 < w < 7$ を満たすもの（ $w = 6$ ）はないので $0$ 個。
- $j = 2$ （ $a_{2} = 3$ ）： $S \subseteq {1, 3, 4}$ の重み和は $0, 2, 4, 5, 6, 7, 9, 11$ 。 $4 < w < 7$ を満たすのは $w = 5$ （ $S = {4}$ ）と $w = 6$ （ $S = {1, 3}$ ）で $2$ 個。
- $j = 3$ （ $a_{3} = 4$ ）： $S \subseteq {1, 2, 4}$ の重み和は $0, 2, 3, 5, 5, 7, 8, 10$ 。 $3 < w < 7$ を満たすのは $S = {1, 2}$ と $S = {4}$ （ともに $w = 5$ ）で $2$ 個。
- $j = 4$ （ $a_{4} = 5$ ）： $S \subseteq {1, 2, 3}$ の重み和は $0, 2, 3, 4, 5, 6, 7, 9$ 。 $2 < w < 7$ を満たすのは $w = 3, 4, 5, 6$ （ $S = {2}, {3}, {1, 2}, {1, 3}$ ）で $4$ 個。

異なる $(j, S)$ からは異なる点が得られるので、非整数頂点は $0 + 2 + 2 + 4 = 8$ 個である。

以上より、頂点の個数は $9 + 8 = 17$ である。

別解

$P$ は立方体 $[0, 1]^{4}$ に超平面 $2 x_{1} + 3 x_{2} + 4 x_{3} + 5 x_{4} \leq 7$ を加えた多面体である。頂点は、4 次元で一次独立な 4 本の制約が等号で成り立つ点である。したがって次の 2 種類に分けて数える。

(1) 0-1 ベクトルで実行可能なもの。これらは立方体の頂点なので $P$ の頂点でもある。重みの和が 7 以下の部分集合を数える。
- 空集合: 1 個
- 1 元: 4 個
- 2 元: {2,3}=5, {2,4}=6, {2,5}=7, {3,4}=7 の 4 個。{3,5}=8, {4,5}=9 は不可。
- 3 元: 最小でも 2+3+4=9 なので不可。

合計 9 個。

(2) ナップサック制約が等号で、ちょうど 1 つの座標 $x_{j}$ が非整数、他の 3 座標が 0 または 1 であるもの。他の座標の重みの和を $w$ とすると、 $x_{j} = (7 - w) / a_{j}$ が $0 < x_{j} < 1$ を満たす必要がある。すなわち $0 < 7 - w < a_{j}$ 。
- $j = 1$ （ $a = 2$ ）: 他の重み {3,4,5} の部分和で $5 < w < 7$ となるものは無い。0 個。
- $j = 2$ （ $a = 3$ ）: 他の重み {2,4,5} の部分和で $4 < w < 7$ となるものは $w = 5$ （{5}）と $w = 6$ （{2,4}）。2 個。
- $j = 3$ （ $a = 4$ ）: 他の重み {2,3,5} の部分和で $3 < w < 7$ となるものは $w = 5$ （{5} と {2,3}）。2 個。
- $j = 4$ （ $a = 5$ ）: 他の重み {2,3,4} の部分和で $2 < w < 7$ となるものは $w = 3, 4, 5, 6$ の 4 個。

合計 8 個。これらは 4 本の制約が一次独立なので頂点である。

以上より頂点の個数は $9 + 8 = 17$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題