Recherche Opérationnelle
Série No1
Formulation des problèmes sous formes de
Programmes linéaires
Exercice n° 1.
Une entreprise a arrêté la production d'un certain produit non profitable. Ceci a crée un excès
considérable de capacité de production. Les responsables envisagent de considérer cet excès
de capacité aux produits suivants: 1, 2 et 3. Les capacités disponibles sur les machines à
utiliser sont données dans le tableau suivant :
Type de machine Temps disponible (heures machine/semaine)
Machine de coupe
Tour
Fraiseuse
500
350
150
Le nombre d'heures machine nécessaire pour la fabrication d'une unité de chaque type de
produit est donné dans le tableau suivant :
Type de machine Produit 1 Produit 2 Produit 3
9
Machine de coupe
5
Tour
3
Fraiseuse
5
0
2
3
4
0
Le service commercial indique que les possibilités de vente sont presque non limitées pour les
produits 1 et 2, et que le volume des ventes du produit 3 est de 20 unités par semaine. Le
profit unitaire de chacun des produits 1, 2, et 3 est de 30D, 12D, et 15D, respectivement.
Advertisement
Formuler un Programme Linéaire pour déterminer les quantités à produire de chaque type de
produit afin de maximiser le profit de l'entreprise.
Exercice n° 2.
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.
Produit brut Orge Arachide Sésame
% protéines
% graisses
Coût/tonne
12
2
25
52
2
41
42
10
39
1
Recherche Opérationnelle
1. 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.
Exercice n° 3.
La compagnie aérienne CONTINENT AIRLINES prévoit de rajouter des vols entre les
différents aéroports qu’elle dessert. Cette nouvelle charge implique le recrutement d’agents de
soutien au sol permettant de représenter la compagnie et d’orienter ses clients vers leurs vols
de connexion s’ils se trouvent dans une zone de transit.
La compagnie souhaite garantir un bon taux de service à ses clients avec un coût minimal.
Selon les nouveaux horaires des vols planifiés, CONTINENT AIRLINES a identifié le
nombre minimal d’agents nécessaire pour chaque plage horaire de la journée (tableau 1).
Advertisement
La réglementation impose qu’un agent travaille 8h par jour. La compagnie a choisi de
fonctionner en 5 équipes par jour définies comme suit :
‐ Équipe 1 : de 6h à 14h
‐ Équipe 2 : de 8h à 16h
‐ Équipe 3 : de midi à 20h
‐ Équipe 4 : de 16h à minuit
‐ Équipe 5 : de 22h à 6h
Ainsi dans le tableau 1, nous avons indiqué la couverture des plages horaires par les
différentes équipes de travail. Comme certaines équipes sont moins désirables que d’autres la
rémunération d’un agent diffère d’une équipe à l’autre. Ainsi, pour chaque équipe, le coût
journalier d’un agent est représenté par la dernière ligne du tableau.
Plage horaire
6h-8h
8h-10h
10h-midi
Midi-14h
14h-16h
16h-18h
18h-20h
20h-22h
22h-minuit
Minuit-6h
Coût journalier par agent
4
5
2
Équipe
3
1
Période de temps couverte par équipe Nombre
Advertisement
minimum
d’agents
48
79
65
87
64
73
82
43
52
15
170
160
175
180
195
Tableau 1 : les données relatives à la planification du personnel de CONTINENT AIRLINES
2
Recherche Opérationnelle
Advertisement
Écrire un programme linéaire permettant de déterminer, pour chaque jour, le nombre d’agents
à employer par équipe, afin de minimiser le coût total du personnel par jour tout en
garantissant le niveau de service requis.
Exercice n° 4.
Un chocolatier-confiseur reçoit une commande de 3000 assortiments de chocolat. Pour les
confectionner, il a convenu d’y placer 3 sortes de chocolats, dénotés respectivement chocolats
1, 2 et 3 ; les chocolats coûtent respectivement au kilo ; 4 D ; 1,45 D et 2,40 D.
Chaque assortiment doit peser un kilo et se vendra 8 D. Les chocolats de type 1 doivent
représenter entre 10 % et 20 % du poids d’un assortiment ; les chocolats 1 et 2 présents dans
un assortiment ne doivent pas peser plus de 800 gr. Au moins la moitié du poids d’un
assortiment doit provenir des chocolats 1 et 3.
Comment le chocolatier-confiseur doit-il répartir ses achats entre les 3 sortes de chocolats
pour maximiser les revenus nets qu’il tirera de la vente des assortiments ?
Exercice n° 5.
A) L’usine A "produit deux produits périssables" p et q. Elle les vend à 42 dinars pour
chaque pièce de type p et 48 dinars pour chaque pièce de type q.
A la fin de la journée, le transporteur réclame à l’usine 2 D/kg transporté moyennant une
garantie de 4000 dinars.
Les produits p et q s’élabore à partir de deux matériaux N et M selon la recette suivante :
Poids unitaire M N
4 3
P
2 1
q
7
3
Il s’agit d’avoir le revenu net le plus élevé. On suppose que l’usine dispose de 3000 kg de M
et de 2000 kg de N, on peut traiter 5600 kg durant la journée.
Comment peut-on maximiser le profit ?
B) Le grossiste exige la livraison d’au moins de 2450kg de p et 1800kg de q. Il importe une
pénalité de 5d/kg manquant de p et 1,5d/kg manquant de q.
3