Naouel ZRELLI Méthode de Simplexe
Méthode de Simplexe
Introduction :
La méthode de résolution du (P.L) a été découverte par Dantzig et Kantorovich en 1950. Son principe est basé
sur la résolution graphique. Dantzig a constaté qu'une solution optimale se trouvait toujours à un sommet du
polyèdre des solutions réalisables. Comme on ne pourrait pas calculer la solution à chaque sommet (pour 100
variables à 10 contraintes, il ya 1370 milliard de sommets). Dantzig a trouvé un moyen de passer systémati-
quement d'un sommet donné à un sommet voisin oû la fonction objectif est au moins aussi bonne. Comme le
nombre de sommets est limité on parvient aprés plusieurs itérations à la solution optimale.
I Forme standard d'un P.L
Un (P.L) peut avoir des contraintes d'égalités (=) ou des contraintes d'inégalités (≤ et ≥). Avant l'application
de la méthode de Simplexe, le (P.L) doit être converti en un (P.L) équivalent où :
1. Toutes les contraintes sont des égalités.
2. Toutes les variables sont positives.
3. Les c÷ cients du second membre sont positifs (b ≥ 0)
Exemple :
Max
z(x)= 4x1 + 3x2
x1 + x2 ≤ 40
(P.L)
s.c 2x1 + x2 ≥ 60
x1 ≥ 0, x2 ≥ 0
1. Pour convertir la première contrainte (≤) en une contrainte d'égalité, on dé nit la variable d'écart s1
(slack variable) qui représente la quantité de ressource non utilisée dans cette contrainte :
s1 = −x1 − x2 + 40 =⇒ x1 + x2 + s1 = 40, tel que s1 ≥ 0
2. Pour une contrainte (≥) , on dé nit la variable d'excès e1 (excess variable) :
e1 = 2x1 + x2 − 60 =⇒ 2x1 + x2 − e1 = 60, tel que e1 ≥ 0
On obtient alors
Forme standard
Max
z(x)= 4x1 + 3x2 + 0s1 + 0e1
x1 + x2 +s1 = 40
s.c 2x1 + x2 −e1 = 60
x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, e1 ≥ 0
Page 1
Naouel ZRELLI Méthode de Simplexe
II Algorithme de Simplexe
II.1 Inégalités "≤"
II.1.1 Maximisation de la fonction objectif
Etude sur un exemple : on considère le le (P.L) suivant :
Max
z(x)= 5x1 + 4x2
4x1 + 3x2 ≤ 120
(P.L)
s.c 2x1 + 5x2 ≤ 130
x1 ≥ 0, x2 ≥ 0
Etape 1 :
Ecrire la forme standard en introduisant les variables d'écart (si )1≤i≤2
Forme standard :
Max
z(x)= 5x1 + 4x2 + 0s1 + 0s2
4x1 + 3x2 +s1 = 120
s.c 2x1 + 5x2 +s2 = 130
x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0
et construire la table suivante :
Table initiale :
x1 x2 s1 s2 b Variables de base
4 3 1 0 120 s1
Variables hors base
2 5 0 1 130 s2 x1 = 0, x2 = 0
−5 −4 0 0 0
La première partie de la table contient les coe cients des contraintes
La dernière ligne de la table contient les coe cients de z(x) en écrivant :
z(x) − 5x1 − 4x2 − 0s1 − 0s2 = 0
La méthode de simplexe commence par l'identi cation d'une solution réalisable de base initiale,
cette solution obtenue en annulant les variables de décision. C'est à dire, pour x1 = 0 et x2 = 0,
les contraintes de la forme standard donnent s1 = 120 ≥ 0 et s2 = 130 ≥ 0 qui sont réalisables
(car elles sont positives).
x1 et x2 sont appelées variables hors base.
s1 et s2 sont appelées variables de base.
Page 2
Naouel ZRELLI Méthode de Simplexe
Etape 2 : (variable entrante)
Repérer l'élément négatif le plus grand en valeur absolue dans la dernière ligne de la table. soit k
sa colonne alors xk est une variable entrante.
| − 5| > | − 4|
−5 est située à la première colonne (k=1) de la table par suite x1 est une variable entrante.
x1 x2 s1 s2 b Variables de base
4 3 1 0 120 s1
Variables hors base
2 5 0 1 130 s2
x1 = 0, x2 = 0
−5
−4 0 0 0
y
Si toutes les valeurs de la dernière ligne de la table sont positives alors le table est sous sa forme
nale est la solution obtenue est optimale (x1 = 0, x2 = 0).
Etape 3 : (pivot et variable sortante)
Diviser les coe cients de la dernière colonne de la table contenant b (second membre du (P.L)) par
les coe cients strictement positifs de la (k)ère colonne (terme par terme)
120 130
(Pour k = 1) <
4 2
le diviseur qui donne le plus petit quotient s'appelle le pivot =4 (dans notre exemple).
S'il existe plusieurs qui donnent la même valeur choisir l'un d'entre eux.
x1 x2 s1 s2 b Variables de base
4 3 1 0 120 s1
Variables hors base
2 5 0 1 130 s2
x1 = 0, x2 = 0
−5
−4 0 0 0
y
L'intersection de la colonne de la variable entrante et de la ligne de la variable sortante est le pivot.
x1 x2 s1 s2 b Variables de base
3 1 0 120 s1 →
Variables hors base
2 5 0 1 130 s2
x1 = 0, x2 = 0
−5
−4 0 0 0
y
s1 est une variable sortante.
Page 3
Naouel ZRELLI Méthode de Simplexe
Etape 4 :
Remplacer les variables sortante et entrante dans le nouveau tableau
Rendre le pivot égale 1 en divisant les coe cients de la ligne contenant le pivot par ce pivot.
x1 x2 s1 s2 b Variables de base
L1 3 1
L1 ← 1 0 30 x1
4 4 4 Variables hors base
L2 2 5 0 1 130 s2 s1 = 0, x2 = 0
L3 −5 −4 0 0 0
Etape 5 :
Annuler tous les éléments de la colonne k du pivot (sauf le pivot) en utilisant la méthode de Gauss.
Commencer par une table contenant seulement la ligne du pivot
x1 x2 s1 s2 b Variables de base
3 1
L1 1 0 30 x1
4 4 Variables hors base
L2 s2 s1 = 0, x2 = 0
L3
Faire les opération élémentaires sur les lignes
L2 ← L2 − 2L1
L3 ← L3 + 5L1
(à l'extérieur de la table) en utilisant les deux dernières tables : on prend la ligne L1 de la dernière
table et les lignes L2 et L3 de l'avant dernière.
L2 2 5 0 1 130 L3 −5 −4 0 0 0
− +
3 1 15 5
2L1 2 0 60 5L1 5 0 150
2 2 4 4
7 1 1 5
0 − 1 70 0 − 0 150
2 2 4 4
Ensuite, remplir la table :
x1 x2 s1 s2 b Variables de base
3 1
L1 1 0 30 x1
4 4
Variables hors base
7 1
L2 0 − 1 70 s2 s1 = 0, x2 = 0
2 2
1 5
L3 0 − 0 150
4 4
A cette étape, la solution est x1 = 30 et x2 = 0, mais la méthode de simplexe ne s'arrête
pas car il reste encore des valeurs négatives dans la dernière ligne de la table (la valeur
correspondante à b est exclue)
Page 4
Naouel ZRELLI Méthode de Simplexe
Recommencer la procédure à partir de l'Etape 2 à l'Etape 5 jusqu'à la disparition des éléments
négatifs de la dernière ligne.
(a) L'élément négatif est situé à la colonne k = 2 =⇒ x2 est une variable entrante.
(b) Nous divisons les éléments de b par les éléments strictement positifs de la 2ème colonne :
30 70 7
> =⇒ le pivot =
3 7 2
4 2
(c) L'intersection de la variable sortante et la variable entrante est le pivot =⇒ s2 est une variable sortante
(d) Changer les variables sortante et entrante, ensuite rendre le pivot=1, en n annuler les éléments
de la colonne contenant le pivot.
1
L2 ← 7 L2
2
3
L1 ← L1 − L2
4
1
L3 ← L3 + L2
4
x1 x2 s1 s2 b Variables de base
L1 x1
Variables hors base
1 2
L2 0 1 − 20 x2 s1 = 0, s2 = 0
7 7
L3
3 1 1 5
L1 1 0 30 L3 0 − 0 150
4 4 4 4
− +
3 3 3 6 1 1 1 2
L2 0 − 15 L2 0 − 5
4 4 28 28 4 4 28 28
10 6 34 2
1 0 − 15 0 0 155
28 28 28 28
Maintenant, remplir la table :
x1 x2 s1 s2 b Variables de base
5 3
L1 1 0 − 15 x1
14 14
Variables hors base
1 2
L2 0 1 − 20 x2 s1 = 0, s2 = 0
7 7
17 1
L3 0 0 155
14 14
Tous les éléments (correspondants aux variables x1 , x2 , s1 , s2 ) de la dernière ligne sont positifs
(l'élément placé à la colonne b est exclus) alors la méthode de Simplexe s'arrete et la solution
optimale :
x∗1 = 15 , x∗2 = 20 et z ∗ = 155
Page 5
Naouel ZRELLI Méthode de Simplexe
Véri cations :
O1 Remplacer la solution optimale dans z(x) du (P.L) : z(x ) = 5 × 15 + 4 × 20 = 155 et véri er que
∗
cette valeur existe dans la dernière ligne de la colonne de b de la table ( 155 ).
O2 De la dernière table, extraire la matrice placée dans les colonnes des s notée B et la matrice placée
i
dans les colonnes des xi notée I (la dernière ligne de la table est exclue).
Ensuite, prendre la matrice A du (P.L) et calculer A B ou BA selon le format des produits matriciels
et véri er que AB=I ou BA=I
5 3
4 3
−
1 0
14 14
A= B = =⇒ AB = =I
1 2
2 5 − 0 1
7 7
O3 Utiliser le b (second membre) du P.L pour calculer Bb :
5 3
−
14 14 120
15
130 = = b nale
1 2 20
−
7 7
Page 6
Naouel ZRELLI Méthode de Simplexe
O4 Ecrire le C de la forme standard :
( 5 4 0 0 )
C= ↓ ↓ ↓ ↓
x1 x2 s1 s2
Choisir le nouveau C selon l'ordre des variables de base dans la table nale :
( 5 4 )
C= ↓ ↓
x1 x2
Remarque : si par exemple dans la table nale les variables de base sont : s1 le premier
et x1 le deuxième alors on écrit C = (0 5).
Calculer CB :
5 3
−
14 14
(5 4) = ( 17 1 )
1 2
14 14
−
7 7
La matrice ligne résultante doit apparaitre dans la dernière ligne de la table dont les colonnes sont
celles des variables d'écart si .
Page 7
