ENIT Recherche Opérationnelle
TD 1 : FORMULATION DES PROGRAMMES LINÉAIRES
RÉSOLUTION GRAPHIQUE
Correction
Exercice 1 :
1. Variables de décision :
x1 : Quantité à produire de P1,
x2 : Quantité à produire de P2,
x3 : Quantité à produire de P3.
(PL1) max 30 x1 + 12 x2 + 15 x3
sc 9 x1 + 3 x2 + 5 x3 500
5 x1 + 4 x2 350
3 x1 + 2 x3 150
x3 20
x 1 , x 2 , x3 0
Exercice 2 :
[Link] de décision :
x1 : Quantité d’orge,
x2 : Quantité d’arachide,
x3 : Quantité de sésame.
(PL1) min 25 x1 + 41 x2 + 39 x3
sc 12 x1 + 52 x2 + 42 x3 22
2 x1 + 2 x2 + 10 x3 3,6
x1 + x2 + x3 = 1
x 1 , x 2 , x3 0
2. x1 + x2 + x3 = 1 alors x3 = 1 - x1 - x2
(PL1)’ min -14 x1 + 2 x2 + 39
sc -30 x1 + 10 x2 -20
-8 x1 - 8 x2 -6,4
x1 + x2 1
x1 , x 2 0
Ou encore
(PL1)’ min -14 x1 + 2 x2
sc 30 x1 - 10 x2 20
8 x1 + 8 x2 6,4
x1 + x2 1
x1 , x 2 0
A. Ouled Bedhief DABABI 1
ENIT Recherche Opérationnelle
Après la résolution graphique, la solution optimale est : (0,75 ; 0,25 ; 0) avec z* = 29
Exercice 3 :
[Link] de décision :
x1 : Quantité à produire de A,
x2 : Quantité à produire de B.
(PL1) max 7 x1 + 5 x2
sc x1 + 2 x2 6.000
2 x1 + x2 8.000
x1 3.500
x2 2.500
x1, x2 0
2.
La résolution graphique du problème montre que la solution est le point intersection entre les
deux droites :
xA+2xB = 6000
2xA+xB = 8000
la solution optimale est xA=10000/3 ; xB=4000/3 et Z* = 30000
3.
Une unité supplémentaire de R1 augmenterait x2 de 2/3, réduirait x1 de 1/3 et augmenterait z*
de une unité :
x1 = 3.333 et x2 = 4.002/3 z* = 30.001.
4.
Une unité supplémentaire de R2 augmenterait x1 de 2/3, réduirait x2 de 1/3 et augmenterait z*
de 3 unités :
x1 = 3.334 et x2 = 1.333 z* = 30.003.
Exercice 4 :
Variables de décision :
xi : Montant à investir dans le placement de type A, au début de l’année i, i = 1, 2, 3,
yi : Montant à investir dans le placement de type B, au début de l’année i, i = 1 ou 2.
Fonction objectif :
Max z = 1,15x3 + 1,90 y2
Contraintes budgétaires :
Année 1 : x1 + y1 10.000
Année 2 : x2 + y2 10.000 - x1 - y1 + 1,15 x1
Année 3 : x3 10.000 - x1 - y1 + 1,15 x1 - x2 - y2 + 1,15 x2 + 1,90 y1
A. Ouled Bedhief DABABI 2
ENIT Recherche Opérationnelle
Le programme linéaire s’écrit alors :
(PL) Max z = 1,15x3 + 1,90 y2
sc x1 + y1 10.000
- 0,15 x1 + x2 + y1 + y2 10.000
- 0,15 x1 - 0,15 x2 + x3 - 0,90 y1 + y2 10.000
xi 0 i = 1, 2, 3
yi 0 i = 1, 2
Exercice 5.
1. Variables de décision :
xi : Quantité à produire pendant le mois i.
si : Quantité en stock au début du mois i.
Le problème consiste à minimiser le coût de production, le coût d’augmentation de la
production et le coût de stockage :
S.c
Exercice 6.
1- Les variables de décision :
Yi = 1 si le projet i est réalisé
Yi = 0 sinon
i = 1,..3
Fonction objectif :
Max Z= 16Y1 + 22Y2 + 12 Y3 + 8Y4.
Conditions = Les contraintes :
Budget
5Y1 + 7Y2 + 4Y3 + 3 Y4 ≤ 14
Le programme linéaire s'écrit alors:
Max Z=16 Y1 + 22 Y3 + 13 Y3 + 8 Y4
S.C
PL 5 Y1 + 7 Y2 + 4 Y3 + 3 Y4 ≤ 14
Y1 , Y2 , Y3 , Y4 { 0 , 1 }
A. Ouled Bedhief DABABI 3
ENIT Recherche Opérationnelle
2.a.
Nombre de projets réalisés.
Y1 + Y2 +Y3 + Y4 ≤ 2
2. b.
Si Y2 = 1 alors Y1 = 1 <==> Si Y1 = 0 alors Y2 = 0
Y2 ≤ Y1
2 .c .
Si Y2 = 1 alors Y4 = 0 <==> Si Y2 = 1 alors 1 – Y4 = 1
Y2 + Y4 ≤ 1
A. Ouled Bedhief DABABI 4
