概要
双対問題とは，ある最適化問題の良い上界を求めるための問題をいいます．
ここでは最適化問題の例として線形計画問題を取り上げ，その双対問題について具体例を通して考えます．
線形計画問題とその双対問題
主問題（線形計画問題）
\begin{aligned}
\max_{x} \quad
& \sum_{j\in J}c_j x_j, \\
\text{s.t.} \quad
& \sum_{j \in J} D_{ij} x_j \le d_i, \, i \in I\\
& x_j \ge 0, \, j \in J
\end{aligned}
双対問題
\begin{aligned}
\min_{y} \quad
& \sum_{i \in I} d_i y_i, \\
\text{s.t.} \quad
& \sum_{i \in I} D_{ij} y_i \ge c_j, \, j \in J\\
& y_i \ge 0, \, i \in I
\end{aligned}
具体例
線形計画問題における主問題と双対問題の関係を，次の家具の製造計画の例を用いて説明します．
まず，作りたい家具 J（椅子，テーブル）と家具を作るのに使える資源 I （木材，労働時間）があるとします．
さらに，家具 j\in J を作ると c_j の利益が発生する一方で，資源 i\in I を D_{ij} だけ使うとします．
使える資源量は各資源 i ごとに d_i で与えられているとします．
ここまでの変数を整理すると以下の通りです．
- 集合
-
J: 家具（椅子，テーブル）
-
I: 資源（木材，労働人数）
- 問題設定
-
c_j: 家具 j を作成することによる利益
-
D_{ij}: 家具 i を作成するのに要する資源 j の量
-
d_i: 使うことのできる資源 i の量
ここで，限られた資源の中で，可能な限り多くの利益を得ることを考えます．家具 j の製造台数を x_j とすると，上記の主問題が得られます．
具体的な問題に落とし込むために，以下のような問題設定が与えられているとします．
| \ j
|
椅子(j=1) |
テーブル(j=2) |
| 利益 c_j [円/台] |
300 |
500 |
|
i \ j
|
椅子(j=1) |
テーブル(j=2) |
| 木材(i=1) [m^2/台] |
2 |
3 |
| 労働時間(i=2) [h/台] |
4 |
3 |
| i |
使用可能な資源量 d_i
|
| 木材(i=1) [m^2] |
10 |
| 労働時間(i=2) [h] |
35 |
この時，利益最大化を目的とする主問題は以下のように定式化されます．
\begin{aligned}
\max_{x_1, x_2} \quad
& 300 x_1 + 500 x_2 , \\
\text{s.t.} \quad
& 2x_1 + 3x_2 \le 10 \cdots ①,\\
& 4x_1 + 3x_2 \le 35 \cdots ②,\\
& x_1, x_2 \ge 0
\end{aligned}
ここで，ある非負変数 y_1, y_2 を導入し，制約①と②にかけて以下の不等式を得ます．
x_1 (2y_1 + 4y_2) + x_2 (3y_1 + 3y_2) \le 10y_1 + 35y_2
この式の左辺は主問題の目的関数と同じ形をしています．仮に，
\begin{aligned}
300 &\le 2y_1 + 4y_2 \cdots ③\\
500 &\le 3y_1 + 3y_2 \cdots ④
\end{aligned}
を満たすような y_1^*, y_2^* が存在すれば，
\begin{aligned}
300 x_1 + 500 x_2 \le x_1 (2y_1^* + 4y_2^*) + x_2 (3y_1^* + 3y_2^*) \le 10y_1^* + 35y_2^*
\end{aligned}
より，元の目的関数値の上限値を得ることができます．この上限値を上界といいます．
y_1^*, y_2^* の例として，(y_1^*, y_2^*)=(1000,1000) を考えると 10y_1^* + 35y_2^* = 45000 となり，得られる利益の最大値は 45000 [円]以下であることがわかります．
また，(y_1^*, y_2^*)=(100,100) を考えると，10y_1^* + 35y_2^* = 4500 となり，得られる利益の最大値は 4500 [円]以下であることがわかり，先ほどより精度良く上界を得ることができました．
このように，より良い上界を得ることは，主問題の最大値を精度良く見積もることに繋がります．
より良い上界を得るための問題を双対問題といいます．今回の例では，③④を満たす y_1, y_2 のうち，10y_1 + 35y_2 を最小化するようなものを求める問題であり，以下のように定式化されます．
\begin{aligned}
\min_{y_1, y_2} \quad
& 10y_1 + 35y_2 , \\
\text{s.t.} \quad
& 2y_1 + 4y_2 \ge 300 \cdots ③,\\
& 3y_1 + 3y_2 \ge 500 \cdots ④,\\
& y_1, y_2 \ge 0
\end{aligned}
最後に，双対問題を導出するために導入した変数 y_1, y_2 の解釈について考えます．
先ほどの双対問題において，省略していた単位を表示すると以下のようになります．
\begin{aligned}
\min_{y_1, y_2} \quad
& 10\,[m^2]\,y_1 + 35\,[h]\,y_2 , \\
\text{s.t.} \quad
& 2\,[m^2/\text{台}]\,y_1 + 4\,[h/\text{台}]\,y_2 \ge 300\,[\text{円/台}] \quad (③),\\
& 3\,[m^2/\text{台}]\,y_1 + 3\,[h/\text{台}]\,y_2 \ge 500\,[\text{円/台}] \quad (④),\\
& y_1, y_2 \ge 0
\end{aligned}
③④の式から，y_1 の単位は [円/m^2]，y_2 の単位は [円/h] であることがわかります．つまり双対問題を導出するために導入した変数は，各資源の単位量あたりの価値を表していることがわかります．
さらに，双対問題の目的関数は，使用可能な資源を全て使った場合の製造コストを表していることがわかります．
では，先ほどの例で (y_1^*, y_2^*)=(1000,1000) としていたのは，木材に適当な付加価値をつけ，さらに時給をとんでもなく釣り上げていたわけですね．（そりゃ儲けも出ます）
Discussion