U.S.T.O. M.B.
3ème Année Ingénieur d’état en Informatique - IA
Département Informatique Programmation Linéaire et Informatique
FICHE TD N°2
Exercice 1 :
Une entreprise fabrique deux produits P1 et P2. La fabrication de ces produits nécessite du temps de travail,
du temps machine et de la matière première. Les coefficients techniques de production ainsi que les bénéfices
par unité de produit sont fournis dans le tableau suivant :
P1 P2
Temps machine 1.5 h 0.8 h
Heures de travail 0.75 h 0.5 h
Quantité de Matières Premières 2kg 1kg
Bénéfice 1500 DA 800 DA
Chaque semaine 0.4 Tonnes de matière première au plus peuvent être achetées. L’entreprise emploie 4
personnes qui travaillent chacune 38 h par semaine. Chaque semaine la disponibilité en temps machine est de
320 h. L’entreprise désire connaître le plan de fabrication hebdomadaire qui maximiserait son bénéfice,
sachant que la demande hebdomadaire du produit P1 est au moins 50 unités. Donner le modèle de PL
correspondant.
Exercice 2 :
Une entreprise peut fabriquer trois types de produits : Le produit A à la cadence de 35 unités par heure,
le produit B à la cadence de 45 unités par heure, le produit C à la cadence de 20 unités par heure.
Cette fabrication utilise une machine unique disponible 200 heures par mois. Le bénéfice unitaire pour le
produit A est de 600 DA, pour B de 400 DA et de 800 DA pour C. Ces produits sont vendus en totalité à un
grossiste, on a observé qu’on ne pouvait écouler par mois plus de 4900 unités de chaque produit.
D’autre part chaque unité doit être vérifiée avant sa commercialisation. Une équipe de trois techniciens est
chargée de cette mission ; chaque technicien travaille 170 heures par mois. La vérification d’une unité de type
A prend 4 minutes, de type B 3 minutes et de type C 2 minutes.
Donner le modèle de PL permettant de décrire le plan de fabrication mensuel qui maximiserait les bénéfices.
Exercice 3 :
On désire déterminer la composition, à cout minimal, d’un aliment pour bétail qui est obtenu en mélangeant
au plus trois produits bruts, orge, arachide, sésame. L’aliment ainsi conditionné devra comporter au moins
22% de protéines et 3.6% de graisses. On a indiqué dans le tableau suivant les pourcentages de protéines et de
graisses contenus dans chacun des produits ainsi que leur coût :
Orge Arachide Sésame
% protéines 12% 52% 42%
% graisses 2% 2% 10%
Coût 25 41 39
Donner le modèle PL correspondant.
Exercice 4 :
Une scierie souhaite s’approvisionner en bois de différentes essences (chêne, hêtre et sapin). Compte tenu de
la demande en bois scié, elle souhaite acquérir au moins 200m3 de chêne, au moins 160m3 de hêtre et au
moins 300m3 de sapin. Les prix au m3 sur le marché traditionnel sont de 14KDA pour le chêne, 9KDA pour le
hêtre et 7KDA pour le sapin (1KDA=1000DA).
Mais la société peut aussi profiter des offres de certains exploitants forestiers qui proposent des lots à
moindre coût du bois de qualité équivalente. Trois offres ont été sélectionnées :
Offre A : Lots de 15m3 de chêne, 15m3 de hêtre et 20m3 de sapin. Prix du lot : 384 KDA.
Offre B : Lots de 16m3 de chêne, 8m3 de hêtre et 24m3 de sapin. Prix du lot : 396 KDA.
Offre C : Lots de 9m3 de chêne, 24m3 de hêtre et 12m3 de sapin. Prix du lot : 288 KDA.
1) Déterminer le prix de la quantité de bois que souhaite acquérir cette société si elle se fournit sur le
marché traditionnel et achète les quantités minimales désirées.
2) La société désire connaître le plan d’approvisionnement optimal à partir des 3 offres A, B et C
proposées par les exploitants. Donner le modèle de PL correspondant.
Exercice 5 :
Une importante entreprise d’appareils électroménagers dispose de deux usines U1 et U2 localisées à différents
endroits au pays. La production annuelle de U1 est 15000 unités alors que celle de U2 est 12000 unités. Ces
usines alimentent trois points de vente dont la demande annuelle est la suivante :
Points de vente Demande annuelle
A 10 000 unités
B 8 000 unités
C 9 000 unités
Les coûts unitaires de transport de chaque usine à chaque point de vente sont indiqués comme suit :
A B C
U1 5 6 6
U2 11 9 4
L’entreprise désire connaître la quantité annuelle d’appareils électroménagers à transporter des usines U1 et
U2 vers les points de vente A,B,C.
1. Formuler le modèle de PL qui permettrait d’obtenir un plan de transport à un coût minimum.
2. Pensez-vous que l’entreprise peut satisfaire la demande de ses points de ventes ? Justifier.
Solution Fiche TD N°2
EXERCICES DE MODELISATION
DEMARCHE GENERALE A SUIVRE :
1) Variables de décision : - Quelles sont les inconnues du problème ?
2) Contraintes : - Quelles sont les restrictions associées au processus en question ?
- Existe-t-il d’autres restrictions sur les variables ?
3) Fonction objectif : - Quelle type d’optimisation (max ou min) à envisager ?
- Quelle est la valeur des coefficients économiques ?
Remarque : Faire attention à la cohérence des unités
Exercice 1 :
1) Variables de décision
L’entreprise désire connaître le plan de fabrication hebdomadaire : Nombre de produits P1, P2 à fabriquer par
semaine. On définit xi : Nombre de produits de type Pi à fabriquer par semaine (i = 1,2).
2) Contraintes
- Restrictions associées au processus de fabrication
Pour cela, il faut identifier les ressources de l’entreprise qui sont :
- Le Temps Machine,
- Les heures de Travail des employés,
- La matière première.
• Temps Machine
Le temps machine disponible est de 320 heures
1.5 x1 + 0.8x2 ≤ 320
h unité h
Vérification d’unité : *
unité semaine semaine
• Heures de Travail
L’Entreprise dispose de 4 personnes qui travaillent 38h chacune par semaine
Soit 4 x 38 = 152 Heures de Travail par semaine.
0.75 x1 + 0.5x2 ≤ 152
h unité h
Vérification d’unité : *
unité semaine semaine
• Matières Premières
Chaque semaine 0.4 Tonnes de matière première au plus peuvent être achetées,
Soit 400 kg/semaine
2x1 + x2 ≤ 400
kg unité kg
Vérification d’unité : *
unité semaine semaine
- D’autres restrictions sur les variables ?
• La demande hebdomadaire du produit P1 est au moins 50 unités.
x1 ≥ 50
• Contraintes de non négativité
x1 ≥ 0, x2 ≥ 0
3) Fonction objectif
- Quelle type d’optimisation? Max (maximiser le bénéfice)
Bénéfice hebdomadaire = Z = 1500x1 + 800x2
Ainsi le PL est formulé comme suit :
Max Z = 1500x1 + 800x2
Avec 1.5 x1 + 0.8x2 ≤ 320
0.75 x1 + 0.5x2 ≤ 152
2x1 + x2 ≤ 400
x1 ≥ 50
x1 ≥ 0, x2 ≥ 0
Exercice 2 :
x1 : Nombre d’unités à fabriquer du produit A par mois
x2 : Nombre d’unités à fabriquer du produit B par mois
x3 : Nombre d’unités à fabriquer du produit C par mois
Max Z = 600x1 + 400x2 + 800x3
Avec 4 x1 + 3x2 + 2x3 ≤ 170 x 3 x 60 = 30600
(1/35) x1 + (1/45) x2 + (1/20) x3 ≤ 200
x1 ≤ 4900
x2 ≤ 4900
x3 ≤ 4900
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Exercice 3 :
x1 : Quantité d’orge
x2 : Quantité d’arachide
x3 : Quantité de sésame
Min Z = 25x1 + 41x2 + 39x3
Avec 12 x1 + 52x2 + 42x3 22
2 x1 + 2 x2 + 10 x3 3.6
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Exercice 4 :
1. Marché Traditionnel
Cout = 14 x 200 + 9 x 160 + 7 x 300 = 6340 KDA
2. Modèle PL à partir des offres A,B,C
x1 : Nombre de lots de type A
x2 : Nombre de lots de type B
x3 : Nombre de lots de type C
Min Z = 384x1 + 396x2 + 288x3
Avec 15 x1 + 16x2 + 9x3 200
15 x1 + 8 x2 + 24 x3 160
20 x1 + 24 x2 + 12 x3 300
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Exercice 5 :
Problème de Transport, utiliser de préférence des variables à double indice xij
1. Modèle PL
xij : Quantité à transporter de l’usine i au point de vente j par année.
Min Z = 5x11 + 6x12 + 6x13 + 11x21 + 9x22 + 4x23
Avec x11 + x12 + x13 ≤ 15000
x21 + x22 + x23 ≤ 12000
x11 + x21 10000
x12 + x22 8000
x13 + x23 9000
xij ≥ 0 i = 1,2 j = 1,..3
2. Pensez-vous que l’entreprise peut satisfaire la demande de ses points de ventes ? Justifier.
Oui puisqu’il suffit que la production totale des usines soit supérieure ou égale à la demande des points de
ventes. Dans notre cas il y a égalité.
Total Production = 15000 + 12000 = 27000
Total demande = 10000 + 8000 + 9000 = 27000