線形計画の双対性｜数理最適化

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

📎 前提：シンプレックス法　|　関連：感度分析・凸最適化問題と双対理論

要点（BLUF）

どの LP（主問題）にも、対をなす 双対問題が定まる。
弱双対：双対の目的値は常に主の目的値を下から（または上から）抑える。
強双対：LP が最適解を持てば 主と双対の最適値は一致する。差（双対ギャップ）はゼロ。
相補性：効いていない制約の双対変数は0、ゼロでない変数の双対制約は等号で効く。

概念 ── 主問題と双対問題

主問題（最大化、生産計画の形）：

\max_{x \ge 0}\ c^\top x \quad \text{s.t.}\quad Ax \le b

その 双対問題（最小化）：

\min_{y \ge 0}\ b^\top y \quad \text{s.t.}\quad A^\top y \ge c

対応のルール：主の制約↔双対の変数、主の変数↔双対の制約。主が「資源 $b$ をどう使って利益 $c$ を最大化するか」なら、双対は「資源 $b$ に値段 $y$ を付けて総コスト $b^\top y$ を最小化（ただし各製品の利益 $c$ を下回らない値付け）」という鏡像問題。 $y$ が 影の価格（感度分析）。

弱双対定理

任意の主実行可能 $x$ と双対実行可能 $y$ について：

c^\top x \le (A^\top y)^\top x = y^\top (Ax) \le y^\top b = b^\top y

（1つ目は $A^\top y \ge c,\ x\ge0$ 、2つ目は $Ax \le b,\ y\ge0$ から）。要するに：どんな実行可能な主・双対の値も、主 ≤ 双対の関係で挟まれる。よって どちらかの実行可能値は他方の最適値の保証（限界）になる。これは最適性の証明書（停止判定）に使える。

強双対定理

定理：主問題が有限最適解を持つなら、双対問題も最適解を持ち、

c^\top x^\star = b^\top y^\star \quad (\text{双対ギャップ} = 0).

弱双対で「主 ≤ 双対」が常に成り立つ中で、LP では 等号まで到達できる。これは凸性と多面体の構造（あるいは分離超平面定理）から従う。非線形では一般にギャップが残る（凸最適化問題と双対理論）が、LP は常にギャップゼロという特別に強い性質を持つ。

相補性（complementary slackness）

最適 $(x^\star, y^\star)$ では、各 $i,j$ について：

y_i^\star \,(b_i - (Ax^\star)_i) = 0, \qquad x_j^\star \,((A^\top y^\star)_j - c_j) = 0.

意味：制約に余りがある（ $b_i - (Ax)_i > 0$ ）なら、その資源の影の価格 $y_i^\star = 0$ （余っている資源に値段はつかない）。逆に影の価格が正なら、その制約は等号で効いている（資源を使い切っている）。これがシンプレックス法の被約費用（シンプレックス法）と直結する。

Pythonで強双対を確認

生産計画 LP の主と双対を別々に解いて、最適値が一致するか見る。

from scipy.optimize import linprog

# 主: max 40xA+30xB s.t. 2xA+xB<=120, xA+xB<=100, x>=0
c = [-40, -30]
res_p = linprog(c, A_ub=[[2,1],[1,1]], b_ub=[120,100],
                bounds=[(0,None),(0,None)], method="highs")
print(f"主問題  最適利益 = {-res_p.fun:.0f}  (xA={res_p.x[0]:.0f}, xB={res_p.x[1]:.0f})")

# 双対: min 120y1+100y2 s.t. 2y1+y2>=40, y1+y2>=30, y>=0
res_d = linprog([120,100], A_ub=[[-2,-1],[-1,-1]], b_ub=[-40,-30],
                bounds=[(0,None),(0,None)], method="highs")
print(f"双対問題 最適コスト = {res_d.fun:.0f}  (y1={res_d.x[0]:.0f}, y2={res_d.x[1]:.0f})")
print(f"双対ギャップ = {res_d.fun - (-res_p.fun):.0f}")

実行結果：

主問題  最適利益 = 3200  (xA=20, xB=80)
双対問題 最適コスト = 3200  (y1=10, y2=20)
双対ギャップ = 0

主の利益 3200 と双対のコスト 3200 が一致（ギャップ0）。双対解 $y=(10,20)$ は資源（機械時間・材料）の影の価格で、感度分析でその意味を見る。両資源とも使い切っている（相補性で $y>0$ ）。

数式の直観的意味

双対変数 $y_i$ は「制約 $i$ の右辺 $b_i$ を1単位緩めたときの最適値の増分」＝資源の限界価値。弱双対の不等式 $c^\top x \le b^\top y$ は「どんな配分の利益も、資源を値付けした総価値を超えない」という会計恒等式に近い。強双対はその不等式が 最適点でぴったり等号になること、つまり「利益を最大化した状態では、資源は1円の無駄もなくその限界価値どおりに使われている」ことを意味する。相補性はその仕分けで、「余った資源は値0、使い切った資源は正の値」という当たり前を数式化したもの。

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

双対の双対は主。双対をもう一度取ると元に戻る。覚えると向きを間違えない。
強双対は LP では常に成立だが、非線形・非凸では一般に成立しない（Slater 等の条件が要る、凸最適化問題と双対理論）。
影の価格は局所的：右辺を大きく動かすと基底が変わり、価格も変わる（許容範囲がある、感度分析）。
主が非有界なら双対は実行不能、主が実行不能なら双対は非有界（または両方実行不能）。