Techniques d’optimisation
TD nº 1 : formulation d’un PL et résolution graphique
Exercice nº1
Une entreprise peut fabriquer un même produit dans deux ateliers. Les capacités de production de
ces deux ateliers, exprimées en quantité de produit, sont de 7 pour le premier atelier et de 10 pour le
second. D’autre part, on suppose que le nombre d’heures de main d’œuvre qu’on peut affecter
globalement à cette production est de 60. Or, chaque unité de produit nécessite 6 heures de main d’œuvre
dans le premier atelier et 5 heures dans le second.
Enfin, la production totale doit permettre de satisfaire au moins une demande de 8. Sachant que
les couts variables unitaires sont de 2 pour le premier atelier et de 3 pour le second, l’entreprise désire
produire à cout minimum.
1) Ecrire le programme linéaire correspondant : définir les variables et donner l’interprétation de
chacune des contraintes et de la fonction objective ?
2) Déterminer graphiquement l’optimum ?
Exercice nº2
Une entreprise fabrique deux types de produits : A et B. Le type A est de meilleure qualité que le
type B. Le bénéfice net est de 2 dinars pour A et de 1,5 dinars pour B.
Le temps de fabrication pour le type A est deux fois le temps de fabrication pour le type B et si
tous les produits « étaient du type B l’entreprise pourrait en fabriquer 1000 par jour ».
L’approvisionnement en matière première est suffisant pour 800 produits par jour (type A ou B).
Enfin on peut produire au maximum 400 de type A et 700 du type B chaque jour.
Quels sont les nombres respectifs de produit des deux types à fabriquer chaque jour de manière à
maximiser le bénéfice total de l’entreprise ? (Utiliser la méthode graphique).
Exercice n°3
Une raffinerie de pétrole traite deux sortes de brut pour donner des produits finis avec les
rendements suivants (en pourcentage). Les quotas de production imposent de fabriquer au plus 825
milliers de m3 d’essence, 750 milliers de m3 de gasoil et 1065 milliers de m3 de fuel. La marge bénéficiaire
laissée par le traitement du brut 1 est de 3 milliers d’euros par millier de m3 et celle du brut 2 est de 4
milliers d’euros par millier de m3.
Brut 1 Brut 2
Essence 25% 35%
Gasoil 30% 30%
Fuel 45% 35%
1. Ecrire le programme linéaire correspondant : définir les variables et donner l’interprétation de
chacune des contraintes et de la fonction objective ?
2. Donner une représentation graphique du domaine réalisable. Interprétez graphiquement.
Exercice N°4
Nous souhaitons établir un horaire quotidien, sachant que chaque jour est divisé en
périodes et en supposant que nous avons pu estimer un nombre minimum d’employés devant être
affecté durant chaque période. Le travail journalier est réparti sur des équipes qui travaillent 8
heures. Plusieurs équipes partagent une même période, mais chaque équipe exige un salaire
particulier. Nous souhaitons savoir combien d’employés doit-on affecter à chaque équipe de
travail de façon à minimiser le total des salaires versés, en respectant le nombre minimum
d’employés pour chaque période. Les données du problème sont données dans la Table 2.
Table 2 : Données du problème d’horaire de personnel
Période Equipe 1 Equipe 2 Equipe 3 Equipe 4 Equipe 5 Minimum
employés
6-8 X 48
8-10 X X 79
10-12 X X 65
12-14 X X X 87
14-16 X X 64
16-18 X X 73
18-20 X X 82
20-22 X 43
22-24 X X 52
0-6 X 15
Salaire par 70 60 75 80 95
employé (Dt)
Formuler le problème sous forme d’un programme linéaire.
