Université Larbi Ben M’Hidi, Oum El Bouaghi Le 11/01/2023
Département Maths et Informatique
3eme Année Licence Informatique SI
Matière : Programmation Linéaire
Examen Final
Exercice 1 : (10 points)
Une laiterie fabrique deux types de « YAOURTS A LA FRAISE » A et B qui lui rapportent des profits
de 400 DA et 500 DA (par Kilo). Chaque yaourt doit respecter les proportions suivantes de
matières premières :
A B
Fraise 2 1
Lait 1 2
Sucre 0 1
Les matières premières sont en quantité limitée : 800 kilos de fraises, 700 kilos de lait
et 300 kilos de sucre.
a) Ecrire le programme linéaire (P) permettant de déterminer le plan de production conduisant au
profit maximal.
b) Résoudre (P) graphiquement
c) Interpréter et analyser les résultats obtenus.
d) On suppose que le prix de vente de Yaourt A varie. Etudier graphiquement les conséquences
de cette variation du profit sur le plan de production.
e) L’incertitude sur la quantité du Fraise susceptible d'être livrée est grande. Quel serait l'impact
sur le plan de production d'une modification de cette quantité de matière première.
Exercice 2 : (10 points)
On considère le programme linéaire (P) suivant:
Max Z= 400x1 + 500x2
S.c :
(P) 2x1 + x2 ≤ 800
x1 + 2x2 ≤ 700
x2 ≤ 300
x 1, x 2 ≥ 0
a) Mettre le problème (P) sous forme standard.
b) Déterminer la solution optimale de (P) par la méthode du Simplexe.
c) Ecrire le programme dual (D) du programme (P).
d) Déduire la solution optimale du programme (D).
Bon courage !
Corrigé-Type
Exercice 1 : (10 points)
a) le programme linéaire : (2 points)
Les variables de décision : x1 et x2 représentent les quantités du yaourt A et B respectivement.
Max Z= 400x1 + 500x2
S.c :
(P) 2x1 + x2 ≤ 800 ….(1)
x1 + 2x2 ≤ 700 ….(2)
x2 ≤ 300 …(3)
x1, x2 ≥ 0
b) Résolution graphique de (P) (2 points)
Le domaine des solutions réalisables est représenté par la zone verte (délimité par le polygone HGCB).
En utilisant la méthode des droites parallèles, L’optimum global est unique est se situe au point
C(300, 200) avec pour Z= 220000.
c) Interprétation et analyse des résultats obtenus. (1 point)
Donc pour atteindre l’optimum, les quantités à produire sont 300Kg de yaourt A et 200kg de yaourt B.
Le profit maximum sera 220000 DA.
L’analyse de cette solution montre que tous la quantité de Fraise et de lait sont utilisées (contraintes
saturées), mais qu'il reste 100kg du sucre disponible.
d) Etude graphique des conséquences de variation du profit sur le produit A. (2.5 points)
Si le prix de Yaourt A varie, graphiquement cela se traduit par le modification de la pente de la droite
représentant la fonction objectif dont l'équation devient p 1x1 + 500 x2= k.
La pente de la droite associée à la contrainte (1) est en valeur absolue de 2 celle associée à la contrainte
(2) est en valeur absolue de 1/2.
Donc si 1/2 ≤ p1/ 500 ≤ 2 Alors (250 ≤ p1≤ 1000 ) la solution optimale est encore associée au point C.
Si p1≥ 1000 , la solution optimale est associée au point B.
Si 0 ≤ p1≤250, la solution optimale est associée au point G.
Pour p1 = 1000 tous les points du segment CB correspondent à des solutions optimales
Pour p1 = 250 tous les points du segment GC correspondent à des solutions optimales
e) L'impact sur le plan de production d'une modification de quantité de fraise. (2.5 point)
La contrainte portant sur la quantité de fraise est représentée par la droite (1) dont l’équation :
2x1+ x2 = 800 passe à 2x1 + x2 = 800 + δ. Graphiquement cela signifie que la contrainte (1) se déplace
parallèlement à elle-même, vers le haut, si δest positif, vers le bas si δest négatif.
- les coordonnées du point d'intersection des droites (1) et (2).
2x1+ x2 = 800 + δet x1 + 2x2 = 700
Soit x1 = 300 + 2δ/3 et x2 = 200 - δ/3
- cette solution est dans le domaine des solutions réalisables.
x1 ≥ 0 , x2 ≥ 0 et la contrainte (3) doit rester satisfaite :
x1 ≥ 0 ⟺300 + 2δ/3 ≥ 0⟺δ≥ - 450
x2 ≥ 0 ⟺200 - δ/3 ≥ 0⟺δ≤ 600
Contrainte (3) satisfaite ⟺200 - δ/3 ≤ 300 ⟺δ≥ 300
Soit 300 ≤ δ≤ 600
- Tant que δ reste compris entre 300 et 600, la solution optimale reste à l’intersection des contraintes (1)
et (2) : c’est à dire que la quantité de fraise et de lait continuent d’être utilisée entièrement alors qu’il
reste toujours du sucre disponible.
Pour δ kilos de fraise supplémentaire, la production de yaourt A augmente de 2δ/3 alors que celle de
yaourt B diminue de δ/3. La variation du profit sera alors égale à 400* 2δ/3 - 500* δ/2 = 100δ
Exercice 2 : (10 points)
On considère le programme linéaire (P) suivant:
Max Z= 400x1 + 500x2
S.c :
(P) 2x1 + x2 ≤ 800
x1 + 2x2 ≤ 700
x2 ≤ 300
x 1, x 2 ≥ 0
a) Le problème (P) sous forme standard. (2 point)
Max Z= 400x1 + 500x2
(P) 2x1 + x2 +e1= 800
x1 + 2x2 +e2= 700
x2 +e3= 300
x1, x2 ≥ 0 e1,3≥0
b) La solution optimale de (P) par la méthode du Simplexe. (4 points)
x1 x2 e1 e2 e3 bi R
e1 2 1 1 0 0 800 800
e2 1 2 0 1 0 700 350
e3 0 1 0 0 1 300 300
Z 400 500 0 0 0 0
e1 2 0 1 0 -1 500 250
e2 1 0 0 1 -2 100 100
x2 0 1 0 0 1 300 ∞
Z 400 0 0 0 -500 -150000
e1 0 0 1 -2 3 300 100
x1 1 0 0 1 -2 100 <0
x2 0 1 0 0 1 300 300
Z 0 0 0 -400 300 -190000
e3 0 0 1/3 -2/3 1 100
x1 1 0 2/3 -4/3 0 300
x2 0 1 -1/3 2/3 0 200
Z 0 0 -100 -200 0 -220000
x1=300, x2=200, Z=220000
e1=0, e2=0, e3=100
c) Le programme dual (D) du programme (P). (2 points)
Min W= 800 y1 + 700 y2 + 300 y3
S.c :
(D) 2y1 + y2 ≥ 400
y1 + 2y2 + y3 ≥ 500
y1, y2 , y3≥ 0
d) La solution optimale du programme (D). (2 points)
y1=100, y2=200, y3= 0, W=220000
u1=0, u2=0
