確率計画法｜数理最適化

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：最適化問題とは・線形計画の標準形と幾何　|　関連：サンプル平均近似（SAA）

要点（BLUF）

確率計画は 不確実なパラメータを確率分布として扱い、期待値を最適化する。
2段階リコース：第1段で「先に決める（here-and-now）」、不確実性が判明した後、第2段で「修正する（recourse）」。
目的は「第1段コスト＋第2段の期待リコースコスト」の最小化。新聞売り子問題が最小例。

概念 ── 決める→観測する→修正する

現実の意思決定は、不確実性が判明する前に行わねばならないことが多い（需要を見る前に発注、天候を知る前に作付け）。確率計画は、この「先に決める変数（第1段）」と「不確実性判明後に調整する変数（第2段＝リコース）」を分けてモデル化する。

graph LR
  A["第1段: 不確実性の前に決める x (here-and-now)"] --> B["不確実性 ξ が実現(観測)"]
  B --> C["第2段: ξ に応じて修正 y(ξ) (recourse)"]
  C --> D["総コスト = 第1段 + 期待リコース を最小化"]

2段階確率計画の定式化

\min_x\ c^\top x + \mathbb{E}_\xi\bigl[\, Q(x,\xi) \,\bigr] \quad \text{s.t.}\quad Ax = b,\ x \ge 0

ここで第2段の最適リコースコスト：

Q(x,\xi) = \min_{y \ge 0}\ \{\, q(\xi)^\top y \mid W y = h(\xi) - T(\xi)\, x \,\}

第1段 $x$ を決めた後、シナリオ $\xi$ が実現すると、その制約のもとで最良の修正 $y$ を取る。期待値 $\mathbb{E}_\xi[Q]$ を織り込んで第1段を最適化するのがポイント。リコースが常に可能（任意の $x,\xi$ で第2段が実行可能）なら 完全リコースという。

新聞売り子問題（最小例）

新聞を1部 $c=6$ で仕入れ $p=10$ で売る。売れ残りは $s=2$ で処分。需要 $D$ は不確実。発注量 $x$ が第1段（需要を見る前に決める）、販売量 $\min(x,D)$ が第2段（需要判明後に決まる）。期待利益最大の $x$ は？

理論解は 臨界比（critical fractile）：

x^\star = F_D^{-1}\!\left(\frac{p-c}{p-s}\right)

「品切れの損 $(p-c)$ 」と「売れ残りの損 $(c-s)$ 」のバランスで決まる分位点。ここでは $(p-c)/(p-s) = 4/8 = 0.5$ なので、需要分布の 中央値が最適発注量。

import numpy as np

p, c, s = 10.0, 6.0, 2.0          # 売価・仕入・残価
critical_ratio = (p - c) / (p - s)
print(f"臨界比 = (p-c)/(p-s) = {critical_ratio:.3f}")

# 需要 ~ N(100, 20^2)。期待利益を発注量xの関数として評価(シナリオ平均)
rng = np.random.default_rng(0)
demands = rng.normal(100, 20, 100000)    # 多数のシナリオで期待値を近似

def expected_profit(x):
    sales = np.minimum(x, demands)            # 売れる量
    leftover = np.maximum(0, x - demands)     # 売れ残り
    return np.mean(p*sales + s*leftover - c*x)

grid = np.arange(80, 121, 1.0)
best_x = grid[int(np.argmax([expected_profit(x) for x in grid]))]
print(f"最適発注量 = {best_x:.0f}  (臨界比0.5 -> 需要の中央値100)")

実行結果：

臨界比 = (p-c)/(p-s) = 0.500
最適発注量 = 100  (臨界比0.5 -> 需要の中央値100)

臨界比 0.5 なので最適発注量は需要の中央値 100。期待利益を最大化する点が、品切れリスクと売れ残りリスクをちょうど釣り合わせる分位点になっている ── これが確率計画の典型的な構造。確率分布が分からず標本だけある場合の解き方が SAA（サンプル平均近似（SAA））。

多段階への拡張

2段階を時間方向に繰り返すと 多段階確率計画になる。各段で「観測 → 決定」を繰り返し、不確実性は シナリオ木で表す。在庫補充・ダム運用・資産運用など、逐次的に決定を修正していく問題が該当。多段階は 動的計画法（ベルマンの原理、動的計画法とベルマンの原理） とも結びつき、状態に対する価値関数を後ろ向きに解く構造を持つ。ただし段数・シナリオが増えると爆発的に重くなり、近似（シナリオ削減・確率的双対動的計画 SDDP）が要る。

数式の直観的意味

確率計画の本質は「期待値という1つの目的に、無数のシナリオを畳み込む」こと。第1段 $x$ を固定すると、各シナリオ $\xi$ での最適リコース $Q(x,\xi)$ が決まり、その期待値 $\mathbb{E}[Q(x,\xi)]$ が $x$ の関数になる。完全リコースの確率計画では、この期待リコース関数 $\mathbb{E}[Q(x,\xi)]$ が $x$ について凸（各 $Q$ が凸で、凸関数の期待値は凸、凸集合と凸関数）になる ── だから全体が凸最適化になり、効率的に解ける。臨界比の式は、期待利益の微分をゼロにする1次条件（最適性条件の地図）から導かれ、「限界品切れ損＝限界売れ残り損」の釣り合いを表す。リコース変数 $y$ は「事後に取れる最善手」で、これを織り込むからこそ、過度に保守的でも楽観的でもない決定が得られる。

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

期待値最適化はリスク中立：平均は良くてもテール（最悪）が悪い解を選びうる。リスク回避なら CVaR（リスクを織り込む最適化（CVaR最小化））。
「期待値の最適 ≠ 平均シナリオの最適」：平均需要だけで解くと不確実性を無視する（イェンセンの不等式で期待リコースを過小評価）。
完全リコースの確認：第2段がどんな $x,\xi$ でも実行可能か。そうでないと実行不能シナリオの扱いが要る。
シナリオ数が増えると巨大 LP になる。SAA・分解法（Benders）で対処。