Optimisation et Recherche opérationelle Septembre 2017
Feuille exercices 1 : Modélisation, résolution graphique et dualité
[email protected],
[email protected]Exercice 1 : Moutarde
Une entreprise produit trois modèles de moutarde : Douce, Forte ou Extra Forte. Pour chaque type
de pot de moutarde de 3.5kg chacun, on renseigne dans le tableau ci-dessous :
la quantité nécessaire en huile, vinaigre et graines de moutarde;
la main d'÷uvre;
le pro t.
Type Huile (L) Vinaigre (L) Graines (kg) Main d÷uvre (h) Pro t (=C)
Douce 1.5 0.1 0.1 1 1
Forte 1.2 0.14 0.09 0.8 1.2
Extra Forte 1.1 0.12 0.12 1.2 2
L'entreprise possède 100L d'huile, 11L de vinaigre, 10kg de Graines de moutarde et peut fournir
90 heures de travail.
Question 1 Formuler sous forme de problème linéaire le problème consistant à trouver les quantités
qu'il faut produire de ces trois types de moutarde a n d'obtenir un pro t maximum.
Exercice 2 : Usine
Une usine fabrique deux produits P et P . Le marché est porteur et toute la production de la
semaine sera vendue. Chacun de ces produits demande des heures de fabrication sur les machines
1 2
A, B et C comme indiqué dans le tableau ci-dessous. Ce tableau indique également la disponibilité
totale de chaque machine par semaine.
Machine A Machine B Machine C
Produit P 2h 0h 1h
Produit P 3h 1h 0h
1
Disponibilité 18h 3h 5h
2
On cherche à maximiser les pro ts de l'entreprise, sachant que la vente du produit P rapporte (en
terme de marge) 1000 =C à l'entreprise, et la vente du produit P rapporte 2000 =C.
1
2
Question 1 Modélisez ce problème sous forme d'un PL. Pensez à bien décrire à quoi correspondent
vos variables (et les unités choisies).
Question 2 [A faire chez vous pour vous entrainer] Résolvez graphiquement votre PL (on supposera les
variables réelles - la fabrication d'un même produit pouvant être réalisée sur deux semaines consécutives).
Donnez les valeurs des variables et de la fonction d'optimisation lorsque l'optimum est atteint.
Exercice 3 : Chocolaterie
Une chocolaterie peut produire du chocolat noir, du chocolat au lait ou du chocolat blanc à partir
de cacao et de lait. L'entreprise dispose de 500 kilos de cacao et de 1000 litres de lait. Les quantités
d'ingrédients nécessaires et le prix de vente par kilo de chocolat produit sont donnés dans le tableau
suivant pour chaque type :
1
Cacao (g) Lait (l) Prix de vente (=C)
Un kilo de chocolat noir 800 0 8
Un kilo de chocolat au lait 400 0.4 5
Un kilo de chocolat blanc 200 0.6 3
On cherche à maximiser les pro ts de l'entreprise.
Question 1 Modélisez ce problème sous forme d'un programme linéaire.
Un kilo de chocolat au lait peut également être produit à partir de 500 grammes de chocolat noir
et de 0,3 litre de lait. Le coût d'une telle transformation est de 0.5 euro par kilo de chocolat noir
transformé.
Question 2 En ajoutant cette nouvelle possibilité, modélisez ce problème sous forme d'un programme
linéaire.
Exercice 4 : Fabrication d'huile d'olives (J.-F. Hêche)
Une entreprise fabrique trois qualités diérentes d'huile d'olive. Les quantités maximales pouvant
être vendues chaque mois ainsi que les prix de vente sont donnés dans la table suivante :
Produit Ventes maximales Prix de vente
(en litres) (en =C/litre)
Huile A 3000 4
Huile B 3000 6
Huile C 2000 10
L'entreprise paie 1000=C pour une tonne d'olives. Chaque tonne d'olives fournit soit 300 litres
d'huile A soit 200 litres d'huile B (les coûts de ces transformations ne sont pas modélisés). Chaque
litre d'huile A peut être ra né pour produire 6 dl d'huile B et 3 dl d'huile C. Le coût d'un tel
ra nement est de 0.5 =C par litre. De même, chaque litre d'huile B peut être ra né pour obtenir
8 dl d'huile C. Le coût de ce ra nement et de 0.3=C par litre.
Question 1 Formuler un programme linéaire a n d'aider l'entreprise à déterminer un plan de production
mensuel maximisant son pro t. Préciser clairement les variables de décision, la fonction objectif et les
contraintes.
Exercice 5 : Soit le programme linéaire
max z = 3x + 2y
s.c. x − y ≥ −2
2x + y ≤ 8
x + y ≤ 5
x , y ≥ 0
Question 1 Dessiner la région admissible du problème.
Question 2 Déterminer graphiquement la solution optimale.
Exercice 6 : Une famille utilise 6 produits alimentaires comme source de vitamine A et C. Le
tableau ci-dessous indique pour chacun des produits le nombre d'unités de vitamines par kg, ainsi
que leur prix. On sait que la famille a besoin d'au moins 9 unités de vitamine A, et 19 de vitamine
C.
2
produits (unités/kg) demande
1 2 3 4 5 6 (unités)
Vitamine A 1 0 2 2 1 2 9
Vitamine C 0 1 3 1 3 2 19
Prix par kg 35 30 60 50 27 22
Quels produits la famille doit-elle acheter pour minimiser le coût total tout en assurant ses besoins
en vitamine?
Question 1 Écrire le programme linéaire associé à ce problème.
Question 2 Écrire le dual de ce problème.
Question 3 Proposer une interprétation du dual.
Exercice 7 : Vente de téléphones portables (W. Bienia)
Avant l'arrivage massif de nouveaux modèles, un vendeur de téléphones portables veut écouler
rapidement son stock composé de 8 appareils, 4 kits main libre et 19 cartes avec des communications
prépayées.
Après une étude de marché, il sait que, dans cette période de soldes, il peut proposer aux clients
un téléphone avec deux cartes et que cette ore va lui rapporter un pro t net de 7=C.
Il peut aussi préparer à l'avance un coret composé d'un téléphone, d'un kit mains libres et de 3
cartes avec des communications prépayées, ce qui va lui rapporter un pro t net de 9=C.
Il est assuré de pouvoir vendre n'importe quelle quantité de ses ores dans la limite des stocks
disponibles et il souhaite maximiser son pro t.
Question 1 Modéliser ce problème comme un programme linéaire.
Un représentant d'une grande surface souhaite racheter le stock. Quel prix doit-il proposer au
revendeur pour minimiser ses coûts?
Question 2 Modéliser le problème du représentant comme un programme linéaire.
Exercice 8 : Soit le programme linéaire suivant.
min 30x − y + 3z + 5t
s.c. 4x − y + z ≥ 5
5x − y − z + t ≥ 3
x, y, z, t ≥ 0
Question 1 Expliquer pourquoi le problème dual est plus simple à résoudre.
Question 2 Ecrire le problème dual.
Question 3 Résoudre graphiquement le problème dual. Donner la solution optimale et la valeur de
l'objectif à l'optimal.
Question 4 Comment faire pour retrouver la solution optimale du primal ?
