LP: large M method

Big M method

Lorsque le simplex possède des variables artificielles, il est possible de ne pas trouver de solution de départ évident (tester si l’origine est dans le definition field). Dans ce cas il faut trouver une solution de départ avec la méthode du grand M.

Cette méthode calcule un problème auxiliaire avant de résoudre le simplexe du linear program, c’est pourquoi on parle d’un simplexe en deux phases.

Why an artificial variable?

Avant d’expliquer comment obtenir une solution pour commencer le simplexe, il est important de comprendre pourquoi il est nécessaire de rajouter une variable artificielle en plus de la slack variable.

Take as an example the following linear program:

non-feasible origin degenerate simplex big M method artificial variable

Let's add the variance variables:

non-feasible origin degenerate simplex big M method artificial variable

The simplex starts by taking the base variables at zero, so with the following vector (0, 0, -19, 32). This is impossible because X3 cannot take a negative value. This is why a new variable must be added, which will therefore be artificial.

non-feasible origin degenerate simplex big M method artificial variable

Here the vector (0, 0, 0, 19, 32) is a feasible solution. But since it is an artificial variable, it must be possible to remove it from the Simplex in order to be able to find a global solution. It is therefore necessary that X5 = 0. To check if this is possible, we are looking to minimize X5.

Construction of Phase 1

We prepare in a similar way to the initial table of the Simplex method, but with some differences. By taking the previous example, we try to solve the following problem:

non-feasible origin degenerate simplex big M method artificial variable

We know that only X4 and X5 are in the base, so the first step is to express the objective function with the non-base variables (here X1, X2, X3). In the example, this is possible thanks to the first constraint.

The first step is to solve the following linear program:

non-feasible origin degenerate simplex big M method artificial variable

Phase 2

The second phase of the Two-Phase method is developed exactly like the Simplex method, except that before starting the iterations it is necessary to remove the columns corresponding to the artificial variables, and to reconstruct the original table.

  • Delete the columns of artificial variables: Si nous sommes parvenus à la conclusion que le problème initial a une solution, on doit préparer notre tableau pour la deuxième phase. Cette étape est très simple, il suffit de supprimer les colonnes correspondantes aux variables artificielles.
  • Reconstruction of the initial table: The initial array, in this case, remains roughly equal to the last array of the first phase. The line of the objective function should be modified only by that of the initial problem and recalculate the line Z (in the same way as in the first table of phase 1).

The stopping condition is the same as in the Simplex method. In other words, when in the indicator line none of the values of the reduced costs is negative (because we are in the case of a maximization).

The previous simplex gives for optimal solution Z = 0 with the vector (0, 19/3, 0, 20/3, 0). That means that it is possible to do without the artificial variable and that the solution found is in the space of definition of the initial problem (since X5 does not intervene and that it is out of base). The final solution gives the following simplex:

non-feasible origin degenerate simplex big M method artificial variable

The last step of phase 1 consists of taking the initial objective function (here -2X1 - X2) and replacing all the base variables with non-base variables (here X2 and X4 are in the base, X1 and X3 are outside the bases ).

We have for the first constraint X2 = 19/3 - 2 / 3X1 + 1 / 3X3, we can therefore rewrite the objective function by: Z = - 4 / 3X1 - 1 / 3X2 -19/3.

From this point, all the iterations, until reaching the optimal solution of the problem, show no difference with the Simplex method.

Simplex algorithm

Here is the revisited simplex algorithm:

non-feasible origin degenerate simplex big M method artificial variable two-phase simplex

 

To share
en_GBEN
%d bloggers like this: