LP: Canonical form and standard form

Linear programs follow certain rules when writing it. A linear program that follows the rules is said to be canonical. The simplex algorithm can only be applied to linear programs in canonical form.

Canonical form

A linear program in its canonical form is:

  • A Maximization problem, under constraints Lower or equal, of which all the variables are strictly positive.
  • A Minimization problem, under constraints Superior or equal, of which all the variables are strictly positive.

If the linear program does not correspond to these criteria, the constraints or the objective function must be transformed according to the following operations:

  • max z = – min -z
  • x + y ≥ b is equivalent to – x – y ≤ – b
  • x + y = b is equivalent to x + y ≥ b, x + y ≤ b

The canonical form is often represented in its matrix form:

  • the vector of the coefficients of the objective function: c of size n
  • the matrix of the coefficients of the left part of the constraints: A of size m * n
  • the vector of the constants of the right part of the constraints: b of size m
  • the vector of variables: x of size n

Ainsi le programme linéaire suivant :

S’écrit sous la forme suivante :

Standard form

For each inequality constraint of the canonical form, we add a positive slack variable e such that:

Ax ≤ b ⇔ Ax + e = b, e ≥ 0, ici e est un vecteur de taille m de variables d’écarts.

Thus the canonical form is brought to the standard form by adding the slack variables in the variable vector:

  • the vector of the coefficients of the objective function: c of size n + m (n for x and m for e although the latter do not enter into the calculation)
  • the matrix of the coefficients of the left part of the constraints: Ã of size m * (n + m), the right part of the matrix being an Identity matrix of size m.
  • the vector of the constants of the right part of the constraints: b of size m
  • the vector of size variables n + m

Certain inequalities do not allow positive base variables to be obtained. For this it is necessary to add other variables called excess and artificial variables.

Here are the rules to follow to best transform the simplex into standard form:

  • « greater or equal » or « less than or equal with b negative » constraints: make b positive and add « – excess variable + artificial variable »
  • « equality » constraints: add « + artificial variable »
  • « less than or equal with b positive » constraints: add « + slack variable » as seen above.