Converting a Linear Program to Standard Form

Standard form requires a minimization objective, equality constraints, and nonnegative variables. Any linear program can be converted to an equivalent standard-form program by negating a maximization objective, introducing slack or surplus variables, and splitting free variables into a difference of two nonnegative variables.

Definition

In this course, standard form means a linear program written as $min c^{T} x$ subject to $A x = b$ and $x \geq 0$ : a minimisation, every constraint an equality, every decision variable nonnegative.

The qualifier is not pedantry. Other texts fix a maximisation, or admit inequality constraints, and call that standard form; none is more correct. A conversion is only well defined once the target shape is named, and the theory built on it, the basis, the reduced costs, the optimality test, is stated for this one.

Formal statement

$min c^{T} x subject to A x = b, x \geq 0$ , with $A$ an $m \times n$ matrix, $b \in R^{m}$ , and $c \in R^{n}$ .

Assumptions and scope

Converting a maximization objective by minimizing its negation preserves the set of optimal solutions; the optimal value changes sign.
A slack or surplus variable is itself a decision variable of the converted program and carries a nonnegativity restriction.
Splitting a free variable $x$ into $x^{+} - x^{-}$ with $x^{+}, x^{-} \geq 0$ does not determine $x^{+}$ and $x^{-}$ uniquely, so the converted program may have multiple optimal solutions representing the same original solution.

Worked material

Contrast

Slack and surplus are not interchangeable

The sign on the introduced variable is determined by the direction of the inequality, and getting it wrong changes the feasible set.

Correct. $x_{1} - x_{2} \geq 1$ becomes $x_{1} - x_{2} - e_{1} = 1$ with $e_{1} \geq 0$ .

Incorrect. $x_{1} - x_{2} \geq 1$ becomes $x_{1} - x_{2} + s_{1} = 1$ with $s_{1} \geq 0$ .

Why the second fails: with $s_{1} \geq 0$ , the equation forces $x_{1} - x_{2} = 1 - s_{1} \leq 1$ . That is the opposite restriction from the one the original constraint states. A point such as $x_{1} = 5, x_{2} = 0$ satisfies the original constraint but cannot satisfy the incorrect conversion for any $s_{1} \geq 0$ .

The reliable check is directional: a $\leq$ constraint has room left over, so you add the leftover; a $\geq$ constraint has an excess, so you subtract the excess.

Common errors

Common misconception

A greater-than-or-equal constraint is converted to an equality by adding a nonnegative variable, in the same way a less-than-or-equal constraint is.

Related units

Connected

Transforming the Variables (best taken before)
Extreme Points and Basic Feasible Solutions (used by)

Learn this topic

Converting Linear Programs to Standard Form

Used in

Linear Programming

Sources

Introduction to Linear Optimization (1997)

Converting a Linear Program to Standard Form

Assumptions and scope

Worked material

Slack and surplus are not interchangeable

Common errors

Related units

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history