TAKEO

TAKEO

図で理解する最適化シリーズ 第1回 / 全3回

高校数学で解く線形最適化 — 直線を動かして最大値を探す

「3x+2y3x+2y をできるだけ大きくしたい」。ただし、xx と yy は好き勝手に増やせない。

こんな問題は、一見すると2つの変数を同時に動かす必要があって難しそうに見える。しかし、高校数学で学ぶ「直線」と「領域」だけで解くことができる。

この第1回では、計算よりも図形のイメージを大切にしながら、線形最適化（線形計画法）の入口を見ていく。

1. 何を最大化するのか

今回の問題はこちら。

最大化：f(x,y)=3x+2y制約条件：x+y≤62x+y≤8x≥0,y≥0\begin{aligned} \text{最大化：}\quad &f(x,y)=3x+2y\\ \text{制約条件：}\quad &x+y\leq6\\ &2x+y\leq8\\ &x\geq0,\quad y\geq0 \end{aligned}

f(x,y)=3x+2yf(x,y)=3x+2y を目的関数、不等式を制約条件と呼ぶ。

例えば、xx と yy を2種類の商品の生産量、3x+2y3x+2y を利益と考えてもいい。資源には限りがあるため、作れる量に制限がかかるわけだ。

注意したいのは、目的関数だけでは最大値を決められないこと。x,yx,y をいくらでも大きくできるなら、3x+2y3x+2y に上限はない。今回は制約条件があるからこそ、最大化が意味を持つ。

2. 制約条件を「領域」に変える

まずは各不等式を yy について解く。

x+y≤6  ⟺  y≤6−x2x+y≤8  ⟺  y≤8−2x\begin{aligned} x+y\leq6 &\iff y\leq6-x\\ 2x+y\leq8 &\iff y\leq8-2x \end{aligned}

つまり、グラフでは次の条件をすべて同時に満たす部分を探せばいい。

  • 直線 y=6−xy=6-x の下側
  • 直線 y=8−2xy=8-2x の下側
  • x≥0x\geq0 かつ y≥0y\geq0（第1象限）

重なり合った部分を実行可能領域と呼ぶ。今回は四角形になる。

インタラクティブ

制約を重ねて、動ける領域を見つける

x + y ≤ 6、2x + y ≤ 8、x ≥ 0、y ≥ 0

まず1つずつ、直線の下側を見てみましょう。両方を満たす共通部分が、実行可能領域です。

制約条件が重なる領域第1象限で両方の共通部分を表示。共通部分の頂点は (0,0)、(4,0)、(2,4)、(0,6)。0123451234567xyx + y = 62x + y = 8(0, 0)(4, 0)(2, 4)(0, 6)
  • x + y = 6
  • 2x + y = 8
  • 実行可能領域
4つの条件を同時に満たす四角形

緑の四角形の内側と辺の上なら、すべての制約を満たします。頂点は (0,0)、(4,0)、(2,4)、(0,6) です。

表示範囲は x = 0〜5、y = 0〜7。境界も「≤」に含まれます。

3. 目的関数も「直線」に変える

ここが核心だ。目的関数の値を kk と置く。

3x+2y=k3x+2y=k

これを yy について解くと、

y=−32x+k2y=-\frac{3}{2}x+\frac{k}{2}

傾きが −32-\frac32、切片が k2\frac{k}{2} の直線になった。

kk を大きくすると、傾きを変えずに直線が上へ平行移動する。

したがって、次の操作をすればよい。

  1. 3x+2y=k3x+2y=k という直線を描く。
  2. 直線を上へ動かして kk を大きくする。
  3. 実行可能領域と交わる最後の位置を探す。
インタラクティブ

直線を動かして、最後に触れる位置を探す

3x + 2y = k　↔　y = −1.5x + k/2

k を増やすと、黒い直線が上へ動きます。緑の領域に触れたまま、どこまで動かせるでしょうか？

目的関数の直線 3x + 2y = 8実行可能領域は固定。k = 8。直線は領域と交わります。0123451234567xyx + y = 62x + y = 8(0, 0)(4, 0)(2, 4)(0, 6)
  • x + y = 6
  • 2x + y = 8
  • 実行可能領域
  • 3x + 2y = k
  • 領域内の交点・線分
まだ領域と交わっています

3x + 2y = 8.0 を満たす点が領域内にあります。k をさらに増やして、最後に触れる位置を探してみましょう。

4つの頂点の値を比べる
頂点 (x, y)3x + 2y比較
(0, 0)0—
(4, 0)12—
(2, 4)14最大
(0, 6)12—

領域は固定です。判定は頂点での値の比較に基づきます。この問題では、領域上の目的関数の値は0〜14です。

この考え方を目的関数の等値線（等高線）を動かすという。2変数の最適化を、目で見える問題に置き換えられた。

4. 実際に最大値を求める

図を見ると、最後に直線が触れるのは、2本の境界直線の交点だと予想できる。

{x+y=62x+y=8\begin{cases} x+y=6\\ 2x+y=8 \end{cases}

上の2式を引けば、

x=2,y=4x=2,\qquad y=4

この点の目的関数は、

f(2,4)=3⋅2+2⋅4=14f(2,4)=3\cdot2+2\cdot4=14

最大値は 1414、そのとき (x,y)=(2,4)(x,y)=(2,4) である。

念のため、実行可能領域の4つの頂点も調べてみよう。

頂点 (x,y)(x,y)3x+2y3x+2y
(0,0)(0,0)00
(4,0)(4,0)1212
(2,4)(2,4)1414
(0,6)(0,6)1212

確かに (2,4)(2,4) が最大になっている。

5. なぜ「頂点」を調べればいいのか

直感的には、直線状の目的関数を多角形の上で最大化すると、少なくとも1つの頂点で最大値が達成されるからだ（実行可能領域が空でない有界な多角形の場合）。

例えば、ある辺の途中の点は、その辺の両端の点を使って

P=(1−t)A+tB(0≤t≤1)P=(1-t)A+tB\qquad(0\leq t\leq1)

と表せる。目的関数 f(x,y)=3x+2yf(x,y)=3x+2y は一次式なので、

f(P)=(1−t)f(A)+tf(B)f(P)=(1-t)f(A)+tf(B)

が成り立つ。つまり、辺の途中の値は両端の値の間に収まる。途中だけが両端より大きくなることはない。

この性質を使うと、多角形の内部から境界へ、境界から頂点へと、値を下げずに移動できる。だから頂点を調べれば十分なのだ。

ただし、最適解が必ず1点だけとは限らない。

最適解が無数にある例

例えば、

最大化：3x+y制約条件：3x+y≤2000x≥0,y≥0\begin{aligned} \text{最大化：}\quad &3x+y\\ \text{制約条件：}\quad &3x+y\leq2000\\ &x\geq0,\quad y\geq0 \end{aligned}

なら、最大値は 20002000。しかも、

3x+y=2000,0≤x≤200033x+y=2000,\qquad 0\leq x\leq\frac{2000}{3}

を満たす線分上のすべての点が最適解になる。

目的関数の直線と制約の境界が重なっているからだ。頂点で最大値を達成することと、頂点だけが最適解であることは違う。

6. 今回のまとめ

  • 目的関数は「何を最大化・最小化したいか」を表す。
  • 制約条件が表す領域を実行可能領域という。
  • 3x+2y=k3x+2y=k のような直線を平行移動すると、最大化を図形的に理解できる。
  • 有界な多角形の線形最適化では、少なくとも1つの頂点が最適解になる。
  • 辺全体が最適解になる場合もある。

ここまでは高校数学の「図形と方程式」の延長だ。

では、目的関数が 3x+2y3x+2y のような直線ではなく、曲がった曲面だったらどうするのだろう？

次回：偏微分で解く非線形最適化 — 3D曲面の底を探す

ホームへ