Section3.

La méthode
du simplexe

1
Introduction
❑La procédure graphique est utilisée pour la résolution des
programmes linéaires. Cette méthode est limitée aux cas de deux
variables de décision.
❑Par contre, dans la plupart des problèmes réels, on a plus que deux
variables à déterminer.
❑Pour un problème de taille quelconque, c’est la méthode du simplexe
qui est utilisée.
❑Cette méthode a été développée par George Dantzig en 1947.

2
La méthode du simplexe
Etape1. Ajout des Etape2. Déterminer une
variables d’écart solution de base réalisable

Est-elle optimale?

Etape3: Non Oui

• Etape1: Tableau
• Etape2: Variable entrante
Etape3. Trouver Stop
• Etape3: Variable sortante
une solution
• Etape4: Mise à jour du tableau
admissible
• Etape5: Critère de sortie

3
La méthode du simplexe
𝑚𝑎𝑥 𝑍 = 𝑥1+2𝑥2
−3𝑥1 + 2𝑥2 + 𝒆𝟏 = 2
{ −𝑥1 + 2𝑥2 + 𝑒2 = 4
𝑥1 + 𝑥2 + 𝑒3 = 5
𝑥1; 𝑥2 ≥ 0

4
La méthode du simplexe
1. Ajout des variables d’écart:
−3𝑥1 + 2𝑥2 + 𝒆𝟏 = 2
{ −𝑥1 + 2𝑥2 + 𝒆𝟐 = 4
𝑥1 + 𝑥2 + 𝒆𝟑 = 5
∀𝑖 ∈ 1,3 ; 𝑒𝑖 ≥ 0; 𝑥1; 𝑥2 ≥ 0
𝑚𝑎𝑥 𝑍 = 𝑥1+2𝑥2
2. Solution de base réalisable: 𝑥1=0 ; 𝑥2=0
On a: e1=2
e2=4
e3=5
Z=0 => est-elle optimale? Non

5
La méthode du simplexe
3.1 Tableau Variables hors
base
Contraintes

X1 X2 e1 e2 e3 C
e1 -3 2 1 0 0 2
Variables de base
e2 -1 2 0 1 0 4
e3 1 1 0 0 1 5
Z 1 2 0 0 0 0
Coefficient de Z

6
La méthode du simplexe
3.2 Variable entrante (Colonne Pivot)
Colonne Pivot: Cp
X1 X2 e1 e2 e3 C

e1 -3 2 1 0 0 2
e2 -1 2 0 1 0 4
e3 1 1 0 0 1 5
Z 1 2 0 0 0 0

Colonne Pivot: 𝒎𝒂𝒙(𝒄𝒐𝒆𝒇 𝒁 )=2

=> Variable entrante: X2

7
La méthode du simplexe
3.3 Variable sortante (Ligne Pivot)
Le pivot 𝑳𝒑 ∩ 𝑪𝒑
X1 X2 e1 e2 e3 C K
𝑪
e1 -3 2 1 0 0 2 =𝟏
Lp
𝑪𝒑
𝑪
e2 -1 2 0 1 0 4 =𝟐
𝑪𝒑
𝑪
e3 1 1 0 0 1 5 =𝟓
𝑪𝒑

Z 1 2 0 0 0 0
Cp
𝐶
Ligne Pivot(Lp): calcul min(K)>0 avec 𝑘 = 𝐶𝑝

min 𝑘 = 1 > 0
=> Variable sortante: e1
8
La méthode du simplexe
3.4 Mettre à jour le tableau

X1 X2 e1 e2 e3 C
X2 -3/2 2/2 1/2 0/2 0/2 2/2 Lp/Pivot=
e2 -1 2 0 1 0 4 Lp/2
e3 1 1 0 0 1 5
Z 1 2 0 0 0 0

9
 La méthode du simplexe
3.4 Mettre à jour le tableau

X1 X2 e1 e2 e3 C
X2 -3/2 1 1/2 0 0 1 Lp/Pivot= Lp/2
Li-2Lp e2 -1 0 0 1 0 4
Li-Lp e3 1 0 0 0 1 5
Li-2Lp Z 1 0 0 0 0 0

Colonne Pivot=0 sauf le Pivot

10
 La méthode du simplexe
4.1 La solution est-elle optimale?

X1 X2 e1 e2 e3 C
X2 -3/2 1 1/2 0 0 1 Lp/Pivot= Lp/2
Li-2Lp e2 2 0 -1 1 1 2
Li-Lp e3 5/2 0 -1/2 0 1 4
Li-2Lp Z 4 0 -1 0 0 -2

∀ 𝑪𝒐𝒆𝒇 𝒛 ≤ 𝟎 => 4>0 n’est pas optimale

11
La méthode du simplexe
4.2 Variable entrante (Colonne Pivot)

X1 X2 e1 e2 e3 C
X2 -3/2 1 1/2 0 0 1
e2 2 0 -1 1 1 2
e3 5/2 0 -1/2 0 1 4
Z 4 0 -1 0 0 -2

Colonne Pivot: 𝒎𝒂𝒙(𝒄𝒐𝒆𝒇 𝒁 )=4

=> Variable entrante: X1

12
La méthode du simplexe
4.3 Variable sortante (Ligne Pivot)
X1 X2 e1 e2 e3 C K
X2 -3/2 1 1/2 0 0 1
e2 2 0 -1 1 1 2 1 Lp
e3 5/2 0 -1/2 0 1 4 8/5
Z 4 0 -1 0 0 -2

>=0
𝐶𝑖
Ligne Pivot(Lp): calcul min(Ki)>0 avec 𝐾 =
𝐶𝑝𝑖

min 𝑘 = 1 > 0
=> Variable sortante: e2

13
La méthode du simplexe
4.4 Mettre à jour le tableau
X1 X2 e1 e2 e3 C K
X2 -3/2 1 1/2 0 0 1
X1 2/2 0/2 -1/2 1/2 1/2 2/2 1 Lp
e3 5/2 0 -1/2 0 1 4 8/5
Z 4 0 -1 0 0 -2
Cp

14
 La méthode du simplexe
4.4 Mettre à jour le tableau
X1 X2 e1 e2 e3 C
Li+3/2Lp X2 0 1 1/2 0 0 1
X1 1 0 -1/2 1/2 1/2 1 Lp
Li-5/2Lp e3 0 0 -1/2 0 1 4
Li-4Lp Z 0 0 -1 0 0 -2

15
 La méthode du simplexe
4.4 Mettre à jour le tableau
X1 X2 e1 e2 e3 C
Li+3/2Lp X2 0 1 0 1/3 1/3 3
X1 1 0 0 -1/3 -2/3 2 Lp
Li-5/2Lp e3 0 0 1 -5/3 4/3 2
Li-4Lp Z 0 0 0 -1/3 -4/3 -8

∀ 𝑪𝒐𝒆𝒇 𝒛 ≤ 𝟎 => La solution est optimale

16
La méthode du simplexe
4.5 La solution est-elle optimale?
X1 X2 e1 e2 e3 C
X2 0 1 0 1/3 1/3 3
X1 1 0 0 -1/3 -2/3 2
e3 0 0 1 -5/3 4/3 2
Z 0 0 0 -1/3 -4/3 -8

∀ 𝑪𝒐𝒆𝒇 𝒛 ≤ 𝟎 => oui la solution est optimale X1=2

X2=3
Z=8

17
Application
Considérons le problème :
𝑚𝑎𝑥 𝑍 = 20𝑥1+25𝑥2
2𝑥1 + 3𝑥2 ≤ 40
{ 4𝑥 1 + 2𝑥2 ≤ 48
𝑥1 , 𝑥2 ≥ 0

18
Solution

19