TD1 2024-2025

Programmation linéaire ING-4-S-GLSI A/B

Exercice 1
Un atelier fabrique des tables et des bureaux. Chaque table nécessite 2,5 h pour
l’assemblage, 3 h pour le polissage et 1 h pour la mise en caisse. Chaque bureau exige 1 h pour l’assemblage,
3 h pour le polissage et 2 h pour la mise en caisse. L’entreprise ne peut disposer, chaque semaine, de plus de
10 h pour l’assemblage, de 15 h pour le polissage et de 8 h pour la mise en caisse. Sa marge de profit est de
30 DT par table et de 40 DT par bureau.
Modéliser ce problème sous la forme d’un programme linéaire.

Exercice 2
On doit organiser un pont aérien pour transporter 1600 personnes et 90 tonnes de bagages. Les
avions disponibles sont de deux types: 12 du type A et 9 du type B. Le type A peut transporter, à pleine
charge, 200 personnes et 6 tonnes de bagages. Le type B, 100 personnes et 6 tonnes de bagages. La location
d’un avion du type A coûte 800.000 $; la location d’un avion du type B coûte 200.000 $.
Trouver une formulation au problème, permettant de minimiser le coût de location.

Exercice 3
Un maraîcher, vendant des citrons et des oranges, veut les grouper par lots de vente. Le premier lot
contient 5 citrons et 1 orange, et se vend à 4 DT. Le deuxième lot contient 1 citron et 10 oranges, et se vend
à 6 DT. Il dispose au total de 60 citrons et 110 oranges.
Quelle est la répartition la plus avantageuse pour lui, entre les deux types de lots ?

Exercice 4
Une compagnie d’alimentation dispose de 1000 kilos de café africain, 2000 kilos de café brésilien et
500 kilos de café colombien. Elle ensache deux sortes de café. La première sorte, « Doux réveil », est un
mélange à parties égales de café africain et brésilien et se vend à 6 $ le kilo. La deuxième sorte, « Arôme
velouté », est un mélange de trois parties de café brésilien pour une partie de café colombien et se vend à 8
$ le kilo.
Le problème consiste à déterminer quelle quantité de café de chaque sorte la compagnie devrait ensacher de
façon à maximiser son profit.
Formuler ce problème à l’aide d’un modèle de programmation linéaire.

Exercice 5
Une entreprise chimique livre deux types de mélanges P et T obtenus à partir des trois éléments A, B et C
selon les pourcentages et prix de production donnés par le tableau ci-dessous.
Modéliser ce problème pour satisfaire les besoins en produits A, B et C donnés dans le tableau suivant à un
prix minimum.

P T Besoin (Kg)
A 20% 40% 7
B 30% 50% 2
C 20% 10% 4
Prix par Kg 10 8

1
Exercice 6
Un agriculteur souhaite mélanger des engrais de façon à obtenir au minimum 15 unités de potasse,
20 unités de nitrates et 24 unités de phosphates. Il achète deux types d’engrais. Le type 1 procure 3 unités de
potasse, 1 unité de nitrates et 3 unités de phosphates. Il coûte 120 DT. Le type 2 procure 1 unité de potasse,
5 unités de nitrates et 2 unités de phosphates. Il coûte 60 DT.
Exprimer à l’aide d’un programme linéaire la combinaison d’engrais qui remplit les conditions exigées au
moindre coût.

Exercice 7
Une entreprise veut déménager son matériel composé de 450 machines de trois types : M1, M2, M3.
Elle décide de louer des camions. La société de location dispose de trois sortes de véhicule : V1, V2, V3 dont
les tarifs sont respectivement de 500, 800 et 1200 Dinars pour un voyage. Les camions V1 peuvent chacun
transporter une machine M1, 4 machines M2 et 10 machines M3. Pour des raisons techniques la place d’une
machine d’un type donné ne peut être utilisée pour une machine d’un autre type. Chaque camion V2 peut
transporter 2 machines M1, 6 machines M2 et 20 machines M3. Alors que le véhicule V3 à pour capacité
maximum : 4 machines M1, 20 machines M2 et 24 machines M3. On veut transporter en un seul convoi au
moins 30 machines M1, 120 machines M2 et 300 machines M3. L’entreprise veut déterminer le nombre de
véhicules à louer pour minimiser le coût total de transport.

Donner le modèle linéaire de ce problème sans le résoudre.

Exercice 8

Une entreprise possède deux usines et trois clients. La production des usines est respectivement de
350 et 450 unités. L’entreprise doit acheminer vers ces clients respectivement 200, 300 et 50 unités. Les coûts
de transport de chaque usine i (i = 1, 2) vers chaque client j (j = 1, 2, 3) sont donnés dans le tableau ci-
dessous :
Usine \ Client C1 C2 C3
U1 25 17 16
U2 24 18 14
Par exemple, le coût c12 de transport de l’usine 1 vers le client 2 est égal à 17, soit c12 = 17. L’objectif de
l’entreprise est de minimiser le coût de transport des produits acheminés des
usines vers les clients.
Modéliser ce problème de transport sous la forme d’un programme linéaire. On notera par xij le nombre
d’unités transportées de l’usine i vers le client j.

Exercice 9
Un fermier élève des poulets, des canards et des dindons. Il veut avoir 500 volatiles, mais pas plus de 300
canards à la fois. Supposons que l’élevage d’un poulet revienne à 15 DT, celui d’un canard à 10 DT et celui
d’un dindon à 40 DT.
Admettons que le fermier puisse vendre ses poulets à 30 DT/pièce, les canards à 20 DT/pièce et les dindons à
W DT. Il voudrait savoir quelles volailles il faut élever pour réaliser le profit maximum.
1. Quelles contraintes pour ce problème.
2. Donner en fonction de W l’expression du profit.
3. Transformer le problème linéaire à un problème à deux variables et donner la politique d’élevage
optimale du fermier dans le cas : a) W=40 DT b) W=50 DT.