この記事について

これまで「双対問題の導出」「ラグランジュ緩和との対応」「3つの重要定理（弱双対・強双対・相補性条件）」を扱いました。理論は分かったけど、実用的に何の役に立つの？ という疑問はまだあるかと思います。（自分の理解整理などもありややあいまいなところもあるので何かあれば優しくご指摘もらえると嬉しいです。）

この記事では双対問題が活躍する3つの実用シーンを紹介します。

感度分析：入力データが変わるとどうなるか？
潜在価格（Shadow Price）：資源の経済的価値
双対単体法：再最適化を効率化する手法

生産計画問題の例

例として生産計画を扱います。

ある工場では3種類の原料（原料A、原料B、原料C）を使って、
3種類の製品（製品1、製品2、製品3）を製造している。
収益が最大となる各製品の1日当たりの製造量を求めよ。

原料	製品1	製品2	製品3	供給量
原料A	$a_{11}$	$a_{12}$	$a_{13}$	$b_1$
原料B	$a_{21}$	$a_{22}$	$a_{23}$	$b_2$
原料C	$a_{31}$	$a_{32}$	$a_{33}$	$b_3$
収益	$p_1$	$p_2$	$p_3$

主問題：

\begin{aligned}
\text{maximize} \quad & p_1 x_1 + p_2 x_2 + p_3 x_3 \\
\text{subject to} \quad & a_{11} x_1 + a_{12} x_2 + a_{13} x_3 \leq b_1 \quad \text{(原料A)} \\
& a_{21} x_1 + a_{22} x_2 + a_{23} x_3 \leq b_2 \quad \text{(原料B)} \\
& a_{31} x_1 + a_{32} x_2 + a_{33} x_3 \leq b_3 \quad \text{(原料C)} \\
& x_1, x_2, x_3 \geq 0
\end{aligned}

具体的な数値で解いてみます。

import pulp

# データ
p = [80, 60, 40]                      # 各製品の収益
A = [[4, 2, 1],                        # 原料A
     [2, 4, 2],                        # 原料B
     [1, 1, 2]]                        # 原料C
b = [100, 120, 80]                     # 供給量

# 主問題
P = pulp.LpProblem("Factory", pulp.LpMaximize)
x = [pulp.LpVariable(f"x{j+1}", lowBound=0) for j in range(3)]
P += pulp.lpSum(p[j] * x[j] for j in range(3))

constraints = []
for i in range(3):
    c = pulp.lpSum(A[i][j] * x[j] for j in range(3)) <= b[i]
    P += c
    constraints.append(c)

P.solve(pulp.PULP_CBC_CMD(msg=0))

print("=== 主問題 ===")
for j, var in enumerate(x):
    print(f"x{j+1} = {pulp.value(var):.2f}")
print(f"総収益: {pulp.value(P.objective):.2f}")

実行結果：

=== 主問題 ===
x1 = 13.33
x2 = 8.89
x3 = 28.89
総収益: 2755.56

1. 感度分析：どの資源を増やすのが最もお得か？

「原料の供給量を $\Delta_i$ 増やせるなら、どの原料を増やすのが最も収益を上げるか？」

これを定量化するのが感度分析です。

双対変数と最適値の関係

結論から言うと、双対変数の最適解 $y_i^$ が『資源 $i$ を 1 単位増やしたときの収益の増加量』を表すのですが、「なぜ双対変数 $y_i^$ が『資源 $i$ を 1 単位増やしたときの収益の増加量』を表すのか？」を3ステップで見ていきます。

ステップ1：強双対定理は何を言っているか

強双対定理より、主問題と双対問題の最適値は一致します：

z^* = \mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^* = \sum_i b_i y_i^*

これは「最適収益 $z^$ は、 **供給量 $b_i$ と双対変数 $y_i^$ の内積**で表せる」と読めます。$y_i^$ を「資源 $i$ の限界価値」と思えば、$b_i \times y_i^$ は「資源 $i$ 全体が生み出す価値」。各資源の価値の総和が最適収益と一致する、というのが強双対定理の経済的な意味です（手持ちの資源の価値が、生産で得られる収益にちょうど還元されるイメージです）。

ステップ2：供給量を少しだけ変えてみる

ここで原料 $i$ の供給量を $b_i \to b_i + \Delta_i$ と少し増やすと、新しい最適値はどうなるか？

ここでのキモは「変化が小さければ最適基底（どの制約が等号で効くか）は変わらない」ということです。最適基底が変わらないなら双対側の解 $y^*$ もそのまま使い回せます。よって新しい最適値は、

\sum_i (b_i + \Delta_i) y_i^* = \underbrace{\sum_i b_i y_i^*}_{= z^*} + \sum_i \Delta_i y_i^*
= z^* + \sum_i \Delta_i y_i^*

つまり「元の最適値」に「変化 $\Delta_i$ と双対変数 $y_i^*$ の内積」を足したものが新しい最適値になります。

ステップ3：原料 $i$ のみ 1 単位増やすと…

特に「原料 $i$ だけ 1 単位（$\Delta_i = 1$、他はゼロ）増やす」場合、最適値の増加量は単に $y_i^*$ そのものになります。微分で書けば：

\frac{\partial z^*}{\partial b_i} = y_i^*

具体例で見てみます。後で計算する双対解は

$y_1^* = 15.5556$（原料A）
$y_2^* = 5.5556$（原料B）
$y_3^* = 6.6667$（原料C）

このとき、

原料Aを 1 単位増やす → 収益は 約 15.5556 増える
原料Bを 1 単位増やす → 収益は約 5.5556 増える
原料Cを 1 単位増やす → 収益は約 6.6667 増える

実際に後の「## 数値で検証」セクションで $b_1$ を $100 \to 101$ に変えて解き直すと、最適値が $2755.5555 \to 2771.1111$ となり、ピッタリ 15.5556 増えることが確認できます。

潜在価格（Shadow Price）

\frac{\partial z^*}{\partial b_i} = y_i^*

この $y_i^*$ を 潜在価格（Shadow Price） または 限界価値 と呼びます。「制約資源 $i$ を 1 単位増やしたときの最適値の改善量」を表します。

実務的な解釈：

$y_i^* > 0$：制約 $i$ がボトルネック。資源を増やすと収益が上がる
$y_i^* = 0$：制約 $i$ は余裕がある。これを増やしても意味がない

PuLPで潜在価格を取得

PuLPでは制約オブジェクトの pi 属性で潜在価格が取れます。

print("=== 潜在価格（Shadow Price） ===")
names = ['原料A', '原料B', '原料C']
for i, c in enumerate(constraints):
    print(f"{names[i]}: y{i+1}* = {c.pi:.4f}")

print("\n=== どの資源を 1 単位増やすと収益が一番上がるか？ ===")
shadow_prices = [c.pi for c in constraints]
best = max(range(3), key=lambda i: shadow_prices[i])
print(f"→ {names[best]} を増やすべき（潜在価格 {shadow_prices[best]:.4f}）")

実行結果：

=== 潜在価格（Shadow Price） ===
原料A: y1* = 15.5556
原料B: y2* = 5.5556
原料C: y3* = 6.6667

=== どの資源を 1 単位増やすと収益が一番上がるか？ ===
→ 原料A を増やすべき（潜在価格 15.5556）

原料Aを 1 単位増やすと、約 15.5556 だけ収益が増えることが分かります。

数値で検証

実際に原料Aを 1 単位増やして解き直すと、収益がだいたい 15.5556 増えるはずです。

b_new = [101, 120, 80]   # 原料Aを +1
P2 = pulp.LpProblem("Factory_plus1", pulp.LpMaximize)
x2_vars = [pulp.LpVariable(f"x{j+1}", lowBound=0) for j in range(3)]
P2 += pulp.lpSum(p[j] * x2_vars[j] for j in range(3))
for i in range(3):
    P2 += pulp.lpSum(A[i][j] * x2_vars[j] for j in range(3)) <= b_new[i]
P2.solve(pulp.PULP_CBC_CMD(msg=0))

print(f"\n元の最適値: {pulp.value(P.objective):.4f}")
print(f"原料A+1 後の最適値: {pulp.value(P2.objective):.4f}")
print(f"差分: {pulp.value(P2.objective) - pulp.value(P.objective):.4f}")

実行結果：

元の最適値: 2755.5555
原料A+1 後の最適値: 2771.1111
差分: 15.5556

ぴったり潜在価格 15.5556 だけ収益が増えました。これが感度分析の力です。

2. 列生成法（Column Generation）：新しい商品を作るべきか？

「工場長が『新しい製品 X を作ろうか』と言ってきた。X 1 単位の生産に原料A $a'_1$、原料B $a'_2$、原料C $a'_3$ が必要で、収益は $p'$。生産する意味はあるか？」

このとき双対解 $\mathbf{y}^*$ がそのまま判定基準になります。

判定式

新しい製品を生産する場合、必要な原料の「潜在的コスト」は：

\text{潜在コスト} = a'_1 y_1^* + a'_2 y_2^* + a'_3 y_3^*

これと収益 $p'$ を比較：

\boxed{\sum_i a'_i y_i^* < p' \Rightarrow \text{生産すべき}}

意味：「原料を使うことで失う潜在収益」より「製品 X からの収益」が大きければ得をする、という直感的な判定式です。

PuLPで判定

# 候補製品 X：必要量とX 1単位あたりの収益
new_products = [
    {'name': '製品X', 'a': [3, 2, 1], 'p': 70},
    {'name': '製品Y', 'a': [2, 1, 3], 'p': 50},
    {'name': '製品Z', 'a': [1, 1, 1], 'p': 30},
]

print("=== 新製品生産判定 ===")
for w in new_products:
    cost = sum(w['a'][i] * shadow_prices[i] for i in range(3))
    profit = w['p']
    verdict = "生産すべき！" if profit > cost else "生産しても損"
    print(f"{w['name']}: 潜在コスト={cost:.2f}, 収益={profit}, → {verdict}")

実行結果：

=== 新製品生産判定 ===
製品X: 潜在コスト=64.44, 収益=70, → 生産すべき！
製品Y: 潜在コスト=56.67, 収益=50, → 生産しても損
製品Z: 潜在コスト=27.78, 収益=30, → 生産すべき！

これは 列生成法（Column Generation） という最適化手法の基本アイデアです。膨大な数の変数を持つLPを、必要な変数だけ動的に追加しながら解く方法で、大規模な配送問題や生産計画で広く使われています。

3. 双対単体法：再最適化を効率化

実務では「最適解を出した後で、入力データを少しだけ変えて解き直したい」という場面が頻繁にあります。これを 再最適化（Warm Start） と呼びます。

問題：右辺が変わると…

通常の単体法で得た最適基底解 $(\mathbf{x}_B^, \mathbf{x}_N^)$ は、制約の右辺 $\mathbf{b}$ が変わると：

\mathbf{x}_B^* = \mathbf{B}^{-1} \mathbf{b}

が負になることがあり、実行不能になります。一からやり直すのはコスト的に勿体ないです。

双対単体法のアイデア

ここで強双対定理を思い出します：主問題と双対問題は同じ最適基底に対応していました。

主問題が実行不能（$\mathbf{x}_B$ が負）になっても、双対側では引き続き実行可能だったりします。よって

1. 主問題の最適基底解の辞書を「転置」して双対側の辞書を得る
2. 双対側でピボット操作（単体法）を回して、再び実行可能にする
3. 双対側が最適 ⇔ 主側も最適

このように 「主問題が一時的に実行不能でも、双対側を実行可能に保ったまま再最適化」 するのが双対単体法です。

いつ双対単体法を使うか

制約の右辺 $\mathbf{b}$ を変更したとき
新しい制約を追加したとき（MIPの分枝限定法はこれを大量に行う）
MIPソルバーの分枝操作の各ノードで

これらの場面で双対単体法は単体法を一から回すより圧倒的に速いです。

Gurobi での指定

import gurobipy as gp

model = gp.Model()
# ... 問題定義 ...

model.setParam('Method', 1)   # 1 = 双対単体法
model.optimize()

Gurobiの Method パラメータ：

値	内容
0	主単体法（Primal Simplex）
1	双対単体法（Dual Simplex）
2	バリア法（内点法）
-1	自動選択

MIPソルバーの分枝限定法の内部では、ノードごとのLPを双対単体法で解くのが標準的です（前回の基底解を warm start として使えるため）。

まとめ

感度分析：双対変数 $y^*$ は制約の右辺 $b_i$ を 1 単位変えたときの最適値の変化率
潜在価格（Shadow Price）：$y_i^* > 0$ ならボトルネック、$y_i^* = 0$ なら余裕あり
列生成法：「新しい変数を追加すべきか」を $\sum a'_i y_i^* < p'$ で判定
双対単体法：右辺 $b$ や制約追加時の 再最適化に強い手法
商用ソルバーは Method パラメータで主/双対/内点法を切り替え可能