Big M method
When the simplex has artificial variables, it is possible not to find an obvious starting solution (test if the origin is in the definition field). In this case, a starting solution must be found using the big M method.
This method computes an auxiliary problem before solving the simplex of the linear program, which is why it is called a two-phase simplex.
Why an artificial variable?
Before explaining how to obtain a solution to start the simplex, it is important to understand why it is necessary to add an artificial variable in addition to the slack variable.
Take as an example the following linear program:
Let's add the gap variables:
The simplex starts by taking the base variables to zero, so with the next vector (0, 0, -19, 32). This is impossible because X3 cannot take a negative value. This is why it is necessary to add a new variable, which will therefore be artificial.
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 seek 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. Continuing the previous example, we seek to solve the following problem:
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:
Phase 2
The second phase of the Two Phases method is elaborated exactly like the Simplex method, except that before starting the iterations it is necessary to delete the columns corresponding to the artificial variables, and to reconstruct the original table.
- Delete the columns of artificial variables: If we have come to the conclusion that the initial problem has a solution, we need to prepare our table for the second phase. This step is very simple, you just have to delete the columns corresponding to the artificial variables.
- 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 preceding simplex gives for optimal solution Z=0 with the vector (0, 19/3, 0, 20/3, 0). This 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 basis). The final solution gives the following simplex:
The last step of phase 1 consists of taking the initial objective function (here -2X1 – X2) and replacing all the base variables with off-base variables (here X2 and X4 are in the base, X1 and X3 are off-base ).
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 simplex algorithm revisited:
