Recherche opérationnelle

Algorithme du Simplexe

Professeur : Oussama TILFANI

Année Universitaire : 2024 - 2025
Frome algébrique du Simplexe

❑ La méthode algébrique requiert l’évaluation d’un nombre plus

large de solutions possibles, dont les solutions non réalisables.
❑ Une meilleure approche serait capable de :
- Evaluer uniquement les solutions réalisables.
- N’évaluer que les meilleures solutions.
- S’arrêter lorsque la solution optimale est retrouvée.

→ Algorithme du Simplexe
 Résolution algébrique Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
s/c
3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎
No Variables de Variables fixes Solution Fonction objectif Commentaire
base
1. X3 et X4 X1 = 0 et X2 = 0 X3 = 21 et X4=24 Z=0 Solution réalisable

2. X1 et X3 X2 et X4 X1 = 6 et X3 = 3 Z = 60 Solution réalisable

3. X1 et X4 X2 et X3 X1 = 7 et X4 = -4 Solution non
réalisable
4. X2 et X3 X1 et X4 X2 = 8 et X3 = -3 Solution non
réalisable
5. X2 et X4 X1 et X3 X2 = 7 et X4 = 3 Z = 63 Solution réalisable

6. X1 et X2 X3 et X4 X1 = 3 et X2 = 4 Z=66 Optimum
Algorithme du Simplexe
Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
s/c
3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎

• Dans la résolution algébrique, nous avons introduit deux variables « slack

variables » , ou variables de surplus.
• Ces variables ne contribuent pas à la fonction objectif.
• Pour résoudre le problème avec la méthode algébrique, nous avons besoin de
fixer deux variables et résoudre pour les deux autres (variables de base).
 Algorithme du Simplexe
Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
s/c
3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎
• On suppose 𝑿𝟑 et 𝑿𝟒 les variables de base, alors
𝑿𝟑 = 21 − 3𝑿𝟏 − 3𝑿𝟐 On réécrit les variables de base en fonction des variables fixes
𝑿𝟒 = 24 − 4𝑿𝟏 − 3𝑿𝟐
Z = 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒 = 0
• Il s’agit d’un problème de maximisation, donc on augmente les variables de base
progressivement.
• On commence par la variable ayant le coefficient le plus élevé, à savoir 𝑿𝟏 .
 Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
Algorithme du Simplexe s/c
3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
• On augmente progressivement 𝑿𝟏 : 𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎
𝑿𝟑 = 21 − 3𝑿𝟏 − 3𝑿𝟐 (Les limites de 𝑿𝟏 sont 6 et 7, on augmente 𝑿𝟏 progressivement à 6)
𝑿𝟒 = 24 − 4𝑿𝟏 − 3𝑿𝟐 Pour 𝑿𝟏 = 6 elle va jouer le rôle de 𝑿𝟒
• Dans ce cas 𝑿𝟏 devient une variable de base. On peut écrire :
𝟏 𝟑
4𝑿𝟏 = 24 −𝑿𝟒 − 3𝑿𝟐 ou encore 𝑿𝟏 = 6 − 𝑿𝟒 − 𝑿𝟐
𝟒 𝟒
𝟏 𝟑 𝟑 𝟑
Et pour 𝑿𝟑 : 𝑿𝟑 = 21 − 3(6 − 𝑿𝟒 − 𝑿𝟐 )− 3𝑿𝟐 =𝟑+ 𝑿𝟒 − 𝑿𝟐
𝟒 𝟒 𝟒 𝟒
On remplace dans la fonction objectif :
𝟏 𝟑 𝟓 𝟑
Z = 10(6 − 𝑿𝟒 − 𝑿𝟐 ) + 𝟗𝑿𝟐 = 60− 𝑿𝟒 + 𝑿𝟐
𝟒 𝟒 𝟐 𝟐
 Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
Algorithme du Simplexe s/c
3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
• On peut augmenter progressivement 𝑿𝟐 : 𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎
𝟏 𝟑 𝟓 𝟑
Z = 10(6 − 𝑿𝟒 − 𝑿𝟐 ) + 𝟗𝑿𝟐 = 60− 𝑿𝟒 + 𝑿𝟐
𝟒 𝟒 𝟐 𝟐
𝟏 𝟑 𝟑 𝟑
A partir de l’équation 𝑿𝟏 = 6 − 𝑿𝟒 − 𝑿𝟐 et 𝑿𝟑 =𝟑+ 𝑿𝟒 − 𝑿𝟐
𝟒 𝟒 𝟒 𝟒
Si on augmente 𝑿𝟐 alors 𝑿𝟏 va diminuer
(𝑿𝟐 au plus 8 ou 4, donc la valeur maximale de 𝑿𝟐 est 4)
Pour 𝑿𝟐 = 𝟒 alors 𝑿𝟑 = 𝟎
 Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
Algorithme du Simplexe s/c
3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
• On remplace par 𝑿𝟐 : 𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎
𝟑 𝟑
𝑿 = 𝟑 + 𝑿𝟒 − 𝑿𝟑
𝟒 𝟐 𝟒
𝟒
𝑿𝟐 = 𝟒 + 𝑿𝟒 − 𝑿𝟑
𝟑
𝟏 𝟑 𝟏 𝟑 𝟒
A partir de l’équation 𝑿𝟏 = 6 − 𝑿𝟒 − 𝑿𝟐 = 𝑿𝟏 = 6 − 𝑿𝟒 − (𝟒 + 𝑿𝟒 − 𝑿𝟑 )
𝟒 𝟒 𝟒 𝟒 𝟑
𝑿𝟏 = 3 − 𝑿𝟒 + 𝑿𝟑
𝟓 𝟑 𝟓 𝟑 𝟒
En remplace dans Z = 60− 𝑿𝟒 + 𝑿𝟐 = 60− 𝑿𝟒 + (𝟒 + 𝑿𝟒 − 𝑿𝟑 )
𝟐 𝟐 𝟐 𝟐 𝟑
Z= 66−𝟐𝑿𝟑 − 𝑿𝟒
Par ailleurs Z ne peut être maximisée que si 𝑿𝟑 = 𝟎 et 𝑿𝟒 = 𝟎
 Algorithme du Simplexe : Logique
• Déterminer des variables de base (non nulles).
• Ecrire les variables de base en fonction des autres à partir des contraintes
• Evaluer la fonction objectif.
• La valeur initiale de Z = 0 or on cherche à maximiser, donc il faut chercher les variables à augmenter.
• On commence par la variable ayant l’impact le plus élevé.
• On continue à augmenter la variable concernée jusqu’à sa limite supérieure, en remplaçant la variable
de base associée à la contrainte qui définit la limite supérieure (celle qui s’annule en premier lieu).
• Une variable qui été 0 devient de base, et l’autre initialement de base devient 0. Donc on réécrit les
variables de base en fonction des autres à partir des contraintes.
• La fonction objectif sera réécrite en fonction des variables 0 et une constante.
• On raisonne sur la variable qui va augmenter encore la fonction objectif
• Cette nouvelle variable devient une variable de base, il faut exprimer les variables de base dans cette
itération. On part à l’équation qui détermine la valeur maximale de cette nouvelle variable.
• On remplace également dans l’autre variable de base.
• On s’arrête lorsqu’on ne peut plus améliorer la fonction objectif.
 Algorithme du Simplexe : Commentaires
• Cet algorithme n’évalue que les solutions réalisables
• Uniquement 3 solutions qui ont été évaluées, appartenant toutes au
domaine réalisable.
• On évalue que les meilleures solutions.
 Algorithme du Simplexe : Forme tabulaire
• Les formes tabulaires et algébrique du Simplexe reposent sur la même
logique, les mêmes itérations.
• La forme algébrique utilise les équations explicites
• La forme tabulaire les représente en un tableau.
• On considère le problème de maximisation :
Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
s/c
3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
𝑿 𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎
 Algorithme du Simplexe : Forme tabulaire
Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
1ère itération Variables de base
s/c
Coefficient des
variables de base 3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
10 9 0 0 𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎
CB XB X1 X2 X3 X4 RHS 
0 X3 3 3 1 0 21 7
0 X4 4 3 0 1 24 6
Cj-Zj 10 9 0 0 0
 Permet de déterminer la variable qui va sortir de la base
j : représente la variable
Cj : le coût de la variable (le coefficient associé à la variable dans la fonction objectif)
Zj : le produit de Cb et les coefficients de Xj dans les équations des contraintes
 Algorithme du Simplexe : Forme tabulaire
Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
2ème itération Ligne pivot
s/c
4 représente la colonne pivot 3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎
10 9 0 0
CB XB X1 X2 X3 X4 RHS  La variable qui va
quitter la base est
0 X3 3 3 1 0 21 7 X4 qui  minimal
0 X4 4 3 0 1 24 6 La variable qui va
Cj-Zj 10 9 0 0 0 rejoindre la base X1 qui
le coefficient le plus
0 X3 0 3/4 1 - 3/4 3 4 élevé
10 X1 1 3/4 0 1/4 6 8 X3 va quitter la
base
Cj-Zj 0 3/2 0 -5/2 60
Cette ligne est obtenue en
X2 va rejoindre la base divisant les éléments de la ligne
de X4 par l’élément pivot
 Algorithme du Simplexe : Forme tabulaire
Max 10𝑿𝟏 +9𝑿𝟐 +0𝑿𝟑 + 𝟎𝑿𝟒
3ème itération s/c
3𝑿𝟏 +3𝑿𝟐 + 𝑿𝟑 = 21
4𝑿𝟏 +3𝑿𝟐 + 𝑿𝟒 = 24
𝑿𝟏 ; 𝑿𝟐 ; 𝑿 𝟑 ; 𝑿𝟒 ≥ 𝟎
10 9 0 0
CB XB X1 X2 X3 X4 RHS 
0 X3 3 3 1 0 21 7
0 X4 4 3 0 1 24 6
Cj-Zj 10 9 0 0 0
0 X3 0 3/4 1 - 3/4 3 4
10 X1 1 3/4 0 1/4 6 8
Cj-Zj 0 3/2 0 -5/2 60
9 X2 0 1 4/3 -1 4
10 X1 1 0 -1 1 3
Cj-Zj 0 0 -2 -1 66Optimum
 Algorithme du Simplexe : Forme tabulaire
• Les formes tabulaire et algébrique du Simplexe reposent sur la même
logique, les mêmes itérations.
• La forme algébrique utilise les équations explicites
• La forme tabulaire les représente en un tableau.
• On considère le problème de minimisation :
Min 𝟕𝑿𝟏 +𝟓𝑿𝟐
s/c
𝑿𝟏 +𝑿𝟐 ≥ 𝟒
5𝑿𝟏 +𝟐𝑿𝟐 ≥ 10
𝑿𝟏 ; 𝑿𝟐 ≥ 𝟎
 Algorithme du Simplexe : Forme tabulaire
Min 𝟕𝑿𝟏 +𝟓𝑿𝟐 Min 𝟕𝑿𝟏 +𝟓𝑿𝟐 + 𝟎𝑿𝟑 + 𝟎𝑿𝟒
s/c On rajoute des variables slack s/c
𝑿𝟏 +𝑿𝟐 ≥ 𝟒 (variables d’écart) 𝑿𝟏 +𝑿𝟐 −𝑿𝟑 = 𝟒
5𝑿𝟏 +𝟐𝑿𝟐 ≥ 10 5𝑿𝟏 +𝟐𝑿𝟐 − 𝑿𝟒 = 10
𝑿𝟏 ; 𝑿𝟐 ≥ 𝟎 𝑿 𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ≥ 𝟎
On ne peut pas commencer la procédure du simplexe avec des variables négatives:
𝑿𝟑 = −𝟒 + 𝑿𝟏 +𝑿𝟐 on rajoute des variables artificielles:

Min 𝟕𝑿𝟏 +𝟓𝑿𝟐 +𝟎𝑿𝟑 + 𝟎𝑿𝟒 + 𝑴𝒂𝟏 + 𝑴𝒂𝟐

𝑿𝟏 +𝑿𝟐 −𝑿𝟑 + 𝒂𝟏 = 𝟒
5𝑿𝟏 +𝟐𝑿𝟐 − 𝑿𝟒 + 𝒂𝟐 = 10
𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ; 𝒂𝟏 ; 𝒂𝟐 ≥ 𝟎
 Algorithme du Simplexe : Forme tabulaire
Transformer le problème :
Min f(x) ⇔ Max (-f(x))
Donc le problème sera de la frome :
Max (−(𝟕𝑿𝟏 +𝟓𝑿𝟐 +𝟎𝑿𝟑 + 𝟎𝑿𝟒 + 𝑴𝒂𝟏 + 𝑴𝒂𝟐 ))
𝑿𝟏 +𝑿𝟐 −𝑿𝟑 + 𝒂𝟏 = 𝟒
5𝑿𝟏 +𝟐𝑿𝟐 − 𝑿𝟒 + 𝒂𝟐 = 10
𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ; 𝒂𝟏 ; 𝒂𝟐 ≥ 𝟎
Algorithme du Simplexe : Forme tabulaire
-7 -5 0 0 -M -M
CB XB X1 X2 X3 X4 a1 a2 RHS 

-M a1 1 1 -1 0 1 0 4 4

-M a2 5 2 0 -1 0 1 10 2

Cj-Zj 6M-7 3M-5 -M -M 0 0 ---

-M a1 0 3/5 -1 1/5 1 -1/5 2 10/3

-7 X1 1 2/5 0 -1/5 0 1/5 2 5

Cj-Zj 0 (3M-11)/5 -M (M-7)/5 0 (-6M+7)/5 ---

-5 X2 0 1 -5/3 1/3 5/3 -1/3 10/3

-7 X1 1 0 2/3 -1/3 2/3 1/3 2/3

Cj-Zj 0 0 -11/3 -11/3 (-3M+11)/3 (-3M+2)/3 -64/3

Algorithme du Simplexe : Solution infinie

Max 𝟏𝟎𝑿𝟏 +𝟗𝑿𝟐 Max 𝟏𝟎𝑿𝟏 +𝟗𝑿𝟐 + 𝟎𝑿𝟑 + 𝟎𝑿𝟒

s/c s/c
𝑿𝟏 − 𝑿𝟐 ≤ 5 On rajoute des variables slack 𝑿𝟏 −𝑿𝟐 +𝑿𝟑 = 5
4𝑿𝟏 ≤ 24
(variables d’écart) 4𝑿𝟏 +𝑿𝟒 = 24
𝑿𝟏 ; 𝑿𝟐 ≥ 𝟎 𝑿𝟏 ; 𝑿𝟐 ; 𝑿 𝟑 ; 𝑿𝟒 ≥ 𝟎
Algorithme du Simplexe : Solution infinie
10 9 0 0
CB XB X1 X2 X3 X4 RHS 
0 X3 1 -1 1 0 5 5
0 X4 4 0 0 1 24 6
Cj-Zj 10 9 0 0 0
10 X1 1 -1 1 0 5
0 X4 0 4 -4 1 4 1
Cj-Zj 0 19 -10 0 50
X1 1 0 0 1/4 6
X2 0 1 -1 1/4 1
Cj-Zj 0 0 9 -19/4 69
Une variable est éligible pour accéder à la base. Mais aucune variable n’est capable de sortir
Algorithme du Simplexe : Solution infinie

Max 𝟏𝟎𝑿𝟏 +𝟗𝑿𝟐

s/c
𝑿𝟏 − 𝑿𝟐 ≤ 5
4𝑿𝟏 ≤ 24
𝑿𝟏 ; 𝑿𝟐 ≥ 𝟎
Algorithme du Simplexe : Solution non réalisable

Max 𝟏𝟎𝑿𝟏 +𝟗𝑿𝟐 + 𝟎𝑿𝟑 + 𝟎𝑿𝟒 − 𝑴𝒂𝟏

Max 𝟏𝟎𝑿𝟏 +𝟗𝑿𝟐
s/c
s/c On peut écrire sous forme
𝑿𝟏 +𝑿𝟐 +𝑿𝟑 = 5
𝑿𝟏 + 𝑿𝟐 ≤ 5
4𝑿𝟏 − 𝑿𝟒 + 𝒂𝟏 = 24
4𝑿𝟏 ≥ 24
𝑿𝟏 ; 𝑿𝟐 ; 𝑿𝟑 ; 𝑿𝟒 ; 𝒂𝟏 ≥ 𝟎
𝑿𝟏 ; 𝑿𝟐 ≥ 𝟎
Algorithme du Simplexe : Solution non réalisable
10 9 0 0 -M
CB XB X1 X2 X3 X4 a1 RHS 
0 X3 1 1 1 0 0 5 5
-M a1 4 0 0 -1 1 24 6
Cj-Zj 4M+10 M+9 0 M 0 ---
10 X1 1 1 1 0 0 5
-M a1 0 -4 -4 -1 1 4
Cj-Zj 0 -4M-1 -4M-10 -M 0 ---

L’optimum est atteint mais avec une variable artificielle dans la solution. La solution n’est
pas réalisable
Prenons l’exemple 1 suivant :
Max Z = 87x1 + 147x2 + 258x3.

x1 + 2x2 + 3x3 ≤ 90
s.c 15x1 + 21x2 + 30x3 ≤ 1260
x1 + x2 + x3 ≤ 84

x1 ≥0, x2 ≥0 et x3 ≥0
Forme Standard du PL

Max z = 87x1 + 147x2 + 258x3.

s.c x1 + 2x2 + 3x3 + e1 = 90

15x1 + 21x2 + 30x3 + e2 = 1260
x1 + x2 + x3 + e3 = 84
x ≥ 0, x2 ≥ 0 et x3 ≥ 0 e1 ≥ 0, e2 ≥ 0 et e3 ≥ 0
 La construction du tableau initial

Les calculs nécessités par l’algorithme du simplexe s’effectuent plus facilement et plus
rapidement lorsque le modèle linéaire est disposé sous forme de tableau
simplexe.
Un tel tableau présente, de façon visuelle et structurée, les variables et les coefficients du
modèle. De plus, chaque tableau met en évidence une solution de base particulière du
modèle linéaire, dite solution de base associée, ou encore solution canonique associée.

26
Tableau du simplexe
On présente notre solution avec le tableau suivant :
87 147 258 0 0 0
CB XB X1 X2 X3 e1 e2 e3 RHS 

0 e1 1 2 3 1 0 0 90 30

0 e2 15 21 30 0 1 0 1260 42
0 e3 1 1 1 0 0 1 84 84
27

Cj-Zj 87 147 258 0 0 0 0

Chaque tableau du simplexe partitionne les variables en 2 groupes :
les variables de base : les variables de base sont les 3 variables apparaissant dans
la section gauche.
les variables hors base : les variables hors base sont les 3 autres.
Par exemple, les variables hors base du tableau précédent sont x1, x2 et x3. De façon
générale, la solution de base associée à un tableau s’obtient en posant égales à 0
les variables hors base et donnant à chacune des variables de base la valeur
apparaissant sur la même ligne.
la variable entrante
Le choix de la variable entrante
La solution de base initiale du modèle n’est pas optimale.
Comment s’en convaincre par des arguments strictement algébriques ? S’il n’est pas optimale, il
faut augmenter la valeur de l’une ou l’autre de ces variables x1; x2; x3.
Laquelle, ou lesquelles choisir ?
Selon la remarque 1 : on augmentera la variable qui rapporte le plus x3, la variable ayant le
28

coût réduit le plus élevé

Afin de simplifier l’analyse, supposons que x1 et x2 gardent pour le moment la valeur
0. On augmente x3, le bénéfice va augmenter.
le Pivot
87 147 258 0 0 0
CB XB X1 X2 X3 e1 e2 e3 RHS 

0 e1 1 2 3 1 0 0 90 30

0 e2 15 21 30 0 1 0 1260 42
0 e3 1 1 1 0 0 1 84 84
Cj-Zj 87 147 258 29
0 0 0 0

choix de pivot
Pour chaque itération, nous suivons les règles suivantes :
- Variable entrante : plus fort coefficient strictement positif.
- Variable sortante : plus petite valeur strictement positive dans .
- Le pivot : intersection de la ligne et de la colonne sélectionnée.
x3 variable entrante remplace la variable e1 dans le nouveau tableau. Le pivot est égal à 3.
Transformation du tableau
Ligne x3 (ancienne ligne e1) −→ Ligne e1/3 . (Division par le pivot).
Ligne e2 −→Ligne e2 −30 ligne x3
Ligne e3 −→ Ligne e3− ligne x3
On obtient le tableau suivant :

87 147 258 0 0 0
CB XB X1 X2 X3 e1 e2 e3 RHS 

258 X3 1/3 2/3 1 1/3 0 0 30

0 e2 5 1 0 -10 1 0 360
0 e3 2/3 1/ 3 0 -1/3 0 1 54
Cj-Zj 1 -25 0 -86 0 0 0 7740

Remarque importante
On vérifie pour chaque tableau calculé que les valeurs des variables de base sont
positives ou nulles.
La règle d pivot consiste à
- Remplacer le pivot par la valeur 1 en divisant la ligne pivot par 1.
- Associer la valeur 0 aux autres composante de la colonne pivot.
- Associer la valeur 0 au coût réduit de la nouvelle variable
entrante.

Remarques 31

- Le passage de l’ancien tableau au nouveau tableau traduit le passage du sommet

(0, 0, 0) ou le bénéfice est nul à un autre sommet ou le bénéfice est 7740 (le bénéfice
a été amélioré)
- La fonction bénéfice est z = 7740 + x1 − 25x2 − 86e1, z peut augmenter si on aug-
mente x1 avec x2 = e1 = 0. Il faut passer à un autre sommet, l’algorithme n’est pas
encore terminé.
On effectue notre choix du pivot :

87 147 258 0 0 0
CB XB X1 X2 X3 e1 e2 e3 RHS 

258 X3 1/3 2/3 1 1/3 0 0 30 90

0 e2 5 1 0 -10 1 0 360 72
0 e3 2/3 1/ 3 0 -1/3 0 1 54 81
Cj-Zj 1 -25 0 -86 0 0 7740
32

Transformation du tableau
- La variable entrante est celle de coût réduit Cj-Zj le plus élevé, c’est la variable x1.
- La variable sortante est celle qui minimise b c’est la variable e2.
- Le pivot = 5. La variable x1 remplace la variable e2.
- Ligne x1 (ancienne ligne e2) −→ Ligne e2/5 (Division par le pivot).
- Ligne x3 −→Ligne x3 − 1/3 ligne x1
- Ligne e3 −→Ligne e3 − 2/3ligne x1
 87 147 258 0 0 0
CB XB X1 X2 X3 e1 e2 e3 RHS 

258 X3 0 3/5 1 -1/3 -1/12 0 6

87 X1 1 1/5 0 -2 1/5 0 72

0 e3 1/5 0 1 -1/6 1 6
0
Cj-Zj 0 -25,2 0 -84 -1/5 0 7812
33

Remarques importantes
S’il n’y a pas de candidat pour quitter la base, on peut faire croître la variable en- trante et donc aussi
la fonction objectif autant qu’on le veut. Dans ce cas, le problème est non borné.
S’il y a plusieurs candidats pour quitter la base, alors n’importe lequel de ces can- didats peut servir.
La présence de plusieurs candidats pour quitter la base a une conséquence importante : la
dégénérescence.
 Utilisation du solveur Excel
• En pratique, il est utile d’utiliser des outils informatiques pour la résolution des
problèmes linéaires.
• Plusieurs logiciels peuvent être utilisés : Matlab, Python, Lindo, CPLEX, AMP…
• Solveur excel : outil simple permettant de résoudre des problèmes linéaire
• Il est limité à 200 contraintes, par contre les autres outils permettent de
résoudre des problèmes avec des milliers de contraintes.
• Nous allons examiner deux problèmes avec le solveur excel.
Un petit peu de théorie
Tout problème de programmation linéaire peut être ramené à la
forme suivante dite forme standard
Max z=c1 x1 + c2 x2 + ⋯ cj xj + ⋯ cn xn
a11 x1 + a12 x2 + ⋯ a1j xj + ⋯ a1n xn = 𝑏1
a21 x1 + a22 x2 + ⋯ a2j xj + ⋯ a2n xn = 𝑏2
⋮
s/c ai1 x1 + ai2 x2 + ⋯ aij xj + ⋯ ain xn = 𝑏𝑖
⋮
am1 x1 + am2 x2 + ⋯ amj xj + ⋯ amn xn = 𝑏𝑚
x1 ≥ 0 x 2 ≥ 0 ⋯ x j ≥ 0 ⋯ x n ≥ 0
 Variable de
Transformations surplus
Variable
Maximiser f(x)  Minimiser –f(x)
d’écart
Xj ≤ 0 ➔ Xj = - X’j ; X’j ≥ 0
𝑥𝑗 = 𝑥𝑗+ − 𝑥𝑗− ; 𝑥𝑗+ ≥ 0 𝑒𝑡 𝑥𝑗− ≥ 0
Xj sans signe ➔
𝑛 𝑛
෍ 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑑𝑖
𝑗=1
➔ ෍ 𝑎𝑖𝑗 𝑥𝑗 − 𝑥𝑖𝑠 = 𝑑𝑖
𝑗=1
𝑒𝑡 𝑥𝑖𝑠 ≥ 0

𝑛 𝑛

෍ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑑𝑖 ➔ ෍ 𝑎𝑖𝑗 𝑥𝑗 + 𝑥𝑖𝑒 = 𝑑𝑖 𝑒𝑡 𝑥𝑖𝑒 ≥ 0

𝑗=1 𝑗=1
Représentation matricielle
n

Max z= ෍ cj xj Max z=c t x

j=1
n (P2 ) ተ Ax = b
(𝑃0 ) s/c ቊ
s/c
෍ aij xj = bi i=1,2,...,m x≥0
j=1
xj ≥ 0 j=1,2,...,n

𝑥1 𝑐1
𝑎11 𝑎12 𝑎13 ⋯ 𝑎1𝑛
𝑥2 𝑐2
𝑎21 𝑎22 𝑎23 ⋯ 𝑎2𝑛
𝐀= , 𝐱= ⋮ 𝐜= ⋮
⋮ ⋮ ⋮ ⋮ ⋮
⋮ ⋮
𝑎𝑚1 𝑎𝑚2 𝑎𝑚3 ⋯ 𝑎𝑚𝑛
𝑥𝑛 𝑐𝑛
𝐱 ≥ 𝟎 𝑢𝑛𝑒 𝑛𝑜𝑡𝑎𝑡𝑖𝑜𝑛 : 𝑒𝑙𝑙𝑒 𝑠𝑖𝑔𝑛𝑖𝑓𝑖𝑒 𝑥𝑖 ≥ 0 ∀ 𝑖 = 1 à 𝑛
Max +3x’1 - 4x2 + x3+ - x3-
s/c
- x’1 + 2x2 + 4x3+ - 4x3- - s1 = 50
- 2x’1 + 3x2 - x3+ + x3- + s2 = 70
- x’1 + x2 + x3+ - x3- = 60
X’1 ≥ 0 x2 ≥ 0 x3+ ≥ 0 x3- ≥ 0 s1 ≥ 0 s2 ≥ 0
 𝑎1𝑗 𝑏1 n
𝑎2𝑗 𝑏2
𝐚.𝐣 = ⋮ 𝑒𝑡 𝑏= Max z= ෍ cj xj
⋮
𝑎𝑚𝑗 𝑏𝑚 j=1
n
(P1 )
෍ a.j xj = b
s/c
j=1
xj ≥ 0 j=1,2,...,n

𝑀𝑎𝑥 3𝑥′1 − 4𝑥2 + 𝑥3+ − 𝑥3−

𝑠/𝑐
−1 2 4 −4 −1 1 50
+ −
−2 𝑥′1 + 3 𝑥2 + −1 𝑥3 + +1 𝑥3 + 0 𝑠1 + 0 𝑠2 = 70
−1 1 1 −1 0 0 60
𝑥′1 ≥ 0 𝑥2 ≥ 0 𝑥3+ ≥ 0 𝑥3− ≥ 0 𝑠1 ≥ 0 𝑠2 ≥ 0
 𝑥′1
𝑥2
𝑥3+
𝑀𝑎𝑥 3 −4 1 −1 0 0
𝑥3−
𝑠1
𝑠2
𝑠/𝑐
𝑥′1
𝑥2
−1 2 4 −4 −1 0 50
𝑥3+
−2 3 −1 1 0 1 = 70
𝑥3−
−1 1 1 −1 0 0 60
𝑠1
𝑠2
𝐱≥𝟎
 Max z=c t x
(P2 ) ተ Ax = b
s/c ቊ
x≥0

Cas particulier :
Le système Ax = b sera supposé non redondant.
Cette hypothèse est équivalente à rang(A) = m et par conséquent m  n.
Propriétés importantes du rang
[Link] rang d'une matrice A est toujours inférieur ou égal au plus petit de ses
dimensions :
[Link](A) ≤ min(m,n) où A est une matrice m×n.
[Link] rang(A)=min(m,n) alors A est de rang maximal.
[Link] matrice carrée n×n est inversible si et seulement si son rang est n.
 Définition 1
• On appelle base B toute sous-matrice carrée régulière (mxm) extraite
de A (il en existe au moins une, puisque rang(A) = m).
• Les m variables associées aux colonnes d'une base B sont appelées
variables de base
• Variables de base ➔ un sous vecteur xB
• Variables hors base ➔ un sous vecteur xN.
Définition 2
• On appelle solution de base (associée à la base B), la solution
particulière de BxB + NxN = b obtenue en posant XN = 0.
• ➔ XB = B-1b
• Une solution de base est dite réalisable si XB ≥ 0
• Une solution de base est dite dégénérée si le vecteur B-1b a des
composantes nulles.
 Soit B une base, en permutant les colonnes de A,
Ax = b ➔ BxB + NxN = b
5x1 +2x2 + 3𝑥3 + 4𝑥4 + x5 = 22
ቐ5𝑥1 + x2 + x3 + 5𝑥4 + 4𝑥5 = 22
4𝑥1 + 2𝑥2 + 3𝑥3 + 3𝑥4 = 18

𝑥4
4 5 2 3 1 𝑥3
𝐱 𝐵 = 𝑥1 𝐱𝑁 = 𝑥
B= 5 5 1 𝑁= 1 4 𝑥2 5
3 4 2 3 0

4𝑥4 + 5x1 +2x2 + 3𝑥3 + x5 = 22 4 5 2 𝑥4 3 1 22

𝑥3
𝑥1 + 1 4
ቐ5𝑥4 + 5𝑥1 + x2 + x3 + 4𝑥5 = 22 5 5 1 𝑥5 = 22
3𝑥4 + 4𝑥1 + 2𝑥2 + 3𝑥3 = 18 3 4 2 𝑥2 3 0 18
 Exemple 1
5x1 +2x2 + 3𝑥3 + 4𝑥4 + x5 = 22 solution de base
ቐ5𝑥1 + x2 + x3 + 5𝑥4 + 4𝑥5 = 22
4𝑥1 + 2𝑥2 + 3𝑥3 + 3𝑥4 = 18 admissible non-
dégénérée

5 2 4
(i) B = 5 1 5 𝑒𝑠𝑡 𝑢𝑛𝑒 𝑚𝑎𝑡𝑟𝑖𝑐𝑒 𝑑𝑒 𝑏𝑎𝑠𝑒.
4 2 3
𝑥1
𝑥3
x𝐵 = 𝑥2 x𝑁 = 𝑥
5
𝑥4 𝑥3 0
En posant x𝑁 = 𝑥5 =
0
5x1 +2x2 + 4𝑥4 = 22 x1 = 2 x 2 = 2 x 4 = 2
ቐ5𝑥1 + x2 + 5𝑥4 = 22
4𝑥1 + 2𝑥2 + 3𝑥4 = 18
 Exemple 2
solution de base
5x1 +2x2 + 3𝑥3 + 4𝑥4 + x5 = 22 non-admissible
ቐ5𝑥1 + x2 + x3 + 5𝑥4 + 4𝑥5 = 22
4𝑥1 + 2𝑥2 + 3𝑥3 + 3𝑥4 = 18 non-dégénérée

5 2 3
(𝑖𝑖) B = 5 1 1 𝑒𝑠𝑡 𝑢𝑛𝑒 𝑚𝑎𝑡𝑟𝑖𝑐𝑒 𝑑𝑒 𝑏𝑎𝑠𝑒.
4 2 3
𝑥1 4 𝑥4 0
x𝐵 = 𝑥2 = 4 x𝑁 = 𝑥 =
𝑥3 5 0
−2
 Exemple 3
5x1 +2x2 + 3𝑥3 + 4𝑥4 + x5 = 22 solution de base
ቐ5𝑥1 + x2 + x3 + 5𝑥4 + 4𝑥5 = 22
4𝑥1 + 2𝑥2 + 3𝑥3 + 3𝑥4 = 18 admissible
dégénérée

5 3 4
(𝑖𝑖𝑖) B = 5 1 5 𝑒𝑠𝑡 𝑢𝑛𝑒 𝑚𝑎𝑡𝑟𝑖𝑐𝑒 𝑑𝑒 𝑏𝑎𝑠𝑒.
4 3 3
𝑥1 0 𝑥2 0
x𝐵 = 𝑥3 = 2 x𝑁 = 𝑥 =
𝑥4 5 0
4
 Exemple 4
5x1 +2x2 + 3𝑥3 + 4𝑥4 + x5 = 22 solution de base
ቐ5𝑥1 + x2 + x3 + 5𝑥4 + 4𝑥5 = 22
4𝑥1 + 2𝑥2 + 3𝑥3 + 3𝑥4 = 18 admissible
dégénérée

2 3 4
(𝑖𝑖) B = 1 1 5 𝑒𝑠𝑡 𝑢𝑛𝑒 𝑚𝑎𝑡𝑟𝑖𝑐𝑒 𝑑𝑒 𝑏𝑎𝑠𝑒.
2 3 3
𝑥2 0 𝑥1 0
x𝐵 = 𝑥3 = 2 x𝑁 = 𝑥 =
𝑥4 5 0
4

Même solution que dans l’exemple 3 2 bases & même solution

 Ensemble convexe et point extrême
• Un ensemble C  En est convexe si pour tout couple de points x, y  C et pour
tout nombre réel   [0,1] 𝐳 = 𝛼𝐱 + 1 − 𝛼 𝐲 ∈ 𝐶

• Dans un ensemble convexe C  En , tout point z pour lequel il

n'existe aucun couple de points distincts x, y  C et aucun nombre
réel   ]0,1[ tels que z = x + (1- )y , est un point extrême.
 Solution réalisable et point extrême
• La notion géométrique de point extrême correspond à la notion algébrique de
solution de base réalisable.
 Solutions de base adjacentes
• On appelle solutions de base adjacentes deux solutions de base dont les
variables de base sont les mêmes sauf une qui est de base dans la première
base et hors base dans la seconde.
Classification des ensembles de solutions
• Au final un problème linéaire peut admettre :

1. Une solution optimale.

2. Une infinité de solution.
3. Une solution infinie.
4. Aucune solution réalisable.

Ceci fonction de l’ensemble admissible et de la fonction objective.

Théorème 1

Soit 𝑋 = 𝐱 ∈ 𝐸 𝑛 : 𝐀𝐱 = 𝐛, 𝐱 ≥ 𝟎

où A est une matrice de dimension mxn et

b  Em.
x* est un point extrême de X si et seulement
si x* est une solution de base réalisable de X.
Théorème 2 :
Théorème Fondamental de PL
Soit le programme linéaire (P) suivant:
Max cx
s/c AX = b
x≥ 0

où A est une matrice réelle mxn de rang m.

i. Si (P) admet une solution réalisable, alors il admet
une solution de base réalisable.
ii. Si (P) admet une solution optimale finie, alors
admet une solution de base optimale.
Algorithme du Simplexe : synthèse
• Ce qui est à retenir du simplexe :
1. Condition d’optimalité : la variable entrante dans un problème de
maximisation est la variable nonbase dont le coefficient Cj- Zj le plus élevé.
2. Condition de faisabilité : la variable sortante est la variable de la base dont
le ratio  a la plus petite valeur (on ignore les valeurs négatives).
3. Transformation de Gauss Jordan:
a. Ligne pivot :
i. Remplacer la variable sortante de l’ancienne base par la variable entrante.
ii. Nouvelle ligne pivot = ancienne ligne  élément pivot
b. Les autres lignes :
Nouvelle ligne = ligne actuelle – (coefficient pour obtenir 0 de I)*(nouvelle
ligne pivot)