シンプレックス法｜数理最適化

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：線形計画の標準形と幾何　|　関連：線形計画の双対性

要点（BLUF）

シンプレックス法は 頂点から隣の頂点へ、目的を改善し続けて渡り歩くアルゴリズム。
各頂点は 基底解（ $n$ 変数のうち $m$ 個を基底にし残りを0）に対応する。
どの変数を基底に入れるかは 被約費用（reduced cost） が決め、すべて非負なら最適で停止。

概念 ── 頂点＝基底解

標準形 $Ax=b,\ x\ge0$ （ $A$ は $m\times n$ ）を考える。 $n$ 個の変数から $m$ 個を選んで 基底変数とし、残り $n-m$ 個を 非基底変数＝0 に固定する。基底の連立 $B x_B = b$ を解いた $x_B \ge 0$ が 基底実行可能解で、これが凸多面体の頂点に対応する（線形計画の標準形と幾何）。

頂点が有限個なのは、基底の選び方が $\binom{n}{m}$ 通りと有限だから。シンプレックス法は全部試さず、改善する方向にだけ進む。

アルゴリズム ── ピボットで隣の頂点へ

graph TD
  A["初期頂点(基底実行可能解)"] --> B["被約費用を計算"]
  B --> C{"改善する非基底変数があるか"}
  C -->|"ある"| D["入る変数を選ぶ(価格付け)"]
  D --> E["比率テストで出る変数を選ぶ"]
  E --> F["ピボット = 隣の頂点へ移動"]
  F --> B
  C -->|"ない(全て非負)"| G["最適 = 停止"]

価格付け（入る変数）：非基底変数 $x_j$ の 被約費用 $\bar c_j = c_j - c_B^\top B^{-1} A_j$ を見る。 $\bar c_j < 0$ （最小化）なら、 $x_j$ を増やすと目的が下がる。
比率テスト（出る変数）： $x_j$ を増やすと、ある基底変数が先に0になる。最初に0になる変数が基底から出る（ $\min_i b_i / (B^{-1}A_j)_i$ 、正の成分のみ）。
ピボット：基底を入れ替える＝隣接頂点へ移動。目的は改善（または不変）。
停止：すべての $\bar c_j \ge 0$ なら、どの方向に動いても改善せず最適。

被約費用が最適性を保証する理由

被約費用 $\bar c_j$ は「非基底変数 $x_j$ を1単位増やしたときの目的の正味変化」。基底変数が連動して変わる分まで織り込んだ値だ。すべての $\bar c_j \ge 0$ なら、どの非基底変数を増やしても目的は下がらない ── つまり現在の頂点が局所最適。LP は凸（局所最適と大域最適・凸性の役割）なので、局所最適は大域最適。これでシンプレックス法の停止＝最適が正当化される。被約費用は双対変数 $y = (B^{-1})^\top c_B$ を使って $\bar c_j = c_j - y^\top A_j$ とも書け、ここに 双対性（線形計画の双対性）が顔を出す。

Pythonで頂点最適に到達

scipy の linprog(method="highs-ds") は デュアルシンプレックス。生産計画 LP を解くと、頂点 $(20,80)$ に到達する（線形計画の標準形と幾何の頂点列挙と一致）。

from scipy.optimize import linprog

# max 40xA+30xB を -最小化（符号反転）
c = [-40, -30]
A_ub = [[2, 1], [1, 1]]   # 2xA+xB<=120, xA+xB<=100
b_ub = [120, 100]
bounds = [(0, None), (0, None)]

res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method="highs-ds")
print(f"最適解 xA={res.x[0]:.1f}, xB={res.x[1]:.1f}, 利益={-res.fun:.0f}")

実行結果：

最適解 xA=20.0, xB=80.0, 利益=3200

頂点列挙で最大だった $(20,80)$ にシンプレックスが到達。原点 $(0,0)$ から始めて、 $x_B$ を入れて $(0,100)$ 、次に $x_A$ を入れて $(20,80)$ ── というように2回のピボットで角を渡る（具体的なピボット経路は問題と規則による）。

計算量と実務

最悪計算量は指数時間（Klee–Minty の例で頂点を全部辿る）。だが 実用上はほぼ線形〜多項式的に速く、長年の主力。
多項式時間保証が欲しいときは内点法（内点法入門）。大規模疎問題では両者を使い分ける。
退化（同じ頂点に複数の基底が対応）でサイクルが起き得る。Bland 規則などで回避する。

数式の直観的意味

シンプレックス法の賢さは「内点を通らず、縁の頂点だけを目的が良くなる向きに辿る」点にある。LP の最適が頂点にある（線形計画の標準形と幾何）以上、頂点だけ調べれば十分で、しかも隣接頂点へ「下る」だけなので、凸性が後戻りしないことを保証する。被約費用が全部非負になった瞬間に「もう下る隣がない」＝大域最適、と判断できる。この局所的な判定（隣だけ見る）が大域最適を保証するのは、ひとえに凸多面体＋線形目的という構造のおかげ。

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

「シンプレックス＝必ず速い」ではない。最悪は指数。ただし実務性能は良好。
初期実行可能解が必要：原点が実行可能でないときは2段階法やビッグM法で人工変数から始める。
退化とサイクルに注意。Bland 規則・摂動で回避。
シンプレックスは LP 専用。整数制約は扱えない（分枝限定法で LP 緩和の解として使う）。