Introduction

La méthode du simplexe en deux phases

Les cas particuliers ou pathologiques

aft
Méthode Simplexe : Phase1 et Phase2

Metrane Abdelmoutalib

Dr EMSI
Marrakech Maroc
[Link]@[Link]

November 24, 2020

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
La méthode du simplexe en deux phases
Les cas particuliers ou pathologiques

1 Introduction

2 La méthode du simplexe en deux phases

Introduction
Résolution de PLFI par la méthode du simplexe
Phase 2

3 Les cas particuliers ou pathologiques

Modèle sans solution admissible
Modèles non bornés

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
La méthode du simplexe en deux phases
Les cas particuliers ou pathologiques

Introduction
Ce n’est pas toujours simple de construire le tableau initial de la méthode du
simplexe. Une solution de base réalisable n’est pas toujours simple de la
trouver.

Nous essayons de traiter ce problème dans ce chapitre à l’aide de l’exemple

suivant (PL):
Max Z = 2000x1 + 1000x2

s.c 10x1 + 5x2 ≤ 200

2x1 + 3x2 = 60
(PL) x1 ≤ 12
x2 ≥ 6
x1 ≥ 0, x2 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
La méthode du simplexe en deux phases
Les cas particuliers ou pathologiques

l’ajout de variable d’écart (PLS)

Max Z = 2000x1 + 1000x2

s.c 10x1 + 5x2 + e1 = 200

2x1 + 3x2 = 60
(PLS) x1 + e3 = 12
x2 − e4 = 6
xi ≥ 0, ej ≥ 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
La méthode du simplexe en deux phases
Les cas particuliers ou pathologiques

l’ajout de variable d’écart (PLS)

Max Z = 2000x1 + 1000x2

s.c 10x1 + 5x2 + e1 = 200

2x1 + 3x2 = 60
(PLS) x1 + e3 = 12
x2 − e4 = 6
xi ≥ 0, ej ≥ 0

Proposition

(PL) ⇔ (PLS)

Solution de base réalisable?

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
La méthode du simplexe en deux phases
Les cas particuliers ou pathologiques

l’ajout de variable d’écart (PLS)

Max Z = 2000x1 + 1000x2

s.c 10x1 + 5x2 + e1 = 200

2x1 + 3x2 = 60
(PLS) x1 + e3 = 12
x2 − e4 = 6
xi ≥ 0, ej ≥ 0

Proposition

(PL) ⇔ (PLS)

Solution de base réalisable? pas facile de la trouver!!

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

L’approche géométrique qu’on peut utiliser pour trouver la solution optimale

est valable uniquement en dimension 2 ou au maximum en dimension 3. La
plupart des modèles rencontrés en pratique ne satisfont pas à cette condition. Il
existe une autre façon de procéder, de nature algébrique, qui utilise
astucieusement l’algorithme du simplexe et cela en ajoutant des variables
appelées artificielles dans les contraintes non réalisables si on remplace les
variables originales par 0 dans le (PLS).

Problème (PLF )

Max Z = 2000x1 + 1000x2

s.c 10x1 + 5x2 + e1 = 200

2x1 + 3x2 + a2 = 60
(PLF) x1 + e3 = 12
x2 − e4 + a4 = 6
xi ≥ 0, ej ≥ 0, a2 , a4 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Proposition

(PLS ⇔ PLF ) ⇐⇒ a2 = a4 = 0

Objectif
Pour obtenir un modèle équivalent à (PLS), il faudrait ajouter au modèle
précédent la double contrainte suivante :
a2 = a4 = 0
ce qui nous ramènerait à la situation de départ !

L’astuce consiste à ne inclure la double contrainte dans le modèle, mais à

utiliser une fonction-objectif qui pénalise le fait que les variables artificielles
prennent des valeurs positives. On considère ici le modèle (PMFI ) obtenu du
modèle précédent en substituant à z = 2000x1 + 1000x2 l’objectif suivant :
Min zA = a2 + a4 ou Max zA = −a2 − a4

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Problème (PLFI )

Min Za = a2 + a4

s.c 10x1 + 5x2 + e1 = 200

2x1 + 3x2 + a2 = 60
(PLFI ) x1 + e3 = 12
x2 − e4 + a4 = 6
xi ≥ 0, ej ≥ 0, a2 , a4 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Solution de base réalisable

(x1 , x2 ) = (0, 0), (e1 , e3 , e4 ) = (200, 12, 0) et (a2 , a4 ) = (60, 6). On a 4
contraintes et 7 variables, par suite 7-4 variables nulles.
x1 , x2 et e4 sont hors base.
e1 , e3 , a2 et a4 sont de base.

Remarque
Il ne faut pas que la fonction objectif soit en fonction des variables de
bases:

Za = a2 + a4 = (60 − 2x1 − 3x2 ) + (6 − x2 + e4 ) = 66 − 2x1 − 4x2 + e4

Si à la fin de résolution, la fonction objectif de PLFI est non nulle, alors

PLS n’admet pas de solution réalisable.

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Tableau initial de la phase I

Ce n’est pas un vrai tableau du simplexe puisque il faut que les coûts des
variables de base soient égales à 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

L05 = L5 − L2 et L”5 = L05 − L4

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Tableau final de la phase I

Figure: Tableau final de la phase 1

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Fin de la phase 1
Le dernier tableau est final de la phase 1 puisque tous les éléments de la
ligne C j sont tous positifs.
Comme la valeur optimal du (PLFI ) est 0, alors ce tableau final fournira
une solution de base réalisable de (PLS) qui est (x1 , x2 ) = (0, 20) et
(e1 , e3 , e4 ) = (100, 12, 14).
Le tableau initial de la phase 2 sera construit à partir du tableau final de la
phase 1.
Si la valeur optimal du (PLFI ) n’est pas égal à zéro (Za 6= 0), alors PLS
n’admet pas de solution réalisable.

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Tableau initial de la phase II

La phase II reprend l’objectif original qui était de maximiser
z = 2000x1 + 1000x2 . Le tableau initial de la phase II s’obtient en modifiant le
dernier tableau de la première phase de la façon suivante :
Les colonnes associées aux variables artificielles sont supprimées;
La dernière lignes est recalculée à partir des nouveaux coefficients de base.

Remarque

Max2000x1 + 1000x2 = −Min − 2000x1 − 1000x2

Alors résoudre un problème de maximisation revient à résoudre un problème de
minimisation avec un signe (-) près.

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Tableau initial de la phase II

Figure: Tableau Initial de la phase II

Ce n’est pas un vrai tableau de simplexe puisque le coût d’une variable de base
est différent de 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Tableau initial de la phase II

L05 = L5 − 1000L4

Ce Tableau n’est pas final puisque il y a au moins un élément de la ligne Cj

(Coût réduit) qui est positif.

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Tableau suivant de la phase II

Ce Tableau est final puisque tous les éléments de la ligne Cj (Coût réduit) sont
tous négatifs ou nuls.

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction Introduction
La méthode du simplexe en deux phases Résolution de PLFI par la méthode du simplexe
Les cas particuliers ou pathologiques Phase 2

Fin de Phase II
Puisque tous les valeurs de la dernière ligne (cj ) sont négatives ou nulles, alors
le dernier tableau est final, par suite la solution optimal et (x1 , x2 ) = (12, 12)

Remarques
Si on n’a pas une solution de base réalisable simple (Évidante) pour (PLS),
alors il faut faire la phase 1 de la méthode du simplexe dont le but de trouver
cette solution de base réalisable, et on a les deux cas suivantes:
Si Za 6= 0, alors il n’existe aucune solution réalisable et par suite aucune
solution du (PL).
Si Za = 0, alors le domaine réalisable et non vide, en plus on peut trouver
une solution de base réalisables à partir du tableau final de la phase 1. Le
dernier tableau de la phase 1 sera le tableau initial de la phase 2 en
supprimant les colonnes des variables artificielles et en recalculant la
denière ligne (cj ).

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
Modèle sans solution admissible
La méthode du simplexe en deux phases
Modèles non bornés
Les cas particuliers ou pathologiques

(PL)

Max Z = 1000x1 + 2000x2

s.c 10x1 + 5x2 ≤ 200

2x1 + 3x2 ≤ 60
(PL1 ) x1 ≥ 34
2x2 ≥ 14
x1 ≥ 0, x2 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
Modèle sans solution admissible
La méthode du simplexe en deux phases
Modèles non bornés
Les cas particuliers ou pathologiques

l’ajout de variable d’écart (PLS)

Max Z = 1000x1 + 2000x2

s.c 10x1 + 5x2 + e1 = 200

2x1 + 3x2 + e2 = 60
(PLS) x1 − e3 = 34
2x2 − e4 = 14
xi ≥ 0, ej ≥ 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
Modèle sans solution admissible
La méthode du simplexe en deux phases
Modèles non bornés
Les cas particuliers ou pathologiques

L’ajout de variable artificielle (PLFI )

Puisque (x1 , x2 ) = (0, 0) n’est pas réalisable, alors on aura besoin de la phase 1.
On ajoute uniquement des variables artificielles pour la 3ème et 4ème contraintes

Min Za = a3 + a4

s.c 10x1 + 5x2 + e1 = 200

2x1 + 3x2 + e2 = 60
(PLF1 ) x1 − e3 + a3 = 34
2x2 − e4 + a4 = 14
xi ≥ 0, ej ≥ 0, a3 , a4 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
Modèle sans solution admissible
La méthode du simplexe en deux phases
Modèles non bornés
Les cas particuliers ou pathologiques

Itération 1 et 2 de phase I

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
Modèle sans solution admissible
La méthode du simplexe en deux phases
Modèles non bornés
Les cas particuliers ou pathologiques

Fin de la phase I

C’est le tableau final de la phase 1 puisque tous les coefficients de la ligne des
coûts sont tous positifs (Problème de minimisation). Alors Comme la valeurs
optimale (Za ) de la phase 1 est non nulle (Za = 17.5 6= 0) alors il n’existe
aucune solution réalisable. Par suite, le problème (PL1 ) n’admet pas de
solution.

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2

 Introduction
Modèle sans solution admissible
La méthode du simplexe en deux phases
Modèles non bornés
Les cas particuliers ou pathologiques

(Modèles non bornés)

Max Z = x1 + 2x2

s.c − 2x1 + 3x2 ≤ 6

6x1 − 9x2 ≤ 18
x1 ≥ 1
x1 ≥ 0, x2 ≥ 0

Metrane Abdelmoutalib Méthode Simplexe : Phase1 et Phase2