双対問題 (線形計画の)

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

線形計画問題

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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}^{n}a_{ij}y_{i}\geq c_{j}&(j=1,2,\ldots ,n),\\&y_{i}\geq 0&(i=1,2,\ldots ,m).\end{array}}\,$