CHAPITRE III

Méthode du Simplexe
Introduction
• La résolution graphique ne concerne que des problèmes avec deux
variables alors que les problèmes réels peuvent en avoir plusieurs
milliers, voire plusieurs centaines de milliers.

• Dans ce chapitre, nous allons illustrer le principe d’un algorithme de

résolution: l’algorithme simplexe

• Cet algorithme est du à Dantzig 1947

Base et Solutions de base
Représentation
Représentation matricielle
Exemple
Algorithme du simplexe
• Soit le programme linéaire:
 Algorithme simplexe
• Étape 0: écrire le programme linéaire sous forme standard puis construire le tableau initial.
-Programme linéaire sous forme standard

-Tableau initial

La base initiale de l’espace colonne sera {e1, e2, …, em}, e1= b1, e2=b2, …, em=bm
les autres variables seront égales à 0 (x1=x2=…=xn=0) ce qui correspond au point de départ x=(0, 0, …, 0)
Algorithme du Simplexe

C’est la variable à introduire dans la base

Algorithme du Simplexe
C’est la variable qui sort de la base
Exemple
Exemple
Etape 0
Exemple
• Etape 0 (suite)
• On forme le tableau initial T

B x1 x2 e1 e2
e1 2 3 1 0 40
e2 4 2 0 1 48
20 25 0 0

• Les variables de base sont {e1, e2} et la solution de base est (0, 0, 40, 48) ce qui correspond à
l’origine dans le plan.
Exemple
 Exemple

Ligne pivot= Li L1
L2 akj=2
L3
Pivot=aij

Li=Li/aij (L1=L1/pivot)
On applique l’élimination de gauss jordan
(Ligne de pivot
B x1 x2 e1 e2 Est divisée par le pivot)

x2 2/3 1 1/3 0 40/3

T[2,1]=4-(2/3)*2=8/3
e2 8/3 0 -2/3 1 64/3 L2=L2-L1/pivot*a2,2
T[2,2]=2-(3/3)*2=0
T[2,3]=0-(1/3)*2=-2/3
T[2,4]=1-(0/3)*2=1
T[2,5]=48-(40/3)*2=-2/3
 Exemple

Ligne pivot= Li

akj=25
Pivot=aij

On applique l’élimination de gauss jordan Li=Li/aij

(Ligne de pivot
B x1 x2 e1 e2 Est divisée par le pivot)
T[3,1]=20-(2/3)*25=10/3 x2 2/3 1 1/3 0 40/3
T[3,2]=25-(3/3)*25=0 e2 8/3 0 -2/3 1 64/3
T[3,3]=0-(1/3)*25=-25/3
T[3,4]=0-(0/3)*25=0 10/3 0 -25/3 0 -1000/3 L3=L3-L1/pivot*a3,2
T[3,5]=0-(40/3)*25=-1000/3
La solution de base sera x2=40/3, e2=64/3 et Z=1000/3
 Exemple
Colonne pivot
akj pour L1=2/3
B x1 x2 e1 e2 Critère
x2 2/3 1 1/3 0 40/3 (40/3)/(2/3)=20
Ligne pivot e2 8/3
8/3 0 -2/3 1 64/3 (64/3)/(8/3)=8 e2 va sortir de la base
10/3 0 -25/3 0 -1000/3

Pivot On choisit la première colonne car x1 est la seule

Variable qui augmente Z donc x1 va entrer dans la base

akj pour L3=10/3

La nouvelle base sera B={x2, x1}

Exemple
• En appliquant le même calcul:
Li=Li/pivot , i=2
Lk=Lk-Li/pivot*akj , k=1,3
• On obtient le tableau suivant:

L’algorithme se termine ici car tous les coefficients des colonnes x1, x2, e1 et e2 sont négatifs.
Donc on ne peut pas augmenter davantage la fonction économique Z.
La solution optimale sera: x1=8, x2=8, e1=e2=0 et Z=360
Ce qui correspond au sommet (8,8) dans le plan.
Le signe – dans le coin inférieur droit est dû au fait que l’on avait initialement ajouter la ligne
CtX-Z=0. Donc à la fin on aura –Z=-360
Méthode de deux phases
• Soit le système linéaire :
Max Z= x1+ 2x2
s.c. 2x1 +x2 >=2
x1 + 2x2 >=2
x1+ x2<=3
x1, x2 >=0

On veut résoudre le système ci-dessus par la méthode de simplexe

Méthode de deux phases
• On réécrit le système linéaire sous la forme standard
• Forme standard :
Max Z= x1+ 2x2
s.c. 2x1 +x2 – e1=2
x1 + 2x2 – e2=2
x1+ x2 + e3=3
x1, x2, e1, e2, e3 >=0
• Si on considère Base={e1 , e2 , e3 } , la solution de base (e1 = -2, e2 = -2,
e3=3) n’est pas réalisable car: e1 et e2 sont négatives.
• Solution: recherche d’une base réalisable
Méthode de deux phases
Résolution de problème auxiliaire
• On ajoute des variables artificielles sur les contraintes où c’est nécessaire c’est-à-
dire sur les contraintes où les variables d’écart sont précédées du signe –
• On minimise ensuite la somme des variables artificielles afin de les rendre nulles
• Min Z’=a1 + a2
s.c. 2x1 +x2 – e1 + a1 =2
x1 + 2x2 – e2 + a2 =2
x1+ x2 + e3=3
x1, x2, e1, e2, e3 , a1 , a2 >=0
• Base={a1 , a2 , e3}, solution de base est a1 =2, a2 =2, e3=3, x1 =x2 =e1 = e2 =0
• On résout le problème avec cette base de départ. Si on trouve a1 = a2=0 (hors-
base) alors on a une base réalisable formée par 3 variables du problème de
départ
Méthode de deux phases
• Phase 1
–Résolution du problème auxiliaire
–Si les variables artificielles se sont annulées
Alors on a une base de départ pour le problème initial, aller en phase
2
Sinon le problème initial n’a pas de solution réalisable (domaine vide)
STOP
•Phase 2
–Résoudre le problème initial en partant de la base trouvée en phase 1
 Méthode de deux phases
Min Z’=a1 + a2
s.c. 2x1 +x2 – e1 + a1 =2
x1 + 2x2 – e2 + a2 =2
x1+ x2 + e3=3
x1, x2, e1, e2, e3 , a1 , a2 >=0
Il faut exprimer Z’ en fonction des variables hors base
a1 =2- 2x1 +x2 – e1
a2 =2- x1 + 2x2 – e2
Z’=4-3 x1 - 3 x2 + e1 + e2
Tableau -4+Z’= 3 x1 + 3 x2 - e1 - e2
initial Base x1 x2 e1 e2 e3 a1 a2 b critère
a1 va
a1 2 1 -1 0 0 1 0 2 2/2=1 sortir
a2 1 2 0 -1 0 0 1 2 2/1=2 de base
e3 1 1 0 0 1 0 0 3 3/1=3
3 3 -1 -1 0 0 0 4-Z’

x1 va rentrer en base
 Méthode de deux phases
Base x1 x2 e1 e2 e3 a1 a2 b critère
Ligne
a1 2 1 -1 0 0 1 0 2 2/2=1 pivot
a2 1 2 0 -1 0 0 1 2 2/1=2
e3 1 1 0 0 1 0 0 3 3/1=3
3 3 -1 -1 0 0 0 4-Z’
Colonne pivot
Puisque x1 et x2 ont le même coefficient le choix entre les deux variables est donc arbitraire
Nouvelle base B={x1 , a2 , e3 }
Itération 1
Base x1 x2 e1 e2 e3 a2 b critère
x1 1 1/2 -1/2 0 0 0 1
a2 va
a2 0 3/2 1/2 -1 0 1 1 1/1/2=2 sortir de base
e3 0 1/2 1/2 0 1 0 2 2/1/2=4
0 3/2 1/2 -1 0 0 1-z’

e1 va rentrer en base
 Méthode de deux phases
Base x1 x2 e1 e2 e3 a2 b critère
x1 1 1/2 -1/2 0 0 0 1
a2 0 3/2 1/2 -1 0 1 1 1/1/2=2
e3 0 1/2 1/2 0 1 0 2 2/1/2=4
0 3/2 1/2 -1 0 0 1-z’
Itération 2
Base x1 x2 e1 e2 e3 b
x1 1 2 0 -1 0 2
e1 0 3 1 -2 0 2
e3 0 -1 0 1 1 1
0 0 0 0 0 0

Les variables artificielles sont hors base, on a maintenant une base pour le problème initial.
Méthode de deux phases
Phase 2
Base x1 x2 e1 e2 e3 b
x1 1 2 0 -1 0 2
e1 0 3 1 -2 0 2
e3 0 -1 0 1 1 1
0 0 0 0 0 0

Variable de base={x1 , e1 , e3 }, variable hors base={x2 , e2 }

Il faut exprimer la fonction Z= x1+ 2x2 en fonction des variables hors base x2 et e2

On remplace x1 par son expression en fonction de x2 et e2 donnée par la ligne 1 du tableau (ligne verte)
x1 = 2-2x2 + e2
Z=x1+ 2x2  Z= 2-2x2 + e2 + 2x2
 Z= 2 + e2

-2+Z= e2
 Méthode de deux phases
Itération 3
Base x1 x2 e1 e2 e3 b
x1 1 2 0 -1 0 2
e1 0 3 1 -2 0 2
e3 0 -1 0 1 1 1 e3 va sortir de base
0 0 0 1 0 -2+Z

e2 va rentrer en base
Itération 4
Base x1 x2 e1 e2 e3 b Critère
x1 1 1 0 0 1 3 3/1=3 x1 va sortir de base
e1 0 1 1 0 2 4 4/1=4
e2 0 -1 0 1 1 1
0 1 0 0 -1 -3+Z

x2 va rentrer en base
 Méthode de deux phases
Base x1 x2 e1 e2 e3 b Critère
x1 1 1 0 0 1 3 3/1=3 x1 va sortir de base
e1 0 1 1 0 2 4 4/1=4
e2 0 -1 0 1 1 1
0 1 0 0 -1 -3+Z
Itération 5 x2 va rentrer en base
Base x1 x2 e1 e2 e3 b
x2 1 1 0 0 1 3
e1 -1 0 1 0 1 1
e2 1 0 0 1 2 4
-1 0 0 0 -2 -6+Z

Tout les coefficients sont négatifs donc l’algorithme se termine

La solution est x2=3, e1=1, e2=4 et Z=6