Université Libre de Tunis

Chapitre 3

La méthode de Simplexe

Mejri Meriem

Année Universitaire : 2019-2020

Méthode Simplexe

3.1. Introduction

• La méthode géométrique est limitée dans le cas de 2 variables

de décision.

• Pour un problème de taille quelconque, c’est

la méthode

Simplexe qui est utilisée.

o Développée Par George Dantzig en 1947

o Très efficace et performante pour les problèmes de

grande taille

Méthode Simplexe

3.2. Algorithme de Simplexe

• Cet algorithme permet de déterminer la solution optimale, si

elle existe, d’un problème de programmation linéaire à n

variables.

• Le principe de la méthode est de transformer les contraintes

qui sont des inéquations en équations en ajoutant des variables

positives que l’on appelle variables d’écart. Puis on transforme

ce système d’équations linéaires jusqu’à trouver la solution

optimale.

Méthode Simplexe

3.3. Les étapes de la méthode Simplexe

• Première étape :

La formulation mathématique du problème

• Deuxième étape :

Mise sous forme standard du problème

• Troisième étape :

Application de l’algorithme du simplexe

Méthode Simplexe

3.4. les différentes formes

A) Formes canoniques

• Lorsque l’ensemble de contraintes se présentent sous forme

d’inégalité ≤ ou ≥, on parle de forme canonique.

• On distingue deux formes canonique :

inférieure ou égale

‐ La forme canonique de type 1 où les contraintes sont de

est une

type

maximisation.

‐ La forme canonique de type 2 où les contraintes sont de

est une

type

minimisation.

supérieure ou égale

l’objectif

(≤)

(≥)

Méthode Simplexe

B) Forme mixte

• On peut dans ce cas avoir un mélange d’inégalité supérieure

ou égale (≥) et inférieure ou égale (≤).

fonction objective

• La

minimisation

C) Forme standard

est une maximisation ou une

• Toute les contraintes sont des égalités

• L’objectif consiste à maximiser ou à minimiser

Méthode Simplexe

3.5. Introduction des variables d’écarts et des variables

artificielles

• Pour changer les formes canoniques en des formes standards,

les variables

(VE) et

on utilise les variables d’écarts

artificielles (VA)

• Les variables initiales du programme s’appelle des variables

réelles (VR)

1er cas :



Méthode Simplexe

1212max 1014 151020xxxxVRVE12121max 1014 151020 xxxxSMéthode Simplexe

2éme cas :



M : très grand chiffre

1212max 1020 4xxxxVRVE VA1211211max 1020 4 xxMAxxSAMéthode Simplexe

3éme cas :



M : très grand chiffre

1212min 310 5610xxxxVRVE VA1211211min 310 56S10 xxMAxxAMéthode Simplexe

4éme cas :

Le 1er cas est aussi valable s’il s’agit d’une minimisation

Méthode Simplexe

3.6. La méthode Simplexe

• Le principe est basé sur la solution graphique.

• Dantzig a un sommet de polyèdre de solution réalisable. La

méthode consiste à se déplacé d’un sommet à un autre en

s’assurant que la fonction objective s’améliore.

• On regroupe généralement

les données sous forme d’un

tableau appelé tableau de simplexe.

• Pour appliquer l’algorithme du simplexe,

il faut s’assurer

l’existence d’une solution de base, solution où toutes les

variables sont nulles.

Méthode Simplexe

A) 1er cas : inégalité : inférieure ou égale

a. Constitution du 1er tableau



112211111211221112max ,,,0nnnnnnmmnnmnCxCxCxaxaxbaxaxbaxaxbxxx1122111111211222111212max ,,,0 ,,,0nnnnnnmmnnmmnmCxCxCxaxaxSbaxaxSbaxaxSbxxxSSSMéthode Simplexe

coefficient correspond aux variables

coefficients

variables

des variables

de base

A = (aij)i,j

matrice des coefficients

des contraintes du programme

standard

deuxième

terme des

contraintes

Ci -Zi

• Chaque colonne correspond à l’une des variables, la deuxième

colonne comporte les noms des variables de base

• Les variables qui interviennent dans l’expression de f sont les

variables hors base

= 0, 0iikbaavecakExemple 1:



120

130

Méthode Simplexe

12121212 54 43120 25130 0, 0Maxxxscxxxxxx1212112212 54 43S120 25S130 0, 0Maxxxscxxxxxx1x2xjjCZjCjZ1S1S2S2Sb. Les étapes de simplexe pour la maximisation

 Etape1: Construire le tableau initiale

Méthode Simplexe

 Etape2: Repérer l’élément positif le plus grand de la dernière ligne du

est la variable entrante. Si tous les éléments de

tableau, soit k sa colonne,

la dernière ligne sont négatifs, alors le tableau est dans sa forme finale et la

solution est optimale.

 Etape3: Pour chaque ligne i, on divise l’élément bi par

si k>0

 Etape4: Choisir le quotient positif le plus petit, s’il correspond à la ligne l.

On appelle Pivot le nombre

La variable sortante est celle qui correspond à la ligne l du tableau.

 Etape5: Redessiner le tableau en respectant les formules suivantes:

 Etape6: Recommencer les étapes 25 jusqu’à la disparition des éléments

positifs de la dernière ligne du tableau.

Le tableau donne alors la solution optimale.

kx 0, 0iikbavecakalka'''; lliiikllkLLLLaLaikaMéthode Simplexe

Exemple1

Variable

entrante

Nombre

Pivot

Variable

sortante

Variable entrante

Nombre

Pivot

Variable

sortante

3/4

7/2

1/4

-1/2

-5/4

Quantité

120

130

Quantité

-150

1x2xjjCZjCjZ1x2x1xjjCZjCjZ'''11221, 24LLLLL1S1S2S2S2S2S1SMéthode Simplexe

5/14

-1/7

-3/14

2/7

-17/14

-1/14

-155

La solution optimale est obtenue car tous les éléments de la

dernière ligne sont négatifs ou nuls.

1x2x1x2xjjCZjCjZ'""'"221123, 7/24LLLLL121215, 20, 0, 0 155xxSSZ2S1SMéthode Simplexe

c. Problème de minimisation

Remarque :

Min Z = Max (-Z)

On peut transformer un problème de minimisation en un

problème de maximisation et le traiter de la même façon que

l’exemple précédent.

Exemple :



Méthode Simplexe

12121212 -32 511 235 0, 0Minxxscxxxxxx121211221212 -32 511 235 0, 0, 0, 0MinxxscxxSxxSxxSS121211221212 32 511 235 0, 0, 0, 0MaxxxscxxSxxSxxSSVariable

entrante

Méthode Simplexe

Nombre

Pivot

Variable

sortante

7/2

3/2

-5/2

Quantité

5/2

Quantité

-1/2

17/2

1/2

5/2

-3/2

-15/2

La solution optimale est obtenue car tous les éléments de la dernière ligne sont

négatifs ou nuls.

1x2xjjCZjCjZ1x2xjjCZjCjZ'''22112, 2LLLLL1S1S2S2S2S1S1S1x1212517, 0, , 02215 2xxSSZMéthode Simplexe

B) 2ème cas : inégalité : supérieur ou égal



1212121212 s.c. 212 5874 624 , 0Minxxxxxxxxxx1212312111222123312123123 s.c. 212 5874 624 , , S, S, S, A, A, A0MinxxMAMAMAxxSAxxSAxxSAxx1212312111222123312123123 - s.c. 212 5874 624 , , S, S, S, A, A, A0MaxxxMAMAMAxxSAxxSAxxSAxxNombre

pivot

Variable

entrante

-1

8M-1

15M-1

-M

Méthode Simplexe

-1

-M

110M

Quantité

37/4

Variable

sortante

Nombre

pivot

-M

-1

11/6

11/3

1/6

Variable

sortante

Variable

entrante

-1

-M

-1

1/6

4/3

-1/6

-M

-1/6

-4/3

1/6

50M+4

Quantité

48/11

126/11

1x2x1S2S1A1A2A2A3S3A3AjCjZjjCZ1x2x1S2S1A1A2A2A3S3A2xjCjZjjCZ'''''33113223, , 86LLLLLLLL115M-2631M-26-151M+66Nombre

pivot

Variable

entrante

-1

-M

Méthode Simplexe

-1

-M

-1

Variable

sortante

Nombre

pivot

-1

Variable

sortante

Quantité

-1/11

48/11

-1

2/11

36/11

-8

1/11

6/11

-2

-2/11

-1/11

-6/11

1/11

-1

-M

Variable

entrante

-1

-M

Quantité

-3/11

4/11

-1/2

1/2

1/22

-5/22

-1

3/11

-4/11

126/11

63/2

1/2

-1/2

-1/22

5/22

23/11

-46/5

-5/22

3/22

-M

149/11

1x2x1S2S1x1A2A2A3S3A2xjCjZjjCZ'""'""'"11221331111, , 11/636LLLLLLLL52M-111M-111-M+111x2x1S2S1x1A2A1S3S3A2xjCjZjjCZ5-3M+11"'''''''''''''''''''2211233261, , 21111LLLLLLLL5-M-223-M-22Méthode Simplexe

-1

-8/11

1/11

-1

5/11

-2/11

-10/11

-1/11

-M

8/11

-1/11

-2

-5/11

2/11

-1

-M

1x2x1S2S1x1A2A3S3S3A2xjCjZjjCZ''''"''''''''''''''''''''''22112332452, , 1122LLLLLLLL311M111M121231232, 8, 0, 0, 26, A0, A0, A0 10xxSSSZC) 3ème cas : inégalité : mixte



Méthode Simplexe

121212212 56 s.c. -4 53 60 5 , 0Maxxxxxxxxxx1212121121222121212 56 s.c. -4 5360 5 , , S, S, A, A0MaxxxMAMAxxSxxAxSAxxVariable

entrante

-1

5+5M 6+4M

8/5

3/5

M+3

-M

Nombre

pivot

Variable

sortante

Variable

entrante

Nombre

pivot

Variable

sortante

-M

-1

-M

-1

1/5

-M

-M-1

Méthode Simplexe

Quantité

-4

Quantité

1x2x1S2S1S1A2A1A2AjCjZjjCZ''''2211233, , 5LLLLLLL1x2x1S2S1S1A2A1x2AjCjZjjCZVariable

entrante

Nombre

pivot

Variable

sortante

Méthode Simplexe

-M

8/5

3/5

-1

1/5

-8/5

-3/5

-M-1 -M-3

Quantité

-5

5/8

-3/8

5/8

-15/8

-M

1/8

-1

-M-11/8 -M -90

1x2x1S2S1S1A2A1x2xjCjZjjCZ"''''''"''''''"'''112213313, , 8/55LLLLLLLL1x2x1S2S2S1A2A1x2xjCjZjjCZ'''''''''''''3311322383, , 55LLLLLLLL1212126, 10, 0, 5, A0, A0 90xxSSZMéthode Simplexe

3.7. Les problèmes irréguliers

Dans cette section, on présente plusieurs cas d’irrégularité

pouvant se présenter lors de l’utilisation de la méthode du

simplexe dans la résolution d’un programme linéaire.

3.7.1. Quantité négative

Si une des contraintes du programme linéaire se présente

avec un second membre négatif, la méthode de simplexe ne

s’applique plus.

En multipliant toute la contrainte par -1 le second membre

devient positif.

12128 -8xxxxMéthode Simplexe

3.7.2. Variable sans contraintes de signe (non négativité)

Supposons que l’une des variables soit sans contrainte de signe.

Alors, on écrit cette variable sous forme d’une différence de deux

variables non-négatives.

Exemple:

est sans contrainte de signe, on pose

Le programme linéaire devient:

1212121 2 . 3240 30 0MaxZxxscxxxxx2x22222 0 0.xxxouxetx122122122122 2() . 32()40 ()30 0,0,0MaxZxxxscxxxxxxxxxMéthode Simplexe

3.7.3. Les problèmes à solution impossible

On reconnaît graphiquement un problème impossible en remarquant

que l’ensemble des solutions réalisables est vide.

Le programme linéaire suivant n’a pas de solution :

12121212 . 10 20 0,0MinxxscxxxxxxMéthode Simplexe

Avec la méthode de simplexe, on reconnaît que le problème est

impossible si une ou plusieurs variables artificielles sont présentes dans

la base dans le tableau de simplexe optimal, ce qui signifie que la

solution donnée par ce tableau n’est pas réellement réalisable.

Le tableau optimal, après deux itérations, nous donne la variable

artificielle A1 dans la base avec la valeur 10. Donc le problème est

impossible.

-M

-1

-3-M -M

-M

1x2x1S2S1A1AjCjZjjCZ2xMéthode Simplexe

Remarque :

Un programme de maximisation ou de minimisation avec seulement

des contraintes de type «  » ne peut pas être impossible (sous

l’hypothèse que le second membre b est positif). Ceci est dû au fait que

lors de la résolution de ce genre de programme par la méthode de

simplexe on n'utilise pas des variables artificielles. Donc il est

impossible de les retrouver dans la solution optimale.

Méthode Simplexe

3.7.4. Les problèmes à solution infinie

Graphiquement, ce problème est caractérisé par le fait qu’on peut

déplacer la droite de la fonction objectif indéfiniment de manière à

accroître la valeur, en gardant toujours une intersection non vide avec

l’ensemble des solutions réalisables.

Considérons le PL suivant :

12121212 . 5 10 329 0,0MaxxxscxxxxxxMéthode Simplexe

Avec la méthode de simplexe, on reconnaît ce problème lorsque la

variable entrante n’admet aucune limite sur sa valeur d’entrée, c’est à

dire que tous les ratios

sont négatifs ou nuls.

Sur notre exemple, il suffit d’une itération pour trouver le tableau

suivant sans lequel la variable x2 entre et n’admet aucune limite sur la

valeur avec laquelle elle entre dans la base.

-1/5

-7/5

6/5

-1/5

3/5

1/5

Variable entrante

négatif

1x2x1S2S2SjCjZjjCZ1x()iikbaMéthode Simplexe

3.7.5. Les problèmes à solutions multiples

Graphiquement, ce problème est caractérisé par le fait que la pente

de la droite représentant la fonction objectif (z = 0) est égale à la pente

de l’une des contraintes restrictives.

Soit l’exemple suivant :

Graphiquement (figure), on voit que le problème admet une infinité de

solutions (tous les points sur le segment BC). Il suffit donc de donner

les points B et C pour connaître l’ensemble des solutions.

12121212 4515 ( -3) . 22240 ( -1) 3 140 ( -3) 0,0MaxxxdepentescxxdepentexxdepentexxAvec la méthode de simplexe, on reconnaît l’existence de solutions multiples

en remarquant que, dans le tableau optimal, une des variables hors base admet un

(Cj - Zj) nul. Ceci indique que cette variable peut entrer dans la base et donner une

nouvelle solution sans que la valeur de la fonction objectif ne change.

Méthode Simplexe

Pour l’exemple précédent, le

tableau optimal est :

La solution optimale est :

4/3

1/3

-2/3

440/3

1/3

-15

140/3

2100

110

140

La variable x2 est sélectionnée pour

entrer dans la base et la variable S1 est

sélectionnée pour sortir de la base. D’où le tableau :

Ce tableau donne une seconde

solution optimale:

3/4

-1/2

110

-1/4

1/2

-15

2100

1x2x1S2S1xjCjZjjCZ1S1x2x1S2S1xjCjZjjCZ2x1212140440, 0, , 0, 210033xxSSZ121210, 110, 0, 0, 2100xxSSZ

Chapitre 3: La Méthode de Simplexe

Chapitre 3: La Méthode de Simplexe