双対問題 (線形計画の)

【そうついもんだい (dual problem)】

線形計画問題 \[ \begin{array}{lll} \mbox{max.} & \displaystyle \sum_{j=1}^{n}c_jx_j & \\ \mbox{s.t.} & \displaystyle \sum_{j=1}^na_{ij}x_j\leq b_i & (i=1,2,\ldots,m), \\

           & x_j \geq 0\  & (j=1,2,\ldots,n)

\end{array} \] に対して, 以下の線形計画問題を双対問題と呼ぶ. 元の問題を主問題と呼ぶ. \[ \begin{array}{lllll} \mbox{min.} & \displaystyle \sum_{i=1}^{m}b_i y_i & \\ \mbox{s.t.} & \displaystyle \sum_{i=1}^na_{ij}y_i\geq c_j & (j=1,2,\ldots,n), \\

           & y_i \geq 0  &  (i=1,2,\ldots,m).

\end{array} \]