La méthode des deux phases (simplexe) :

Cette méthode consiste à résoudre un problème de programmation linéaire en deux parties:

La phase I : consiste à annuler toutes les variables artificielles en utilisant une fonction
objectif artificielle (minimizer za). Si l’on ne peut pas annuler toutes les variables, alors le
problème n’est pas réalisable.
La phase II : consiste à remplacer la fonction objectif artificielle de la phase I par la vraie
fonction objectif à maximiser. On utilise alors la solution réalisable de base obtenue à la fin de
la phase I.

Cas 1: za = 0 et il ne reste plus de vecteurs artificiels dans la base

Maximiser z = 2x1 + 3x2 + 5x3
sous contraintes x1 + 4x2 - 3x3 ≤ 8
2x1 - x2 ≤ 5
5x1 + 2x2 - x3 = 19
et x1, x2, x3 ≥ 0
Transformons ce problème sous forme standard :

Maximiser z = 2x1 + 3x2 + 5x3+0 x4 +0 x5

sous contraintes x1 + 4x2 - 3x3 + x4 = 8
2x1 - x2 + x5 = 5
5x1 + 2x2 - x3 = 19
et x1, x2, x3, x4, x5 ≥ 0

Pour utiliser la méthode de simplexe, on doit avoir une matrice de base égale à l’identité. Pour
cela, on ajoute une variable artificielle (xa1):

Maximiser z = 2x1 + 3x2 + 5x3+0 x4 +0 x5+ xa1

sous contraintes x1 + 4x2 - 3x3 + x4 = 8
2x1 - x2 + x5 = 5
5x1 + 2x2 - x3 + xa1 = 19
et x1, x2, x3, x4, x5, xa1 ≥ 0

Phase 1: La fonction objectif artificielle à maximiser est za = - xa1 puisque les coefficients
des autres variables sont nuls.

Maximiser za = 0 x1 + 0 x2 + 0 x3+0 x4 +0 x5 - xa1

sous contraintes x1 + 4x2 - 3x3 + x4 = 8
2x1 - x2 + x5 = 5
5x1 + 2x2 - x3 + xa1 = 19
et x1, x2, x3, x4, x5, xa1 ≥ 0
Etape 1

xb cb a1 a2 a3 a4 a5 a*1 D D/a1
X4 0 1 4 -3 1 0 0 8 8
X5 0 2 -1 0 0 1 0 5 5/2=2,5
Xa1 -1 5 2 -1 0 0 1 19 19/5=3,8
ci 0 0 0 0 0 -1
yi -5 -2 1 0 0 -1
ci-yi 5 2 -1 0 0 0 Za=-19
Etape 2
xb cb a1 a2 a3 a4 a5 a*1 D D/a1
X4 0 0 9/2 -3 1 -1/2 0 11/2 11/9=1,22
X1 0 1 -1/2 0 0 1/2 0 5/2 -5
Xa1 -1 0 9/2 -1 0 -5/2 1 13/2 13/9=1,44
ci 0 0 0 0 0 -1
yi 0 -9/2 1 0 5/2 -1
ci-yi 0 9/2 -1 0 -5/2 0 Za=-13/2
Etape 3
xb cb a1 a2 a3 a4 a5 a*1 D D/a1
X2 0 0 1 -6/9 2/9 -1/9 0 11/9 -11/6
X1 0 1 0 -6/18 2/18 8/18 0 56/18 -56/6
Xa1 -1 0 0 2 -1 -2 1 1 1/2
ci 0 0 0 0 0 -1
yi 0 0 -2 1 2 -1
ci-yi 0 0 2 -1 -2 0 Za=-1
Etape 4
xb cb a1 a2 a3 a4 a5 a*1 D D/a1
X2 0 0 1 0 -1/9 -7/9 3/9 14/9
X1 0 1 0 0 -1/18 2/18 3/18 59/18
X3 0 0 0 1 -1/2 -1 1/2 1/2
ci 0 0 0 0 0 -1
yi 0 0 0 0 0 0

1 59/18
ci-yi 0 0 0 0 0 -1 Za=0

2 = 14/9
3 1/2
LA SOLUTION DE BASE : Za=0 et Xa1=0

Phase 2 : Maximiser z = 2x1 + 3x2 + 5x3+0 x4 +0 x5

Etape 1
xb cb a1 a2 a3 a4 a5 D D/a1
X2 3 0 1 0 -1/9 -7/9 14/9 -2
X1 2 1 0 0 -1/18 2/18 59/18 59/2
X3 5 0 0 1 -1/2 -1 1/2 -1/2
ci 2 3 5 0 0
yi 2 3 5 -53/18 -64/9
ci-yi 0 0 0 53/18 64/9 Z=247/18
Etape 2
xb cb a1 a2 a3 a4 a5 D D/a1
X2 3 7 1 0 -1/2 0 441/18
X5 0 9 0 0 -1/2 1 59/2
X3 5 9 0 1 -1 0 30
ci 2 3 5 0 0
yi 66 3 5 -13/2 0
ci-yi -64 0 0 13/2 0 Z=447/2

LA SOLUTION EST L’infini

Cas 2: za = 0 et il reste un ou plusieurs vecteurs artificiels dans la base.

Minimiser z = -2x1 + 3x2 - 5x3

sous contraintes x1 + x2 + x3 = 6
- x1 + x2 + 2x3 = 4
2x2 + 3x3 = 10
x3 ≤ 2
et x1 , x2 , x3 ≥ 0
Réécriture du problème sous une forme adaptée à la méthode de simplexe :
Maximiser -z = +2x1 - 3x2+5x3+0 x4+xa1+xa2+xa3
sous contraintes x1 + x2 + x3 + xa1 = 6
- x1 + x2 + 2x3 +xa2 = 4
2x2 + 3x3+xa3 = 10
x3 +x4 = 2
et x1 , x2 , x3, x4, xa1, xa2, xa3 ≥ 0

Phase 1 La fonction objectif artificielle s’écrit :

Maximiser za =0 x1 +0 x2+0 x3+0 x4 - xa1 - xa2 - xa3

Etape 1
xb cb a1 a2 a3 a4 a*1 a*2 a*3 D D/a3
Xa1 -1 1 1 1 0 1 0 0 6 6
Xa2 -1 -1 1 2 0 0 1 0 4 2
Xa3 -1 0 2 3 0 0 0 1 10 10/3
X4 0 0 0 1 1 0 0 0 2 2
ci 0 0 0 0 -1 -1 -1
yi 0 -4 -6 0 -1 -1 -1
ci-yi 0 4 6 0 0 0 0 Za=-20
Etape 2
xb cb a1 a2 a3 a4 a*1 a*2 a*3 D D/a1
Xa1 -1 3/2 1/2 0 0 1 -1/2 0 4 8/3
X3 0 -1/2 1/2 1 0 0 ½ 0 2 -4
Xa3 -1 3/2 1/2 0 0 0 -3/2 1 4 8/3
X4 0 1/2 -1/2 0 1 0 -1/2 0 0 0
ci 0 0 0 0 -1 -1 -1
yi -3 -1 0 0 -1 2 -1
ci-yi 3 1 0 0 0 -3 0 Za=-8
Etape 3
xb cb a1 a2 a3 a4 a*1 a*2 a*3 D D/a2
Xa1 -1 0 2 0 -3 1 1 0 4 2
X3 0 0 0 1 1 0 0 0 2 ∝
Xa3 -1 0 2 0 -3 0 0 1 4 2
X1 0 1 -1 0 2 0 -1 0 0 -0
ci 0 0 0 0 -1 -1 -1
yi 0 -4 0 6 -1 -1 -1
ci-yi 0 4 0 -6 0 0 0 Za=-8
Etape 4
xb cb a1 a2 a3 a4 a*1 a*2 a*3 D
X2 0 0 1 0 -3/2 1/2 ½ 0 2
X3 0 0 0 1 1 0 0 0 2
Xa3 -1 0 0 0 0 -1 -1 1 0
X1 0 1 0 0 1/2 1/2 -1/2 0 2
ci 0 0 0 0 -1 -1 -1
yi 0 0 0 0 1 1 -1
ci-yi 0 0 0 0 -2 -2 0 Za=0

2 2
3 = 2 3=0
3 0
LA SOLUTION DE BASE Za=0 et
1 2
On commence la phase 2 en s’assurant que Xa3 ne devient pas positive

Phase 2 :

Maximiser -z = +2x1 - 3x2+5x3+0 x4 +0 xa3

xb cb a1 a2 a3 a4 a*3 D
X2 -3 0 1 0 -3/2 0 2
X3 5 0 0 1 1 0 2
Xa3 0 0 0 0 0 1 0
X1 2 1 0 0 1/2 0 2
ci 2 -3 5 0 0
yi 2 -3 5 21/2 0

2 2
ci-yi 0 0 0 -21/2 0 -Z=8

3 = 2
3 0
La solution optimale et Z=- 8
1 2
Cas 3: za < 0 ; dans ce cas, il n’existe pas de solution réalisable.

Maximiser z = x1 + 2x2 + x3
sous contraintes x1 - x2 + x3 ≤ 4
2x1 + 2x2 + 3x3 ≤ 6
3x1 + x2 + 4x3 ≥ 12
et x1, x2, x3 ≥ 0

Réécriture du problème sous une forme adaptée à la méthode de simplexe :

Maximiser z = x1 + 2x2 + x3+0 x4+ 0 x5+ 0 x6+ xa1
sous contraintes x1 - x2 + x3 +x4 = 4
2x1 + 2x2 + 3x3 +x5= 6
3x1 + x2 + 4x3 –x6 +xa1 = 12
et x1, x2, x3 ,x4, x5, x6, xa1≥ 0
Phase 1 La fonction objectif artificielle s’écrit :

Maximiser za =0 x1 + 0 x2 +0 x3+0 x4+ 0 x5+ 0 x6 - xa1

Etape 1

xb cb a1 a2 a3 a4 a5 a6 a*1 D D/a3
X4 0 1 -1 1 1 0 0 0 4 4
X5 0 2 2 3 0 1 0 0 6 2
Xa1 -1 3 1 4 0 0 -1 1 12 3
ci 0 0 0 0 0 0 -1
yi -3 -1 -4 0 0 1 -1
ci-yi 3 1 4 0 0 -1 0 Za=-12
Etape 2

xb cb a1 a2 a3 a4 a5 a6 a*1 D D/a1
X4 0 1/3 -5/3 0 1 -1/3 0 0 2 6
X3 0 2/3 2/3 1 0 1/3 0 0 2 3
Xa1 -1 1/3 -5/3 0 0 -4/3 -1 1 4 12
ci 0 0 0 0 0 0 -1
yi -1/3 5/3 0 0 4/3 1 -1
ci-yi 1/3 -5/3 0 0 -4/3 -1 0 Za=-12
Etape 3

xb cb a1 a2 a3 a4 a5 a6 a*1 D
X4 0 0 -2 -1/2 1 -1/2 0 0 1
X1 0 1 1 3/2 0 1/2 0 0 3
Xa1 -1 0 -2 -1/2 0 -3/2 -1 1 3
ci 0 0 0 0 0 0 -1
yi 0 2 1/2 0 3/2 1 -1
ci-yi 0 -2 -1/2 0 -3/2 -1 0 Za=-3

Za<0 , alors il n’y a pas de solution réalisable.