線形計画の主問題と双対問題

$A\in\mathbb{R}^{m\times n}$, $\boldsymbol{b}\in\mathbb{R}^m$, $\boldsymbol{c}\in\mathbb{R}^n$ に対し、主問題 (P) $\min\ \boldsymbol{c}^{\mathsf{T}}\boldsymbol{x}$ s.t. $A\boldsymbol{x}=\boldsymbol{b}$, $\boldsymbol{x}\ge\boldsymbol{0}$ と、双対問題 (D) $\max\ \boldsymbol{b}^{\mathsf{T}}\boldsymbol{y}$ s.t. $A^{\mathsf{T}}\boldsymbol{y}\le\boldsymbol{c}$ を考える。(P) の最適値を $p^\ast$ と書く。