Recherche opérationnelle
4Info
ESPRIT 2020-2021
Méthode du simplexe
L’algorithme de résolution le plus utilisé lorsque nous avons un nombre de variables ≥ 2.
Méthode du simplexe
dans le cas d'un problème de maximisation sous contraintes et avec un second membre positif
Démarche à suivre :
1) Déterminer la Forme canonique de PL
2) Déterminer la Forme standard de PL : ajouter des variables d’écart en nombre égale à celui des contraintes.
3) Déterminer une première solution réalisable (Faisable) : x 0 : Solution initiale.
Si pour tous i=1..n, on a bi ≥ 0 : on peut poser x0 = (0, . . . , 0, b1, b2, . . . , bm)
Variables de de base (VB) : xn+1, . . . , xn+m ou e1, . . . , em : les variables d’écart.
On note base B = (e1 . . . em)
Variables hors base (VHB) : x1, . . . , xn : ce sont dans ce cas les variables de décision.
Les VHB sont mises à zéro.
x0 est dite Solution de Base Réalisable (SBR) liée à la Base B.
4) Construire 1er tableau de simplexe correspondant à la SBR x0.
5) Tester l’optimalité de la SBR initiale x0.
6) Si x0 est optimale, Arrêter : nous avons résolu le problème.
Sinon, effectuer une itération.
Méthode du simplexe : Exemple d’application
Soit la PL suivant :
Max Z = 30x + 50 y
SC 3x + 2 y 1800
(PL) x 400
y 600
x 0 et y 0
1) Forme canonique
2) Forme standard
3) SBR initiale
4) 1er tableau de simplexe
5) Test d’optimalité
6) Itération
Méthode du simplexe : Exemple d’application
Max Z = 30x + 50 y
SC 3x + 2 y 1800
(PL) x 400
y 600
x 0 et y 0
1) Forme canonique
2) Forme standard
3) SBR initiale
4) 1er tableau de simplexe
5) Test d’optimalité
6) Itération
Méthode du simplexe : Exemple d’application
Max Z = 30x + 50 y Z = 30x + 50 y + 0 e1 + 0 e2 + 0 e3
SC 3x + 2 y 1800 3x + 2 y + e1 = 1800
(PL) x 400 x + e2 = 400
y 600
y + e3 = 600
x 0 et y 0
1) Forme canonique 2) Forme standard
3) SBR initiale
4) 1er tableau de simplexe
5) Test d’optimalité
6) Itération
Méthode du simplexe : Exemple d’application
SBRinitiale = (0,0,1800,400,800)
Max Z = 30x + 50 y Z = 30x + 50 y + 0 e1 + 0 e2 + 0 e3
SC 3x + 2 y 1800 3x + 2 y + e1 = 1800 VB : e1 = 1800 VHB : x = 0
y=0
(PL) x 400 x + e2 = 400
e2 = 400
e3 = 600
y 600
y + e3 = 600
x 0 et y 0 Base = (e1,e2,e3) et Z = 0
1) Forme canonique 2) Forme standard 3) SBR initiale
4) 1er tableau de simplexe
5) Test d’optimalité
6) Itération
Méthode du simplexe : Exemple d’application
3) SBR initiale 4) 1er tableau de simplexe 2) Forme standard
SBRinitiale = (0,0,1800,400,800) 3x + 2 y + e1 = 1800
2 VD 3 V. d’Ecart
VB : e1 = 1800 VHB : x = 0 x + e2 = 400
e2 = 400 y=0
y + e3 = 600
e3 = 600
#1 x y e1 e2 e3
Base = (e1,e2,e3) et Z = 0 e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400 Z = 30x + 50 y + 0 e1 + 0 e2 + 0 e3
e3 0 1 0 0 1 600
30 50 0 0 0 0
Z = 30*0 + 50*0 + 0*1800 + 0*400 + 0*600 = 0
Méthode du simplexe : Exemple d’application
3) SBR initiale 4) 1er tableau de simplexe 2) Forme standard
SBRinitiale = (0,0,1800,400,800) 3x + 2 y + e1 = 1800
VB : e1 = 1800 VHB : x = 0 x + e2 = 400
Variables Hors base : x = y = 0
e2 = 400 y=0
y + e3 = 600
e3 = 600
#1 x y e1 e2 e3
Base = (e1,e2,e3) et Z = 0 e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400 Z = 30x + 50 y + 0 e1 + 0 e2 + 0 e3
e3 0 1 0 0 1 600
30 50 0 0 0 0
Variables de base :
e1 = 1800
e2 = 400
e3 = 600
Méthode du simplexe : Exemple d’application
3) SBR initiale 4) 1er tableau de simplexe 2) Forme standard
SBRinitiale = (0,0,1800,400,800) 3x + 2 y + e1 = 1800
VB : e1 = 1800 VHB : x = 0 x + e2 = 400
e2 = 400 y=0
y + e3 = 600
e3 = 600
#1 x y e1 e2 e3
Base = (e1,e2,e3) et Z = 0 e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400 Z = 30x + 50 y + 0 e1 + 0 e2 + 0 e3
e3 0 1 0 0 1 600
30 50 0 0 0 0
C’est le tableau de simplexe
associé à la SBR (x,y,e1,e2,e3) = (0,0,1800,400,600)
Liée à la base (e1,e2,e3)
De valeur Z = 0
Méthode du simplexe : Exemple d’application
4) 1er tableau de simplexe 5) Test d’optimalité
#1 x y e1 e2 e3 Si tous les coefficients de la fonction objectif sont négatifs ou nuls,
e1 3 2 1 0 0 1800 l’optimum est atteint.
e2 1 0 0 1 0 400 Si nous avons au moins un coefficient strictement positif, nous
e3 0 1 0 0 1 600 devons effectuer une itération.
30 50 0 0 0 0 Ici, la SBR initiale n’est pas optimale, puisque nous avons 30 et 50.
6) Effectuer une Itération ➔ Tracer un 2ème tableau de Simplexe
#2 x y e1 e2 e3 #2 x y e1 e2 e3
? A11 A12 A13 A14 A15 b1
? A21 A22 A23 A24 A25 b2
? A31 A32 A33 A45 A35 b3
C1 C2 C3 C4 C5 ?
Méthode du simplexe : Exemple d’application
#1 x y e1 e2 e3
Effectuer une Itération e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400
1) Choisir les variables à introduire dans la base : Choisir le
e3 0 1 0 0 1 600
coefficient le plus positif de la fonction économique.
30 50 0 0 0 0
2) Choisir les variables à enlever de la base : (Rapport :
second membres / coefficient de la variable choisie).
Retenir le plus faible
#2 x y e1 e2 e3
3) Repérer l’élément pivot
? A11 A12 A13 A14 A15 b1
4) Diviser la ligne pivot par l’élément pivot. ? A21 A22 A23 A24 A25 b2
5) Calculer les coefficients restants du nouveau tableau de ? A31 A32 A33 A45 A35 b3
simplexe. C1 C2 C3 C4 C5 ?
Méthode du simplexe : Exemple d’application
#1 x y e1 e2 e3
Effectuer une Itération e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400
1) Choisir les variables à introduire dans la base : e3 0 1 0 0 1 600
Choisir le coefficient le plus positif de la 30 50 0 0 0 0
fonction économique.
On dit que y est le vecteur entrant (Ve) ou variable
entrante. #2 x y e1 e2 e3
? A11 A12 A13 A14 A15 b1
Le vecteur y va remplacer l’un des vecteurs de base ei.
? A21 A22 A23 A24 A25 b2
? A31 A32 A33 A45 A35 b3
C1 C2 C3 C4 C5 ?
Méthode du simplexe : Exemple d’application
#1 x y e1 e2 e3
Effectuer une Itération e1 3 2 1 0 0 1800 1800/2 = 900
e2 1 0 0 1 0 400 -
2) Choisir la variable à enlever de la base Vs ou e3 0 1 0 0 1 600 600/1 = 600
vecteur sortant : 30 50 0 0 0 0
- Calculer le rapport :
second membres / coefficient du Ve
- Retenir le plus faible
#2 x y e1 e2 e3
? A11 A12 A13 A14 A15 b1
Dans le 2ème tableau de Simplexe, e3 va sortir de la base ? A21 A22 A23 A24 A25 b2
? A31 A32 A33 A45 A35 b3
e3 est le vecteur sortant Vs
C1 C2 C3 C4 C5 ?
Méthode du simplexe : Exemple d’application
#1 x y e1 e2 e3
Effectuer une Itération e1 3 2 1 0 0 1800 1800/2 = 900
e2 1 0 0 1 0 400 -
e3 0 1 0 0 1 600 600/1 = 600
Dans la base du nouveau tableau :
30 50 0 0 0 0
Le vecteur entrant Ve est y
Le vecteur sortant Vs est e3
➔ y va remplacer e3
#2 x y e1 e2 e3
➔ La nouvelle base sera (e1, e2, y)
(en respectant l’ordre). e1 A11 A12 A13 A14 A15 b1
e2 A21 A22 A23 A24 A25 b2
Nouvelle base y A31 A32 A33 A45 A35 b3
C1 C2 C3 C4 C5 ?
Méthode du simplexe : Exemple d’application Colonne pivot : Ve
#1 x y e1 e2 e3
Effectuer une Itération e1 3 2 1 0 0 1800 1800/2 = 900
e2 1 0 0 1 0 400 -
3) Repérer le Pivot. Ligne pivot : Vs e3 0 1 0 0 1 600 600/1 = 600
30 50 0 0 0 0
1 est appelé l’élément Pivot
#2 x y e1 e2 e3
e1 A11 A12 A13 A14 A15 b1
e2 A21 A22 A23 A24 A25 b2
Nouvelle base y A31 A32 A33 A45 A35 b3
C1 C2 C3 C4 C5 ?
Méthode du simplexe : Exemple d’application
#1 x y e1 e2 e3
Effectuer une Itération e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400
4) Diviser la ligne pivot par l’élément pivot. e3 0 1 0 0 1 600
30 50 0 0 0 0
#2 x y e1 e2 e3
e1 A11 A12 A13 A14 A15 b1
e2 A21 A22 A23 A24 A25 b2
y 0 1 0 0 1 600
C1 C2 C3 C4 C5 ?
Méthode du simplexe : Exemple d’application
#1 x y e1 e2 e3
Effectuer une Itération e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400
5) Calculer le reste des valeurs du tableau # 2. e3 0 1 0 0 1 600
30 50 0 0 0 0
#2 x y e1 e2 e3
e1 A11 A12 1 0 A15 b1
e2 A21 A22 0 1 A25 b2
y 0 1 0 0 1 600
C1 C2 0 0 C5 ?
Ve ae2
Méthode du simplexe : Exemple d’application
#1 x y e1 e2 e3
Effectuer une Itération e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400
5) Calculer le reste des valeurs du tableau # 2. Vs e3 0 1 0 0 1 600
30 50 0 0 0 0
as1
#2 x y e1 e2 e3
e1 A11 A12 1 0 A15 Notation:
b1
On pose aij les coefficients du tableau #1 :
e2 A21 A22 0 1 A25 b2
Exemples : a11 = 3, a42 = 50 et a22 = 0
y 0 1 0 0 1 600 aip: coef de la ligne j dans la colonne pivot
C1 C2 0 0 C5 ? apj: coef de la ligne pivot dans la colonne pivot
Le Pivot sera noté : P
Minuscule: tableau précédent
Majuscule: nouveau tableau
Pour chaque ligne i et chaque colonne j, nous aurons : Aij = aij – (aip * apj) / Pivot
Méthode du simplexe : Exemple d’application Ve
#1 x y e1 e2 e3
Effectuer une Itération e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400
5) Calculer le reste des valeurs du tableau # 2. Vs e3 0 1 0 0 1 600
30 50 0 0 0 0
#2 x y e1 e2 e3
e1 A11 A12 1 0 A15 Exemple
b1
e2 A21 A22 0 1 A25 b2 Pour la ligne 1 et la colonne 5, nous aurons :
y 0 1 0 0 1 600 A15 = a15 – (a35 x a12) / Pivot
0 0 -2 = 0 – ( 1 x 2 ) / 1
C1 C2 C5 ?
De même pour le reste des coefficients du tableau # 2 , y compris la nouvelle valeur de Z, les
coefficients Cj, et les coefficients bi.
Méthode du simplexe : Exemple d’application
Effectuer une Itération
A la fin de l’étape 5) de l’itération, nous aurons le tableau de Simplexe # 2 suivant :
Ve
#2 x y e1 e2 e3 #1 x y e1 e2 e3
e1 3 0 1 0 -2 600 e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400 e2 1 0 0 1 0 400
y 0 1 0 0 1 600 Vs e3 0 1 0 0 1 600
30 0 0 0 -50 -30000 30 50 0 0 0 0
- 30 000 = 0 – (50*600) / 1
Méthode du simplexe : Exemple d’application
Effectuer une Itération
A la fin de l’étape 5) de l’itération, nous aurons le tableau de Simplexe # 2 suivant :
#2 x y e1 e2 e3 #1 x y e1 e2 e3
e1 3 0 1 0 -2 600 e1 3 2 1 0 0 1800
e2 1 0 0 1 0 400 e2 1 0 0 1 0 400
y 0 1 0 0 1 600 e3 0 1 0 0 1 600
30 0 0 0 -50 -30000 30 50 0 0 0 0
Méthode du simplexe : Exemple d’application
Effectuer une Itération
A la fin de l’étape 5) de l’itération, nous aurons le tableau de Simplexe # 2 suivant :
#2 x y e1 e2 e3
C’est le tableau de simplexe
e1 3 0 1 0 -2 600
associé à la SBR (x,y,e1,e2,e3) = (0,600,600,400,0)
e2 1 0 0 1 0 400 Liée à la base (e1,e2,y)
y 0 1 0 0 1 600 De valeur Z = 30000
30 0 0 0 -50 -30000
7) Test d’optimalité de la nouvelle solution : La solution est-elle optimale ? ➔ Nouvelle itération
NON !
Méthode du simplexe : Exemple d’application
Effectuer une nouvelle Itération
#2 x y e1 e2 e3 1) Choisir les variables à introduire dans la base :
e1 3 0 1 0 -2 600 Choisir le coefficient le plus positif de la fonction
économique.
e2 1 0 0 1 0 400
y 0 1 0 0 1 600 2) Choisir les variables à enlever de la base : (Rapport :
30 0 0 0 -50 -30000 second membres / coefficient de la variable choisie).
Retenir le plus faible
#3 x y e1 e2 e3 3) Repérer l’élément pivot
? ? ? ? ? ? ? 4) Diviser la ligne pivot par l’élément pivot.
? ? ? ? ? ? ?
5) Calculer les coefficients restants du nouveau tableau
? ? ? ? ? ? ? de simplexe.
? ? ? ? ? ?
Méthode du simplexe : Exemple d’application
Effectuer une nouvelle Itération
#2 x y e1 e2 e3 1) Choisir les variables à introduire dans la base :
e1 3 0 1 0 -2 600 Choisir le coefficient le plus positif de la fonction
économique.
e2 1 0 0 1 0 400
y 0 1 0 0 1 600 2) Choisir les variables à enlever de la base : (Rapport :
30 0 0 0 -50 -30000 second membres / coefficient de la variable choisie).
Retenir le plus faible
#3 x y e1 e2 e3 3) Repérer l’élément pivot
x 1 0 1/3 0 -2/3 200 4) Diviser la ligne pivot par l’élément pivot.
e2 0 0 -1/3 1 2/3 200
5) Calculer les coefficients restants du nouveau tableau
y 0 1 0 0 1 600 de simplexe.
0 0 -10 0 -30 -36000
Méthode du simplexe : Exemple d’application
Effectuer une nouvelle Itération
#2 x y e1 e2 e3 1) Choisir les variables à introduire dans la base :
e1 3 0 1 0 -2 600 Choisir le coefficient le plus positif de la fonction
économique.
e2 1 0 0 1 0 400
y 0 1 0 0 1 600 2) Choisir les variables à enlever de la base : (Rapport :
30 0 0 0 -50 -30000 second membres / coefficient de la variable choisie).
Retenir le plus faible
#3 x y e1 e2 e3 3) Repérer l’élément pivot
x 1 0 1/3 0 -2/3 200 4) Diviser la ligne pivot par l’élément pivot.
e2 0 0 -1/3 1 2/3 200
5) Calculer les coefficients restants du nouveau tableau
y 0 1 0 0 1 600 de simplexe.
0 0 -10 0 -30 -36000
Méthode du simplexe : Exemple d’application
Effectuer une nouvelle Itération Variables de base :
x = 200
#3 x y e1 e2 e3 e2 = 200
y = 600
x 1 0 1/3 0 -2/3 200
e2 0 0 -1/3 1 2/3 200
y 0 1 0 0 1 600 C’est le tableau de simplexe
Z = 36000
0 0 -10 0 -30 -36000 associé à la SBR (x,y,e1,e2,e3) = (200,600,0,200,0)
Liée à la base (e1,e2,y)
De valeur Z = 36000
Test d’optimalité de la nouvelle solution : La solution est-elle optimale ?
Méthode du simplexe : Exemple d’application
Effectuer une nouvelle Itération
#3 x y e1 e2 e3
x 1 0 1/3 0 -2/3 200
e2 0 0 -1/3 1 2/3 200
y 0 1 0 0 1 600
0 0 -10 0 -30 -36000
Condition d’arrêt
Test d’optimalité de la nouvelle solution : La solution est-elle optimale ?
OUI
Méthode du simplexe : Exemple d’application
Effectuer une nouvelle Itération
C’est le tableau de simplexe
#3 x y e1 e2 e3 associé à la SBR* (x*,y*,e1*,e2*,e3*) = (200,600,0,200,0)
Liée à la base (e1,e2,y)
x 1 0 1/3 0 -2/3 200
De valeur Z* = 36000
e2 0 0 -1/3 1 2/3 200
y 0 1 0 0 1 600 SBR* : x* = 200
0 0 -10 0 -30 -36000 y* = 600
Z* = 36000
Condition d’arrêt
Test d’optimalité de la nouvelle solution : La solution est-elle optimale ?
OUI