The simplex algorithm was introduced by George Dantzig in 1946. It is an algorithm which solves linear optimization problems.
The simplex method is an iterative method browsing the vertices of the convex polyhedron until the objective function can no longer be improved. The resolution process is as follows:
Take the following problem to apply the simplex method:
|Maximize||Z=3x + 2y|
|s.t.||2x + y ≤ 18|
|2x + 3y ≤ 42|
|3x + y ≤ 24|
|x ≥ 0 , y ≥ 0|
Step 1 : Canonique form and first solution
Inequations are transformed into equations with the addition of variance variables.
For this, we introduce a slack variable (x3, x4, x5) in each of the constraints of the form ≤:
|2·x1 + x2 + x3 = 18|
|2·x1 + 3·x2 + x4 = 42|
|3·x1 + x2 + x5 = 24|
Then we put the objective function to zero: Z – 3·x1 – x2 – 0·x3 – 0·x4 – 0·x5 = 0. It is possible to initialize the table of the simplex method.
The initial table of the simplex method is composed of all the coefficients of the decision variables of the original problem and the slackvariables.
Aside: Degeneration of the simplex
aside: basic solution and degeneration
At the end of this simplex (for ALP), the minimum cost is zero otherwise an impossibility for (LP) has been detected. If all went well (zero cost), we try to eliminate from the base all the artificial variables.
There are two cases:
Step 2-3 : incoming and outgoing variable for a base
First, we establish the variable that comes in base. For this purpose, we choose the column whose value in the Z line is the lowest of all the negatives. In this case, this would be the variable x1 of coefficient -3. The column of the variable that goes into base called pivot column (in green).
Once the incoming variable is obtained, we determine the outgoing variable. We make that decision thanks to the following test:
Following the previous example we obtain: Cb := 18/2 , 42/2 and 24/3.
The pivot column term that resulted in the smallest positive non-zero quotient in the previous division indicates the line of the deviation variable that comes out base. In this case, it turns out to be x5, of coefficient 3. This line is called pivot line (in red).
The intersection of the pivot line and the pivot column brings out the pivot element, in this case the 3.
Step 3 : refresh the table
The new coefficients of the table are calculated in the following way (Gaussian pivot):
The following example show the change for the variable x4 :
|Previous line x4||42||2||3||0||1||0|
|new line x4||26||0||7/3||0||1||-2/3|
The table corresponding to this second iteration is:
STOP : stop conditions
Without those conditions, we iterate the algorithm
We see that in the last line all the coefficients are positive. The optimal solution is: 33 with the solution vector (12, 3). The solution vector is determined by the value of b on the rows of the basic variables. Note that x5 = 3, ie the constraint 3 (containing the variance variable x5 ) is not saturated.
Algorithm (in french)