不等式の表す領域と線形計画法
3 つの不等式が表す共通領域（実行可能領域）を塗りつぶし、目的関数 z = px + qy の等値線を動かして最適な頂点を見つけます。
制約① a₁x + b₁y ≤ c₁
1.0
2.0
10
制約② a₂x + b₂y ≤ c₂
2.0
1.0
10
制約③ x ≥ 0 ・ y ≥ 0（第1象限）
ON
目的関数 z = p·x + q·y （最大化）
1.0
1.0
—
xy 平面：色つき領域が各不等式、濃い緑が共通領域／赤い破線が目的関数の等値線（点をドラッグで操作）
実行可能領域
—
最適解 (x*, y*)
—
最大値 z*
—
いまの等値線 z
—
1 本の不等式
線形計画法では、この領域の中で目的関数
スライダーで係数を変えて領域の形を作り、等値線を動かして最適な頂点が点灯する様子を確かめましょう。
ax + by ≤ c は、xy 平面を直線で 2 つに分けたうちの片側の領域を表します。
複数の不等式を同時に満たす点の集まりが、それらの共通領域（実行可能領域）です。線形計画法では、この領域の中で目的関数
z = px + qy を最大（または最小）にする点を探します。
z = 一定 の式は平行な直線（等値線）を表し、z を大きくすると等値線は一定方向へ平行移動します。
領域に最後まで触れている点 ── ふつうは頂点（角）── が最適解です。スライダーで係数を変えて領域の形を作り、等値線を動かして最適な頂点が点灯する様子を確かめましょう。
いま何が起きている？
ここがポイント
- ax + by ≤ c は直線
ax + by = cの片側の半平面を表す（原点を代入して向きを判定）。 - 複数の不等式の共通部分が実行可能領域。直線で囲まれるので多角形になる。
- 目的関数
z = px + qyの等値線は平行な直線群。z を変えると平行移動するだけで傾きは変わらない。 - 最適解は領域の頂点で起こる（線形計画法の基本定理）。だから頂点だけ調べれば最大・最小が分かる。