1
La méthode de simplexe
Les étapes de la modélisation
2
1. choix des variables du modèle
Variable: toute quantité utile à la résolution du
problème dont le modèle doit déterminer la valeur.
Les étapes de la modélisation
3
2. Formulation de l’objectif
Fonction objectif: le critère de choix entre les
diverses solutions possibles
Les étapes de la modélisation
4
3. formulation des contraintes
Contraintes: les relations limitant le choix des
valeurs possibles des variables
Modélisation
Exemple 1
Une entreprise fabrique deux types de ceinture A et B. Le
temps de fabrication d’une ceinture de type A est le double
de celui d’une ceinture de type B et si on ne produisait que
des ceintures B on ne pourrait en faire que 1000 au
maximum à cause de la disponibilité en équipement.
L’approvisionnement en cuir ne permet de fabriquer que
800 ceintures au maximum tout type confondu. De plus
l’entreprise dispose de 400 boucles de ceintures pour le
type A et de 700 pour le type B. La vente d’une ceinture A
rapporte 20 um et celle du type B rapporte 15 um. Répartir
la fabrication entre les types A et B de manière à maximiser
le profit de l’entreprise.
5
Modélisation
1. choix des variables du modèle
Définition des variables de décision
Les activités que l’entreprise doit déterminer sont
les quantités à produire des ceintures de types A et
de types B:
x1 : quantité de ceinture de type A fabriquée
x2 : quantité de ceinture de type B fabriquée
On vérifie bien que les variables de décision x1 et x2
sont positives : .
6
Modélisation
2. Formulation de la fonction objectif
La fonction objectif vise à maximiser le profit de
l’entreprise
résultant de la fabrication des ceinture A et B
Les coefficients 20 et 15 respectivement des variables de
décision x1 et x2 sont proportionnels aux profit de A et B.
La fonction objectif est donc :
z 20x1 15x2
7
Modélisation
3. Formulation des contraintes
- La disponibilité en équipement limite la capacité de fabrication en
équivalent ceinture B à au plus 1000 ceintures :
2 x1 x2 1000
- L’approvisionnement maximale en cuir n’autorise pas la fabrication
d’au plus 800 ceintures :
x1 x2 800
8
Modélisation
3. Formulation des contraintes
- La disponibilité maximale en boucles pour ceintures de type A est de :
x1 400
- La disponibilité maximale en boucles pour ceintures de type B est de :
x2 700
9
Modélisation
Programme linéaire sous forme canonique
Max 20 x 15 x
1 2
s.c. 2 x x 1000
1 2
x x 800
1 2
x 0 x 400
1 2
0 x x 700
1 2
x 0, x 0
1 2
10
Initialisation
11
1. Principe
Mettre le programme initial sous forme
standard.
Sélectionner les variables principales
comme variables hors base
Vérifier que la solution obtenue est
admissible
Initialisation
12
2. Principe de la mise sous forme standard
Réécrire les inégalités sous forme d’égalités par ajout:
de variables supplémentaires ou variables
d’écart
qui représente la quantité de ressources
non utilisées
Initialisation
13
3. Forme standard
Max 20 x 15x
1 2
s.c. 2 x x e 1000
1 2 1
x x e 800
1 2 2
x 0 x e 400
1 2 3
0 x x e 700
1 2 4
x 0, x 0, e 0, e 0, e 0 e 0
1 2 1 2 3 4
Initialisation
14
4. Recherche d’une solution de base admissible
• Annulation des variables principales dans le Programme
standard:
x1 = 0
x2 = 0
• Les variables annulées sont appelées variable hors base
• Les variables d’écart prennent la valeur des seconds
membres
des contraintes: Elles sont appelées variables de base
e1= 1000; e2= 800; e3 = 400; e4 = 700
Initialisation
15
4. Recherche d’une solution de base
admissible
La solution initiale obtenue est:
x1 = 0;
x2 = 0;
e1= 1000;
e2= 800;
e3 = 400;
e4 = 700;
Z=0
Toutes les valeurs des variables étant positive ou nulle, la
solution est donc admissible
Notion de tableau Simplexe
16
1. Principe de la méthode
Se déplacer de sommet en sommet adjacent de
l’espace solution de façon à améliorer la fonction
objectif.
Notion de tableau Simplexe
2. Eléments du tableau de Simplexe
• Un tableau Simplexe est constitué des
coefficients des équations algébriques sans
le nom des variables. On aura donc :
1. les coefficients de la fonction objectif
2. les coefficients des variables dans le
membre de gauche des contraintes
3. les coefficients du membre de droite
17
Notion de tableau Simplexe
3. Préparation de la mise en
tableau
Z- 20 x 15 x 0
1 2
2 x x e 1000
1 2 1
x x e 800
1 2 2
x 0 x e 400
1 2 3
0 x x e 700
1 2 4
x 0, x 0, e 0, e 0, e 0, e 0
1 2 1 2 3 4
18
Notion de tableau Simplexe
4. Tableau initiale du simplexe
VB bi x1 x2 e1 e2 e3 e4
Ci z 0 -20 -15 0 0 0 0
0 e1 1000 2 1 1 0 0 0
0 e2 800 1 1 0 1 0 0
0 e3 400 1 0 0 0 1 0
0 e4 700 0 1 0 0 0 1
19
Notion de tableau Simplexe
20
5. Choix de la variable entrante
• Choisir comme variable entrante la variable hors
base dont le coefficient objectif est le plus élevé
lorsque la fonction objectif z est exprimée en
fonction des seules variable hors base
xentrant est tel que centrant min c j
c j 0
Les étapes de la méthode du simplexe
5. Choix de la variable entrante
VB bi x1 x2 e1 e2 e3 e4
Ci z 0 -20 -15 0 0 0 0
0 e1 1000 2 1 1 0 0 0
0 e2 800 1 1 0 1 0 0
0 e3 400 1 0 0 0 1 0
0 e4 700 0 1 0 0 0 1
21
Les étapes de la méthode du simplexe
22
6. Choix de la variable sortante
• La variable sortante est la première à s’annuler
est telle que
bl bi
xsor tan te min
ai ,entrante a
al ,entrante i ,entrante
Les étapes de la méthode du simplexe
6. Choix de la variable sortante
VB bi x1 x2 e1 e2 e3 e4
Ci z 0 -20 -15 0 0 0 0
0 e1 1000 2 1 1 0 0 0
0 e2 800 1 1 0 1 0 0
0 e3 400 1 0 0 0 1 0
0 e4 700 0 1 0 0 0 1
23
Les étapes de la méthode du simplexe
7. Pivotage
• Déterminer la nouvelle solution de base.
La variable entrante prend la place de la
variable sortante dans la base
a
ij tabsuivant
aij tabprecede nt ai ,entrante tabprecede nt xalj tabsuivant
24
Les étapes de la méthode du simplexe
25
7. Pivotage
VB bi x1 x2 e1 e2 e3 e4
z 8000 0 -15 0 0 20 0
0 e1 200 0 1 1 0 -2 0
0 e2 400 0 1 0 1 -1 0
20 x1 400 1 0 0 0 1 0
0 e4 700 0 1 0 0 0 1
VB bi x1 x2 e1 e2 e3 e4
Ci z 0 -20 -15 0 0 0 0
0 e1 1000 2 1 1 0 0 0
0 e2 800 1 1 0 1 0 0
0 e3 400 1 0 0 0 1 0
0 e4 700 0 1 0 0 0 1
/////////// //////////// //////////// //////////// ////////// /////////// /////////// /////////// ////////////
z 8000 0 -15 0 0 20 0
0 e1 200 0 1 1 0 -2 0
0 e2 400 0 1 0 1 -1 0
20 x1 400 1 0 0 0 1 0
0 e4 700 0 1 0 0 0 1
/////////// //////////// //////////// //////////// ////////// /////////// /////////// /////////// ////////////
z 11000 0 0 15 0 -10 0
15 x2 200 0 1 1 0 -2 0
0 e2 200 0 0 -1 1 1 0
20 x1 400 1 0 0 0 1 0
0 e4 500 0 0 -1 0 2 1
26
Les étapes de la méthode du simplexe
VB bi x1 x2 e1 e2 e3 e4
Ci z 13000 0 0 5 10 0 0
15 x2 600 0 1 -1 2 0 0
0 e3 200 0 0 -1 1 1 0
20 x1 200 1 0 1 -1 0 0
0 e4 100 0 0 1 -2 0 1
27
,(
,
,
, Les étapes de la méthode du simplexe
8. Critère d’optimalité
• Tous les coefficients sur la ligne z du
quatrième tableau sont positifs ou nuls
• On ne peut plus améliorer la solution
• La solution est donc optimale et est égale
à:
( x1* , x2* , e1* , e2* , e3* , e4* ) (200,600,0,0,200,100)
z * 13000
28
Les étapes de la méthode du simplexe
9. Critère d’optimalité
• Pour un maximum: Lorsque tous les
coefficients sur la ligne z sont positifs ou
nuls
• Pour un minimum: Lorsque tous les
coefficients sur la ligne z sont négatifs ou
nuls
29
Les étapes de la méthode du simplexe
9. Interprétation de la solution
• x1 200 :Correspond à la production de
*
200 unités de ceinture de type A.
• x 2* 600 Correspond à la production de
600 unités de ceinture de type B.
• La contrainte 3 et 4 sont non saturées, car
leur variable d’écart respective est non
nulle: (e3 200) 4 100)
* *
( e
30
Les étapes de la méthode du simplexe
9. Interprétation de la solution
• La contrainte une et deux sont saturée, car
leur variable d’écart respective est nulle:
(e1* 0) , (e2* 0)
31