Contrle de gestion 1 Budgets de production

Leon 0603C La programmation linaire 2 le simplexe.doc 1/5

Bernard Auge Alexandre Vernhet
Module 06 - Leon 03 : La mthode du simplexe
1 - Principe
Lorsque nous sommes en prsence de plus de deux produits, la mthode du simplexe est la seule
mthode permettant de trouver la combinaison de produits qui rend optimal la fonction conomique.
Le principe de rsolution ncessite un certain nombre dtapes contenu au travers de lalgorithme
du simplexe dont la dmarche est la suivante : (voir schma page suivante)
2 - Application
Reprenons l'exemple de la Leon 2. La rsolution par l'algorithme du simplex se droule selon 8
tapes avant un nouveau passage.
1
re
tape : crire le systme sous forme standard
Il sagit convertir le programme tabli sous forme canonique (systme dinquation) sous la forme
standard (systme dquation avec variable dcarts). Les variables dcart introduites au cours de
cette transformation reprsentent les contraintes techniques et commerciales disponibles quil
convient de saturer.
Forme canonique Forme standard
e
1
, e
2
, e
3
reprsentant les variables dcart

+ =

+
y x MaxB
y x
y
x
y x
50 30
0 et 0
600
400
1800 2 3

y x
e y
e x
e y x
50 30
600
400
1800 2 3
3
2
1
+
= +
= +
= + +

2
me
tape : Construire le premier tableau correspondant la forme standard



















Variables
dcart


x y e
1
e
2
e
3

e
1
3 2 1 0 0 1800
e
2
1 0 0 1 0 400
e
3
0 1 0 0 1 600
MAX 30 50 0 0 0 0
Valeur solutions
(encadr orange)
Valeur en base
(encadr bleu)
Fonction conomique
(zone jaune)
Coefficient E
ij
(Zone verte)
Contrle de gestion 1 Budgets de production
Leon 0603C La programmation linaire 2 le simplexe.doc 2/5
Bernard Auge Alexandre Vernhet

Oui
Dbut
crire le systme sous forme standard
Construire le premier tableau correspondant
la forme standard

Choisir les variables introduire dans la
base : choisir le coefficient le plus fort de la
fonction conomique
Choisir les variables introduire dans la
base : choisir le coefficient le plus fort de la
fonction conomique
Choisir les variables enlever de la base :
(Rapport : second membres / coefficient de
la variable choisie).
Retenir le plus faible
Encadrer le pivot
Multiplier la ligne du pivot par le rapport :
1/ valeur du pivot
Calculer les valeurs des autres lignes :
E
ij
= E
ij
[A
ij
/ Pivot) x ligne du pivot]
E
ij
: coefficient transformer
A
ij
: coefficient de la colonne du pivot
(i ligne, j colonne)

Les coefficients de
la fonction
conomique sont-
ils tous nuls ou
ngatifs ?
Fin
Non
Contrle de gestion 1 Budgets de production
Leon 0603C La programmation linaire 2 le simplexe.doc 3/5
Bernard Auge Alexandre Vernhet
3
me
tape : Choisir les variables introduire dans la base. Pour cela choisir le coefficient le
plus fort de la fonction conomique
Le coefficient de la fonction conomique (MAX) est 50. Ainsi il sagit de la variable y (encadr
rouge) qui rentre en base.













4
me
tape : Choisir la variable enlever de la base (rapport : second membres / coefficient de
la variable choisie). Retenir le plus faible.
Le second membre (encadr vert), nous retenons la valeur la plus faible (en orange) du rapport
second membre (en vert)/coefficient de la variable choisie (en bleu clair). Ainsi la variable e
3
(encadr
violet) est la variable enlever de la base.















5
me
tape : Encadrer le pivot.
Le pivot est gal 1(encadr en bleu)













x y e
1
e
2
e
3
2
me
membre
e
1
3 2 1 0 0 1800 1800/2 = 900
e
2
1 0 0 1 0 400 400/0 =
e
3
0 1 0 0 1 600 600/1 = 600
MAX 30 50 0 0 0 0
ligne du pivot
x y e
1
e
2
e
3

e
1
3 2 1 0 0
180
0
e
2
1 0 0 1 0 400
e
3
0 1 0 0 1 600
MAX 30 50 0 0 0 0
x y e
1
e
2
e
3
2
me
membre
e
1
3 2 1 0 0 1800
e
2
1 0 0 1 0 400
y 0 1 0 0 1 600
MAX 30 50 0 0 0 0
Fonction conomique
E
ij
A
ij
pivot
ligne
du pivot
Contrle de gestion 1 Budgets de production
Leon 0603C La programmation linaire 2 le simplexe.doc 4/5
Bernard Auge Alexandre Vernhet
6
me
tape : Multiplier la ligne du pivot par le rapport : 1 / valeur du pivot (ou diviser la ligne du
pivot par le pivot)













7
me
tape : Calculer les valeurs des autres lignes
E
ij
= E
ij
- [(A
ij
/ Pivot) x Ligne du pivot]
Cette opration consiste transformer E
ij
des autres lignes en E
ij
, nous effectuons un calcul
matriciel.
1
re
ligne 2
me
ligne 4
me
ligne
3 = 3 [(2/1) x 0] 1 = 1 [(0/1) x 0] 30 = 30 [(50/1) x 0]
0 = 2 [(2/1) x 1] 0 = 0 [(0/1 x 1] 0 = 50 [(50/1) x 1]
1 = 1 [(2/1) x 0] 0 = 0 [(0/1 x 0] 0 = 0 [(50/1) x 0]
0 = 0 [(2/1) x 0] 1 = 1 [(0/1 x 0] 0 = 0 [(50/1) x 0]
- 2 = 0 [(2/1) x 1] 0 = 0 [(0/1 x 1] - 50 = 0 [(50/1) x 1]
600 = 1 800 [(2/1) x 600] 400 = 400 [(0/1 x 600] - 30 000 = 0 [(50/1) x 600]












8
me
tape : Les coefficients de la fonction conomique sont ils tous nuls ou ngatifs ? (si oui
nous sommes loptimum, si non nous effectuons un nouveau passage)
Les coefficients de la fonction conomique ne sont pas tous nuls ou ngatifs (30) il convient
deffectuer un nouveau passage.
Nouveau passage :
Choisir les variables introduire dans la base. Pour cela choisir le coefficient le plus fort de la
fonction conomique.
Le coefficient de la fonction conomique (MAX) est 30. Ainsi il sagit de la variable x (encadr
rouge) qui rentre en base.








x y e
1
e
2
e
3
2
me
membre
e
1

e
2

y 0 1 0 0 1 600
MAX
x y e
1
e
2
e
3
2
me
membre
1
re
ligne
e
1
3 0 1 0 -2 600
2
me
ligne e
2
1 0 0 1 0 400
ligne du pivot y 0 1 0 0 1 600
4
me
ligne MAX 30 0 0 0 -50 -30 000

x y e
1
e
2
e
3
2
me
membre
e
1
3 0 1 0 -2 600
e
2
1 0 0 1 0 400
y 0 1 0 0 1 600
MAX 30 0 0 0 -50 -30 000


E
ij
1/pivot
Contrle de gestion 1 Budgets de production
Leon 0603C La programmation linaire 2 le simplexe.doc 5/5
Bernard Auge Alexandre Vernhet
Choisir la variable enlever de la base (rapport : second membres / coefficient de la variable
choisie). Retenir le plus faible.
Le second membre (encadr vert), nous retenons la valeur la plus faible (en orange) du rapport
second membre /coefficient de la variable choisie (encadr rose). Ainsi la variable e
1
(encadr
marron) est la variable enlever de la base.











Le pivot est gal 3 (encadr en vert fonc)
Multiplier la ligne du pivot par 1/3 (ou diviser la ligne du pivot par le pivot : 3)
Calculer les autres de valeur des lignes
2
me
ligne 3
me
ligne 4
me
ligne
0 = 1 [(1/3) x 3] 0 = 0 [(0/3) x 3] 0 = 30 [(30/3) x 3]
0 = 0 [(1/3) x 0] 1 = 1 [(0/3) x 0] 0 = 0 [(30/3) x 0]
- 1/3 = 0 - [(1/3) x 1] 0 = 0 [(0/3) x 1] - 10 = 0 [(30/3) x 1]
1 = 1 - [(1/3) x 0] 0 = 0 [(0/3) x 0] 0 = 0 [(30/3) x 0]
2/3 = 0 - [(1/3) x -2] 1 = 1 [(0/3) x -2] - 30 = -50 [(30/3) x -2]
200 = 400 - [(1/3) x 600] 600 = 600 [(0/3) x 600] - 36 000 = -30 000 [(30/3) x 600]













Les coefficients de la fonction conomique sont tous nuls ou ngatifs, fin de lalgorithme du
simplex. La solution qui rend optimal le programme de production est le suivant :
La marge sur cot variable maximum = 36 000 , les quantits produites x = 200, y = 600, et on
constate que la variable dcart e
2
correspondant la contrainte de march de X nest pas sature.
Nous aurions pu vendre 200 produits X de plus. Par contre e
1
la variable dcart traduisant la
contrainte technique et e
3
la variable dcart correspondant la contrainte commerciale du march du
produit y sont satures.
x y e
1
e
2
e
3
2
me
membre
ligne du
pivot
x 1 0 1/3 0 -2/3 200
2
me
ligne e
2
0 0 -1/3 1 2/3 200
3
me
ligne y 0 1 0 0 1 600
4
me
ligne MAX 0 0 -10 0 -30 -36 000
x y e
1
e
2
e
3
2
me
membre
e
1
3 0 1 0 -2 600 600/3 = 200
e
2
1 0 0 1 0 400 400/1 = 400
y 0 1 0 0 1 600 600/0 =
MAX 30 0 0 0 -50 -30 000