HOME

Standard form for Linear Programs

Table of Contents

What is standard form?

The Simplex Method, which is the procedure we will use for solving linear programs, is easiest to explain for linear programs that are in a fixed format we will call the standard form. A linear program in standard form looks like:

Maximize \( c_1 x_1 + c_2 x_2 + \cdots c_n x_n \)

subject to \[\begin{aligned} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n & \le b_1 \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n & \le b_2 \\ \vdots \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n & \le b_m \\ x_1, x_2, \ldots, x_n & \ge 0 \\ \end{aligned}\]

We can rewrite this is matrix form, by setting:

  • \( \mathbf{x} = (x_1, x_2, \ldots, x_n)^\top\),
  • \( \mathbf{c} = (c_1, c_2, \ldots, c_n)^\top\),
  • \( \mathbf{b} = (b_1, b_2, \ldots, b_m)^\top\), and
  • \(A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{pmatrix}\).

With those definitions we can write the LP as:

Maximize \( \mathbf{c} \cdot \mathbf{x} \)

subject to \(\left\{\begin{aligned} A \mathbf{x} & \le \mathbf{b} \\ \mathbf{x} & \ge 0 \\ \end{aligned}\right.\)

Characteristics of standard form LPs

  • They are about maximizing, not minimizing.
  • They have a positivity constraint for each variable.
  • The other constraints are all of the form “linear combination of variables \(\le\) constant”.

Converting a LP to standard form

You can always convert a LP to an equivalent one that is in standard form. There are several “errors” which you need to know how to fix.

“Error”: the objective function is to be minimized

This is easy: minimizing \( c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \) is the “same” as maximizing \( - c_1 x_1 - c_2 x_2 - \cdots - c_n x_n \).

In what sense is it the same? Well, the maximum value of the new objective function won’t be the same as the minimum of the old objective function, but it is predictable: it’s just minus the minimum of the old function. Also, the values of the variables that lead to the optimum stay the same.

“Error”: a constraint is lower bound

Also easy: you can replace \( a_{i1} x_1 + \cdots + a_{in} x_n \ge b_i \) with \( -a_{i1} x_1 - \cdots - a_{in} x_n \le - b_i \). This doesn’t change which values of the \(x_j\) satisfy the constraints.

“Error”: there is an equality constraint

An equality \( u = v \) is equivalent to the system of inequalities \( u \le v\) and \(u \ge v\). We can use the previous trick to turn those inequalities into something acceptable for a standard form LP. All together, an equality \( a_{i1} x_1 + \cdots + a_{in} x_n = b_i \) gets replaced by the pair of inequalities \[\begin{aligned} a_{i1} x_1 + \cdots + a_{in} x_n & \le b_i \\ -a_{i1} x_1 - \cdots - a_{in} x_n & \le -b_i \\ \end{aligned}\]

“Error”: a variable lacks a positivity constraint

The most subtle “error” a linear program can have that keeps from being in standard form is to have a variable that lacks a positivity constraint, such a variable is called free. We’ll explain two ways to fix that and why you probably only want to ever use the second way.

(Bad) strategy: divide and conquer

If a variable \(x\) is not constrained to be non-negative, in the optimal solution to the LP we don’t know if it should take a positive or negative value. So why not just try both ways? Here’s an example:

Maximize \(- 2x + 3y - 5z\)

subject to \[\begin{aligned} 7x - 5y + 6z & \le 10 \\ -2x + 8y - 4z & \le 3 \\ 9x - 2y - 5z & \le 4 \\ y, z & \ge 0 \\ \end{aligned}\]

This problem is almost in standard form, the only issue is that \(x\) is missing a positivity constraint. The maximum of the objective can be found as the maximum of two subproblems: one where we add the constraint \( x \ge 0 \) and one where we add instead \( x \le 0\):

(A) Maximize \(- 2x + 3y - 5z\)

subject to \[\begin{aligned} 7x - 5y + 6z & \le 10 \\ -2x + 8y - 4z & \le 3 \\ 9x - 2y - 5z & \le 4 \\ x, y, z & \ge 0 \\ \end{aligned}\]

(B) Maximize \(- 2x + 3y - 5z\)

subject to \[\begin{aligned} 7x - 5y + 6z & \le 10 \\ -2x + 8y - 4z & \le 3 \\ 9x - 2y - 5z & \le 4 \\ y, z & \ge 0 \\ x \le 0 \end{aligned}\]

Problem (B) can be recast in standard form by a change of variables: flipping the sign of \(x\), say, letting \( x' = -x \) it becomes:

(B’) Maximize \(2x' + 3y - 5z\)

subject to \[\begin{aligned} -7x' - 5y + 6z & \le 10 \\ 2x' + 8y - 4z & \le 3 \\ -9x' - 2y - 5z & \le 4 \\ x', y, z & \ge 0 \\ \end{aligned}\]

Later on we will learn how to solve this LPs, but for know I’ll just list the solutions:

  • For (A) the maximum is \( 1.125 \) (achieved, for example, for \(x = 0, y = 0.375, z = 0 \)).
  • For (B’) the maximum is \( 3 \) (achieved, for example, for \(x=1.5, y=0, z=0\)).

So the maximum for the original problem that had no positivity constraint for \(x\) is \( 3 \), and as this came from (B’), the maximum for the original problem will have a negative value of \(x\).

The main reason to avoid this strategy is that it creates a lot of extra work. Even in this example it turned solving one LP into solving two. But it gets worse if there are more variables lacking a positivity constraint: if we had \(k\) variables lacking a positivity constraint this strategy would have us solve one LP for every combination of signs of those \(k\) variables, that is, \(2^k\) different LPs!

Good Strategy: make a difference!

There is a way to turn an LP with free variables into just one equivalent LP via a change of variables. If \(x\) is free, we can set \(x = x' - x''\) where \( x', x'' \ge 0\) —a difference of non-negative numbers can have any sign at all!

Our example from above becomes the following LP in standard form:

Maximize \(- 2x' + 2x'' + 3y - 5z\)

subject to \[\begin{aligned} 7x' -7x'' - 5y + 6z & \le 10 \\ -2x' +2x'' + 8y - 4z & \le 3 \\ 9x' -9x'' - 2y - 5z & \le 4 \\ x', x'', y, z & \ge 0 \\ \end{aligned}\]

In what sense is this equivalent to the old LP? Well, given any values \( x', x'', y, z \) satisfying the constraints of the new LP, setting \( x = x'-x'' \) and keeping the value of \(y\) and \(z\) yields valid values for the original LP, with the same value for the objective functions. Conversely, if \(x,y,z\) are values satisfying the constraints of the original we can keep \(y\) and \(z\) and define non-negative \(x', x''\) as follows:

  • If \(x \ge 0\), we can take \( x' = x, x'' = 0\).
  • If \(x < 0\), we can take \( x' = 0, x'' = -x\).

This gets us values satisfying the constraints of the new LP, with the same value for the objective function. In particular, notice that the maximum of the objective functions will be the same for the original and the new LP.

Notice that there are infinitely many choices we could have made above when picking values for \(x'\) and \(x''\). For example, if \(x=-5\) we said take \(x'=0, x''=5\), but \(x'=10, x''=15\) would also work (since they are non-negative and \(x'-x''=x\)).

Omar Antolín Camarena