TD 1 - Modélisation en Programme Linéaire
Exercice n° 1 : Formulation d'un aliment (A. B. HADJ-ALOUANE)
On désire déterminer la composition, à coût minimal, d'un aliment pour bétail qui est obtenu en
mélangeant au plus trois produits bruts: orge, arachide, et sésame. L'aliment ainsi conditionné
devra comporter au moins 22% de protéines et au plus 3.6% de graisses, pour se conformer aux
exigences de la clientèle. Le tableau ci-dessous indique les pourcentages de protéines et de
graisses contenus, respectivement, dans l'orge, les arachides et le sésame, ainsi que le coût par
tonne de chacun des produits.
1. Soit xj (j =1,2,3) la fraction de tonne de produit brut j contenue dans une tonne d'aliment.
Formuler le problème sous forme d’un programme linéaire.
2. Montrer qu'il est possible de réduire la dimension du problème. Le résoudre
géométriquement.
Exercice n° 2 : Fabrication d’huile d’olives (J.-F. Heche)
Une entreprise fabrique trois qualités différentes d’huile d’olive. Les quantités maximales
pouvant être vendues chaque mois ainsi que les prix de vente sont donnés dans le tableau
suivant :
dd
L’entreprise paie 1000 dinars pour une tonne d’olives. Chaque tonne d’olives fournit soit 300
litres d’huile A soit 200 litres d’huile B (les coûts de ces transformations ne sont pas modélisés).
Chaque litre d’huile A peut-être raffiné pour produire 6 dl d’huile B et 3 dl d’huile C. Le coût
d’un tel raffinement est de 0.5 dinar par litre. De même, chaque litre d’huile B peut être raffiné
pour obtenir 8 dl d’huile C. Le coût de ce raffinement et de 0.3 dinar par litre.
1. Formuler un programme linéaire afin d’aider l’entreprise a déterminer un plan de production
mensuel maximisant son profit. Préciser clairement les variables de décision, la fonction
objectif et les contraintes.
Exercice n° 3 : Transformation en PL
Considérons le problème suivant :
min z = 2*x + 3*|y − 10|
s.c. |x + 2| + |y| ≤ 15
Reformuler ce problème sous forme de programme linéaire.
Exercice n° 4 : Marketing (N. Brauner)
Une entreprise dispose d'un budget publicitaire de 4800 dinars pour le lancement de son
nouveau produit. Sa campagne publicitaire utilisera à la fois des spots télévisés et des pages
dans la presse quotidienne. On pense que chaque minute de télévision va atteindre 100 000
nouveaux spectateurs et chaque page dans un journal va être lue par 80 000 nouveaux lecteurs.
Une minute de télévision coûte 800 dinars et une page dans un journal 600 dinars. La direction
de l'entreprise souhaite diffuser au moins trois minutes de spot et une page dans un journal. Son
objectif est de maximiser le nombre total de cibles (spectateurs et lecteurs).
1. Modéliser ce problème en programme linéaire.
Exercice n° 5 : Fabrication du gâteau (A. B. HADJ-ALOUANE)
Une compagnie fabrique deux types de mélange pour gâteau : A et B en utilisant deux
ressources : R1 et R2. Le tableau suivant résume les données pertinentes :
1. Formuler le problème de détermination des quantités à produire de A et de B sous forme d’un
PL.
2. Trouver géométriquement l'optimum fractionnaire, son arrondi et l'optimum entier.
3. Calculer l’augmentation du profit total qui résulte d’une unité supplémentaire de R1.
4. Quelle serait l’augmentation du profit si on augmente R2 d’une unité.
Exercice n° 6 : Planification de production
Un fabriquant doit produire une certaine marchandise en vue de satisfaire des commandes pour
les n mois à venir. Pour le mois i, la demande est de ri unités, et la production est de xi unités.
La commande du mois i peut être satisfaite soit à partir de la production du mois i soit du stock
disponible en début de période. Les coûts de production sont variables d’un mois à l’autre et
valent ci unités monétaires par unité de produit pendant le mois i. Il n’y a pas de contraintes de
capacité de production, sauf que le niveau de production au cours de chaque mois doit être au
moins égal à celui du mois précédent. Par ailleurs, l’augmentation de production d’un mois à
l’autre revient à di unités monétaires par unité de produit supplémentaire. L’entreprise peut
avoir intérêt à produire pendant un certain mois plus d’unités que nécessaire pour satisfaire la
demande de ce mois, et stocker l’excès en vue de satisfaire la demande pendant un mois
ultérieur. Elle doit, cependant, subir des frais de stockage de ei unités monétaires par unité
stockée du mois i au mois i+1.
L’entreprise veut déterminer le plan de production et de stockage pour les n mois à venir de
façon à minimiser le coût total de production et de stockage tout en répondant aux besoins des
clients.
En supposant que le stock initial est nul, écrire le programme linéaire correspondant à ce
problème.
1. Formuler ce problème de production sous forme d’un PL.
