多面体の頂点（基底解）

不等式系で与えられた多面体 $P \subset R^{n}$ の頂点を、実行可能で、活性な制約のうち一次独立なものが $n$ 個ある点として特徴づけ、小さな多面体の頂点を列挙して個数を求められる

前提

行列の階数と解の存在（大学数学線形代数）
不等式の表す領域（数学II 図形と方程式）

この技能までの道筋（43 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
平行線と線分の比（中学数学相似と三平方の定理）
2点間の距離と内分点・外分点（数学II 図形と方程式）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
因数分解（中学数学数と式）
平方完成と 2 次関数のグラフ（数学I 2次関数）
円の方程式（数学II 図形と方程式）
連立方程式の解き方（加減法・代入法）（中学数学方程式）
1 次関数の式の求め方（中学数学関数）
直線の方程式（数学II 図形と方程式）
不等式の表す領域（数学II 図形と方程式）

説明

有限個の 1 次不等式 $a_{i}^{T} x \leq b_{i} (i = 1, \dots, m)$ をすべて満たす点 $x \in R^{n}$ の集合 $P$ を多面体といいます（有界とは限らず、帯状の領域や半空間のように無限に広がるものも含みます）。平面なら多角形、空間なら多面体の「角」にあたる点が頂点で、線形計画問題では、 $P$ が頂点をもつ（直線を丸ごと含まない）とき、最適解があれば頂点の中にも最適解があることが知られています（帯状の領域のように頂点をもたない多面体では、この探し方は使えません）。この技能では、頂点を「 $P$ に属し、等号で成り立っている制約の中に一次独立なものが $n$ 個ある点」として代数的に特徴づけ、連立 1 次方程式を解くことで小さな多面体の頂点を列挙し、その個数を求められるようになります。このような点は線形計画では基底解（実行可能なら実行可能基底解）とも呼ばれます。

なぜそうしてよいのか

まず言葉を定めます。点 $x \in P$ で $a_{i}^{T} x = b_{i}$ となっている制約を $x$ で活性な制約といいます。 $x \in P$ が $P$ の頂点であるとは、 $x$ が $P$ の異なる 2 点を結ぶ線分の中点にならないこと、つまり $x = \frac{1}{2} (y + z)$ , $y, z \in P$ なら $y = z = x$ となることとします（線分の真ん中に挟まれていない「とがった点」）。

活性な制約の階数が $n$ 未満なら頂点ではない: 活性な制約のベクトル $a_{i}^{T}$ を行として並べた行列の階数が $n$ より小さければ、斉次連立方程式 $a_{i}^{T} d = 0$ （ $i$ は活性な制約）は $d \neq = 0$ の解をもちます（未知数 $n$ 個に対し階数が $n$ 未満なので自由度が残る）。活性でない制約は $a_{j}^{T} x < b_{j}$ と余裕があるので、十分小さい $ε > 0$ をとれば $x \pm ε d$ は活性でない制約を満たし、活性な制約は $a_{i}^{T} (x \pm ε d) = b_{i}$ のまま満たします。よって $x \pm ε d \in P$ で、 $x$ はこの異なる 2 点の中点なので頂点ではありません。

階数が $n$ なら頂点である: $x = \frac{1}{2} (y + z)$ , $y, z \in P$ とします。活性な制約 $i$ について $a_{i}^{T} y \leq b_{i}$ , $a_{i}^{T} z \leq b_{i}$ で、平均が $a_{i}^{T} x = b_{i}$ なので、両方とも等号です。すると $y, z, x$ はどれも連立方程式「 $a_{i}^{T} w = b_{i}$ （ $i$ は活性な制約）」の解です。係数行列の階数が $n$ （未知数の個数）なので解はただ 1 つで、 $y = z = x$ 。以上から、 $x$ が頂点 $⟺$ $x \in P$ かつ $x$ で活性な制約の中に一次独立なものが $n$ 個あることがわかります。したがって頂点は、 $m$ 本の制約から一次独立な $n$ 本を選んで等号として解き、得られた点が残りの不等式も満たすかを調べれば、すべて見つかります（1 つの頂点が複数の組から出ることはあります）。

手順

多面体を $a_{i}^{T} x \leq b_{i}$ （ $\geq$ の制約も含めてよい）の形の $m$ 本の制約として並べ、次元 $n$ を確認する
$m$ 本から $n$ 本の制約を選ぶ組合せ（ $(n m)$ 通り）を順に考え、選んだ $n$ 本を等号にした連立 1 次方程式を作る
係数行列の階数が $n$ でない組（平行な制約を含むなど）や解のない組は捨て、階数 $n$ の組ではただ 1 つの解を求める
得られた点が残りすべての不等式を満たすか（実行可能か）を確かめ、満たすものだけを頂点とする
異なる組から同じ点が出ていないかを確認し、重複を除いた点の個数を数える

例題

$R^{3}$ の多面体 $P = {(x, y, z) ∣ x \geq 0, y \geq 0, z \geq 0, x + y + z \leq 2, x \leq 1}$ の頂点の個数を求めよ。

例題の解答

手順 1: 制約は ① $x \geq 0$ , ② $y \geq 0$ , ③ $z \geq 0$ , ④ $x + y + z \leq 2$ , ⑤ $x \leq 1$ の $m = 5$ 本、 $n = 3$ 。

手順 2〜4: 5 本から 3 本を選ぶ $(3 5) = 10$ 通りを調べる。① $x = 0$ と ⑤ $x = 1$ は同時に成り立たない（係数ベクトルが平行で、等号にすると矛盾する）ので、①⑤を両方含む 3 通り（①②⑤、①③⑤、①④⑤）は解なし。残りの 7 通りはいずれも係数行列の階数が 3 で、解はただ 1 つ。
- ①②③: $(0, 0, 0)$ 実行可能
- ①②④: $(0, 0, 2)$ 実行可能
- ①③④: $(0, 2, 0)$ 実行可能
- ②③④: $(2, 0, 0)$ は ⑤ $x \leq 1$ に反するので頂点ではない
- ②③⑤: $(1, 0, 0)$ 実行可能
- ②④⑤: $y = 0, x = 1, x + y + z = 2$ より $(1, 0, 1)$ 実行可能
- ③④⑤: $z = 0, x = 1, x + y + z = 2$ より $(1, 1, 0)$ 実行可能

手順 5: 得られた実行可能な点 $(0, 0, 0), (0, 0, 2), (0, 2, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0)$ はすべて異なる。

よって頂点の個数は $6$ 。

答え: $6$

よくある誤り

$n$ 本の制約を等号にして解いた点を、実行可能性を確かめずに頂点に数えてしまう誤り。例題で②③④から得た $(2, 0, 0)$ は $x \leq 1$ に反するので頂点ではない。正しくは残りの不等式をすべて代入して確かめる。
実行可能な点を与えた組の数をそのまま頂点の個数としてしまう誤り。 $R^{2}$ の多角形 ${x \geq 0, y \geq 0, x + y \leq 1, x + 2 y \leq 1}$ では、点 $(1, 0)$ で $y \geq 0$ , $x + y \leq 1$ , $x + 2 y \leq 1$ の 3 本が活性になり、組 ${y = 0, x + y = 1}$ , ${y = 0, x + 2 y = 1}$ , ${x + y = 1, x + 2 y = 1}$ の 3 通りがどれも $(1, 0)$ を与える。実行可能な点を与える組は全部で 5 通り（ほかに ${x = 0, y = 0} \to (0, 0)$ , ${x = 0, x + 2 y = 1} \to (0, \frac{1}{2})$ ）だが、頂点は $(0, 0), (1, 0), (0, \frac{1}{2})$ の 3 個。正しくは得られた点の重複を除いて数える。
活性な制約が $n$ 本あれば頂点だと判断してしまう誤り。 $R^{2}$ で制約を $x \geq 0, x \leq 1, x \leq 1$ と（同じものを 2 回）書いた多面体の点 $(1, 0)$ では、活性な制約は 2 本だが同じ制約で一次独立でなく、階数は $1 < 2$ なので頂点ではない（直線 $x = 1$ 上を動ける）。正しくは活性な制約の本数ではなく階数が $n$ であることを確かめる。
どんな多面体にも必ず頂点があると思い込む誤り。 ${(x, y) ∣ 0 \leq x \leq 1}$ は有界でない帯状の多面体で、どの点でも活性な制約は $x = 0$ か $x = 1$ の一方だけ（階数 $1 < 2$ ）なので頂点の個数は $0$ 。正しくは階数 $n$ の組が実行可能な点を与えるかをきちんと調べる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 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$ の頂点の個数を求めよ。

この技能を使う問題

この技能の次に学べること

整数計画の線形計画緩和と整数性（大学院数学凸最適化・組合せ最適化）