双対線形計画問題
ある線形計画問題(LP1)に対して
minimize
c_1^Tx_1 + c_2^Tx_2
subject to
A_{11} x_1 + A_{12} x_2 \ge b_1
A_{21} x_1 + A_{22} x_2 = b_2
x_1 \ge 0
次の線形計画問題(LP2)を双対問題という
maximize
b_1^T y_1 + b_2^T y_2
subject to
A_{11}^Ty_1 + A_{21}^Ty_2 \le c_1
A_{12}^Ty_1 + A_{22}^Ty_2 = c_2
y_1 \ge 0
maximizeに変わってたり不等号の向きが変わってたりするので符号を反転してLP1に揃えることこうなる
minimize
-b_1^T y_1 - b_2^T y_2
subject to
-A_{11}^Ty_1 - A_{21}^Ty_2 \ge -c_1
-A_{12}^Ty_1 - A_{22}^Ty_2 = -c_2
y_1 \ge 0
LP1とLP2の変数の対応は下記のようになるので、この変換を2回行うと元に戻ることがわかる
変数対応
| LP1 | x1 | x2 | c1 | c2 | b1 | b2 | A11 | A12 | A21 | A22 | |
| LP2 | y1 | y2 | -b1 | -b2 | -c1 | -c2 | -A11^T | -A21^T | -A12^T | -A22^T |
よりシンプルな問題について
minimize
c^Tx
subject to
A x = b
x \ge 0
の双対問題は下記
minimize
-b^Ty
subject to
-A^T y \ge -c
変数対応
| x | c | b | A | ||||||||
| LP1 | x1 | x2 | c1 | c2 | b1 | b2 | A11 | A12 | A21 | A22 |
考え方
xに正の制約がついてるからこれはx1に対応
目的関数でx1の係数はc1
制約は等式で、x1に注目するとA21とb2
他の値は全部ゼロ
双対問題に代入する
A21が掛かるのはy2、これをyと呼ぶことにする
y2には正の制約はついてないことに注意
minimize
c_1x_1 + c_2x_2
subject to
a_{11} x_1 + a_{12} x_2 \ge b_1 \cdots (eq1)
a_{21} x_1 + a_{22} x_2 \ge b_2 \cdots (eq2)
x_1 \ge 0, x_2 \ge 0
y_1 \times eq1 + y_2 \times eq2 を考える(y_1 \ge 0, y_2 \ge 0)
(a_{11}y_1 + a_{21}y_2) x_1 + (a_{12} y_1 + a_{22} y_2) x_2 \ge b_1 y_1 + b_2 y_2
もし左辺が目的関数より小さいなら、目的関数は右辺より大きい
c_1x_1 + c_2x_2 \ge (a_{11}y_1 + a_{21}y_2) x_1 + (a_{12} y_1 + a_{22} y_2) x_2 \ge b_1 y_1 + b_2 y_2
なので右辺をなるべく大きくするようにyを選ぶと下記の線形計画問題になる
maximize
b_1y_1 + b_2y_2
subject to
c_1 \ge a_{11}y_1 + a_{21}y_2
c_2 \ge a_{12} y_1 + a_{22} y_2
y_1 \ge 0, y_2 \ge 0
ref:
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]