The Simplex Method or Solving Linear

Program

Frédéric Giroire

FG Simplex 1/20
Motivation

• Most popular method to solve linear programs.

• Principle: smartly explore basic solutions (corner point solutions),

improving the value of the solution.

FG Simplex 2/20
The simplex

Start with a problem written under the standard form.

Maximize 5x1 + 4x2 + 3x3

Subject to :
2x1 + 3x2 − x3 ≤ 5
4x1 + x2 − 2x3 ≤ 11
3x1 + 4x2 − 2x3 ≤ 8
x1 , x2 , x3 ≥ 0.

FG Simplex 3/20
The simplex

First step: introduce new variables, slack variables.

2x1 + 3x2 + x3 ≤ 5

We note x4 the slack (difference) between the right member and 5,

that is
x4 = 5 − 2x1 − 3x2 − x3 .

The inequation can now be written as

x4 ≥ 0.

FG Simplex 4/20
The simplex

Similarly, for the 2 others inequalities:

4x1 + x2 − 2x3 ≤ 11
3x1 + 4x2 − 2x3 ≤ 8

We define x5 and x6 :

x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3

And the inequalities can be written as

x5 ≥ 0, x6 ≥ 0.

FG Simplex 5/20
The simplex

To summarize, we introduce three slack variables x4 , x5 , x6 :

x4 = 5 − 2x1 − 3x2 − x3
x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3
z = 5x1 + 4x2 + 3x3 .

The problem can be written as:

Maximize z subject to x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.

slack variables x4 , x5 , x6 decision variables x1 , x2 , x3 . The two

problems are equivalent.

FG Simplex 6/20
The simplex

Second step: Find an initial solution.

In our example, x1 = 0, x2 = 0, x3 = 0 is feasible.
We compute the value of x4 , x5 , x6 .

x4 = 5 − 2x1 − 3x2 − x3 = 5

Similarly, x5 = 11 and x6 = 8.
We get an initial solution

x1 = 0, x2 = 0, x3 = 0, x4 = 5, x5 = 11, x6 = 8

of value z = 0

FG Simplex 7/20
The simplex

Dictionary:

x4 = 5 − 2x1 − 3x2 − x3
x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3
z = 5x1 + 4x2 + 3x3 .

Basic variables: x4 , x5 , x6 , variables on the left.

Non-basic variable: x1 , x2 , x3 , variables on the right.
A dictionary is feasible if a feasible solution is obtained by setting all
non-basic variables to 0.

FG Simplex 8/20
The simplex

Dictionary:

x4 = 5 − 2x1 − 3x2 − x3
x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3
z = 5x1 + 4x2 + 3x3 .

Basic variables: x4 , x5 , x6 , variables on the left.

Non-basic variable: x1 , x2 , x3 , variables on the right.
A dictionary is feasible if a feasible solution is obtained by setting all
non-basic variables to 0.

FG Simplex 8/20
The simplex

Simplex strategy: find an optimal solution by successive

improvements.
Rule: we increase the value of the variable of largest positive
coefficient in z.

x4 = 5 − 2x1 − 3x2 − x3
x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3
z = 5 x1 + 4x2 + 3x3 .
Here, we try to increase x1 .

FG Simplex 9/20
The simplex

How much can we increase x1 ?

x4 = 5 − 2x1 − 3x2 − x3
x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3
z = 5x1 + 4x2 + 3x3 .

We have x4 ≥ 0 .
5
It implies 5 − 2x1 ≥ 0, that is x1 ≤ .
2

FG Simplex 10/20
The simplex

How much can we increase x1 ?

x4 = 5 − 2x1 − 3x2 − x3
x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3
z = 5x1 + 4x2 + 3x3 .

We have x4 ≥ 0 .
It implies 5 − 2x1 ≥ 0, that is x1 ≤ 5/2 .
Similarly,
x5 ≥ 0 gives x1 ≤ 11/4.
x6 ≥ 0 gives x1 ≤ 8/3.

FG Simplex 11/20
The simplex

How much can we increase x1 ?

x4 = 5 − 2x1 − 3x2 − x3
x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3
z = 5x1 + 4x2 + 3x3 .

We have x4 ≥ 0 .
It implies 5 − 2x1 ≥ 0, that is x1 ≤ 5/2 Strongest constraint
Similarly,
x5 ≥ 0 gives x1 ≤ 11/4.
x6 ≥ 0 gives x1 ≤ 8/3.

FG Simplex 12/20
The simplex

How much can we increase x1 ?

x4 = 5 − 2x1 − 3x2 − x3
x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3
z = 5x1 + 4x2 + 3x3 .

We have x4 ≥ 0 .
It implies 5 − 2x1 ≥ 0, that is x1 ≤ 5/2 Strongest constraint

We get a new solution: x1 = 5/2, x4 = 0

with better value z = 5 · 5/2 = 25/2.
We still have x2 = x3 = 0 and now x5 = 11 − 4 · 5/2 = 1,
x6 = 8 − 3 · 5/2 = 1/2

FG Simplex 13/20
The simplex

We build a new feasible dictionary.

x4 = 5 − 2x1 − 3x2 − x3
x5 = 11 − 4x1 − x2 − 2x3
x6 = 8 − 3x1 − 4x2 − 2x3
z = 5x1 + 4x2 + 3x3 .
x1 enters the bases and x4 leaves it:

x1 = 5/2 − 3/2x2 − 1/2x3 − 1/2x4

FG Simplex 14/20
The simplex

We replace x1 by its expression in function of x2 , x3 , x4 .

x1 = 5/2 − 1/2x4 − 3/2x2 − 1/2x3

x5 = 11 − 4(5/2 − 3/2x2 − 1/2x3 − 1/2x4 ) − x2 − 2x3
x6 = 8 − 3(5/2 − 3/2x2 − 1/2x3 − 1/2x4 ) − 4x2 − 2x3
z = 5(5/2 − 3/2x2 − 1/2x3 − 1/2x4 ) + 4x2 + 3x3 .

FG Simplex 15/20
The simplex

Finally, we get the new dictionary:

5
x1 = 2
− 32 x2 − 1
2
x3 − 12 x4
x5 = 1 + 5 x2 + 2 x4
1
x6 = 2
+ 12 x2 − 1
2
x3 + 32 x4
25
z = 2
− 72 x2 + 1
2
x3 − 52 x4 .

FG Simplex 16/20
The simplex

Finally, we get the new dictionary:

3 1 1
x1 = 5/ 2 − 2
x2 − 2
x3 − 2
x4
x5 = 1 + 5 x2 + 2 x4
1 1 3
x6 = 1/ 2 + 2
x2 − 2
x3 + 2
x4
z = 25/2 − 7/2 x2 + 1/2 x3 − 5/2 x4 .

We can read the solution directly from the dictionary:

Non basic variables: x2 = x3 = x4 = 0.
Basic variables: x1 = 5/2, x5 = 1, x6 = 1/2.
Value of the solution: z = 25/2.

FG Simplex 17/20
The simplex

5
x1 = 2
− 32 x2 − 1
2
x3 − 12 x4
x5 = 1 + 5 x2 + 2 x4
1
x6 = 2
+ 12 x2 − 1
2
x3 + 32 x4
25
z = 2
− 72 x2 + 1
2
x3 − 52 x4 .

New step of the simplex:

- x3 enters the basis (variable with largest positive coefficient).
- 3d equation is the strictest constaint x3 ≤ 1.
- x6 leaves the basis.

FG Simplex 18/20
The simplex

New feasible dictionary:

x3 = 1 + x2 + 3x4 − 2x6
x1 = 2 − 2x2 − 2x4 + x6
x5 = 1 + 5x2 + 2x4
z = 13 − 3x2 − x4 − x6 .

With new solution:

x1 = 2, x2 = 0, x3 = 1, x4 = 0, x5 = 1, x6 = 0

of value z = 13.

This solution is optimal.

All coefficients in z are negative and x2 ≥ 0, x4 ≥ 0, x6 ≥ 0, so z ≤ 13.

FG Simplex 19/20
The simplex

New feasible dictionary:

x3 = 1 + x2 + 3x4 − 2x6
x1 = 2 − 2x2 − 2x4 + x6
x5 = 1 + 5x2 + 2x4
z = 13 − 3x2 − x4 − x6 .

With new solution:

x1 = 2, x2 = 0, x3 = 1, x4 = 0, x5 = 1, x6 = 0

of value z = 13.

This solution is optimal.

All coefficients in z are negative and x2 ≥ 0, x4 ≥ 0, x6 ≥ 0, so z ≤ 13.

FG Simplex 19/20
Take Aways

• Most popular method to solve linear programs.

• Principle: smartly explore basic solutions (corner point solutions),

improving the value of the solution.

• Complexity:
• In theory, NP-complete (can explore a number of solutions
exponentiel in the number of variables and constraints).
• In practice, almost linear in the number of constraints.

• Polynomial methods exists: the ellipsoid method.

FG Simplex 20/20