線形計画の角に答え
線形計画問題の最適解は、実行可能領域の 頂点（角） のどれかに必ず現れます。目的関数ベクトルを回し、制約をドラッグして角の移動を体感します。
35°
8.0
7.0
目的ベクトル c
—
最適頂点 (x, y)
—
最適値 z = c·x
—
頂点の数
—
実行可能領域（青）と最適頂点（赤）── 破線の制約はドラッグで平行移動できます
線形計画（LP）は、1次式の目的関数
制約を満たす点の集合は 凸多角形（実行可能領域） になります。目的関数の値が等しい点は「レベル線」という平行な直線群をなし、その線をベクトル c の向きへ押し進めて 領域からはみ出す直前で止まる場所が最適解です。
だから最適解は、領域の中ではなく必ず 角（頂点） に現れます。これが単体法（シンプレックス法）が頂点だけを探す理由です。θ を回し、制約をドラッグして、答えが角から角へ飛び移る様子を確かめましょう。
z = c₁x + c₂y を、いくつかの 1次不等式の制約 のもとで最大化（または最小化）する問題です。制約を満たす点の集合は 凸多角形（実行可能領域） になります。目的関数の値が等しい点は「レベル線」という平行な直線群をなし、その線をベクトル c の向きへ押し進めて 領域からはみ出す直前で止まる場所が最適解です。
だから最適解は、領域の中ではなく必ず 角（頂点） に現れます。これが単体法（シンプレックス法）が頂点だけを探す理由です。θ を回し、制約をドラッグして、答えが角から角へ飛び移る様子を確かめましょう。
いま何が起きている？
ここがポイント
- 最適解は頂点に出る ── 目的関数が線形なので、最大値は内部ではなく必ず実行可能領域の角（または辺）で達成される。
- レベル線を c 方向に押す ── 等しい z の点は平行な直線群。それを c の向きへ動かして領域を出る直前が最適。
- θ を回すと答えが角から角へ飛ぶ ── 目的の向きが少し変わるだけで最適頂点が隣の角へ瞬間移動する（辺と平行になると辺全体が最適）。
- 制約を動かすと頂点が動く ── 制約の直線（破線）をドラッグすると、その交点である頂点が移動し、最適値も連続的に変化する。これが感度分析の直観。