Full Conversion of an LP to Standard Form

A linear program in standard form has four properties: the objective is minimized, every constraint is an equality, every decision variable is non-negative, and every right-hand side is non-negative.

$$\min\ \mathbf{c}^T \mathbf{x} \quad \text{subject to} \quad A\mathbf{x} = \mathbf{b},\ \ \mathbf{x} \geq \mathbf{0},\ \ \mathbf{b} \geq \mathbf{0}.$$

Most LPs do not arrive in this form. We already know three transformations:

1. Max to min: replace $\max\ \mathbf{c}^T \mathbf{x}$ with $\min\ -\mathbf{c}^T \mathbf{x}$.
2. Slack for $\leq$: replace $\mathbf{a}^T \mathbf{x} \leq b$ with $\mathbf{a}^T \mathbf{x} + s = b,\ s \geq 0$.
3. Surplus for $\geq$: replace $\mathbf{a}^T \mathbf{x} \geq b$ with $\mathbf{a}^T \mathbf{x} - s = b,\ s \geq 0$.

Combining these three handles any LP whose variables are already non-negative and whose right-hand sides are already non-negative. For example,

$$\max\ 2x_1 + 5x_2 \quad \text{s.t.}\quad x_1 + x_2 \leq 7,\ \ 3x_1 - x_2 \geq 1,\ \ x_1, x_2 \geq 0$$

becomes

$$\min\ -2x_1 - 5x_2 \quad \text{s.t.}\quad x_1 + x_2 + s_1 = 7,\ \ 3x_1 - x_2 - s_2 = 1,\ \ x_1, x_2, s_1, s_2 \geq 0.$$

Free variables and negative right-hand sides require two further tools, which we develop next.