Chapitre 3

Résolution des programmes linéaires

Méthode du Simplexe

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Présentation de la méthode Simplexe

❑ La méthode du simplexe, appelé aussi méthode de Dantzig, a été élaborée par George Dantzig en 1947
❑ Demeure jusqu’à présent l’une des meilleures méthodes pratiques utilisée en programmation linéaire
❑ La méthode du Simplexe est formulée à travers:
▪ La méthode algébrique (devient difficile une fois le nombre de variables et containtes augmente)
▪ La méthode des Tableaux Simplexe ( Objet de ce chapitre)
❑ La méthode du simplexe suit un processus itératif et convergent.
▪ Itératif: dans la mesure, où partant d’une solution de base, elle l’améliore progressivement par itérations
successives.
▪ Convergent: car toutes les solutions qui se succèdent à travers les itérations, doivent aboutir à une solution
qui correspondra à l’optimum de la fonction objective considérée.

❑ Son principe repose sur l’exploration des sommets de la région admissible en améliorant à chaque itération la
valeur de l’objectif
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 2- Notions générales

2.1. Forme générale/forme canonique/ forme standard d’un PL

2.1.1. Forme générale : Rappel

 La forme générale d’un PL est :

Max (ou min) z =σ𝒏𝑱=𝟏 𝒄𝒋𝒙𝒋
Sous les Contraintes :
𝒏

෍ 𝒂𝒊𝒋𝒙𝒋 ≤= ≥𝒃𝒊 𝒑𝒐𝒖𝒓 𝒊 = 𝟏, … . . , 𝒎

𝑱=𝟏

xj ≥ 0 ∀ 𝒋 = 𝟏, … . . , 𝒏
Avec
 xj: variables de décision du programme linéaire ( inconnues)
 aij , bi, cj : paramètres du programme linéaires (connus)
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 2- Notions générales

2.1.2. Forme canonique

La forme canonique d’un PL repose sur les points suivants :
❑ Maximisation de la fonction objectif
❑ Toutes les contraintes sont des inégalités de type ≤
❑ Toutes les variables sont positives.
donc la forme canonique d’un PL est la suivante
Max z =σ𝒏𝑱=𝟏 𝒄𝒋𝒙𝒋
Sous les Contraintes : σ𝒏𝑱=𝟏 𝒂𝒊𝒋𝒙𝒋 ≤ 𝒃𝒊 𝒑𝒐𝒖𝒓 𝒊 = 𝟏, … . . , 𝒎
xj ≥ 0 ∀ 𝒋 = 𝟏, … . . , 𝒏
❑ en utilisant la forme matricielle : Max Z= cT x
Ax ≤b
x ≥0
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 2- Notions générales

2.1.2. Forme canonique

Exemple:
Max Z= cT x
Max 5x1 + 4x2 + 3x3 Ax ≤b
2x1 + 3x2 + x3 ≤ 5
(P) 4x1 + x2 + 2x3 ≤ 11 x ≥0
3x1 + 4x2 + 2x3 ≤ 8
x1, x2, x3 ≥ 0

Avec:

5 5 x1
2 3 1
4 11 x2
c= ; b= ; A= 4 1 2 ; x=
3 8 x3
3 4 2

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2- Notions générales

2.1.3. Forme standard

La forme standard d’un PL est la forme exigée par la méthode Simplexe, elle repose sur les points suivants :
❑ Maximisation de la fonction objectif
❑ Toutes les contraintes sont des égalités =
❑ Toutes les variables sont positives.
donc la forme standard d’un PL est la suivante
Max z =σ𝒏𝑱=𝟏 𝒄𝒋𝒙𝒋
Sous les Contraintes : σ𝒏𝑱=𝟏 𝒂𝒊𝒋𝒙𝒋 = 𝒃𝒊 𝒑𝒐𝒖𝒓 𝒊 = 𝟏, … . . , 𝒎
xj ≥ 0 ∀ 𝒋 = 𝟏, … . . , 𝒏
❑ en utilisant la forme matricielle : Max Z= cT x
Ax =b
x ≥0
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 2- Notions générales

2.1.4. Passage de la forme générale à la forme canonique

On applique les transformations suivantes:
❑ Min Z → Max –Z
❑ Inéquations de type ≥ → inéquations de type ≤
❑ Transformer les équations en des inéquations ≤ :
a11 x1+ a12 x2 + …+ a1n xn = b1 → a11 x1+ a12 x2 + …+ a1n xn ≤ b1
a11 x1+ a12 x2 + …+ a1n xn ≥ b1

→ a11 x1+ a12 x2 + …+ a1n xn ≤ b1

-a11 x1- a12 x2 - …- a1n xn ≤ -b1

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2- Notions générales

2.1.5. Passage de la forme Canonique à la forme standard

On applique les transformations suivantes:

y est appelée variable d’écart

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2- Notions générales

2.1.5. Passage de la forme Canonique à la forme standard

Exemple:
Soit le PL suivant :

Min 5x1 -2 x2 Max -5x1 +2 x2 + 0 s1 + 0 s2

(P) x1 -x2 ≤ 5 x1 -x2 + s1 = 5
2x1 + 3x2 ≤ 4 2x1 + 3x2 + s2= 4
(P’)
-x1 + 6x2 = 12 -x1 + 6x2 = 12
x1, x2, x3 ≥ 0 x1, x2, s1 , s2 ≥ 0

❑ P’ est la forme standard de P

❑ Les variables supplémentaires s1 et s2 sont appelées variables d’écart.
Chaque variable d’écart est associée à une contrainte.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2- Notions générales

2.2. Variables de base/Variable hors base

Soit A x= b, un système d’équations linéaires avec A une matrice de type (mxn) , m ≤n et rang(A)=m :

❑ Il existe au moins une sous-matrice de A, qu’on notera B, matrice carrée inversible de type
(mxm) d’ordre m.

❑ On appelle base toute sous-matrice B carrée inversible extraite de A de type (m,m)

❑ les variables associées aux colonnes de B sont appelées variable de base, les autres: variables
hors base

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

3.1. Principe du Simplexe

1 2 3
Mettre le PL sous Commencer par Améliorer la
sa forme une solution de solution de base
standard base et élaborer par des itérations
le premier successives
tableau Simplexe (tableaux
simplexe) jusqu’à
obtention de la
solution optimale

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

1- Ecrire le PL sous sa forme standard

3.2. Etapes de la méthode du Simplexe

2- Identifier la première solution de base

3- Construire le premier tableau Simplexe

4- Choisir la variable à introduire à la base

Non

5-Identifier la variable à enlever de la base

Tester si la dernière
ligne du tableau ne
contient que des 6- Améliorer la solution de base par le pivotage
éléments négatifs
ou nuls
oui 7-Dresser le tableau simplexe suivant

Fin
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 3- Phases d’élaboration de la méthode Simplexe

3.3. Appréhension de la méthode Simplexe à travers un exemple

On considère le PL suivant:
Max 5x1 + 4x2 + 3x3
2x1 + 3x2 + x3 ≤ 5
(P) 4x1 + x2 + 2x3 ≤ 11
3x1 + 4x2 + 2x3 ≤ 8
x1, x2, x3 ≥ 0

Etape 1 : écrire le PL sous sa forme standard

Max 5x1 + 4x2 + 3x3
En rajoutant les variables d’écart notre PL devient: 2x1 + 3x2 + x3 +s1= 5
(P’) 4x1 + x2 + 2x3 + s2 = 11
3x1 + 4x2 + 2x3 + s3 = 8
x1, x2, x3 ,s1 ,s2 ,s3 ≥ 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Etape 1 : écrire le PL sous sa forme standard

La forme matricielle du PL: Max 5x1 + 4x2 + 3x3

2x1 + 3x2 + x3 +s1= 5
(P’) 4x1 + x2 + 2x3 + s2 = 11
3x1 + 4x2 + 2x3 + s3 = 8
x1, x2, x3 ,s1 ,s2 ,s3 ≥ 0

5
4 5
𝟐 𝟑 𝟏 1 0 0
3 11
c= ; b= ; A= 𝟒 𝟏 𝟐 0 1 0
0 8
𝟑 𝟒 𝟐 0 0 1
0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Etape 2: identifier une première solution de base

❑ Pour une première solution de base, on considère celle évidente, mais éloignée de la solution
optimale, qui est l’origine, c’est-à-dire : x1=x2=x3= 0

❑ On annule donc les variables de décision x1, x2, x3 qui deviennent des variables Hors base (VHB)

❑ Cette solution à l’origine permet de trouver les valeurs de s1 ,s2 ,s3 qui sont les variables de base (VB):

s1= 5- 2x1 - 3x2 - x3 s1= 5

s2 = 11- 4x1 - x2 - 2x3 s2 = 11
s3 = 8- 3x1 - 4x2 - 2x3 s3 = 8

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Etape 3: construire le premier tableau Simplexe

❑ À partir de notre solution de base initiale, on va construire le premier tableau Simplexe qui se dresse comme suit:

Max 5x1 + 4x2 + 3x3

cj 5 4 3 0 0 0
2x1 + 3x2 + x3 +s1= 5
ci VB x1 x2 x3 s1 s2 s3 bi (P’) 4x1 + x2 + 2x3 + s2 = 11
0 s1 2 3 1 1 0 0 5 3x1 + 4x2 + 2x3 + s3 = 8
x1, x2, x3 ,s1 ,s2 ,s3 ≥ 0
0 s2 4 1 2 0 1 0 11
0 s3 3 4 2 0 0 1 8
zj 0 0 0 0 0 0 0
cj-zj 5 4 3 0 0 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Etape 3: construire le premier tableau Simplexe

❑ À partir de notre solution de base initiale, on va construire le premier tableau Simplexe qui se dresse comme suit:

Max 5x1 + 4x2 + 3x3

Coeff. des 2x1 + 3x2 + x3 +s1= 5
VHB dans la
(P’) 4x1 + x2 + 2x3 + s2 = 11
fonction 3x1 + 4x2 + 2x3 + s3 = 8
objectif x1, x2, x3 ,s1 ,s2 ,s3 ≥ 0
Solution :Valeurs
des Variables de
base

Zj = σ ciaij 𝑎ij:Coefficients de
la matrice des
contraintes
Profit
marginal
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 3- Phases d’élaboration de la méthode Simplexe

Etape 3: construire le premier tableau Simplexe Max 5x1 + 4x2 + 3x3

2x1 + 3x2 + x3 +s1= 5
(P’) 4x1 + x2 + 2x3 + s2 = 11
3x1 + 4x2 + 2x3 + s3 = 8
x1, x2, x3 ,s1 ,s2 ,s3 ≥ 0
❑ Les Variables de base : s1 s2 s3
❑ Les variables Hors base: x1 x2 x3

❑ la solution de base:

(x1 x2 x3 s1 s2 s3 )= (0 0 0 5 11 8)

❑ Cette solution n’est pas optimale. On

recherchera donc une solution de base
meilleure: d’où une autre iteration (Objectif
de la prochaine étape su Simplexe)
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 3- Phases d’élaboration de la méthode Simplexe

Etape 4: changement de base en choisissant la variable entrante

❑ Cette étape consiste à amélioration la solution de base à partir du premier tableau du Max 5x + 4x + 3x
1 2 3
simplexe. 2x1 + 3x2 + x3 +s1= 5
❑ On augmente la fonction objectif en introduisant une variable dans la (P’)
Base prenant la place d’une autre variable qui va sortir de la base
4x1 + x2 + 2x3 + s2 = 11
3x1 + 4x2 + 2x3 + s3 = 8
❑ Une augmentation d’une unité de x1 fera augmenter la fonction objectif de 5 x1, x2, x3 ,s1 ,s2 ,s3 ≥ 0
❑ Une augmentation d’une unité de x2 fera augmenter la fonction objectif de 4
❑ Une augmentation d’une unité de x3 fera augmenter la fonction objectif de 3

❑ Nous avons intérêt à maximiser le plus vite possible la valeur de la

fonction objectif donc augmenter la variable ayant le coefficient
le plus grand strictement positif ici x1

Règle de choix de la variable entrante: dans le cas de maximisation

on choisit la variable ayant le plus grand coefficient strictement positif
de la dernière ligne du tableau Simplexe

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Etape 4: changement de base en choisissant la variable entrante

❑ la variable entrante à la base est donc x1

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Etape 5: identifier la variable à enlever de la base :choix de la variable sortante

❑ La colonne qui correspond à la variable entrante est
appelé la colonne pivot
❑ Pour choisir la variable sortante à enlever de la
base, on calcule le rapport des coefficients bi
sur les coefficients de la colonne pivot

❑ Dans le cas où le coefficient dans la colonne

entrante est négatif ou nul, on ne le compte pas
dans le calcul du minimum.

❑ On choisit la ligne qui correspond à la valeur

minimale de ce ratio: c’est la ligne pivot

❑ La variable correspondante( ici s1) sera la variable sortante

de la base remplacée par celle entrante
❑ On appellera l’intersection de la colonne pivot et la ligne
du pivot, l’élément pivot ou le pivot de gauss (ici c’est 2)
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 3- Phases d’élaboration de la méthode Simplexe

Etape 6: le pivotage
❑ Dans cette phase, on dressera un deuxième
tableau simplexe à travers l’opération de
pivotage qui consiste à rendre le pivot=1

❑ Pour rendre le pivot=1, on divisera la ligne

du pivot par le pivot

❑ Il ne faut pas oublier de placer variable

entrante à la place de celle sortante et de
remplir la case correspondant au
coefficient de la variable de base entrante

❑ la nouvelle solution de base réalisable sera

donc formée par les variables ( x1,s2, s3)

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Etape 6: le pivotage
Pour remplir les coefficients des autres lignes du tableau simplexe
,on suit la méthode de pivot de gauss qui consiste à:
❑ transformer la colonne du pivot à un vecteur unité (les
coefficients de la colonne du pivot sont nuls sauf le pivot =1)

❑ Les autres coefficients sont obtenus par la règle du rectangle:

(élément de la colonne du pivot x élement de la ligne pivot)

NV= AV-
𝑷𝑰𝑽𝑶𝑻

3𝑥1 1
NV=2- =
2 2
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 3- Phases d’élaboration de la méthode Simplexe

❑ Une fois le tableau rempli, la solution trouvée est donc:

z=25/2=12,5 avec

(x1 x2 x3 s1 s2 s3 )= (5/2 0 0 0 1 1/2 )

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Etape 7: tester la dernière ligne du tableau

❑ Si, la dernière ligne du tableau du simplexe ne contient que
des éléments négatifs ou nuls (pour les variables Hors base),
pour un problème de maximisation, cela signifie que l’optimum
est atteint(le critère D’arrêt de l’algorithme est cj-zj≤0 pour VHB)

❑ Sinon, il faut conduire une autre itération en reprenant toutes

les étapes précédentes jusqu’à satisfaire ce critère d’arrêt.

❑ Dans notre cas, il reste encore une valeur positive non nulle qui
correspond à la variable X3: elle sera donc la nouvelle variable
à introduire à la base et sa colonne devient la colonne pivot

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Itération 2:
❑ X3 est la variable qi correspond au plus grand coefficient non
nul de la dernière ligne du tableau donc c’est nouvelle
variable entrante.
❑ pour identifier la variable sortante, on calcule le ratio des bi
sur la colonne pivot

❑ Le ratio minimum correspond la ligne

de s3: c’est la variable sortante qui sera
Remplacée par X3
❑ Le nouveau élément pivot est donc
1/2

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Itération 2:
Pour améliorer la solution, On remplit maintenant le nouveau
tableau en procédant de la même manière qu’auparavant, on
obtient ce tableau simplexe,

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 3- Phases d’élaboration de la méthode Simplexe

Itération 2:
❑ La dernière ligne du tableau Simplexe de cette deuxième
itération n’a que des coefficients négatifs et nuls, l’algorithme a
convergé donc vers la solution optimale qui donne:

Zmax= 13 avec:

(x1 x2 x3 s1 s2 s3 )= (2 0 1 0 1 0)

❑ Dans cet exemple s2 =1, ceci signifie que

La deuxième contrainte n'est pas saturée!
Par contre s1 et s3 sont nuls ce quiveut dire que
les contraintes 1 et 3 sont saturées.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
Soit le problème d'optimisation suivant :

Max 3x1 + 5x2

x1 + 2x2 ≤ 10000
(P) 2x1 + 3x2 ≤ 12000
x1 + 4x2 ≤ 15000
x1, x2 ≥ 0

Résoudre ce PL par la méthode du simplexe

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
Étape 1: écrire le PL sous sa forme standard

Max 3x1 + 5x2 Max 3x1 + 5x2

x1 + 2x2 ≤ 10000 x1 + 2x2 + s1=10000
(P) (P) 2x1 + 3x2 + s2 =12000
2x1 + 3x2 ≤ 12000
x1 + 4x2 ≤ 15000 x1 + 4x2 + s3 = 15000
x1, x2 ≥ 0 x1, x2 ,s1 ,s2 ,s3≥ 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
Étape 2: 1er tableau Simplexe à partir de la solution initiale de base Max 3x1 + 5x2
x1 + 2x2 + s1=10000
(P) 2x1 + 3x2 + s2 =12000
x1 + 4x2 + s3 = 15000
x1, x2 ,s1 ,s2 ,s3≥ 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
Étape 2: 1er tableau Simplexe à partir de la solution initiale de base Max 3x1 + 5x2
x1 + 2x2 + s1=10000
(P) 2x1 + 3x2 + s2 =12000
x1 + 4x2 + s3 = 15000
x1, x2 ,s1 ,s2 ,s3≥ 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
Étape 3: identifier la variable entrante

Elle correspond à la
variable qui a le plus
grand coefficient dans la
dernière ligne du tableau
Simplexe ici 5 donc la
variable x2

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
Étape 4: identifier la variable sortante

Le ratio minimum
correspond la variable s3
C’est la variable sortante
qui sera remplacée par x2
Le pivot est donc 4

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
Étape 4: amélioration de la solution en construisant un deuxième tableau simplexe
Itération 1

La solution pour cette itération est

z= 5*3750=18750

Pour (x1 x2 s1 s2 s3 )= (0 3750 0 0 0)

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
La dernière ligne contient encore une valeur positive, il faut donc améliorer d’avantage la
fonction objectif en procédant à un autre changement de base à travers une autre
itération

La prochaine
variable entrante
pour la prochaine
itération est donc X1

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
Itération 2:

La variable sortante est s2

qui sera remplacée par
x1 et le nouveau pivot est
1,25

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 1:
Itération 2:

La dernière ligne du tableau Simplexe

ne contient que des éléments nuls et
négatifs: l’algorithme a convergé vers
la solution optimale.

Zmax= 3*600+5*3600= 19800

Avec

(x1 x2 s1 s2 s3 )= (600 3600 2200 0 0)

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 4- Exemples d’application de la méthode Simplexe

Exercice 2:

Max z = 3x1 + 4x2 + 2x3

x1 + x2 - x3 ≤ 10
x1 - 2x2 + 3x3 ≤ 14
x1; x2; x3 ≥ 0

Résoudre ce PL à travers la méthode Simplexe

La solution optimale est :x1=0 x2=44 x3=34

Avec zmax=244

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

Dans les sections précédentes, nous avons utilisé la méthode du Simplexe

en considérant les deux hypothèses suivantes:

❑ On part d’une solution de base de départ réalisable (celle associée à

l’origine)

❑ Le programme linéaire est non dégénéré (C’est-à-dire les bi>0 et les

variables de décision sont strictement positives)

En général, ces hypothèses ne sont toujours pas vérifiées!

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

L’objectif de cette deuxième partie de ce chapitre est d’étudier tous les cas possibles des
PLs en rapportant les modifications nécessaires à la méthode Simplexe:

❑ Résoudre le cas de minimisation

❑ Le cas des bi<0

❑ Le cas des variables non positives ou sans contraintes de signe

❑ Les PLs particuliers ( solution impossible, infinité de solutions, problème non borné et
problème dégénéré)

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

Dans le cas de minimisation de l’objectif, les itérations et l’optimalité de la méthode du

simplexe sont déterminés par les critères suivants :

❑ Critère de la variable entrante : On choisit la variable hors base ayant le coût réduit (l’effet
net) le plus négatif ( puisqu’on cherche à minimiser z)

❑ Critère de la variable sortante : le même que dans le cas de maximisation, puisque ce

critère est lié à la réalisabilité des variables( on prend le min du ratio)

❑ Critère d’optimalité : L’algorithme du simplexe s’arrête quand tous les coûts réduits des
variables hors base (coefficients de la dernière ligne du tableau simplexe) sont tous positifs
ou nuls.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

Considérant le PL suivant:

Min -x1 - 2x2

Sc

(P) -3x1 + 2x2 ≤2

-x1 + 2x2 ≤ 4
x1 + x2 ≤ 5
x1, x2 ≥ 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

1ère étape: écrire le programme sous sa forme standard:

On remarque ici que tous les termes du second membre sont positifs (2,4,5), donc la solution
de base initiale est celle qui correspond aux variables de base (s1,s2 et s3) et les variables hors
base x1 et x2.
La solution initiale est ( x1 x2 s1 s2 s3)=( 0 0 2 4 5 )
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

2ème étape: le tableau Simplexe initial

cj -1 -2 0 0 0
ci VB x1 x2 s1 s2 s3 bi
0 s1 -3 2 1 0 0 2
0 s2 -1 2 0 1 0 4
0 s3 1 1 0 0 1 5
zj 0 0 0 0 0 0
cj-zj -1 -2 0 0 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

2ème étape: le tableau Simplexe initial

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

3ème étape: variable entrante et variable sortante

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

3ème étape: variable entrante et variable sortante

Le pivot est 2
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

4ème étape: construction du nouveau tableau simplexe à travers les opérations de pivotage

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

4ème étape: construction du nouveau tableau simplexe à travers les opérations de pivotage

Nous sommes passés de z=0 vers z=-2 avec la

solution:
( x1 x2 s1 s2 s3)=( 0 1 0 2 4 )
La dernière ligne contient encore un élément
négatif, on doit minimiser davantage z à travers
une deuxième itération
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

2ème itération

Variable entrante: x2
Variable sortante: x1
Le pivot:2

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

2ème itération

Nous sommes passés de z=0 vers z=-2 ensuite vers

z=-6 avec la solution:

( x1 x2 s1 s2 s3)=( 1 5/2 0 0 3/2)

Ce n’est pas encore la solution de base, il reste

encore une VHB (s1) avec un effet net négatif.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

3ème itération

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

3ème itération

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

3ème itération

Le critère d’arrêt est satifait.Nous sommes passés

de z=0 vers z=-2 vers z=-6
Et enfin Vers la solution optimale zmin=-8:

( x1 x2 s1 s2 s3)=( 2 3 2 0 0)

La contrainte 1 n’est pas saturée.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.1. Cas de la minimisation

Remarque :

On peut résoudre le problème de minimisation en

considérant que Min Z revient à Max -Z et résoudre
le PL en suivant les étapes du simplexe pour une
maximisation.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2. le cas général

Dans le cas général on peut avoir les situations suivantes :

❑ Une ou plusieurs contraintes possède un second membre bi négatif, alors il y a violation de la

contrainte de positivité pour la variable d’écart concernée (ei=bi<0).

❑ Le problème contient déjà des contraintes d’égalité alors ces dernières n’ont pas besoin de
l’adjonction de variables d’écart et il n’existe pas de sous-matrice identité dans la matrice A :
dans ce cas on ne peut démarrer à partir d’une solution de base à l’origine

Ceci dit, Il est nécessaire de mettre en place une procédure pour obtenir une matrice identité
comme matrice de base initiale et qui correspond à une solution de base initiale réalisable. En
général, une telle procédure est basée sur l’adjonction de ce qu’on appelle : variables artificielles.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2. le cas général

5.2.1. La méthode du grand M (big M)

Partons du PL suivant:
Max 3x1 + 2x2
x1 + 3x2 –e1=5
(P) Forme standard (P) 3x1 + x2 =7

x1, x2 ≥ 0

En donnant aux variables x1 et x2 la valeur zéro, on

trouve que la variable S1 est négative (e1 =-5) et la
deuxième contrainte n’est pas vérifiée (0=7). Ainsi,
l’origine n’est pas une solution réalisable et on ne
pourra pas utiliser l'algorithme du simplexe.
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.2. le cas général

5.2.1. La méthode du grand M (big M)

Pour pallier à ce problème, nous allons introduire à notre système des variables artificielles:
Max 3x1 + 2x2 Max 3x1 + 2x2 –M a1–M a2
x1 + 3x2 –e1=5
(P) Variables artificielles x1 + 3x2 –e1 + a1=5
3x1 + x2 =7
(P)
3x1 + x2+ a2 =7
x1, x2 ,s1 ≥ 0
x1, x2 ,s1, a1, a2 ≥ 0

De plus, on transforme la fonction objectif en pondérant les variables artificielles avec un

coefficient –M où M est un nombre positif supposé très grand. Ce coefficient va assurer que
les variables artificielles ne changeront pas le problème traité(Méthode du grand M)

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2. le cas général

5.2.1. La méthode du grand M (big M)

Max 3x1 + 2x2 –M a1–M a2 Avec ces modifications, en donnant aux variables x1 et x2 la valeur zéro,
x1 + 3x2 –e1 + a1=5 On peut démarrer le simplexe avec une solution réalisable à l’origine
(P) Puisque les contraintes sont vérifiées grâce aux variables artificielles
3x1 + x2+ a2 =7
introduites
x1, x2 ,s1, a1, a2 ≥ 0

Les variables artificielles a1 et a2

La matrice des contraintes devient alors: 𝟏 𝟑 −𝟏 𝟏 𝟎 seront donc les VB tandis que
On pourra en extraire une base B carrée A= 𝟑 𝟏 𝟎 𝟎 𝟏 x1, x2 ,e1 seront les VHB pour
inversible associée aux variables construire notre tableau simplexe
artificielles a1 et a2 initial.
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.2. le cas général

5.2.1. La méthode du grand M (big M)

Max 3x1 + 2x2 –M a1–M a2 Après avoir mis le Pl sous la forme standard, la solution de base initiale
x1 + 3x2 –e1 + a1=5 Correspondant au tableau simplexe initial est :
(P)
3x1 + x2+ a2 =7
( x1 x2 e1 a1 a2)=(0 0 0 5 7)
x1, x2 ,s1, a1, a2 ≥ 0

❑ Comme leur nom l’indique, les variables artificielles n’ont aucune interprétation, leur utilité réside
en la possibilité de démarrer le Simplexe à partir une solution d’origine.

❑ Cependant, nous avons intérêt à les faire sortir le plutôt possible de la base car leur présence
cause une diminution importante de la valeur de la fonction objectif ( Coefficient M assez grand)!

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2. le cas général

Max 3x1 + 2x2 –M a1–M a2
5.2.1. La méthode du grand M (big M)
x1 + 3x2 –e1 + a1=5
Construction du tableau initial Simplexe: (P)
3x1 + x2+ a2 =7

cj 3 2 0 -M -M x1, x2 ,s1, a1, a2 ≥ 0

ci VB x1 x2 e1 a1 a2 bi
-M a1 1 3 -1 1 0 5
-M a2 3 1 0 0 1 7
zj -4M -4M M -M -M -12M
cj-zj 3+4M 2+4M -M 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2. le cas général

Max 3x1 + 2x2 –M a1–M a2
5.2.1. La méthode du grand M (big M)
x1 + 3x2 –e1 + a1=5
Construction du tableau initial Simplexe: (P)
3x1 + x2+ a2 =7

x1, x2 ,s1, a1, a2 ≥ 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.1. La méthode du grand M (big M)

Changement de base: identifier la variable entrante et sortante

Variable entrante: x1
Variable sortante :a2
Pivot:3

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.1. La méthode du grand M (big M)

Remplir le deuxième tableau simplexe:

Une fois une variable artificielle sort de la base, on ne la
considère plus dans les opérations qui suivent.

La solution pour cette itération est :

( x1 x2 e1 a1 a2)=(7/3 0 0 8/3 0)

Pour z= 7-8/3M

Une variable artificielle figure encore dans la

solution→ ce n’est pas la solution optimale

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.1. La méthode du grand M (big M)

2ème itération

Variable entrante: x2
Variable sortante :a1
Pivot:8/3

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.1. La méthode du grand M (big M)

2ème itération

La dernière ligne contient encore un élément

positifs pour les VHB, il faut exécuter une 3ème
itération.
la solution de cette itération est:
( x1 x2 e1 a1 a2)=(2 1 0 0 0)

Pour z max= 8
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.2.1. La méthode du grand M (big M)

3ème itération

Variable entrante: e1
Variable sortante :x1
Pivot:1/8

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.1. La méthode du grand M (big M)

3ème itération

La dernière ligne ne contient que des

éléments négatifs ou nuls pour toutes les
VHB: c’est la solution optimale avec
( x1 x2 e1 a1 a2)=(0 7 16 0 0)

Pour z max= 14
La première contrainte est non saturée

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.1. La méthode du grand M (big M)

Remarque:

Dans le cas d’un PL de minimisation, l’application de la méthode M consiste à transformer

la fonction objectif en pondérant les variables artificielles avec un coefficient +M où M est
un nombre positif supposé très grand

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.1. La méthode du grand M (big M)

À RETENIR:
La méthode du grand M consiste à :
❑ Introduire des variables artificielles ai dans les contraintes qui posent un problème pour la
réalisabilité de la base initiale.

❑ Remplacer la fonction objectif par :

Max z=cTx−M σ𝑚 𝑚
𝑖=1 ai (Problème de maximisation) ou Min z= c x+M σ𝑖=1 ai (Problème de minimisation)
T

où M est une constante positive assez grande.

❑ On n’est pas obligé de donner une valeur à M, lorsque M est comparé à un nombre, il sera
toujours considéré comme plus grand.

❑ Si au moins une variable artificielle est encore dans la base dans le tableau optimal, alors le
problème est non réalisable.
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

Les PLs particuliers:

❑ Solution impossible: se produit lorsque la méthode du simplexe se termine avec une

solution où il y a des variables artificielles non nulles

❑ Infinité de solutions: Se produit lorsque dans l’itération finale une variable Hors base a un
coefficient nul dans la dernière ligne( cj-zj=0), ceci veut dire qu’elle peut être introduite
dans la base et donner une autre solution optimale sans changer la valeur de la fonction
objectif.

❑ Problème non borné: Lorsqu’on n’arrive pas à préciser la variable sortante (tous les
coefficients de la colonne de la variable entrante nuls et/ou négatifs → Zmax=+∞)

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Problème dégénéré: le phénomène de dégénérescence se produit lorsque:

▪ Pour déterminer la variable entrante, nous sommes en présence d’au moins deux variables
hors base ayant le même et le plus élevé coefficient strictement positif dans la dernière ligne.

▪ En déterminant la variable sortante, nous sommes en présence d’au moins deux variables de
base ayant le même et le plus petit rapport positif dans la dernière colonne.

▪ lorsque le min du ratio des bi/aij de la colonne entrante=0.

▪ Quand plusieurs variables sont candidates pour sortir de la base, la nouvelle solution de base
aura une (ou plusieurs) variables de base prenant la valeur 0.
On dit alors que la solution de base est dégénérée.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Problème dégénéré:

❑ En cas de dégénérescence, l’algorithme peut revenir sur une solution de base déjà
visitée (→ cycle).
Il existe des règles de pivotage limitant les risques de cycle :
▪ règle de plus petit indice: Règle de bland
▪ perturbation des données : ajouter au membres de droite des contraintes des ϵ
suffisamment petits.

❑ un problème dégénéré n'empêche pas de trouver une solution optimale, mais il peut
ralentir l'algorithme et nécessiter des précautions pour éviter les boucles infinies.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

Les PLs particuliers:

❑ Infinité de solutions:

Min Z= 400x1+ 600x2 Min Z= 400x1+ 600x2 +M a1 +Ma2+Ma3

x1 +1,5 x2 ≥300 x1 +1,5 x2 –s1 +a1=300
(P) (P)
x1 ≥50 X1-s2 +a2=50
x2 ≥100 X2-s3 +a3=100
x1 ; x2 ≥0 Forme standard x1 ; x2 s1 s2 s3 a1 a2 a3≥0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

Min Z= 400x1+ 600x2 +M a1 +Ma2+Ma3

❑ Infinité de solutions:
x1 +1,5 x2 –s1 +a1=300
(P) X1-s2 +a2=50
X2-s3 +a3=100
x1 ; x2 s1 s2 s3 a1 a2 a3≥0
cj 400 600 0 0 0 M M M
ci VB X1 X2 s1 s2 s3 a1 a2 a3 bi
M a1 1 1,5 -1 0 0 1 0 0 300
M a2 1 0 0 -1 0 0 1 0 50
M a3 0 1 0 0 -1 0 0 1 100
zj 2M 2,5M -M -M -M M M M 450M
Cj-zj 400-2M 600-2,5M M M M 0 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

❑ Infinité de solutions:

cj 400 600 0 0 0 M M M
Ratio
ci VB X1 X2 s1 s2 s3 a1 a2 a3 bi
200
M a1 1 1,5 -1 0 0 1 0 0 300
-
M a2 1 0 0 -1 0 0 1 0 50
100
M a3 0 1 0 0 -1 0 0 1 100
zj 2M 2,5M -M -M -M M M M 450M Variable entrante: X2
Variable sortante: a3
Cj-zj 400-2M 600-2,5M M M M 0 0 0
Pivot :1

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

❑ Itération 1:

cj 400 600 0 0 0 M M M
ci VB X1 X2 s1 s2 s3 a1 a2 a3 bi
M a1 1 0 -1 0 1,5 1 0 150
M a2 1 0 0 -1 0 0 1 50
600 X2 0 1 0 0 -1 0 0 1 100

zj 2M 600 -M -M 1,5M-600 M M 60000+

200M
Cj-zj 400-2M 0 M M 600-1,5M 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

cj 400 600 0 0 0 M M M
ci VB X1 X2 s1 s2 s3 a1 a2 a3 bi Ratio
M a1 1 0 -1 0 1,5 1 0 150 150
M a2 1 0 0 -1 0 0 1 50 50
600 X2 0 1 0 0 -1 0 0 1 100 -

zj 2M 600 -M -M 1,5M-600 M M 60000+ Variable entrante: X1

200M Variable sortante: a2
Cj-zj 400-2M 0 M M 600-1,5M 0 0
Pivot :1

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

❑ Itération 2:

cj 400 600 0 0 0 M M M
ci VB X1 X2 s1 s2 s3 a1 a2 a3 bi
M a1 0 0 -1 1 1,5 1 0 100
400 X1 1 0 0 -1 0 0 1 50
600 X2 0 1 0 0 -1 0 0 1 100

zj 400 600 -M M-400 1,5M-600 M M 100M+8

0000
Cj-zj 0 0 M 400-M 600-1,5M 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

❑ Itération 2:

cj 400 600 0 0 0 M M M
ci VB X1 X2 s1 s2 s3 a1 a2 a3 bi Ratio
M a1 0 0 -1 1 1,5 1 0 100 66,66
400 X1 1 0 0 -1 0 0 1 50 -
600 X2 0 1 0 0 -1 0 0 1 100 -
Variable entrante: s3
zj 400 600 -M M-400 1,5M-600 M M 100M+8 Variable sortante: a1
0000
Pivot :1,5
Cj-zj 0 0 M 400-M 600-1,5M 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

❑ Itération 3:

cj 400 600 0 0 0 M M M
ci VB X1 X2 s1 s2 s3 a1 a2 a3 bi Zmin=12000
(X1 x2 s1 s2 s3)
0 s3 0 0 -0,66 0,66 1 1 0 66,66 = (50 166,66 0 0 0,66)
400 X1 1 0 0 -1 0 0 1 50 La condition d’arrêt est
vérifiée mais on remarque
600 X2 0 1 -0,66 0,66 0 0 0 1 166,66 que la VHB s2 a un coût
réduit nul.
zj 400 600 -400 0 0 M M 120000 On peut l’introduire à la
Cj-zj 0 0 400 0 0 0 0 base et trouver une autre
solution optimale sans
le Zmin
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

❑ Itération 2:

cj 400 600 0 0 0 M M M
ci VB X1 X2 s1 s2 s3 a1 a2 a3 bi ratio

0 s3 0 0 -0,66 0,66 1 1 0 66,66 100

400 X1 1 0 0 -1 0 0 1 50 -
600 X2 0 1 -0,66 0,66 0 0 0 1 166,66 250

zj 400 600 -400 0 0 M M 120000

Cj-zj 0 0 400 0 0 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

❑ Itération 4:

cj 400 600 0 0 0
ci VB X1 X2 s1 s2 s3 bi
Nous avons donc trouvé une autre
0 s2 0 0 -1 1 1,5 100 solution optimale sans changer
le Zmin=12000
400 X1 1 0 -1 0 1,5 150
600 X2 0 1 0 0 -1 100 (X1 x2 s1 s2 s3)= ( 150 100 0 100 0)

zj 400 600 -400 0 0 120000

Cj-zj 0 0 400 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

Les PLs particuliers:

❑ Solution impossible:

Min Z=-x 1 +x 2 +M a1
Min Z=-x 1 +x 2 -2x1+x2+s1=2
2x1-x2≥-2 (P)
(P) Forme standard -x1+2x2-s2 + a1=8
x1-2x2≤-8 x1+x2 +s3 =5
x1+x2≤5
x1 ; x2 ≥0 x1 ; x2 ;s1;s2; s3; a1≥0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Application du Simplexe: Min Z=-x 1 +x 2 +M a1

-2x1+x2+s1=2
(P)
cj -1 1 0 0 0 M -x1+2x2-s2 + a1=8
x1+x2 +s3 =5
ci VB X1 X2 s1 s2 s3 a1 bi Ratio x1 ; x2 ;s1;s2; s3; a1≥0
0 s1 -2 1 1 0 0 0 2 2
M a1 -1 2 0 -1 0 1 8 4
Variable entrante: X2
0 s3 1 1 0 0 1 0 5 5
Variable sortante: s1
zj -M 2M 0 -M 0 M 8M Pivot=1
Cj-zj -1+M 1-2M 0 M 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Itération 1:

cj -1 1 0 0 0 M
ci VB X1 X2 s1 s2 s3 a1 bi Ratio

1 x2 -2 1 1 0 0 0 2 -
M a1 3 0 -2 -1 0 1 4 4/3
0 s3 3 0 -1 0 1 0 3 1
zj 3M-2 1 1-2M -M 0 M 2+4M
Variable entrante: X1
Cj-zj 1-3M 0 2M-1 M 0 0
Variable sortante: s3
Pivot=3
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Itération 2:

cj -1 1 0 0 0 M
ci VB X1 X2 s1 s2 s3 a1 bi Ratio

1 x2 0 1 1/3 0 2/3 0 4 12
M a1 0 0 0 -1 -1 1 1 -
-1 x1 1 0 -1/3 0 1/3 0 1 -
zj -1 1 2/3 -M 1/3-M M 3+M
Variable entrante: S1
Cj-zj 0 0 -2/3 M M-1/3 0
Variable sortante: X2
Pivot=1/3
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Itération 3:

cj -1 1 0 0 0 M
ci VB X1 X2 s1 s2 s3 a1 bi

0 S1 0 3 1 0 2 0 12 Le critère d’arrêt est atteint mais

M a1 0 0 0 -1 -1 1 1 avec une solution avec un
coefficient non nul de la variable
-1 x1 1 1 0 0 1 0 8 artificielle→ la solution est
zj -1 -1 0 -M -M-1 M M-8 l’ensemble vide
Cj-zj 0 2 0 M M+1 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

Les PLs particuliers:

❑ Problème non borné:

Max Z= 3x1+5x2 -M a1 -M a2
x1 −x2 -s1+a1=2
Max Z= 3x1+5x2 (P)
-x1 +3x2 -s2+a2=3
(P) x1 −x2 ≥2 Forme standard
x1 ; x2 s1;s2; a1; a2 ≥0
-x1 +3x2 ≥3
x1 ; x2 ≥0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

Max Z= 3x1+5x2 -M a1 -M a2
x1 −x2 -s1+a1=2
❑ Problème non borné : Application du simplexe (P)
-x1 +3x2 -s2+a2=3
x1 ; x2 s1;s2; a1; a2 ≥0
cj 3 5 0 0 -M -M
ci VB X1 X2 s1 s2 a1 a2 bi Ratio

-M a1 1 -1 -1 0 1 0 2 -

-M a2 -1 3 0 -1 0 1 3 1
zj 0 -2M M M -M -M -5M
Cj-zj 3 5+2M -M -M 0 0 Variable entrante: x2
Variable sortante: a2
Pivot=3
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

Max Z= 3x1+5x2 -M a1 -M a2
x1 −x2 -s1+a1=2
❑ Problème non borné : Application du simplexe (P)
-x1 +3x2 -s2+a2=3
x1 ; x2 s1;s2; a1; a2 ≥0
cj 3 5 0 0 -M -M
ci VB X1 X2 s1 s2 a1 a2 bi Ratio

-M a1 1 -1 -1 0 1 0 2 -

-M a2 -1 3 0 -1 0 1 3 1
zj 0 -2M M M -M -M -5M
Cj-zj 3 5+2M -M -M 0 0 Variable entrante: x2
Variable sortante: a2
Pivot=3
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Problème non borné :

❑ itération 1
cj 3 5 0 0 -M
ci VB X1 X2 s1 s2 a1 bi Ratio

-M a1 2/3 0 -1 -1/3 1 3
9/2
5 x2 -1/3 1 0 -1/3 0 1 -
zj -2/3M-5/3 5 M 1/3M-5/3 -M 5-3M
Cj-zj 14/3+2/3M 0 -M 5/3-1/3M 0 Variable entrante: x1
Variable sortante: a1
Pivot=2/3

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Problème non borné :

❑ itération 2
cj 3 5 0 0
Ratio La dernière ligne des coûts réduits
ci VB X1 X2 s1 s2 bi contient encore des éléments
positifs.
3 x1 1 0 -3/2 -1/2 9/2 -
C’est la variable s1 qui doit entrer à
- la base.
5 X2 0 1 -1/2 -1/2 5/2
Néanmoins, tous les ratios seront
négatifs car la colonne de la
zj 3 5 -7 -4 26 variable entrante ne contient que
Cj-zj 0 0 7 4 des éléments négatifs→ le problème
est non borné et zmax=+∞

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

Les PLs particuliers:

❑ Phénomène de dégénérescence: Exemples

VB x₁ x₂ x₃ s1 s2 s3 bi Ratio
X2 4 7 0 0 1 4 4
4/7
X1 2 8 0 1 0 3 0
0
x₃ -2 9 1 0 0 2 0
0
Cj-zj -5 2 0 0 0 1 Variable entrante: x2
Variable sortante: x₁ etx₃
On choisit celle avec le plus petit
indice x₁

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Phénomène de dégénérescence: Exemples

VB x₁ x₂ x₃ s1 s2 s3 bi Ratio
s2 4 1 0 0 1 4 5 5
s1 2 3 0 1 0 3 15 5
x₃ -2 2 1 0 0 2 14 7
Cj-zj -5 6 0 0 0 1
Variable entrante: x2
Variable sortante: s₁ ets₃
On choisit celle avec le plus petit
indice s₁
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 5- la méthode Simplexe : le cas général

5.2.2. Les cas particuliers

❑ Phénomène de dégénérescence: Exemples

VB x₁ x₂ x₃ s1 s2 s3 bi
s2 4 1 0 0 1 4 7 On se retrouve avec 2 variables qui
ont le même coût réduit le plus
s1 2 3 0 1 0 3 5 grand: x2 et x3 → on choisit x2
x₃ -2 2 1 0 0 2 2
Cj-zj -3 6 6 0 0 1

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.3. Le cas des variables sans restriction de signe (VRS)

❑ Une variable négative, appelée variable libre ou Variable sans Restriction

de Signe peut être remplacée par la différence de deux variables positives.

❑ Pour chaque variable sans restriction de signe, on effectue un changement

de variable: on remplace xi par (xi’ – x) dans la fonction objective et les
contraintes (avec xi ’ et x ≥ 0)

❑ On résout ce nouveau programme linéaire par la méthode du

simplexe, et pour retrouver les variables initiales, on effectue de nouveau un
changement de variable dans le résultat final.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.3. Le cas des variables sans restriction de signe (VRS)

❑ Exemple:

Soit le PL suivant:
Pour x1 et x2 , on effectue le
changement suivant:
Min Z= -x1+2x2 x1 = x’1 –x
5x1 +3x2 ≥ -30
(P)
x1 - x2 ≤ 2 X2=x’2 -x
x1 ; x2 VRS

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.3. Le cas des variables sans restriction de signe (VRS)

❑ Exemple:

Le PL devient:

Min Z= -x’1+2x’2 –x + 0 s1 + 0 s2
Min Z= -x’1+2x’2 –x
(P) -5x’1-3x’2 + 8 x +s1 = 30
(P) -5x’1-3x’2 + 8 x ≤ 30 Forme standard
x’1-x’2 +s2 = 2
x’1-x’2 ≤ 2 x’1 ; x’2 ; x ; s1 ; s2 ≥ 0
x’1 ; x’2 ; x ≥ 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.3. Le cas des variables sans restriction de signe (VRS)

❑ Exemple: application du simplexe:

Min Z= -x’1+2x’2 –x + 0 s1 + 0 s2

(P) -5x’1-3x’2 + 8 x +s1 = 30

cj -1 2 -1 0 0
ci VB X’1 X’2 x s1 s2 bi x’1-x’2 +s2 = 2
0 s1 -5 -3 8 1 0 30 x’1 ; x’2 ; x ; s1 ; s2 ≥ 0
0 s2 1 -1 0 0 1 2
zj 0 0 0 0 0 0
cj-zj -1 2 -1 0 0 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.3. Le cas des variables sans restriction de signe (VRS)

❑ Exemple: application du simplexe:

Min Z= -x’1+2x’2 –x + 0 s1 + 0 s2

(P) -5x’1-3x’2 + 8 x +s1 = 30

x’1-x’2 +s2 = 2
x’1 ; x’2 ; x ; s1 ; s2 ≥ 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.3. Le cas des variables sans restriction de signe (VRS)

❑ Exemple: application du simplexe:

2 variables ont le même coefficient

le plus négatif, on choisira dans ce
cas X’1

Variable entrante: X’1

Variable sortante: s2
Pivot :1

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.3. Le cas des variables sans restriction de signe (VRS)

❑ Exemple:

La solution n’est pas encore optimale,

pour la prochaine itération x est la
variable sortante et s1 est la variable
sortante avec un pivot 8

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 5- la méthode Simplexe : le cas général

5.2.3. Le cas des variables sans restriction de signe (VRS)

Min Z= -x1+2x2
❑ Exemple: 5x1 +3x2 ≥ -30
(P)
x1 - x2 ≤ 2
x1 ; x2 VRS

La dernière ligne ne contient que des

valeurs positives ou nuls: c’est la solution
optimale avec: Zmin= -7

(X’1 X’2 x s1 s2)= ( 2 0 5 0 0)

il suffit de remplacer pour trouver les valeurs

des variables initiales, on aura donc:
x1 = 2 - 5 = - 3
x2 = 0 - 5 = - 5 → z = -(-3)+2 (-5) =-7
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès