Université Mohamed Boudiaf de M’sila
Faculté des Mathématique et de l’Informatique
Département d’Informatique
Intitulé du Master : Informatique Décisionnelle et Optimisation
Semestre : S1
Intitulé de l’UE : UEM 1.1
Intitulé de la matière : Programmation linéaire avancée
TD 1
Modélisez les problèmes suivants sous la forme d’un programme linéaire. Formalisez
mathématiquement les données, les variables de décision, la fonction objectif ainsi que les
contraintes.
Exercice n° 1 :
Une entreprise s’adonne à la production de tables et de chaises. Le coût de production de
chaque table est de 30 DA et celui de chaque chaise est de 20 DA. Le marché de vente peut
absorber une production d’au plus 3 tables et 4 chaises par jour. De plus le nombre total de
tables et de chaises vendues ne peut excéder 5 unités par jour. Une fois que l’assemblage est
complété, chaque table requiert 2 heures de séchage et chaque chaise requiert 1 heure de
séchage pour permettre à la colle de se fixer. L’appartement où se fait le séchage ne peut
contenir qu’une seule unité à la fois. Pour des raisons économiques on exige que
l’appartement où on fait le séchage soit utilisé au moins 5 heures par jour. Aussi,
l’empaquetage d’une table requiert 2 opérations et celui d’une chaise, 4 opérations sur une
machine. Pour des raisons économiques on exige également que le nombre d’opérations
exécutées sur cette machine soit au moins égal à 8 par jour.
Formuler sous forme d’un programme linéaire le problème de déterminer le nombre de tables
et de chaises à produire par jour pour minimiser le coût total.
Exercice n° 2 :
Une usine de ciment produit deux types, le ciment C1 et le ciment C2.
La vente d’une tonne de C1 lui donne un bénéfice de 400 DA et une tonne de C2 un bénéfice
de 500 DA.
La production est réalisée sur deux machines M1 et M2. M1 est disponible 6 heures par jours
et M2 est disponible 8 heures par jours.
La production d’une tonne de C1 nécessite 40 minutes sur M1 et 20 minutes sur M2.
La production d’une tonne de C2 nécessite 30 minutes sur M1 et 30 minutes sur M2.
Quelles quantités de ciment C1 et C2 doit-on produire pour maximiser le bénéfice de l’usine ?
1. Donner le programme linéaire
2. Transformer le programme en programme standard.
1
Exercice n° 3 :
Une entreprise fabrique deux produits P1 et P2. Les ressources requises pour la fabrication
d’une tonne de chaque produit et le profit unitaire sont donnés par le tableau suivant :
Quelle quantité de chaque produit l’entreprise devrait-elle fabriquer afin de maximiser son
profit ?
Exercice n° 4 :
Une usine est spécialisée dans la production de deux produits P1 et P2.
Chaque produit nécessite :
– un certain nombre d’heures de machine,
– et un certain nombre d’heures de main d’œuvre.
Machine Main D’œuvre Profit
P1 2 heures / unité 3 heures / unité 25 DA / unité
P2 2 heures / unité 1 heure / unité 15 DA / unité
Total 240 140
1. Formaliser ce problème et donnez le programme linéaire,
2. l’écrire sous la forme standard en utilisant les variables d’écart.
