Cours en version PDF — Course in PDF (english)
The simplex algorithm was introduced by George Dantzig in 1946. It is an algorithm which solves linear optimization problems.
It consists in minimizing a linear function of n real number variables,
where , on a set defined by affine (linear) constraints: equality and inequality. The admissible domain of the problem is a convex polyhedron.
Method
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:
- The problem is written in canonical form.
- A first solution is found.
- Find the pivot column.
- Find the pivot line and perform the Gauss method
- STOP. Optimal solution found or no solution possible.
Example
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 (x_{3}, x_{4}, x_{5}) in each of the constraints of the form ≤:
2·x_{1} + x_{2} + x_{3} = 18 |
2·x_{1} + 3·x_{2} + x_{4} = 42 |
3·x_{1} + x_{2} + x_{5} = 24 |
Then we put the objective function to zero: Z – 3·x_{1} – x_{2} – 0·x_{3} – 0·x_{4} – 0·x_{5} = 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.
First step | |||||||
---|---|---|---|---|---|---|---|
3 | 2 | ||||||
Base | Cb | b | x_{1} | x_{2} | x_{3} | x_{4} | x_{5} |
x_{3} | 9 | 18 | 2 | 1 | 1 | 0 | 0 |
x_{4} | 21 | 42 | 2 | 3 | 0 | 1 | 0 |
x_{5} | 8 | 24 | 3 | 1 | 0 | 0 | 1 |
Z | 0 | -3 | -2 | 0 | 0 | 0 |
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:
- We managed to get out all the artificial variables. We switch to simplex as shown in the example.
- If there are still artificial variables in the base (degenerate base) then the lines associated with these variables are redundant constraints that need to be eliminated.
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 x_{1} 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 x_{5}, 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):
- In the pivot element row, each new element is calculated as:
pivot line element = Old element / Pivot
- In the pivot column: 0 sauf le pivot à 1.
- In other element (cross product):
New element = Old element – (Old pivot line projection’s element *Old pivot columnprojection’s element / Old pivot element).
The following example show the change for the variable x_{4 }:
Previous line x_{4} | 42 | 2 | 3 | 0 | 1 | 0 |
– | – | – | – | – | ||
Cross product | 2*24 | 2*1 | 2*0 | 2*0 | 2*1 | |
/ | / | / | / | / | ||
pivot | 3 | 3 | 3 | 3 | 3 | |
= | devient | = | = | = | = | |
new line x_{4} | 26 | 0 | 7/3 | 0 | 1 | -2/3 |
The table corresponding to this second iteration is:
Second iteration | |||||||
---|---|---|---|---|---|---|---|
3 | 2 | 0 | 0 | 0 | |||
Base | Cb | b | x_{1} | x_{2} | x_{3} | x_{4} | x_{5} |
x_{3} | 0 | 2 | 0 | 1/3 | 1 | 0 | -2/3 |
x_{4} | 0 | 26 | 0 | 7/3 | 0 | 1 | -2/3 |
x_{1} | 0 | 8 | 1 | 1/3 | 0 | 0 | 1/3 |
Z | 24 | 0 | -1 | 0 | 0 | 1 |
STOP : stop conditions
If the goal is maximization, when in the last line (indicator line) there is no negative value among the reduced costs, the stopping condition is obtained.
The value of Z (column b) is the optimal solution of the problem. Another possible case is that in the column of the variable that goes in base all the values are negative or null. Faced with this situation it is not necessary to continue.
Without those conditions, we iterate the algorithm
4th iteration | |||||||
---|---|---|---|---|---|---|---|
3 | 2 | 0 | 0 | 0 | |||
Base | Cb | b | x_{1} | x_{2} | x_{3} | x_{4} | x_{5} |
x_{2} | 0 | 12 | 0 | 1 | -1/2 | 1/2 | 0 |
x_{5} | 0 | 3 | 0 | 0 | -7/4 | 1/4 | 1 |
x_{1} | 0 | 3 | 1 | 0 | 3/4 | -1/4 | 0 |
Z | 33 | 0 | 0 | 5/4 | 1/4 | 0 |
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 x_{5} = 3, ie the constraint 3 (containing the variance variable x_{5} ) is not saturated.
Algorithm (in french)