= Solution
{c}
With primal constraints $Ax=b$, the dual variable is unrestricted in sign:
$$
\boxed{\text{minimize }b^Ty
\quad\text{subject to }A^Ty\geq c,\quad y\in\mathbb R^m.}
$$
Membership of $x$ in the <nonnegative orthant> still yields $c^Tx\leq y^TAx$, but the next step is now the equality $y^TAx=y^Tb$, so no sign condition on $y$ is needed. Equivalently an equality constraint can be replaced by two opposite inequalities whose nonnegative multipliers combine into one free multiplier.
Back to article page
