L3 Informatique
Programmation Linéaire
TD Méthode de simplexe
Exercice 1
Une entreprise disposant de 10 000 m2 de carton en réserve, fabrique
et commercialise 2 types de boîtes en carton. La fabrication d’une
boîte en carton de type 1 ou 2 requiert, respectivement, 1 et 2 m 2 de
carton ainsi que 2 et 3 minutes de temps d’assemblage. Seules 200
heures de travail sont disponibles pendant la semaine à venir. Les
boîtes sont agrafées et il faut quatre fois plus d’agrafes pour une boîte
du second type que pour une du premier. Le stock d’agrafes disponible
permet d’assembler au maximum 15 000 boîtes du premier type. Les
boîtes sont vendues, respectivement, 300 DA et 500DA.
- Formuler le problème de la recherche d’un plan de production
maximisant le chiffre d’affaires de l’entreprise sous forme d’un
programme linéaire.
- Résoudre le problème par la méthode de simplexe
Solution exe1
Max Z=300 x1 + 500 x2
s.c. x1+ 2x2 <= 10000
2 x1 + 3x2 <= 12000
X1 + 4 x2 <= 15000
X1, x2>= 0
L3 Informatique
Programmation Linéaire
Méthode simplexe
Etape 0
Forme standard du PL
Max Z= 300 x1 + 500 x2
s.c. x1+ 2x2 + e1 =10000
2x1 + 3 x2 + e2 = 12000
X1 + 4 x2 + e3 =15000
X1, x2, e1, e2, e3>=0
Tableau initial
Base X1 X2 e1 e2 e3 b
e1 1 2 1 0 0 10000
e2 2 3 0 1 0 12000
e3 1 4 0 0 1 15000
-Z 300 500 0 0 0 0
Itération 1
Etape1
Base X1 X2 e1 e2 e3 b Critère
e1 1 2 1 0 0 10000 10000/2=500
0
e2 2 3 0 1 0 12000 12000/3=400
0
e3 1 4 0 0 1 15000 15000/4=375
0
-Z 300 500 0 0 0 0
X2 va entrer dans la base et e3 va sortir de la base
etape 2
Base X1 X2 e1 e2 e3 b
e1 1/2 0 1 0 -1/2 2500
e2 5/4 0 0 1 -3/4 750
X2 1/4 1 0 0 1/4 3750
L3 Informatique
Programmation Linéaire
-Z 175 0 0 0 -125 -1875*103
Solution e1=2500, e2= 750 , x2= 3750 et x1=e3=0
Itération 2
Etape 1
Base X1 X2 e1 e2 e3 b
e1 1/2 0 1 0 -1/2 2500
e2 5/4 0 0 1 -3/4 750
X2 1/4 1 0 0 1/4 3750
-Z 175 0 0 0 -125 -1875*103
X1 entre dans la base
Etape2
Base X1 X2 e1 e2 e3 b Critère
e1 1/2 0 1 0 -1/2 2500 2500/(1/2)=5000
e2 5/4 0 0 1 -3/4 750 750/(5/4)=600
X2 1/4 1 0 0 1/4 3750 3750/
(1/4)=15000
-Z 175 0 0 0 -125 -1875*103
e2 va sortir de la base
Base X1 X2 e1 e2 e3 b
e1 0 0 1 -5/2 -1/5 2200
X1 1 0 0 4/5 -3/5 600
X2 0 1 0 -1/5 2/5 3600
-Z 0 0 0 -140 -20 -1980*103
L’algorithme s’arrete
Solution optimale est :
E1=2200, x1=600, x2= 3600 et e2=e3=0 Z= 1980*103
Z=300 x1+ 500 x2= 300*600 + 500* 3600=180000+1800000=1980*103
L3 Informatique
Programmation Linéaire
Exercice 2
Résoudre le programme linéaire suivant par la méthode de deux phases :
Max Z=5x1+ 2x2
s.c. 2x1+ x2<=70
x1<=30
x1+ x2>=10
x1, x2>=0
Solution Exercice 2
Max Z=5x1+ 2x2
s.c. 2x1+ x2<=70
x1<=30
x1+ x2>=10
x1, x2>=0
Forme standard
Max Z=5x1+ 2x2
s.c. 2x1+ x2 +e1=70
x1 + e2=30
x1+ x2 – e3=10
x1, x2, e1, e2, e3>=0
Phase I
Min Z’=a
s.c. 2x1+ x2 +e1=70
x1 + e2=30
x1+ x2 – e3 + a=10
x1, x2, e1, e2, e3, a>=0
Base x1 x2 e1 e2 e3 a b Critère
e1 2 1 1 0 0 0 70
e2 1 0 0 1 0 0 30
L3 Informatique
Programmation Linéaire
a 1 1 0 0 -1 1 10
-Z 5 2 0 0 0 0 0
-Z’ 0 0 0 0 0 1 0
Il faut enlever le coefficient de la variable artificielle de la ligne qui exprime la fonction Z’ du
tableau ; pour cela on fait L5 (ligne bleu)=L5 (ligne verte)-L3
Base x1 x2 e1 e2 e3 A b Critère
e1 2 1 1 0 0 0 70 70/2=3
5
e2 1 0 0 1 0 0 30 30/1=3
0
A 1 1 0 0 -1 1 10 10/1=1
0
-Z 5 2 0 0 0 0 0
-Z’ -1 -1 0 0 1 0 -10
Choix de variable entrante= min (-1, -1)
Puisque x1 et x2 ont le même coefficient (=-1)le choix est arbitraire
x1 entre dans la base et A sort de la base
Base x1 x2 e1 e2 e3 B Critère
e1 0 -1 1 0 2 50
e2 0 -1 0 1 1 20
x1 1 1 0 0 -1 10
-Z 0 -3 0 0 5 -50
-Z’ 0 0 0 0 0 0
La variable artificielle est hors base, on a maintenant une base pour le problème initial.
Phase II
Base x1 x2 e1 e2 e3 B Critère
e1 0 -1 1 0 2 50 50/2
e2 0 -1 0 1 1 20 20/1
x1 1 1 0 0 -1 10
-Z 0 -3 0 0 5 -50
e3 rentre dans la base et e2 sort de la base
Base x1 x2 e1 e2 e3 B Critère
e1 0 1 1 -2 0 10
e3 0 -1 0 1 1 20
L3 Informatique
Programmation Linéaire
x1 1 0 0 1 0 30
-Z 0 2 0 -5 0 -150
x2 rentre dans la base et e1 sort de la base
Base x1 x2 e1 e2 e3 B Critère
x2 1 1 1 -2 0 10
e3 0 0 1 -1 1 30
x1 0 0 0 1 0 30
-Z 0 0 -2 -1 0 -170
Tous les coefficients sont <=0 alors l’algorithme s’arrête
Solution optimale : x1=30, x2= 10, e3=30, Z=170