【そうついもんだい (dual problem)】
線形計画問題
max. ∑ j = 1 n c j x j s.t. ∑ j = 1 n a i j x j ≤ b i ( i = 1 , 2 , … , m ) , x j ≥ 0 ( j = 1 , 2 , … , n ) {\displaystyle {\begin{array}{lll}{\mbox{max.}}&\displaystyle \sum _{j=1}^{n}c_{j}x_{j}&\\{\mbox{s.t.}}&\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\leq b_{i}&(i=1,2,\ldots ,m),\\&x_{j}\geq 0\ &(j=1,2,\ldots ,n)\end{array}}\,}
に対して, 以下の線形計画問題を双対問題と呼ぶ. 元の問題を主問題と呼ぶ.
min. ∑ i = 1 m b i y i s.t. ∑ i = 1 n a i j y i ≥ c j ( j = 1 , 2 , … , n ) , y i ≥ 0 ( i = 1 , 2 , … , m ) . {\displaystyle {\begin{array}{lllll}{\mbox{min.}}&\displaystyle \sum _{i=1}^{m}b_{i}y_{i}&\\{\mbox{s.t.}}&\displaystyle \sum _{i=1}^{n}a_{ij}y_{i}\geq c_{j}&(j=1,2,\ldots ,n),\\&y_{i}\geq 0&(i=1,2,\ldots ,m).\end{array}}\,}
