双対線形計画問題

ある線形計画問題(LP1)に対して

• minimize
  • $c_1^T{x}_1+c_2^T{x}_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}^T{y}_1+A_{21}^T{y}_2\le c_1$
  • $A_{12}^T{y}_1+A_{22}^T{y}_2=c_2$
  • $y_1\ge 0$ maximizeに変わってたり不等号の向きが変わってたりするので符号を反転してLP1に揃えることこうなる
• minimize
  • $-b_1^T{y}_1-b_2^T{y}_2$
• subject to
  • $-A_{11}^T{y}_1-A_{21}^T{y}_2\ge -c_1$
  • $-A_{12}^T{y}_1-A_{22}^T{y}_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^{T}x$

• subject to

  • $Ax=b$
  • $x\ge 0$ の双対問題は下記

• minimize

  • $-b^{T}y$

• 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_1{x}_1+c_2{x}_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_1{x}_1+c_2{x}_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_1{y}_1+b_2{y}_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$

LP双対 双対LP 線形計画法 線形計画問題 ref:

• 学習用テキスト 線形計画法 (2) 双対問題と双対定理

集合カバー 整数計画法 緩和線形計画法 プライマルデュアル法の適用 http://www.akita-pu.ac.jp/system/elect/ins/kusakari/japanese/teaching/InfoMath/2008/note/14.pdf