数学II / 軌跡と領域

3つの不等式の領域

★ 基礎領域連立不等式

問題

連立不等式 $x \geq 0$ 、 $y \geq 0$ 、 $x + y \leq 3$ の表す領域を図示せよ。また、この領域は何という図形か答えよ。

ヒントを見る

$3$ つの不等式を $1$ つずつ境界線にして、順に領域を狭めていく。最後に残った形の頂点を全部求めれば、何という図形かも答えられる。

解答・解説

方針

$x \geq 0$ は $y$ 軸の右、 $y \geq 0$ は $x$ 軸の上、 $x + y \leq 3$ は直線 $x + y = 3$ の下側。3つの共通部分は三角形になる。

解答

⓪ 発想 — どう考え始めるか。 $3$ 本の不等式 — $1$ 本ずつ読んで、共通部分を取る。

$x ≧ 0$ : $y$ 軸の右側(境界を含む)
$y ≧ 0$ : $x$ 軸の上側(境界を含む)

この $2$ つで、すでに「第 $1$ 象限(の周を含む部分)」に絞られた。

$x + y ≦ 3$ : 直線 $x + y = 3$ の下側(原点側)

この直線は、 $2$ 点 $(3, 0)$ と $(0, 3)$ を通る( $x$ 切片と $y$ 切片を打てば、すぐ引ける)。

$3$ つの共通部分は、 $3$ 点 $(0, 0)$ 、 $(3, 0)$ 、 $(0, 3)$ を頂点とする三角形(周を含む)になる。

$3$ 本の直線が、領域を三方から囲い込んだ。 制約が増えるほど、領域は狭く、そして閉じていく。

重要連立不等式の領域は共通部分。境界の直線で囲まれた図形になる

$x \geq 0$ : $y$ 軸より右(軸を含む)
$y \geq 0$ : $x$ 軸より上(軸を含む)
$x + y \leq 3$ :直線 $x + y = 3$ の下側(直線を含む)

3つを同時に満たすのは、頂点が $(0, 0)$ 、 $(3, 0)$ 、 $(0, 3)$ の三角形の周および内部。

3つの境界で囲まれた三角形

発展 — 一歩先へ。 この三角形は、現実の問題では「実行可能領域」と呼ばれる。

具体例で見てみよう。

「 $1$ 個 $1$ 時間かかる製品 A と、 $1$ 個 $1$ 時間かかる製品 B を作る。作業時間は $3$ 時間まで。製品の個数は $0$ 個以上。」

$x$ : 製品 A の個数 → $x ≧ 0$
$y$ : 製品 B の個数 → $y ≧ 0$
時間の制約 → $x + y ≦ 3$

まさに、この三角形が「作れる組み合わせ」の全体である。

現実の問題では、制約はもっと多い。

材料の制約: $2 x + 3 y ≦ 12$
予算の制約: $5 x + 4 y ≦ 20$
需要の上限: $x ≦ 4$

制約が $10$ 本あれば、 $10$ 角形(あるいはもっと複雑な多面体)になる。

変数も $2$ 個とは限らない。 製品が $100$ 種類あれば、 $100$ 次元空間の多面体だ — もう図には描けない。

それでも「最適解は頂点にある」という原理は生きている。

問題は、頂点の個数だ。 高次元の多面体は、頂点が天文学的な数になりうる( $100$ 変数・ $100$ 制約なら、理論上は $1 0^{29}$ 個以上)。全部調べるのは不可能。

そこで開発されたのが「単体法(シンプレックス法)」( $1947$ 年、ダンツィーグ)。すべての頂点を調べるのではなく、「隣の頂点で、値がよくなるほうへ」と渡り歩くアルゴリズムだ。

驚くべきことに、この方法は実用上きわめて速い。 $1 0^{29}$ 個の頂点があっても、たいてい数十回の移動で最適解に着く。

現代の物流・生産計画・金融は、この方法の上に成り立っている。 「 $20$ 世紀で最も重要なアルゴリズムの $1$ つ」と呼ばれるゆえんだ。

$3$ 本の不等式で三角形を描く作業。 その先に、世界を動かす最適化の技術がある。

答

3点 $(0, 0)$ 、 $(3, 0)$ 、 $(0, 3)$ を頂点とする三角形の周および内部

別解

「頂点」を正しく求めることが、この先(最大最小)への鍵になる。 頂点の出し方を確実にし、領域の性質も確かめておこう。

頂点の求め方: 境界線を $2$ 本ずつ連立する。

$3$ 本の境界線は

$ℓ_{1} : x = 0, ℓ_{2} : y = 0, ℓ_{3} : x + y = 3$

$2$ 本ずつ組み合わせて、交点を求める。

$ℓ_{1} \cap ℓ_{2}$ : $x = 0$ 、 $y = 0$ → $(0, 0)$
$ℓ_{1} \cap ℓ_{3}$ : $x = 0$ 、 $0 + y = 3$ → $(0, 3)$
$ℓ_{2} \cap ℓ_{3}$ : $y = 0$ 、 $x + 0 = 3$ → $(3, 0)$

$3$ つの頂点が出た。

注意: 交点が必ず頂点になるとは限らない。 求めた交点が、他のすべての不等式を満たすかを確認する必要がある。

たとえば、もし $x + y ≦ 3$ ではなく $x + y ≧ 5$ のような条件が混じっていたら、 $(0, 0)$ は $0 ≧ 5$ を満たさないので頂点にならない(領域外)。

今回は $3$ 点とも、すべての不等式を満たす。

$(0, 0)$ : $0 ≧ 0$ ✓、 $0 ≧ 0$ ✓、 $0 ≦ 3$ ✓
$(3, 0)$ : $3 ≧ 0$ ✓、 $0 ≧ 0$ ✓、 $3 ≦ 3$ ✓
$(0, 3)$ : ✓ ✓ ✓

$3$ 点とも本物の頂点。 三角形が確定した。

この領域の性質を、 $3$ つ確認しておこう。

性質1: 有界である。 領域が無限に広がっていない(有限の範囲に収まっている)。 $3$ 本目の $x + y ≦ 3$ が"ふた"をしたからだ。もしこれがなければ、第 $1$ 象限全体という無限の領域になっていた。

性質2: 凸である。 $1$ 次不等式の共通部分なので、必ず凸(問題6の発展で見た通り)。三角形は確かに凸だ。

性質3: 面積が計算できる。

$\frac{1}{2} \times 3 \times 3 = \frac{9}{2}$

底辺 $3$ 、高さ $3$ の直角三角形。

「有界かつ凸」— この $2$ つが揃うと、最適化がうまくいく。

$有界な凸多角形では、 1 次式の最大・最小は必ず頂点でとる$

これが、次の問題(領域と最大最小)の理論的な根拠になる。

なぜ頂点なのか、直感的に説明しよう。 $1$ 次式 $x + 2 y = k$ の値は、直線を平行移動させると連続的に変わる。領域内で $k$ を大きくしていくと、直線はだんだん領域から出ていく — その最後の瞬間、直線は必ず「角(頂点)」に触れている。

辺に沿って触れる場合もある(そのときは辺全体が最大値をとる)が、そのときも端の頂点は最大値をとっている — だから「頂点だけ調べれば十分」なのだ。

この単純な原理が、線形計画法という巨大な応用分野を支えている。 頂点は有限個しかないから、全部調べれば必ず最適解が見つかる。

ポイント

$x \geq 0$ かつ $y \geq 0$ で第1象限に限定。
さらに斜めの直線で切ると三角形になる。

よくある間違い

$x \geq 0$ 、 $y \geq 0$ を見落として、直線 $x + y = 3$ の下側全体を塗ってしまう
$x + y \leq 3$ の境界線を、 $(3, 0)$ と $(0, 3)$ を通る直線だと気づかず、正確に引けない
求めた交点が他の不等式を満たすか確認せず、領域外の点を頂点にしてしまう