双対線形計画問題

https://gyazo.com/448ff0eede42a3e7683c517b42b504bf

ある線形計画問題(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回行うと元に戻ることがわかる

table:変数対応

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

table:変数対応

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

$ (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: