= Solution
Use the <standard maximum form of a linear program>
$$
\boxed{\max\{c^Tz:Az\leq b,\ z\geq0\}.}
$$
An arbitrary <linear program> can be converted by the following operations.
* Replace minimization of $c^Tx$ by maximization of $-c^Tx$, and negate the resulting optimal value when translating back. A constant term in the objective is recorded separately.
* Replace every unrestricted variable $x_j$ by $z_j^+-z_j^-$ with both new variables nonnegative. A nonpositive variable can instead be negated. A lower bound $x_j\geq\ell$ can be eliminated by writing $x_j=\ell+z_j$, $z_j\geq0$; other bounds remain <linear inequalities>.
* Multiply a $\geq$ row by $-1$. Replace an equality $a^Tx=b$ by the pair $a^Tx\leq b$ and $-a^Tx\leq-b$.
These substitutions preserve the attainable objective values, up to the stated sign and constant corrections, and map <feasible points> in both directions. An alternative standard-form convention uses $Az=b,z\geq0$: add a nonnegative <slack variable> to each upper-bound row, or subtract a nonnegative <surplus variable> from a lower-bound row. The inequality convention above is used in the remaining solutions.
Back to article page
