Introduction

Forme standard
Résolution du PLS
Exemples
Exercices

Méthode Simplexe

Metrane Abdelmoutalib

EMSI
Marrakech Maroc

November 4, 2020

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

1 Introduction

2 Forme standard

3 Résolution du PLS

4 Exemples

5 Exercices

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Introduction
On a vu précédemment que la solution optimale est un sommet situé sur la
frontière du domaine des solutions réalisables.

Une démarche simple est de calculer en chaque sommet la valeur de la fonction

objective et prendre le sommet ou ce dernier est le plus grand. Pour accélérer
cette procédure, on a intérêt, au moment d’explorer un nouveau sommet, à
choisir parmi les sommets voisins de celui ou l’on se trouve celui qui permet
d’obtenir la plus grande augmentation de la fonction économique.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Principe du méthode simplexe

Partant d’une solution réalisable connue, située en un sommet de la frontière
du domaine d’acceptabilité, on cherche parmi les sommets voisins celui qui
améliore le plus la fonction objectif à optimiser. On passe alors à ce sommet et
on recommence jusqu’à ce qu’on soit en un sommet tel que le passage à aucun
des sommets voisins n’améliore la fonction à optimiser. Ce sommet sera alors
l’optimum cherché.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Historique
L’algorithme du simplexe est la méthode la plus utilisée de la recherche
opérationnelle. C’est G.B. Dantzig qui, dans un article paru en 1949, a décrit
cet algorithme, qui constitue l’épine dorsale de la recherche opérationnelle.
Depuis, cet algorithme a fait l’objet de centaines d’articles scientifiques et a
servi à la résolution de nombreux modèles linéaires relatifs à des problèmes de
gestion, de diétique, de transport, d’affectation...

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Prenons l’exemple 1 suivant :

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

s.c x1 + 2x2 + 3x3 ≤ 90

15x1 + 21x2 + 30x3 ≤ 1260
x1 + x2 + x3 ≤ 84
x1 ≥ 0, x2 ≥ 0 et x3 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

1 Introduction

2 Forme standard

3 Résolution du PLS

4 Exemples

5 Exercices

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

La mise sous forme standard consiste à introduire des variables suplémentaires

positives (Variables d’écart) une pour chaque contrainte de manière à réecrire
les inégalité ≤ et ≥ sous forme d’égalité.

Variables d’écart
Rappelons qu’une contrainte du modèle s’écrit comme :
x1 + 2x2 + 3x3 ≤ 90
Et introduisons une nouvelle variables e1 définie ainsi :
e1 = 90 − (x1 + 2x2 + 3x3 )
La variable e1 est qualifiée de variable d’écart. Elle représente dans ce cas le
reste du premier ressource lorsqu’on retient le plan de production (x; y ; z).

La contrainte x1 + 2x2 + 3x3 ≤ 90 est équivalente à la formule suivante :

e1 = 90 − (x1 + 2x2 + 3x3 ) et e1 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Forme Standard PLS

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

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Problème d’agriculteur
Écrivons sous forme standard le problème:

Max z = 1000x1 + 2000x2

s.c x1 + x2 ≤ 150 (Limitation sur le terrain)

4x1 + 2x2 ≤ 440 (Limitation sur l 0 eau)
x1 + 4x2 ≤ 480 (Limitation Main − d 0 oeuvre)
x1 ≤ 90 (Limitation d 0 irrigation)
x1 ≥ 0 et x2 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

(C1) on introduit e1 l’écart entre la surface du terrain utilisé et la surface

totale en hectare.
x1 + x2 + e1 = 150
(C2) on introduit e2 le gain en terme de ressource d’eau.

4x1 + 2x2 + e2 = 440

(C3) on introduit e3 l’écart entre les ressources humaines exploitées et

disponible.
x1 + 4x2 + e3 = 480
(C4) on introduit e4 l’écart entre le périmètre du terrain irrigué et la
limitation maximale exigée.

x1 + e4 = 90

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Problème d’agriculteur sous forme PLS

Max z = 1000x1 + 2000x2

s.c x1 + x2 + e1 = 150
4x1 + 2x2 + e2 = 440
x1 + 4x2 + e3 = 480
x1 + e4 = 90

x1 ≥ 0, x2 ≥ 0, e1 ≥ 0, e2 ≥ 0, e3 ≥ 0, et e4 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Exemple
Ecrire sous forme standard le problème suivant:

Max Z = 4x1 − 6x2 + 25x3 .

s.c x1 − 2x2 + 3x3 ≥ 90

15x1 + 21x2 + 30x3 ≤ 1260
x1 + x2 + x3 = 84
x1 ≥ 0, x2 ≥ 0 et x3 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

1 Introduction

2 Forme standard

3 Résolution du PLS

4 Exemples

5 Exercices

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

La résolution des modèles sous forme standard

Un résumé de l’algorithme du simplexe

L’algorithme du simplexe choisit d’abord un sommet initial, puis effectue une
opération itérative, dite pivotage, qui habituellement correspond à passer d’un
sommet à un sommet adjacent plus ”rentable”.
Nous décrirons le fonctionnement de l’algorithme du simplexe en l’appliquant
sur notre exemple.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Solution initiale

La mise en évidence d’une solution de base admissible initiale

Comme on l’a vu précédemment dans l’exemple 1, les points extrême
correspondent aux solutions de base admissible (réalisable). Celles-ci sont
obtenues en annulant 3 des 6 variables x1 , x2 , x3 , e1 , e2 et e3 . Par exemple,
poser x1 = x2 = x3 = 0 conduit à un système d’équations trivial à résoudre,
notamment :
e1 = 90
e2 = 1260
e3 = 84
Graphiquement, cette solution correspond au sommet O (l’origine). la fonction
objectif est égal à 0.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

On sait, à partir de l’analyse géométrique, que le sommet O n’est pas solution

optimale. Il faut donc modifier cette solution initiale de façon à augmenter la
valeur prise par la fonction objectif z.
L’algorithme du simplexe procède par itérations, chacune correspondant au
passage d’un sommet de la région admissible à un sommet adjacent de cette
région.
Notre exemple exigera 2 itérations.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

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.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Tableau du simplexe

On présente notre solution avec le tableau suivant :

x1 x2 x3 e1 e2 e3 B
e1 1 2 3 1 0 0 90
e2 15 21 30 0 1 0 1260
e3 1 1 1 0 0 1 84
cj 87 147 258 0 0 0 Z

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.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

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 ? Laissons-nous guider par l’intuition : on
augmentera la variable qui rapporte le plus x3 .
Afin de simplifier l’analyse, supposons que x1 et x2 garde pour le moment la
valeur 0. On augmente x3 , le bénéfice va augmenter.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Variable Sortante

Que choisir pour la variable qui va sortir de la base ?

On a potentiellement trois choix : e1 , e2 , e3 .

0 + 0 + 3x3 + e1 =90
0 + 0 + 30x3 + e2 =1260
0 + 0 + 1x3 + e3 =84

x3 ≥ 0 e1 ≥ 0, e2 ≥ 0 et e3 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Autrement

Quelle est la valeur maximale qu’on peut donner à x3 sans violer les contraintes
du modèle ?

la contrainte 3 (e3 = 0): x3 = 84

1260
la contrainte 2 (e2 = 0): x3 = 30
la contrainte 1 (e1 = 0): x3 = 30

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Autrement

Quelle est la valeur maximale qu’on peut donner à x3 sans violer les contraintes
du modèle ?

la contrainte 3 (e3 = 0): x3 = 84

1260
la contrainte 2 (e2 = 0): x3 = 30
la contrainte 1 (e1 = 0): x3 = 30

Si x3 = 84, la contrainte 2 n’est plus satisfaite.

1260
Si x3 = 30
= 42, la contrainte 1 n’est plus verifiée.
Si x3 = 30, tous les contraintes sont verifiée.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

le Pivot

x1 x2 x3 e1 e2 e3 B B /colonne choisie
e1 1 2 3 1 0 0 90 30
e2 15 21 30 0 1 0 1260 42
e3 1 1 1 0 0 1 84 84
cj 87 147 258 0 0 0 0 0

choix de pivot
Pour chaque itération, nous suivons les règles suivantes :
Variable entrante : plus fort coefficient strictement positif dans la ligne Cj
(coût).
Variable sortante : plus petite valeur strictement positive dans la colonne
B/colonne.
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.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Nouveau sommet

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
Ligne B −→ à Ligne cj −258 ligne x3

On obtient le tableau suivant :

x1 x2 x3 e1 e2 e3 B
1 2 1
x3 3 3
1 3
0 0 30
e2 5 1 0 −10 1 0 360
2 1
e3 3 3
0 − 31 0 1 54
cj 1 −25 0 −86 0 0 7740

Remarque importante
On vérifie pour chaque tableau calculé que les valeurs de variable de base sont
positive ou nulle

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Règle de pivot
Une autre manière de construire le tableau suivant:
Diviser la ligne de pivot par la valeur de pivot.
À chacune des variables de base, on associé la valeur 1 à l’intersection de la
ligne et la colonne de cette même variable et le reste de la colonne c’est 0.
Calculer le reste des valeurs du tableau par la règle de pivot.
Par exemple 21 sera remplacer par 21×3−2×30
3
= 1.
147 sera remplacer par 147×3−2×258
3
= −25

Remarques
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 = x1 − 25x2 − 86e1 + 7740 peut augmenter si
on augmente x1 avec x2 = e1 = 0. Il faut passer à un autre sommet,
l’algorithme n’est pas encore terminé.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

On effectue notre choix du pivot :

x1 x2 x3 e1 e2 e3 B B /colonne choisie
1 2 1
x3 3 3
1 3
0 0 30 90
e2 5 1 0 −10 1 0 360 72
2 1
e3 3 3
0 − 13 0 1 54 81
cj 1 −25 0 −86 0 0 7740

Transformation du tableau
Variable entrante qui correspond à la plus grande valeurs positive dans la
ligne cj qui est la variable x1 .
Variable sortante qui correspond à la plus petite valeurs positive dans la
colonne ”B /colonne choisie” qui 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).
1
Ligne x3 −→ à Ligne x3 − 3
ligne x1
2
Ligne e3 −→ à Ligne e3 − 3
ligne x1
Ligne cj −→ à Ligne cj − ligne x1

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Effectuons les calculs sur les lignes x1 et cj . On obtient :

x1 x2 x3 e1 e2 e3 B
x3 6
1 1
x1 1 5
0 −2 5
0 72
e3 6
cj 0 −25, 2 0 −84 − 15 0 7812

La fonction bénéfice s’écrit : Z = 7812 − 25, 2x2 − 84e1 − 15 e2 .

On remarque que si on augmente x2 , e1 ou e2 , le bénéfice ne pourra que
diminuer, on a atteint l’optimum.
l’optimum est atteint lorsque tous les coefficients de la ligne cj sont tous
négatifs ou nuls.

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

La solution est : x3 = 6, x1 = 72, x2 = 0, e3 = 6, e2 = e1 = 0

le bénéfice est : 7812 ( On peut vérifier cette valeur :
72 ∗ 87 + 258 ∗ 6 = 7812 ).

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

1 Introduction

2 Forme standard

3 Résolution du PLS

4 Exemples

5 Exercices

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Problème d’agriculteur
Résoudre ce problème à l’aide de l’algorithme du simplexe:

Max z = 1000x1 + 2000x2

s.c x1 + x2 ≤ 150
4x1 + 2x2 ≤ 440
x1 + 4x2 ≤ 480
x1 ≤ 90
x1 ≥ 0 et x2 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Une société fabrique 3 sortes de produits X, Y et Z à partir de 3 sortes de

composants A, B, C. Pour la production du mois d’octobre 1999, elle dispose
d’un stock de :
1070 composants A
880 composants B
350 composants C

Les quantités de composants intervenant dans les fabrications sont données par
le tableau suivant :
x y z
A 2 1 2
B 1 2 3
C 0 1 4
Les conditions d’exploitation sont les suivantes :
x y z
Prix de vente unitaire 10 8 14
Coût unitaire 3 4 7,5

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Exercice 1
Une société fabrique trois produits A, B et C. La chaı̂ne de montage comprend
deux ateliers I et II. Les capacités (en kWh/jour) des ateliers sont les suivantes
:
Atelier I : 720
Atelier II : 480.
Les caractéristiques de la production sont résumées dans le tableau ci-dessous.
Quel est le programme de production journalier optimal ?

Produit A B C
Bénéfice 108 100 84
Consommation Atelier I 27 10 6
Consommation Atelier II 3 10 14

Metrane Abdelmoutalib Méthode Simplexe

 Introduction
Forme standard
Résolution du PLS
Exemples
Exercices

Exercice 2
L’entreprise Duralumin fabrique pour des entreprises de quincaillerie, des pièces
en inox. Ces pièces sont de trois types : A,B et C. Elles sont fabriquées par lots
de 50 dans un grand atelier où sont rassemblées deux machines pour la
découpe de l’inox, une machine pour l’emboutissage, deux machines pour le
polissage et la finition. Chaque machine fonctionne 120 heures par mois. Les
caractéristiques de fabrication sont rassemblées dans le tableau suivant :

Coût de l’heure Lot A Lot B Lot C

Découpe 20 euros 1h 1,5 h 1,5h
Emboutissage 30 euros 0,5h 1h
Polissage et finition 40 euros 2h 1h 1h
Inox 50 euros 85 euros 68 euros
Prix de vente 200 euros 200 euros 210 euros

Metrane Abdelmoutalib Méthode Simplexe