線形計画の標準形と幾何

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：モデリングの作法・局所最適と大域最適・凸性の役割　|　関連：シンプレックス法

要点（BLUF）

線形計画（LP）は目的・制約がすべて線形。標準形に統一して理論を組む。
実行可能領域は 凸多面体（線形不等式の交わり）。凸なので局所最適＝大域最適。
最適解は必ず頂点（端点）に存在する。だから頂点だけ調べればよい ── これがシンプレックス法の土台。

概念 ── 標準形

LP はいろいろな書き方ができるが、理論では1つの形に統一する。よく使う標準形（等式標準形）：

\min_{x}\ c^\top x \quad \text{s.t.}\quad Ax = b,\ x \ge 0

不等式 $a^\top x \le b$ は スラック変数 $s \ge 0$ を足して $a^\top x + s = b$ と等式化できる。最大化は符号反転（最適化問題とは）、自由変数は $x = x^+ - x^-$ （ $x^\pm \ge 0$ ）に分解。どんな LP もこの形に直せる。

幾何 ── 実行可能領域は凸多面体

線形不等式 $a^\top x \le b$ は 半空間（平らな境界で切った片側）。実行可能領域はそれらの共通部分なので 凸多面体（多面体的な凸集合）になる。

\mathcal{F} = \{\, x \mid Ax \le b,\ x \ge 0 \,\}

凸多面体の「角」が 頂点（端点）。頂点とは、 $\mathcal{F}$ 内の他の2点の内分点として表せない点。

graph LR
  A["線形不等式 = 半空間"] --> B["共通部分 = 凸多面体"]
  B --> C["角 = 頂点(端点)"]
  C --> D["線形目的の最適は頂点で達成"]

中心定理 ── 最適解は頂点にある

定理：LP が最適解を持ち実行可能領域が頂点を持つなら、ある頂点が最適解になる。

直観的な証明：目的関数 $c^\top x$ の等高線は平らな超平面。これを「最も下げた」位置で実行可能領域に接する。平らな等高線が凸多面体に接するとき、接点は必ず頂点（または頂点を含む辺・面）になる。仮に内点 $x_0$ が最適なら、目的を下げる方向 $-c$ に沿って動けるはずで（ $c \ne 0$ なら）、境界にぶつかるまで動かせば目的は変わらないか改善する。これを繰り返すと頂点に到達する。ゆえに頂点に最適解がある。∎

要するに：無限にある実行可能点を全部調べる必要はない。有限個の頂点だけ調べればよい。これが LP を実用的にした。

Pythonで頂点を列挙して確認

冒頭の生産計画 LP（モデリングの作法）： $\max 40x_A + 30x_B$ s.t. $2x_A+x_B\le120,\ x_A+x_B\le100,\ x\ge0$ 。制約境界の交点のうち実行可能なものが頂点。各頂点で目的値を見ると、最大が最適解。

import numpy as np
from itertools import combinations

# 各制約を直線として持つ: (a, b, c) は a*xA + b*xB = c
lines = [(2,1,120), (1,1,100), (1,0,0), (0,1,0)]

def feasible(x, y):
    return (2*x+y <= 120+1e-9) and (x+y <= 100+1e-9) and (x >= -1e-9) and (y >= -1e-9)

vertices = []
for (a1,b1,c1), (a2,b2,c2) in combinations(lines, 2):
    A = np.array([[a1,b1],[a2,b2]], dtype=float)
    if abs(np.linalg.det(A)) < 1e-9:   # 平行な2直線は交点を持たない
        continue
    p = np.linalg.solve(A, np.array([c1,c2], dtype=float))  # 2直線の交点
    if feasible(p[0], p[1]):           # 全制約を満たす交点だけが頂点
        vertices.append((float(round(p[0],2)), float(round(p[1],2))))

for vx, vy in sorted(set(vertices)):
    print(f"  頂点 (xA={vx:.0f}, xB={vy:.0f}) : 目的値 {40*vx+30*vy:.0f}")

実行結果：

  頂点 (xA=0, xB=0) : 目的値 0
  頂点 (xA=0, xB=100) : 目的値 3000
  頂点 (xA=20, xB=80) : 目的値 3200
  頂点 (xA=60, xB=0) : 目的値 2400

頂点は4つだけ。目的値が最大なのは $(20,80)$ で 3200。領域内の無数の点を調べずとも、4頂点の比較で最適解が出る。シンプレックス法はこの頂点を賢く渡り歩く（シンプレックス法）。

数式の直観的意味

なぜ「線形目的＋凸多面体」だと最適が頂点なのか。線形関数には極大・極小の内点がない（勾配 $c$ が一定で、 $c\ne0$ なら必ず下げる方向がある）。だから最小は 領域の縁でしか起きない。さらに縁の中でも「最も尖った点」＝頂点が、平らな等高線と接する自然な場所になる。この「最適は端で起きる」性質は線形性そのものの帰結であり、内点法（内点法入門）が頂点を経由せず別経路で最適に至るのと好対照をなす。

⚠️ よくある誤解・落とし穴

頂点が最適とは「ある頂点が最適」という意味。辺・面全体が最適になることもある（目的の等高線が辺と平行なとき、無数の最適解）。
非有界に注意：実行可能領域が無限に広がり目的が下がり続けると最適解は無い（最適化問題とは）。
スラック変数を忘れない：標準形にするとき不等式ごとに非負スラックを足す。これが感度分析（感度分析）で「制約の余り」になる。
頂点列挙は変数が増えると爆発する（ $n$ 次元で頂点数は指数的）。実務はシンプレックス法・内点法。