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

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

難易度 1大学院の講義の例題レベル大学院数学凸最適化・組合せ最適化

$R^{2}$ の多面体
$P = {(x, y) \in R^{2} ∣ x \geq 0, y \geq 0, x + y \leq 4, x \leq 3, y \leq 3}$
を考える。点 $z \in P$ が $P$ の頂点であるとは、 $z$ で等号が成り立つ（活性な）制約の係数ベクトルのうち一次独立なものが $2$ 個あることとする。 $P$ の頂点の個数を求めよ。

この問題で使うもの

多面体の頂点（基底解）（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

多面体の頂点（基底解）の技能を使う。 $R^{2}$ なので、一次独立な 2 本の制約を等号にした点のうち、 $P$ に属するものが頂点になる。

ヒント 2

制約は 5 本あるので、2 本の選び方 $_{5} C_{2} = 10$ 通りについて、係数ベクトルが一次独立か、交点が残りの制約を満たすかを調べる。

ヒント 3

$(0, 4)$ , $(4, 0)$ , $(3, 3)$ は実行不可能、 $x = 0$ と $x = 3$ 、 $y = 0$ と $y = 3$ の組は平行で交点がない。残りの組の交点を数える。

答えと解説

答えを見る

5

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

解説を読む

ステップ 1: 制約に番号をつける

$(1) x \geq 0, (2) y \geq 0, (3) x + y \leq 4, (4) x \leq 3, (5) y \leq 3$
とし、係数ベクトルはそれぞれ $(1, 0)$ , $(0, 1)$ , $(1, 1)$ , $(1, 0)$ , $(0, 1)$ である。

ステップ 2: 頂点の候補を作る

$R^{2}$ では、頂点は一次独立な 2 本の制約を等号にした連立方程式の解で、しかも $P$ に属する（実行可能な）点である。 $5$ 本から $2$ 本を選ぶ $_{5} C_{2} = 10$ 通りを調べる。

$(1), (2)$ : $(0, 0)$ 。すべての制約を満たす。頂点
$(1), (3)$ : $(0, 4)$ 。 $y \leq 3$ に反する。
$(1), (4)$ : 係数ベクトルが $(1, 0)$ どうしで一次従属（平行）。
$(1), (5)$ : $(0, 3)$ 。 $x + y = 3 \leq 4$ などすべて満たす。頂点
$(2), (3)$ : $(4, 0)$ 。 $x \leq 3$ に反する。
$(2), (4)$ : $(3, 0)$ 。すべて満たす。頂点
$(2), (5)$ : 係数ベクトルが $(0, 1)$ どうしで一次従属。
$(3), (4)$ : $x = 3$ , $x + y = 4$ より $(3, 1)$ 。すべて満たす。頂点
$(3), (5)$ : $y = 3$ , $x + y = 4$ より $(1, 3)$ 。すべて満たす。頂点
$(4), (5)$ : $(3, 3)$ 。 $x + y = 6 > 4$ で $(3)$ に反する。

ステップ 3: 数える

得られた頂点は $(0, 0)$ , $(3, 0)$ , $(3, 1)$ , $(1, 3)$ , $(0, 3)$ で、すべて異なる。よって頂点の個数は $5$ である。

別解

制約は (1) $x \geq 0$ , (2) $y \geq 0$ , (3) $x + y \leq 4$ , (4) $x \leq 3$ , (5) $y \leq 3$ 。係数ベクトルは $(\mp 1, 0)$ , $(0, \mp 1)$ , $(1, 1)$ , $(1, 0)$ , $(0, 1)$ 方向。2 本の一次独立な制約を等号にした交点で、 $P$ に含まれるものを調べる。

(1)(2): $(0, 0)$ 。全制約を満たす。頂点。
(1)(3): $(0, 4)$ 。 $y \leq 3$ に反するので $P$ に含まれない。
(1)(5): $(0, 3)$ 。 $x + y = 3 \leq 4$ で全制約を満たす。頂点。
(2)(3): $(4, 0)$ 。 $x \leq 3$ に反するので不適。
(2)(4): $(3, 0)$ 。 $x + y = 3 \leq 4$ で適。頂点。
(3)(4): $(3, 1)$ 。 $y = 1 \in [0, 3]$ で適。頂点。
(3)(5): $(1, 3)$ 。 $x = 1 \in [0, 3]$ で適。頂点。
(4)(5): $(3, 3)$ 。 $x + y = 6 > 4$ で不適。
(1)(4), (2)(5) は平行で交点なし。

頂点は $(0, 0), (0, 3), (3, 0), (3, 1), (1, 3)$ の 5 個。

検算: $P$ は正方形 $[0, 3]^{2}$ の角 $(3, 3)$ を直線 $x + y = 4$ で切り落とした五角形で、辺は 5 本、頂点も 5 個。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題