= Solution
{c}
If $A$ has $m$ rows and $n$ columns, attach a nonnegative <dual variable> $y_i$ to each of the $m$ upper-bound constraints. The <dual linear program> is
$$
\boxed{\text{minimise }\mathbf b^T\mathbf y
\quad\text{subject to }A^T\mathbf y\ge\mathbf c,\quad\mathbf y\ge\mathbf0.}
$$
Here $A^T$ is the <transpose> of $A$, and all <vector> inequalities hold componentwise. Nonnegative <dual variables> preserve the direction of the original inequalities when taking weighted sums.
Back to article page
