UNIVERSITÉ MOULAY ISMAIL

FACULTÉ POLYDISCIPLINAIRE ERRACHIDIA

RECHECHE OPÉRATIONNELLE

CHAPITRE 4: Méthode de simplexe 2: (méthode des

tableaux)

MANAL YOUB

- FPE - S6 - MANAL YOUB 1

 Introduction
 La méthode algébrique, de résolution des programmes
linéaires, devient compliquée et nécessite une très grande
attention dès que le nombre des variables et de contraintes
est important.

 Il est possible d’adopter une représentation sous forme de

tableaux qui facilite considérablement les calculs. On
effectue généralement les calculs sur le tableau des
coefficients qui porte le nom de tableau Simplexe.

- FPE - S6 - MANAL YOUB 2

 Méthode de simplexe
 Nous décrirons le déroulement de la méthode du simplexe en
l’appliquant au modèle de fabrication des châssis (FC) introduit au
chapitre 2. Reprenons la formulation du programme (FC) dans laquelle
les variables d’écart étaient incluses.

On exprime le problème sous forme matricielle, où :

- FPE - S6 - MANAL YOUB 3

 Méthode de simplexe
1. Tableau initial
On construit un tableau initial du simplexe, qui se compose du
vecteur b, de la matrice A, et d’une ligne [0;c] situés sous les
précédents où 0 correspond à la valeur de z à l’origine
(lorsque x1 = x2 = 0) :

- FPE - S6 - MANAL YOUB 4

 Méthode de simplexe
2. Pivot et changement de base
On appelle changement de base le processus qui consiste à choisir la
variable entrante et la variable sortante.
 Choix de la variable entrante
Dans la dernière ligne, le coefficient dont la valeur est la plus élevée
détermine la variable à entrer dans la base. Donc la variable entrante est
x2. (la colonne de la variable entrante est appelée « colonne pivot »).

- FPE - S6 - MANAL YOUB 5

 Méthode de simplexe
 Choix de la variable sortante
On choisit la variable sortante comme étant la variable de base qui s’annule la
première. cela revient à calculer le minimum du rapport du coefficient du
membre de droite de chaque contrainte sur le coefficient correspondant de la
colonne pivot lorsque ce dernier est strictement positif :

Remarque: Dans le cas où le coefficient dans la colonne entrante est négatif ou

nul, la ligne n’entre pas en compte dans le calcul du minimum.

La variable sortante est alors la variable de base dont la valeur se lit dans la
ligne où le minimum se produit : ici, il s’agit de la deuxième ligne et donc de la
variable x4. On encadre alors la ligne où le minimum se produit. Cette ligne
reçoit le nom de ligne pivot :

- FPE - S6 - MANAL YOUB 6

 Méthode de simplexe

On appelle nombre pivot ou pivot le coefficient situé à l’intersection de la

colonne pivot et de la ligne pivot.
- FPE - S6 - MANAL YOUB 7
 Méthode de simplexe
3. Pivotage et tableaux simplexe
Le pivotage est le processus qui consiste à amener la colonne de la
variable sortante en lieu et place de la variable entrante.
Le pivot nous permettra de transformer le tableau actuel en un
deuxième tableau correspondant à la nouvelle base. Ceci peut être
fait par trois types d’opérations :

1. Transformation de la ligne pivot : pour obtenir la ligne du

pivot transformée, il suffit de diviser tous ses éléments par le
pivot.
2. Transformation de la colonne pivot : après avoir ramené par
division le pivot à 1, toutes les éléments situé au-dessus et au-
dessous du pivot deviennent zéro.
- FPE - S6 - MANAL YOUB 8
Méthode de simplexe

- FPE - S6 - MANAL YOUB 9

 Méthode de simplexe

3. Transformation des autres cases du tableau : pour

obtenir la transformée des autres nombres, il suffit
d’appliquer la règle dite du rectangle :

 a’ est la valeur modifiée du coefficient a qui est considéré

 b est l’élément situé sur la même ligne que a, mais dans la
colonne du pivot
 c est l’élément situé dans la même colonne que a, mais sur
la ligne du pivot

- FPE - S6 - MANAL YOUB 10

 Méthode de simplexe
 Dans le tableau à modifier, le pivot et les coefficient a, b et c forment
les coins d’un rectangle. D’où le nom de la méthode.

Remarquons que la règle du rectangle implique :

 si une ligne contient un 0 à l’intersection avec la colonne du pivot,
cette ligne ne sera pas modifiée.
 si une colonne contient un 0 à l’intersection avec la ligne du pivot,
cette colonne ne sera pas modifiée.
En appliquant ces opérations au tableau initial, on obtient le
deuxième tableau :
- FPE - S6 - MANAL YOUB 11
 Méthode de simplexe

On peut lire directement sur ce tableau la deuxième solution de base

réalisable. En posant x1 = x4 = 0, nous conservons une matrice identité qui
donne x2 = 6, x3 = 4 et x5 = 6. Le premier coefficient de la dernière ligne
(ici, 3000) donne l’opposé de la valeur z dans la deuxième solution de
base réalisable:

- FPE - S6 - MANAL YOUB 12

 Méthode de simplexe
4. Deuxième itération
Le maximum de la fonction z est atteint lorsqu’il n’y a plus de
coefficients positifs dans la dernière ligne. On poursuit les
changements de base et les pivotages, conformément aux
règles exposées ci-dessus, jusqu’à ce qu’on y parvienne.
– Comme il ne reste plus comme coefficient positif (dans la
dernière ligne) que 300,on introduit x1 dans la base. La
colonne de x1 devient la colonne pivot.
– La division de la colonne des seconds membres par la
colonne pivot révèle que le plus faible rapport correspond à
la ligne x5. C’est x5 qui quitte la base. Alors le nombre 3
devient le nouveau pivot
- FPE - S6 - MANAL YOUB 13
Méthode de simplexe

- FPE - S6 - MANAL YOUB 14

 Méthode de simplexe
 Le dernier pas de la deuxième itération consiste à
déterminer la nouvelle solution de base au moyen du
pivotage :
1. Transformation de la ligne et la colonne pivot : Divisons
la ligne pivot par 3, puis annuler tous les éléments de la
colonne pivot sauf le pivot qui est remplacé par 1.

- FPE - S6 - MANAL YOUB 15

 Méthode de simplexe

2. Transformation des autres cases du tableau : Nous

utilisons la règle du rectangle pour transformer le reste des
coefficients. Le résultats est le suivant :

- FPE - S6 - MANAL YOUB 16

 Méthode de simplexe
On peut lire directement sur ce tableau la troisième solution
de base réalisable et la valeur de la fonction objectif z dans
cette solution :

Comme il n’y a plus de coefficients positifs sur la dernière

ligne, la solution courante est optimale. Ainsi :

- FPE - S6 - MANAL YOUB 17

 Méthode de simplexe
Exemple : Utilisation de la méthode du simplexe dans un
problème de minimisation

Zone bleu = contraintes

- FPE - S6 - MANAL YOUB 18
Zone verte = fonction objectif z
Méthode de simplexe

- FPE - S6 - MANAL YOUB 19

Méthode de simplexe

- FPE - S6 - MANAL YOUB 20

 Méthode de simplexe

•Ligne du pivot = ligne de la variable qui sort ici x5 (ligne rose) On la

divise par le pivot entouré en rouge
•Transformation des autres cases du tableau : pour obtenir la transformée
des autres nombres, il suffit d’appliquer la règle dite du rectangle :
a’= a- (b*c) (le pivot=1)
a’ est la valeur modifiée du coefficient a qui est considéré
b est l’élément situé sur la même ligne que a, mais dans la colonne du
pivot
c est l’élément situé dans la même colonne que a, mais sur la ligne du
pivot - FPE - S6 - MANAL YOUB 21
Méthode de simplexe

- FPE - S6 - MANAL YOUB 22

Méthode de simplexe

- FPE - S6 - MANAL YOUB 23

 Méthode de simplexe

•Ligne du pivot = ligne de la variable qui sort ici x3 (ligne rose) On la

divise par le pivot entouré en rouge
•Transformation des autres cases du tableau : pour obtenir la transformée
des autres nombres, il suffit d’appliquer la règle dite du rectangle :
a’= a- (b*c)/ 2 (le pivot=2)
a’ est la valeur modifiée du coefficient a qui est considéré
b est l’élément situé sur la même ligne que a, mais dans la colonne du
pivot
c est l’élément situé dans la même colonne que a, mais sur la ligne du
pivot - FPE - S6 - MANAL YOUB 24
 Méthode de simplexe

Tous les coûts réduits >= (ligne verte) STOP

La solution se lit dans le second membre pour les var. de base
Les var. hors-base sont nulles
La solution est x1=1, x4=1, x2=2, x3=x5=0

- FPE - S6 - MANAL YOUB 25