Converting Linear Programs to Standard Form

In this course, standard form means a minimisation, with equality constraints, and every variable nonnegative. The definition can arrive immediately because the reason to want it is already familiar: the simplex method's basis, its reduced costs and its optimality test are all defined for that shape, so it is the representation in which those objects exist at all.

Other texts fix a maximisation, or admit inequalities, and call that standard form. None is more correct. A conversion is only well defined once the target is named.

Standard form is a convention, not a restriction on which problems can be solved.

The simplex method is described in terms of a system of equations with nonnegative variables, because that is the setting in which a basis and a basic feasible solution are defined. Rather than restate the method for every possible arrangement of constraints, the program is rewritten once into the shape the method expects.

Nothing about the underlying problem changes. The conversion adds bookkeeping variables and may flip the sign of the reported objective value, but the feasible decisions and which of them are best are preserved.

The definition above names three conditions. Each earns its place by what the simplex method needs, and none is arbitrary.

Equality constraints exist so a basis exists. A basis is a choice of $m$ columns of $A$ whose square submatrix is invertible, and that idea needs $Ax=b$ as a system of equations. With inequalities there is nothing to invert and no basic solution to speak of. Slack and surplus variables are how an inequality becomes an equation without changing which decisions are allowed.

Nonnegativity exists so a corner exists. Basic feasible solutions are the corners of the feasible region, and a variable is "at a corner" precisely when it sits at its bound of zero. Without $x\ge 0$ there is no bound to sit at, and the correspondence between bases and corners, the thing that makes a finite search possible, dissolves.

Minimization exists only for uniformity. Unlike the other two this one changes nothing structural; it means the optimality test can be stated once, with a single sign convention for reduced costs, rather than twice.

Why failing one condition is failing. The three are not a checklist where two out of three is nearly there. A program with equalities and nonnegative variables but a maximization objective will run through the algorithm and return the wrong sign. One with a minimization and equalities but a free variable has no basis at all for the simplex method to start from.

Note also what the definition does not require: it says nothing about $b\ge 0$. Many texts add that condition for the specific purpose of starting phase one with a feasible basis, and it is a separate matter from being in standard form.

Apply these four steps in order. Each addresses one of the three standard-form conditions.

Objective direction. If the objective is $max{c}^{\mathsf{T}}x$, replace it with $min(-c{)}^{\mathsf{T}}x$. The optimal solution set is unchanged; the optimal value changes sign, so report $-min(-c^{\mathsf{T}}x)$ as the original maximum.

Less-than-or-equal constraints. For $a_i^{\mathsf{T}}x\le b_i$, add a slack variable $s_i\ge 0$:

The slack measures unused capacity in that constraint.

Greater-than-or-equal constraints. For $a_i^{\mathsf{T}}x\ge b_i$, subtract a surplus variable $e_i\ge 0$:

The surplus measures the amount by which the requirement is exceeded.

Variables whose restriction is not simple nonnegativity. A variable unrestricted in sign, bounded below by a nonzero constant, or restricted to be nonpositive needs a substitution rather than an added variable: the unit on transforming the variables gives the substitution for each case, the constant a shift leaves in the objective, and the rule for recovering the original value afterwards.

After the substitutions, check that every variable in the program, original, slack, surplus, and substituted, carries a nonnegativity restriction.

Problem. Convert to standard form:

Goal. Produce an equivalent program that is a minimization, has only equality constraints, and has only nonnegative variables.

Relevant principle. Each standard-form condition is addressed by one transformation, and each transformation must be applied everywhere the affected quantity appears.

Step 1: objective direction. The objective is a maximization, so negate it: minimize $-3x_1-2x_2$.
Reason: minimizing the negation selects the same $x$ that maximizes the original.

Step 2: the $\le$ constraint. $x_1+x_2\le 4$ becomes $x_1+x_2+s_1=4$ with $s_1\ge 0$.
Reason: the slack absorbs the difference between the left side and the bound.

Step 3: the $\ge$ constraint. $x_1-x_2\ge 1$ becomes $x_1-x_2-e_1=1$ with $e_1\ge 0$.
Reason: the surplus is subtracted, because the left side is at least the bound and the excess must be removed to reach equality.

Step 4: the sign-unrestricted variable. $x_2$ carries no sign restriction, so substitute $x_2=x_2^{+}-x_2^{-}$ with $x_2^{+},x_2^{-}\ge 0$ in the objective and in both constraints. The substitution and its properties, in particular that the pair is not uniquely determined, belong to the unit on transforming the variables.

Result.

subject to

Check. The objective is a minimization; both constraints are equalities; all five variables are nonnegative. All three conditions hold.

Interpretation. If this program has minimum value $v$, the original maximization has maximum value $-v$. The original $x_2$ is recovered as $x_2^{+}-x_2^{-}$.

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\ge 1$ becomes $x_1-x_2-e_1=1$ with $e_1\ge 0$.

Incorrect. $x_1-x_2\ge 1$ becomes $x_1-x_2+s_1=1$ with $s_1\ge 0$.

Why the second fails: with $s_1\ge 0$, the equation forces $x_1-x_2=1-s_1\le 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\ge 0$.

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

The slack-and-surplus sign is the famous trap and it is treated on its own. These are the ones that survive getting that right.

A substitution applied in some places but not others. Replacing a free $x_j$ by $x_j^{+}-x_j^{-}$ is a renaming, so it must reach the objective and every constraint containing $x_j$, not only the constraints where its coefficient is positive, and not only the ones that looked like they needed attention. A substitution carried through three constraints out of four produces a program that is internally consistent, solves cleanly, and answers a different question.

A variable left without a nonnegativity restriction. Standard form requires it of every variable in the final program, introduced ones included. It is easy to convert all the constraints, introduce slacks and surpluses, and never state that they are nonnegative, at which point the program is not in standard form and the basis the simplex method expects does not exist.

The objective value reported without its sign flipped back. Maximizing $c^{\mathsf{T}}x$ becomes minimizing $(-c{)}^{\mathsf{T}}x$, and the two have optimal values differing by a sign. The optimal solution is the same $x$; the optimal value is not. Reporting the minimum of the converted program as the answer to the original maximization is a sign error that no constraint check will catch.

A shifted lower bound whose constant is dropped. Substituting $x_j=y_j+\ell$ leaves a constant $c_j\ell$ in the objective. The converted program's optimal value omits it, so recovering the original value means adding it back. The optimal solution is unaffected, which is exactly why the omission goes unnoticed.

Each of these leaves a program that is feasible, solvable and wrong. Standard form is a claim that the converted program has the same answer as the original, and that claim is what has to be checked, not merely that the result looks like standard form.

The worked conversion above showed all four steps. Here the scaffolding is removed a piece at a time.

First: the steps are named, you supply them.

(a) Is the objective already a minimization? (b) Which constraint needs a surplus, and which a slack? (c) Write the converted program and confirm every variable is nonnegative.

Answer: the objective is untouched; $x_1+x_2\ge 3$ takes a surplus, giving $x_1+x_2-e_1=3$; $x_1\le 6$ takes a slack, giving $x_1+s_1=6$. The program is $min5x_1+x_2$ subject to those two equalities with $x_1,x_2,e_1,s_1\ge 0$. Four variables, all restricted.

Then: no steps named.

Convert it, then say how the original optimal value is recovered from the converted one.

Answer: negate the objective to $min-2x_1+x_2$. Add a slack to the first constraint: $3x_1+x_2+s_1=12$. The bound $x_1\ge 2$ is a shifted lower bound, so substitute $x_1=y_1+2$ with $y_1\ge 0$, which turns the first constraint into $3y_1+x_2+s_1=6$ and the objective into $-2y_1+x_2-4$. Split the free $x_2=x_2^{+}-x_2^{-}$ throughout. The converted program minimizes $-2y_1+x_2^{+}-x_2^{-}-4$ subject to $3y_1+x_2^{+}-x_2^{-}+s_1=6$, all variables nonnegative.

Recovering the value takes both corrections: the shift contributed $-4$, and the negation flips the sign. If the converted minimum is $v$, the original maximum is $-v$. Dropping either correction is a silent error. The program still solves.