Simplex method

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,

simplexe

where simplexe2, 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:

  1. The problem is written in canonical form.
  2. A first solution is found.
  3. Find the pivot column.
  4. Find the pivot line and perform the Gauss method
  • STOP. Optimal solution found or no solution possible.

simplex-method

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 (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.

First step
3 2
Base Cb b x1 x2 x3 x4 x5
x3 9 18 2 1 1 0 0
x4 21 42 2 3 0 1 0
x5 8 24 3 1 0 0 1
Z 0 -3 -2 0 0 0

Aside: Degeneration of the simplex

A feasible basic solution is called degenerate if at least one of the basic variables is equal to zero.
If during the simplex algorithm no encountered base is degenerate, then the algorithm ends in a finite number of iterations.
If there is a degenerate base, then we have a possible loop of the algorithm: we find a base already computed and we loop indefinitely. To treat cases of degeneracy, one can apply the rule of Bland (1977) which ensures the stop of the algorithm in a finite number of iteration.
When several variables are likely to enter or leave the base, we always choose the one with the smallest index.

aside: basic solution and degeneration

To obtain a feasible basic solution or to detect the impossibility, an auxiliary linear programming problem is introduced for slack variables with new ones called artificial variables.
Sans titre13.png
A (LP) admits a feasible solution if and only if the auxiliary problem (ALP) admits an optimal basic solution with a = 0. The simplex algorithm is applied to the auxiliary problem (PLA).

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:

  1. We managed to get out all the artificial variables. We switch to simplex as shown in the example.
  2. 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 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:

To divide each independent term (column b) with the corresponding element of the pivot column, provided that both elements are strictly positive (greater than zero). We choose the line whose result is minimal.

Following the previous example we obtain: Cb := 18/2 , 42/2 and 24/3.

If there is an element lower or equal to zero, we do not perform its quotient. When all the elements of the pivot column have this condition, we accomplishe the stop condition and the problem have a solution without bounded.

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):

  • 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 x4 :

Previous line x4 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 x4 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 x1 x2 x3 x4 x5
x3 0 2 0 1/3 1 0 -2/3
x4 0 26 0 7/3 0 1 -2/3
x1 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 x1 x2 x3 x4 x5
x2 0 12 0 1 -1/2 1/2 0
x5 0 3 0 0 -7/4 1/4 1
x1 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 x5 = 3, ie the constraint 3 (containing the variance variable x5 ) is not saturated.

Algorithm (in french)

simplex

 

Publicités