LES ÉTAPES DE L’ALGORITHME DU SIMPLEXE
Sommaire
1.
Introduction ............................................................................................................................. 1
2. Variables d’écart et d’excédent ............................................................................................... 2
3. Variables de base et variables hors base ................................................................................ 2
4.
Solutions admissibles .............................................................................................................. 3
5. Résolution du programme linéaire (PL) .................................................................................. 3
6.
Le critère d’arrêt ...................................................................................................................... 8
1. Introduction
Un programme linéaire (PL) mis sous la forme particulière où toutes les contraintes
sont des équations et toutes les variables sont non négatives est dit sous forme
standard. Il est noté (PL=).
2. Variables d’écart et d’excédent
Avant que l’algorithme du simplexe puisse être utilisé pour résoudre un programme
linéaire, ce programme linéaire doit être converti en un programme équivalent où
toutes les contraintes technologiques sont des équations et toutes les variables sont
non négatives.
a. Contraintes de type ((cid:3409)) : Pour chaque contrainte (cid:1861) de ce type, on rajoute une
variable d’écart (cid:1857)(cid:3036), tel que (cid:1857)(cid:3036) est une variable positive ou nulle.
Exemple : 3(cid:1876)(cid:2869) (cid:3397) 2(cid:1876)(cid:2870) (cid:3409) 2 se transforme en 3(cid:1876)(cid:2869) (cid:3397) 2(cid:1876)(cid:2870) (cid:3397) (cid:1857)(cid:2869) (cid:3404) 2, (cid:1857)(cid:2869) (cid:3410) 0
b. Contraintes de type ((cid:3410)) : Pour chaque contrainte (cid:1861) de ce type, on retranche
une variable d’excédent (cid:1857)(cid:3036), tel que (cid:1857)(cid:3036) est une variable positive ou nulle.
Exemple : 3(cid:1876)(cid:2869) (cid:3397) 2(cid:1876)(cid:2870) (cid:3410) 2 se transforme en 3(cid:1876)(cid:2869) (cid:3397) 2(cid:1876)(cid:2870)– (cid:1857)(cid:2870) (cid:3404) 2, (cid:1857)(cid:2870) (cid:3410) 0
Un programme linéaire qui contient des contraintes (technologiques) de type (cid:3409) est
noté (PL). Un programme linéaire qui contient des contraintes (technologiques) de type
(cid:4666)(cid:3409), (cid:3410), (cid:3404)) est noté (PG). Un programme linéaire (PL) resp (PG) converti tel que toutes les
contraintes technologiques sont des équations et toutes les variables sont non
négatives est noté (PL=) resp (PG=).
3. Variables de base et variables hors base
Considérons un système d’équations à (cid:1866) variables et (cid:1865) équations où (cid:1866) (cid:3410) (cid:1865). Une
solution de base pour ce système est obtenue de la manière suivante :
a) On pose (cid:1866) (cid:3398) (cid:1865) variables égales à 0. Ces variables sont appelées variables hors
base (V.H.B.).
b) On résout le système pour les (cid:1865) variables restantes. Ces variables sont
appelées les variables de base (V. B.)
c) Le vecteur de variables obtenu est appelé solution de base (il contient les
variables de base et les variables hors base)
Une solution de base est admissible si toutes les variables de la solution de base
sont (cid:3410)0.
Il est vraiment important d’avoir le même nombre de variables que d’équations.
Page 2 sur 8
4. Solutions admissibles
Toute solution de base de (PL=) pour laquelle toutes les variables sont non négatives,
est appelée solution de base admissible. Cette solution de base admissible correspond à
un point extrême.
5. Résolution du programme linéaire (PL)
(PL)
(PL)
Ex : (cid:1839)(cid:1853)(cid:1876) (cid:1852) (cid:3404) 1000 (cid:1876)(cid:2869) (cid:3397) 1200 (cid:1876)(cid:2870)
(cid:1871). (cid:1855). 10 (cid:1876)(cid:2869) (cid:3397) 5(cid:1876)(cid:2870) (cid:3409) 200
2(cid:1876)(cid:2869) (cid:3397) 3(cid:1876)(cid:2870) (cid:3409) 60
(cid:1876)(cid:2869) (cid:3409) 34
(cid:1876)(cid:2870) (cid:3409) 14
(cid:1876)(cid:2869), (cid:1876)(cid:2870) (cid:3410) 0
Ex : (cid:1839)(cid:1853)(cid:1876) (cid:1852) (cid:3404) 1000 (cid:1876)(cid:2869) (cid:3397) 1200 (cid:1876)(cid:2870)
(cid:1871). (cid:1855). 10 (cid:1876)(cid:2869) (cid:3397) 5(cid:1876)(cid:2870) (cid:3397) (cid:1857)(cid:2869) (cid:3404) 200
2(cid:1876)(cid:2869) (cid:3397) 3(cid:1876)(cid:2870) (cid:3397) (cid:1857)(cid:2870) (cid:3404) 60
(cid:1876)(cid:2869) (cid:3397) (cid:1857)(cid:2871) (cid:3404) 34
(cid:1876)(cid:2870) (cid:3397) (cid:1857)(cid:2872) (cid:3404) 14
(cid:1876)(cid:2869), (cid:1876)(cid:2870), (cid:1857)_1, (cid:1857)_2, (cid:1857)_3, (cid:1857)_4 (cid:3410) 0
(cid:4666)(cid:1866) (cid:3398) (cid:1865)(cid:4667) (cid:3404) 0
(cid:1866) (cid:3404) 6 et (cid:1865) (cid:3404) 4
(cid:4666)6 (cid:3398) 4(cid:4667) (cid:3404) 2 variables (cid:3404) 0
Variables hors base
Variables de base:
si (cid:1876)1 (cid:3404) (cid:1876)2 (cid:3404) 0
alors
(cid:1857)(cid:2869) (cid:3404) 200
(cid:1857)(cid:2870) (cid:3404) 60
(cid:1857)(cid:2871) (cid:3404) 34
(cid:1857)(cid:2872) (cid:3404) 14
Page 3 sur 8
Étape A: tableau initial
Coeff. dans Z
Base
Coef. Z Var.base
0
0
0
0
E1
E2
E3
E4
zj
Cj – zj
1000
X1
10
2
1
0
0
1000
1200
X2
5
3
0
1
0
1200
0
E1
1
0
0
0
0
0
0
E2
0
1
0
0
0
0
0
E3
0
0
1
0
0
0
0
E4
0
0
0
1
0
0
bi
200
60
34
14
0
Le tableau initial se construit de la manière suivante :
L’encadré bleu correspond aux coefficients des contraintes du (PL=).
L’encadré vert correspond aux (cid:1878)(cid:3037) : c’est‐à‐dire les coefficients dans (cid:3400) (cid:1853)(cid:3036) .
Exemple pour la colonne de (cid:1850)(cid:2869) nommée ((cid:1853)(cid:2869)) :
0 (cid:3400) 10 (cid:3397) 0 (cid:3400) 2 (cid:3397) 0 (cid:3400) 1 (cid:3397) 0 (cid:3400) 0 (cid:3404) 0
Les encadrés roses correspondent aux coefficients ((cid:1829)(cid:3037)) des variables dans la
fonction objectif ((cid:1852)).
L’encadré gris correspond à la valeur des variables de base.
L’encadré orange correspond à la valeur de (cid:1852), donc la valeur de la fonction
objectif qui se calcule de la façon suivante :
0 (cid:3400) 200 (cid:3397) 0 (cid:3400) 60 (cid:3397) 0 (cid:3400) 34 (cid:3397) 0 (cid:3400) 14 (cid:3404) 0
Étape B : choix de la variable entrante (dans la base)
Maximum des (cid:1829)(cid:3037)– (cid:1878)(cid:3037) pour des problèmes de max.
Minimum des (cid:1829)(cid:3037)– (cid:1878)(cid:3037) pour des problèmes de min.
Dans notre exemple : (cid:1876)(cid:2870) a le plus grand (cid:1829)(cid:3037)– (cid:1878)(cid:3037) donc, il entre dans la base.
Page 4 sur 8
Publicité
Étape C : choix de la variable sortante
Dans un problème de min OU de max, la variable sortante sera le minimum des
(cid:1854)(cid:3036)
(cid:1853)(cid:3036)(cid:3038)
(cid:3628) (cid:1853)(cid:3036)(cid:3038) (cid:3408) 0
Dans notre exemple, nous devons évaluer :
1000
X1
10
2
1
0
0
1000
1200
X2
5
3
0
1
0
1200
0
E1
1
0
0
0
0
0
0
E2
0
1
0
0
0
0
0
E3
0
0
1
0
0
0
0
E4
0
0
0
1
0
0
Var. entrante
Coeff. dans Z
Base
Coef. Z Var.base
0
0
0
0
E1
E2
E3
E4
zj
Cj – zj
200/5 = 40
60/3 = 20
14/1 = 14 → c’est le minimum, donc (cid:1857)(cid:2872) est la variable qui sort de la base.
Étape D : pivotage
Coeff. dans Z
Base
Coef. Z Var.base
0
0
0
0
E1
E2
E3
E4
zj
Cj – zj
1000
X1
10
2
1
0
0
1000
1200
X2
5
3
0
1
0
1200
0
E1
1
0
0
0
0
0
0
E2
0
1
0
0
0
0
0
E3
0
0
1
0
0
0
0
E4
0
0
0
1
0
0
bi
200
60
34
14
0
bi
200
60
34
14
0
La cellule bleue est nommée le pivot. Pour passer au tableau suivant et donc
effectuer la première itération, il est essentiel d’utiliser le pivot.
Page 5 sur 8
Le pivotage s’effectue de la manière suivante :
On commence par diviser la ligne du pivot par le chiffre du pivot.
Dans notre exemple, on divise par 1.
Coeff. dans Z
Base
Coef. Z Var.base
0
0
0
1200
E1
Publicité
E2
E3
X2
zj
Cj – zj
1000
X1
1200
X2
0
E1
0
E2
0
E3
0
E4
0
0
1000
1
0
1200
0
0
0
0
0
0
0
0
0
1
0
0
bi
14
0
Nous poursuivons avec la matrice identité pour les variables de base. Nous inscrivons 1
à l’intersection de chaque variable et 0 ailleurs.
Coeff. dans Z
Base
Coef. Z Var.base
1000
X1
0
0
0
1200
E1
E2
E3
X2
zj
Cj – zj
0
0
1000
1200
X2
0
0
0
1
0
1200
0
E1
1
0
0
0
0
0
0
E2
0
1
0
0
0
0
0
E3
0
0
1
0
0
0
0
E4
1
0
0
bi
14
0
Nous devons calculer les nouvelles valeurs pour les cases restantes à partir du tableau
précédent (tableau initial pour la première itération).
Coeff. dans Z
Base
Coef. Z Var.base
1000
X1
0
0
0
1200
E1
E2
E3
X2
zj
Cj – zj
0
0
1000
1200
X2
0
0
0
1
0
1200
0
E1
1
0
0
0
0
0
0
E2
0
1
0
0
0
0
0
E3
0
0
1
0
0
0
0
E4
1
0
0
bi
14
0
Page 6 sur 8
Publicité
Tableau initial :
Coeff. dans Z
Base
Coef. Z Var.base
0
0
0
0
E1
E2
E3
E4
zj
Cj – zj
1000
X1
10
2
1
0
0
1000
1200
X2
5
3
0
1
0
1200
0
E1
1
0
0
0
0
0
0
E2
0
1
0
0
0
0
0
E3
0
0
1
0
0
0
0
E4
0
0
0
1
0
0
bi
200
60
34
14
0
Dans notre exemple, le 10 contenu dans l’encadré rouge provient de la formule
suivante :
10 (cid:3398)
é(cid:1864)é(cid:1865)(cid:1857)(cid:1866)(cid:1872) (cid:1856)(cid:1857) (cid:1864)(cid:1853) (cid:1864)(cid:1861)(cid:1859)(cid:1866)(cid:1857) (cid:1856)(cid:1873) (cid:1868)(cid:1861)(cid:1874)(cid:1867)(cid:1872) ∗ é(cid:1864)é(cid:1865)(cid:1857)(cid:1866)(cid:1872) (cid:1856)(cid:1857) (cid:1864)(cid:1853) (cid:1855)(cid:1867)(cid:1864)(cid:1867)(cid:1866)(cid:1866)(cid:1857) (cid:1856)(cid:1873) (cid:1868)(cid:1861)(cid:1874)(cid:1867)(cid:1872)
(cid:1868)(cid:1861)(cid:1874)(cid:1867)(cid:1872)
donc 10 – 0∗5
1
(cid:3404) 10.
Faisons un autre exemple avec l'encadré vert. Nous obtenons ‐3 de la façon suivante:
0 (cid:3398)
3 ∗ 1
1
(cid:3404) (cid:3398)3
Coeff. dans Z
Base
Coef. Z Var.base
0
0
0
1200
E1
E2
E3
X2
zj
Cj – zj
1000
X1
10
2
1
0
0
1000
1200
X2
0
0
0
1
0
1200
0
E1
1
0
0
0
0
0
0
E2
0
1
0
0
0
0
0
E3
0
0
1
0
0
0
0
E4
‐5
‐3
0
1
0
0
bi
14
0
Les cases restantes se calculent de la même façon. Lorsque le tableau est rempli
(comme ci‐dessus), il est possible de passer à la deuxième itération qui s'effectue de la
même façon.
Page 7 sur 8
6. Le critère d’arrêt
Nous arrêtons lorsque nous obtenons le critère d'optimalité. L'algorithme du simplexe
s'arrête lorsque:
(cid:1829)(cid:3037) (cid:3398) (cid:1878)(cid:3037) (cid:3409) 0 pour un problème de max
(cid:1829)(cid:3037) (cid:3398) (cid:1878)(cid:3037) (cid:3410) 0 pour un problème de min
Page 8 sur 8