LP の弱双対性と安全な下界

(P) の任意の実行可能解 $\boldsymbol{x}$ が $\boldsymbol{x}\le\bar{\boldsymbol{x}}$ を満たすことが分かっているとする。任意の $\boldsymbol{y}\in\mathbb{R}^m$ について $\boldsymbol{r}=\boldsymbol{c}-A^{\mathsf{T}}\boldsymbol{y}$ とおくと

とくに $\boldsymbol{y}$ が (D) の実行可能解なら $\boldsymbol{r}\ge\boldsymbol{0}$ で、$p^\ast\ge\boldsymbol{b}^{\mathsf{T}}\boldsymbol{y}$（弱双対性。この場合 $\bar{\boldsymbol{x}}$ は不要）。