-
8/3/2019 Exercices corrigs sur PL
1/4
Youssef
1
Exercices sur la programmation linaire
Exercice 1 :
Une entreprise fabrique trois modles de TV couleur A, B et C qui
lui rapportent des profitsde 1600 DH, 3000 DH et 5000 DH. Les
niveaux minima de production pour une semaine sont
de 100 pour A, 150 pour B et 75 pour C. Chaque douzaine de TV de
type i requiert un temps
Fi pour la fabrication, un temps Ai pour lassemblage et un temps
Ei pour lemballage.
A B C
Fi 3 3,5 5
Ai 4 5 8
Ei 1 1,5 3
Pendant une semaine venir, lentreprise aura 150 heures
disponibles pour la fabrication, 200
pour lassemblage et 60 pour lemballage. Formuler un modle
donnant un plan de production
qui maximise le profit de la compagnie.
Exercice 2 :
Un revendeur dordinateurs doit approvisionner son magasin de Fs
et celui de Marrakech
partir des entrepts de Casablanca et de Rabat. Les cots
unitaires en Dirhams de livraison
sont les suivants :
Entrepts/Magasins Marrakech Fs
Casablanca 600 300
Rabat 500 900
Le magasin de Marrakech commande 30 ordinateurs et celui de Fs
en commande 25. Il ya
45 appareils en stock Casablanca et 40 Rabat.
Dterminer par la mthode graphique un programme
dapprovisionnement optimal.
Solutions
Exercice 1 :
On pose A : x, B : y et C : z
***** x y z Limite
Fi 1/4 7/24 5/12 150
Ai 1/3 5/12 2/3 200
Ei 1/12 1/8 1/4 60
Profit par
unit
1600 3000 5000 *****
-
8/3/2019 Exercices corrigs sur PL
2/4
Youssef
2
Max { Z = 1600x +3000y + 5000z }
1/4 x +7/24 y+5/12 z 1501/3 x +5/12 y+2/3 z 200
S C 1/12 x+1/8 y+ 1/4 z 60
x 100
y 150
z 75
Max { Z = 1600x +3000y + 5000z Ma1 Ma2 Ma3 }
1/4 x +7/24 y+5/12 z +e1 = 150
1/3 x +5/12 y+2/3 z +e2 = 200S C 1/12 x+1/8 y+ 1/4 z +e3 = 60x
+a1 e4 = 100
y +a2 e5 = 150
z +a3 e6 = 75
Z = 1600x +3000y + 5000z Ma1 Ma2 Ma3Z = 1600x +3000y + 5000z
M(100 x +e4) M(150 y +e5) M(75 z +e6)
Z = x(1600+M) +y(3000+M) +z(5000+M) Me4 Me5 Me6 325M
Tableau 1
x y z * * * e4 e5 e6 * * * B
e1 1/4 7/24 5/12 1 0 0 0 0 0 0 0 0 150
e2 1/3 5/12 2/3 0 1 0 0 0 0 0 0 0 200
e3 1/12 1/8 1/4 0 0 1 0 0 0 0 0 0 60
a1 1 0 0 0 0 0 -1 0 0 1 0 0 100
a2 0 1 0 0 0 0 0 -1 0 0 1 0 150
a3 0 0 1 0 0 0 0 0 -1 0 0 1 75
Z 1600+M 3000+M 5000+M 0 0 0 -M -M -M 0 0 0 325M
z entre ; R = B/z 75 est le plus petit donc a3 sort
Tableau 2
x y * * * * e4 e5 e6 * * BL1-(5/12)
L6e1 1/4 7/24 0 1 0 0 0 0 5/12 0 0 475/4
L2-(2/3) L6 e2 1/3 5/12 0 0 1 0 0 0 2/3 0 0 150L3-(1/4) L6 e3
1/12 1/8 0 0 0 1 0 0 1/4 0 0 165/4L4 a1 1 0 0 0 0 0 -1 0 0 1 0
100L5 a2 0 1 0 0 0 0 0 -1 0 0 1 150L6 z 0 0 1 0 0 0 0 0 -1 0 0
75
-
8/3/2019 Exercices corrigs sur PL
3/4
Youssef
3
L7-
(5000+M)L6Z 1600+M 3000+M 0 0 0 0 -M -M 5000 0 0 250M-
375000
y entre ; R = B/y 150 est le plus petit donc a2 sort
Tableau 3
x * * * * * e4 e5 e6 * BL1-(7/24)
L5e1 1/4 0 0 1 0 0 0 7/24 5/12 0 75
L2-(5/12)L5
e2 1/3 0 0 0 1 0 0 5/12 2/3 0 175/2
L3-(1/8) L5 e3 1/12 0 0 0 0 1 0 1/8 1/4 0 45/2L4 a1 1 0 0 0 0 0
-1 0 0 1 100L5 y 0 1 0 0 0 0 0 -1 0 0 150L6 z 0 0 1 0 0 0 0 0 -1 0
75L7-
(3000+M)L5Z 1600+M 0 0 0 0 0 -M 3000 5000 0 100M-
825000
x entre ; R = B/x 100 est le plus petit donc a1 sort
Tableau 4
* * * * * * e4 e5 e6 BL1-(1/4) L4 e1 0 50L2-(1/3) L4 e2 0
325/6L3-(1/12)
L4e3 0 85/6
L4 x 1 0 0 0 0 0 -1 0 0 100L5 y 0 150L6
z 0 75L7-(1600+M)L4
Z 0 0 0 0 0 0 1600 3000 5000 -985000
Ainsi : Z*
= 985000 ; x*
= 100 ; y*
= 150 ; z*
= 75 ; e1 = 50 ; e2 = 325/6 ; e3 = 85/6
Exercice 2:
Min { D = 600x1 + 500x2 + 300y1+ 900y2 }
On a x1 + x2 = 30 x2 = 30 x1
y1 + y2 = 25 y2 = 25- y1
Min { D = 600x1 + 500 (30 x1) + 300y1+ 900 (25- y1) }
Min { D = 100x1 - 600y1 + 37500 }
x1 + y1 45x1 + y1 15 ( car x2 + y2 40 ( 30 x1 + 25 y1 40 )
S C x1 30
y1 25x1, y1 0
-
8/3/2019 Exercices corrigs sur PL
4/4
Youssef
4
(E1) x1 + y1 =45 ( 45, 0) ; ( 0, 45 )(E2) x1 + y1 = 15 ( 15, 0)
; ( 0, 15 )
(E3) x1 = 30 ( 30, 0)
(E4) y1 = 25 ( 0, 25)
Sommets A (15,0) B (30,0) C (30,15) D (20,25) E (0,25) F
(0,15)
D 39000 40500 31500 24500 22500 28500
x1 + y1 =45 y1 = 15C (E1) (E3)
x1 = 30 x1 = 30
x1 + y1 =45 x1 = 20D (E1) (E4)
y1 = 25 y1 = 25
Ainsi : D* =22500 ; x1* = 0 ; y1* = 25 ; x2* = 30 ; y2* = 0
