絶対値の表す領域での線形計画

方針

解答

⓪ 発想 — どう考え始めるか。 $|x|+|y|\le 2$ は原点中心のひし形(正方形)の内部。$y\ge 0$ で上半分を切り取ると、頂点 $(2,0),(0,2),(-2,0)$ の三角形になる。

$2x+3y$ は$1$次式。$1$次式の最大最小は、多角形領域では必ず頂点でとる。

だから $3$ つの頂点で $2x+3y$ を計算して比べる。$(2,0)\to 4$、$(0,2)\to 6$、$(-2,0)\to -4$。最大 $6$、最小 $-4$。

① 領域の頂点。 $|x|+|y|\le 2$ はひし形。$y\ge 0$(上半分)をとると、頂点は $(2,0),(0,2),(-2,0)$ の三角形。

② 頂点で $2x+3y$ を比べる。

• $(2,0)\to 2\cdot 2+0=4$
• $(0,2)\to 0+3\cdot 2=6$
• $(-2,0)\to 2\cdot (-2)+0=-4$

③ 結論。 最大値 $6$($(0,2)$)、最小値 $-4$($(-2,0)$)。

まとめ:絶対値の領域は「まず形(ひし形)を確定」。$y\ge 0$ で上半分の三角形になり、$1$ 次式の最大最小は頂点で決まる。$3$ 頂点で値を比べれば最大 $6$・最小 $-4$。境界が絶対値でも、線形計画法の「頂点で比べる」は同じ。

発展 — 一歩先へ。 $1$ 次式の最大は、目的関数の勾配ベクトル $(a,b)$ の向きに「最も遠い頂点」で起こる。凸多角形なら必ず頂点。$|x|+|y|\le c$(マンハッタン距離の円)のような凸領域では、頂点を調べるだけで最適化が済む。凸最適化の最も基本的な例だ。

別解

別解 — 目的関数の勾配方向で「最も遠い頂点」を特定する(得意な人向けの視点)。 $2x+3y$ を最大にするのは、勾配ベクトル $(2,3)$ の向きに最も進んだ点。三角形の頂点のうち、方向 $(2,3)$ への射影が最大の頂点を探す。

各頂点 $(2,0),(0,2),(-2,0)$ の $(2,3)$ 方向への射影(内積): $(2,0)\cdot (2,3)=4$、$(0,2)\cdot (2,3)=6$、$(-2,0)\cdot (2,3)=-4$。

最大の射影は $(0,2)$ の $6$。だから最大は $(0,2)$ で $2x+3y=6$。最小は逆向きに最も進んだ $(-2,0)$ で $-4$。

$3$ 頂点で値を比べる本解と同じ。$1$ 次式 $\vec{c}\cdot (x,y)$ の最大は「$\vec{c}$ 方向に最も遠い頂点」で起こる、というのが線形計画法の基本。目的関数の勾配 $(2,3)$ が上向き成分が大きい($3>2$)ので、上の頂点 $(0,2)$ が有利、と方向から予測できる。