はじめに
前回記事では、LPの単体法・内点法を実装し、PuLPで双対変数（Shadow Price）を取り出しました。その際、双対変数は「制約を1単位緩めたときの目的関数の増加量」とだけ説明しました。
本記事ではこの双対変数の意味を双対性の理論から丁寧に解説します。双対性はLPの最も重要な性質の一つであり、「主問題を解くことと双対問題を解くことが実は同じ問題を別の角度から見ていることに相当する」という深い対称性を持っています。
さらに双対性はハンガリアン法（割り当て問題の最適化アルゴリズム）の理論的基盤でもあります。ハンガリアン法の各操作は双対性の直接の応用であり、双対性を理解することでハンガリアン法が「なぜその操作をするのか」が自然に見えてきます。
本記事で扱うこと
- 双対問題の導出と意味
- 弱双対定理・強双対定理
- 相補性条件
- Shadow Priceの意味とStreamlitデモによる可視化
- ハンガリアン法への接続（双対変数→行ラベル・列ラベル、相補性条件→等号ペア探索）
本記事で扱わないこと
- ハンガリアン法の実装（次回記事で扱います）
- 3変数以上の大規模LPの双対問題
- 双対性の厳密な数学的証明
実装コードはGitHubで公開しており、Streamlit CloudによるインタラクティブなデモURLも公開しています。
- GitHub：https://github.com/Haru8-8/linear-programming
- デモ：https://linear-programming-2pvb8twbvxf7es4gvrwwh6.streamlit.app/
双対問題とは
主問題の復習
前回記事と同じ生産計画問題を使います。
$$\max \quad 3x_1 + 5x_2$$
$$\text{s.t.} \quad 2x_1 + x_2 \leq 20 \quad \text{（機械時間）}$$
$$\quad x_1 + 3x_2 \leq 24 \quad \text{（人員時間）}$$
$$x_1, x_2 \geq 0$$
これを 主問題（Primal） と呼びます。
双対問題の導出
この主問題に対して、対応する 双対問題（Dual） が存在します。双対問題は「主問題の制約に重みをつけて目的関数の上界を作る」という考え方から導かれます。主問題の制約に重み $y_1, y_2 \geq 0$ をかけて足し合わせると：
$$y_1(2x_1 + x_2) + y_2(x_1 + 3x_2) \leq 20y_1 + 24y_2$$
左辺を $x_1$ と $x_2$ でまとめると：
$$(2y_1 + y_2)x_1 + (y_1 + 3y_2)x_2 \leq 20y_1 + 24y_2$$
これが主問題の目的関数 $3x_1 + 5x_2$ を上から抑えるには：
$$3x_1 + 5x_2 \leq (2y_1 + y_2)x_1 + (y_1 + 3y_2)x_2 \leq 20y_1 + 24y_2$$
この不等式が成立するための条件は $2y_1 + y_2 \geq 3$、$y_1 + 3y_2 \geq 5$ です。この条件を制約として上界 $20y_1 + 24y_2$ を最小化する問題が双対問題です。双対変数 $y_1$（機械時間）、$y_2$（人員時間）を導入すると：
$$\min \quad 20y_1 + 24y_2$$
$$\text{s.t.} \quad 2y_1 + y_2 \geq 3$$
$$\quad y_1 + 3y_2 \geq 5$$
$$y_1, y_2 \geq 0$$
変換規則は以下の通りです。
| 主問題 | 双対問題 |
|---|---|
| $\max$ | $\min$ |
| 制約の数（2本） | 双対変数の数（$y_1, y_2$） |
| 変数の数（$x_1, x_2$） | 制約の数（2本） |
| 目的関数係数（3, 5） | 双対制約のRHS |
| 制約のRHS（20, 24） | 双対目的関数係数 |
| 係数行列 $A$ | 転置 $A^T$ |
双対問題の意味
主問題は「製品をいくつ作るか」を決める工場経営者の問題です。
双対問題の立場は 「リソースを買い取りたい外部業者」 です。工場経営者に「機械時間・人員時間を全部売ってください」と交渉する人で、$y_1$ は機械時間1単位あたりの買い取り価格、$y_2$ は人員時間1単位あたりの買い取り価格を表します。機械時間の上限は20時間、人員時間の上限は24時間なので、リソースの買い取り総額は $20y_1 + 24y_2$ です。外部業者の目標は「できるだけ安く買い取る」＝ $\min\ 20y_1 + 24y_2$ です。
外部業者が工場経営者を説得するには「自分で製品を作るより、リソースを売った方が得」と思わせる必要があります。製品Aを1個作るには機械時間2単位・人員時間1単位を消費して利益3が得られます。経営者が「リソースを売る」を選ぶには、そのリソースを売った収入が自分で作った利益以上でなければなりません。
$$2y_1 + y_2 \geq 3$$
主問題の制約は $\leq$ でしたが、双対問題の制約は $\geq$ になっています。これは主問題が「リソースの消費量が上限以下」であるのに対し、双対問題は「リソースの売却収入が製品の利益以上」でなければ経営者が売る動機を持たないためです。製品Bについても同様に $y_1 + 3y_2 \geq 5$ が成立します。
なお、双対問題の制約 $2y_1 + y_2 \geq 3$、$y_1 + 3y_2 \geq 5$ を満たしている状態を双対実行可能性と言います。前回記事の内点法のKKT条件で登場した「双対実行可能性」はこの条件のことです。最適解では主問題・双対問題ともに実行可能であり、かつ強双対定理より目的関数値が一致します。
弱双対定理・強双対定理
弱双対定理
双対問題の導出の中で既に確認した通り、主問題の任意の実行可能解 $x$ と双対問題の任意の実行可能解 $y$ に対して、以下が常に成立します。
$$3x_1 + 5x_2 \leq 20y_1 + 24y_2$$
これを一般化したものが弱双対定理です。双対問題をそのように定義したため成り立つのは自然ですが、定理として名前を与えることで「主問題と双対問題の目的関数値の間には常に大小関係がある」という性質を明確に位置づけることができます。
主問題は下から最大値を目指し、双対問題は上から最小値を目指している構造になっています。つまり双対問題は「主問題の目的関数値をできるだけ小さく上から抑える値を探している」問題です。
\underbrace{0 \leq \cdots}_{\text{主問題が上げてくる}} \longrightarrow \quad ? \quad \longleftarrow \underbrace{\cdots}_{\text{双対問題が下げてくる}}
強双対定理
弱双対定理では主問題と双対問題の間にギャップがある可能性がありました。LPが実行可能でかつ最適解を持つとき、主問題と双対問題の目的関数値が一致します。
$$\text{LPが実行可能でかつ最適解を持つとき} \quad 3x_1 + 5x_2 = 20y_1 + 24y_2$$
最適解では主問題と双対問題の目的関数値が一致します。 主問題が下から上げてくる値と、双対問題が上から下げてくる値が必ず同じ点で出会います。
\underbrace{0 \leq \cdots}_{\text{主問題が上げてくる}} \longrightarrow \quad 49.6 \quad \longleftarrow \underbrace{\cdots}_{\text{双対問題が下げてくる}}
実際に確認します。主問題の最適解は $x_1=7.2, x_2=5.6$、目的値49.6です。PuLPで取得した双対変数は $y_1=0.8, y_2=1.4$ でした。
$$20 \times 0.8 + 24 \times 1.4 = 16 + 33.6 = 49.6 \quad \checkmark$$
Streamlitデモのページ2では制約パラメータをスライダーで変えながら、この等式がリアルタイムに成立することを確認できます。
相補性条件
強双対定理より、最適解では主問題と双対問題の目的関数値が一致します。この一致から、最適解において必ず成立する条件が導かれます。それが相補性条件です。
$$s_i \cdot y_i = 0 \quad \text{（各制約について）}$$
$s_i$ は主問題のスラック変数、$y_i$ は双対変数です。ここでは双対変数を「制約を1単位緩めたときの目的関数の増加量」という角度で捉えます。この条件は「制約に余裕がないか、その制約を緩めるメリットがゼロかのどちらかが必ず成立する」ことを意味します。
- 制約が等号で活きている（$s_i = 0$、余裕なし）→ 制約を緩めれば目的関数が改善できるので $y_i > 0$
- 制約に余裕がある（$s_i > 0$）→ 制約をわざわざ緩めても最適解は変わらないので $y_i = 0$
直感的に言うと、「すでに余っている制約を緩めても意味がない」ということです。余裕のある制約の上限をいくら増やしても最適解は変わらないため、その双対変数は0になります。
今回の最適解 $(7.2, 5.6)$ で確認します。
$$2(7.2) + 5.6 = 20 \quad \Rightarrow \quad s_1 = 0 \quad \Rightarrow \quad y_1 = 0.8 > 0 \quad \checkmark$$
$$7.2 + 3(5.6) = 24 \quad \Rightarrow \quad s_2 = 0 \quad \Rightarrow \quad y_2 = 1.4 > 0 \quad \checkmark$$
両制約とも余裕なしで活きているので、制約を緩めるメリットがあり両方の双対変数が正です。$s_1 \cdot y_1 = 0 \times 0.8 = 0$、$s_2 \cdot y_2 = 0 \times 1.4 = 0$ が成立しています。
Shadow Priceの意味と可視化
Shadow Priceとは
双対変数 $y_i$ はShadow Priceとも呼ばれます。Shadow Priceは「制約の右辺（リソースの上限）を1単位増やしたときの目的関数の増加量」です。
今回の問題では：
- 機械時間の上限を20→21に増やすと、最大利益が $0.8$ 増える（$y_1 = 0.8$）
- 人員時間の上限を24→25に増やすと、最大利益が $1.4$ 増える（$y_2 = 1.4$）
つまりどちらのリソースを増やすと効果的かがShadow Priceを見るだけで分かります。今回は人員時間の方が機械時間より効果が大きいため、人員時間を優先して増やすべきという意思決定に使えます。
PuLPでのShadow Priceの取得
前回記事で示した通り、PuLPでは .pi 属性でShadow Priceを取得できます。
print(f"Shadow Price（機械時間）: {prob.constraints['machine'].pi}")
print(f"Shadow Price（人員時間）: {prob.constraints['labor'].pi}")
実行結果：
Shadow Price（機械時間）: 0.8
Shadow Price（人員時間）: 1.4
Streamlitデモでの可視化
Streamlitデモのページ2では制約の右辺をスライダーで変えながら以下を確認できます。
- Shadow Priceがリアルタイムで更新される
- リソース上限と最大利益の関係グラフ（Shadow Priceが傾きに対応している）
- 強双対定理の確認（主問題の最適値 = $b_1y_1 + b_2y_2$ が常に成立）
- 相補性条件の確認（$s_i \cdot y_i = 0$ が常に成立）
リソース上限と最大利益の関係グラフでは、グラフの傾きがShadow Priceに対応しています。ただしShadow Priceが有効なのはある範囲内だけです。制約を大きく緩めると別の制約がボトルネックになり、Shadow Priceが変化します。この範囲を感度分析と呼びますが、本記事では詳細は省略します。
ハンガリアン法への接続
このセクションで示すこと
ここまで生産計画問題を例に双対性・強双対定理・相補性条件を学びました。これらはLPの理論ですが、実はハンガリアン法（割り当て問題の最適化アルゴリズム）の理論的基盤でもあります。このセクションでは割り当て問題をLP定式化し、その双対問題と相補性条件がハンガリアン法の各操作にどう対応するかを示します。
割り当て問題のLP定式化
4人の作業者を4つのタスクに1対1で割り当てるとき、総コストを最小化する問題を考えます。$x_{ij} \in \{0,1\}$（作業者 $i$ をタスク $j$ に割り当てるなら1）として：
$$\min \sum_{i}\sum_{j} c_{ij} x_{ij}$$
$$\text{s.t.} \quad \sum_j x_{ij} = 1 \quad \forall i \quad \text{（各作業者は1タスクのみ）}$$
$$\sum_i x_{ij} = 1 \quad \forall j \quad \text{（各タスクは1人のみ）}$$
$$x_{ij} \in {0,1}$$
整数制約がついているのでMIPですが、割り当て問題の係数行列は全単模行列（totally unimodular）という特殊な性質を持つため、$x_{ij} \geq 0$ に緩和してもLP最適解が自動的に整数値になります。つまりLP緩和＝整数解が保証されています。
双対問題への変換
行ラベル $u_i$（作業者 $i$ の双対変数）、列ラベル $v_j$（タスク $j$ の双対変数）を導入すると、双対問題は：
$$\max \sum_i u_i + \sum_j v_j$$
$$\text{s.t.} \quad u_i + v_j \leq c_{ij} \quad \forall i,j$$
主問題がコストの最小化なので、双対問題はコストの内訳合計の最大化になります。$u_i$ は作業者 $i$ 側に割り当てるコストの内訳、$v_j$ はタスク $j$ 側に割り当てるコストの内訳です。制約 $u_i + v_j \leq c_{ij}$ は「内訳の合計が実際のコストを超えてはならない」という条件です。強双対定理より最適解では内訳合計の最大値と実際の割り当てコストの最小値が一致します。
$$\sum_{i,j} c_{ij} x_{ij} = \sum_i u_i + \sum_j v_j$$
相補性条件とハンガリアン法の核心
生産計画問題の相補性条件はスラック変数と双対変数の積がゼロでした（$s_i \cdot y_i = 0$）。割り当て問題は等式制約なのでスラック変数がありません。代わりに $x_{ij}$ が「割り当てるかどうか」の変数なので、相補性条件は「割り当てられたペア（$x_{ij} > 0$）では双対ギャップがゼロ」という形になります。
$$x_{ij} > 0 \quad \Rightarrow \quad u_i + v_j = c_{ij}$$
つまり実際に割り当てられたペアでは等号が成立します。$\bar{c}_{ij} = c_{ij} - u_i - v_j$ と定義すると、最適割り当てのペアでは必ず $\bar{c}_{ij} = 0$ になります。
これがハンガリアン法の核心です。
$$\text{最適割り当て} \subseteq {\bar{c}_{ij} = 0 \text{ となるペア}}$$
ハンガリアン法は「双対実行可能性（$u_i + v_j \leq c_{ij}$）を保ちながら、$\bar{c}_{ij} = 0$ となるペアだけを使って全作業者・全タスクを1対1で対応させる」アルゴリズムです。完全マッチングが見つからない場合は双対変数を更新して新しい $\bar{c}_{ij} = 0$ のペアを生み出し、再度マッチングを試みます。
LP双対性との対応まとめ
| LP双対性 | ハンガリアン法 |
|---|---|
| 双対変数 $y_i$ | 行ラベル $u_i$・列ラベル $v_j$ |
| 双対実行可能性 | $u_i + v_j \leq c_{ij}$ |
| 相補性条件 | 等号ペア（$\bar{c}_{ij}=0$）のみで割り当て |
| 双対変数の更新 | $\delta$ だけずらして新しい等号ペアを生成 |
| 強双対定理 | 最適割り当てコスト $= \sum u_i + \sum v_j$ |
ハンガリアン法は「双対実行可能性を保ちながら相補性条件を満たす完全マッチングを拡大する」アルゴリズムであり、LP双対性の直接の応用です。次回記事ではこの理論を踏まえてハンガリアン法を実装します。
おわりに
まとめ
- 主問題（利益最大化）に対して双対問題（リソース買い取りコスト最小化）が対応します。双対問題は「主問題の制約に重みをつけて目的関数の上界を作る」という考え方から導かれ、主問題の制約数が双対変数の数になり、係数行列が転置されます
- 弱双対定理より主問題の目的関数値は常に双対問題の目的関数値以下になります。主問題は下から最大値を目指し、双対問題は上から最小値を目指す構造です
- 強双対定理よりLPが実行可能でかつ最適解を持つとき、主問題と双対問題の目的関数値が一致します。双対ギャップがゼロになることはPuLPとStreamlitデモでリアルタイムに確認できます
- 相補性条件（$s_i \cdot y_i = 0$）より、制約に余裕がない場合はShadow Priceが正になり、余裕がある場合はShadow Priceがゼロになります
- ハンガリアン法は割り当て問題をLP定式化したときの双対性・相補性条件の直接の応用です。双対実行可能性（$u_i + v_j \leq c_{ij}$）を保ちながら相補性条件（$\bar{c}_{ij} = 0$ となるペアのみで割り当て）を満たす完全マッチングを探すアルゴリズムです
次回記事ではこの理論を踏まえてハンガリアン法を実装します。
実装コードはGitHubで公開しており、Streamlit CloudによるインタラクティブなデモURLも公開しています。ぜひ触ってみてください。