UNIVERSITÉ DE BORDEAUX MAGEFI 1ère année

Semestre 1 2017/2018

Épisode I : Programmation linéaire

E XERCICE 1
Production de vins (G. Finke)
Dans une distillerie américaine on produit trois sortes de vin allemands authentiques : Heidelberg sweet,
Heidelberg regular et Deutschland extra dry. Les produits de base, la main d’œuvre et le profit par gallon sont
indiqués dans le tableau ci-dessous.

raisin - type A raisin - type B sucre main d’œuvre profit

(boisseau) (boisseau) (kg) (heures) (=
C)
Heidelberg sweet 1 1 2 2 10
Heidelberg regular 2 0 1 3 12
Deutschl. extra dry 0 2 0 1 20

La distillerie possède 150 boisseaux de raisin de type A, 150 boisseaux de raisin de type B, 80 kg de sucre et
peut fournir 225 heures de travail.
Quelles quantités faut-il produire de ces trois vins pour obtenir un profit maximum ? Formuler comme pro-
gramme linéaire.

E XERCICE 2
Une entreprise dispose d’un budget publicitaire de 4800 (unités monétaires) pour le lancement de son nouveau
produit. Sa campagne publicitaire utilisera à la fois des spots télévisés et des pages dans la presse quotidienne.
On pense que chaque minute de télévision va atteindre 100 000 nouveaux spectateurs et chaque page dans
un journal va être lue par 80 000 nouveaux lecteurs. Une minute de télévision coûte 800 et une page dans un
journal 600. La direction de l’entreprise souhaite diffuser au moins trois minutes de spot et une page dans un
journal. Son objectif est de maximiser le nombre total de cibles (spectateurs et lecteurs).
1. Modéliser ce problème en programme linéaire.
2. Représenter l’espace des solutions réalisables.
3. Quelle est la combinaison optimale si le budget est augmenté de 4800 à 6000 ?
4. Quelle est la décision optimale s’il n’y a pas de contrainte de temps de télévision ?

E XERCICE 3
Fabrication d’huile d’olives (J.-F. Hêche)
Une entreprise fabrique trois qualités diffé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 raffiné
pour produire 6 dl d’huile B et 3 dl d’huile C. Le coût d’un tel raffinement est de 0.5 = C par litre. De même,
chaque litre d’huile B peut être raffiné pour obtenir 8 dl d’huile C. Le coût de ce raffinement et de 0.3=
C par litre.

Formuler un programme linéaire afin d’aider l’entreprise à déterminer un plan de production mensuel maximi-
sant son profit. Préciser clairement les variables de décision, la fonction objectif et les contraintes.
E XERCICE 4
Compagnie aérienne (traduit de Hillier et Lieberman)
Une compagnie aérienne, en pleine expansion, est en train d’organiser son service clientèle et a besoin de
savoir le nombre d’employés dont elle aura besoin pour les prochaines années. L’équipe RO doit donc étudier
les besoins pour déterminer le nombre minimum de personnel nécessaire afin de satisfaire les demandes des
clients. Basé sur l’ordonnancement des vols, un nouveau planning du personnel est préparé pour les différents
créneaux horaires de la journée. Les informations nécessaires pour la planification sont données dans le tableau
suivant.

Créneaux couverts
Créneaux poste 1 poste 2 poste 3 poste 4 poste 5 Nb min pers
6h-8h x 48
8h-10h x x 79
10h-12h x x 65
12h-14h x x x 87
14h-16h x x 64
16h-18h x x 73
18h-20h x x 82
20h-22h x 43
22h-24h x x 52
24h-6h x 15
Coût/1j,1p 170 =
C 160 =
C 175 =
C 180 =
C 195 =
C

Chaque employé doit travailler 8h par jour et 5 jours par semaine. Les postes autorisés comprennent les créneaux
suivants (montré aussi dans le tableau par des croix) :

Poste 1 : 6h à 14h Poste 2 : 8h à 16h Poste 3 : 12h à 20h

Poste 4 : 16h à 24h Poste 5 : 22h à 6h
Pour chaque poste, le coût associé est donné dans la dernière ligne du tableau (Coût/1j,1p : Coût pour une
journée, pour une personne). La question est de savoir combien d’employés il faut affecter dans chaque poste,
chaque jour, afin de minimiser le coût total du personnel et en respectant le nombre minimum du personnel
nécessaire (dernière colonne dans le tableau).

Modéliser ce problème en programme linéaire. Trouver les contraintes redondantes.

E XERCICE 5
Bergamote (J.-F. Hêche)
Une distillerie produit de l’essence de bergamote pour les parfumeurs de la région. La fabrication d’un litre
d’essence de bergamote génère 0.4 litres de déchets polluants liquides. La distillerie peut soit faire traiter ces
déchets par une station d’épuration avant de les déverser dans la rivière, soit les déverser directement dans la
rivière. La station d’épuration traite au plus 8000 litres de déchets par semaine. Le processus d’épuration n’est
pas parfait : 20% des déchets traités par la station d’épuration et déversés ensuite dans la rivière sont encore
polluants. Pour chaque litre de déchets transitant par la station d’épuration, 5 euros sont facturés à la distillerie.
L’état perçoit une taxe de 15 euros par litre de déchets polluants déversé dans la rivière, qu’on ait tenté de les
traiter ou non. La loi limite à 2800 le nombre de litres de déchets polluants pouvant être déversés dans la rivière
chaque semaine. Le prix de vente d’un litre d’essence de bergamote est de 110 euros et le coût des matières
premières pour cette essence est de 20 euros/litre.

La distillerie souhaite maximiser son profit hebdomadaire. En supposant que la distillerie réussit toujours à
vendre tout ce qu’elle produit, énoncer ce problème sous la forme d’un programme linéaire.
E XERCICE 6
Résolution graphique (J.-F. Hêche)
Soit le programme linéaire

max z = 3x + 2y
s.c. x − y ≥ −2
2x + y ≤ 8
x + y ≤ 5
x ≥ 0
y ≥ 0
1. Dessiner la région admissible R du problème.
2. Résoudre le problème graphiquement.

E XERCICE 7
Une usine fabrique deux produits P1 et P2 . Le marché est porteur et toute la production de la semaine sera
vendue. Chacun des ces produits demande des heures de fabrications sur les machines A, B, et C comme
indiqué dans le tableau

A B C
P1 2h 0h 1h
P2 3h 1h 0h
Disponibilité totale
de chaque machine 18h 3h 5h

Les marges brutes de chaque produit sont respectivement :

— M1 = 1000 euros
— M2 = 2000 euros
1. Donner une formalisation du problème dans l’optique de maximiser le gain obtenu par la vente des
deux produits tout en tenant compte des contraintes de fabrication.
2. Fournir une solution graphique.
3. L’entreprise souhaite investir dans l’achat d’une nouvelle machine.
4. Que lui conseillez-vous ?

E XERCICE 8
Simplexe (J.-F. Hêche)
Résoudre le programme linéaire suivant à l’aide de l’algorithme du simplexe :

max z = 3x1 + 2x2

s.c. 2x1 + x2 ≤ 7
x1 ≤ 3
x1 + x2 ≤ 5
x1 , x2 ≥ 0

Spécifier à chaque itération les variables de base et hors base ainsi que le point extrême visité.

E XERCICE 9
La méthode du simplexe termine avec les équations ci-dessous :

z = 10 − x1 − 2x6
x4 = 3 − 2x1 − x5 + x6
x2 = 9 − x1 − 2x5 − 2x6
x3 = 7 + x1 − 2x5 − x6
Indiquer la solution optimale correspondante.
 Trouver une deuxième solution de base optimale.
Déterminer une autre solution optimale qui n’est pas une solution de base.

E XERCICE 10
Une coopérative viticole produit des vins rouges de Bordeaux à partir de différents cépages : cabernet franc,
cabernet-sauvignon et merlot. Le tableau ci-dessous donne les stocks (en hl) pour chaque cépage, ainsi que les
proportions de chaque cépage (en %) et le profit (en = C/litre) pour chaque assemblage A et B.
Cabernet franc Cabernet-sauvignon Merlot Profit
Bordeaux A 30 20 50 7
Bordeaux B 50 10 40 5
Stocks 5 000 1000 4000
Quelles quantités de vins faut-il produire pour maximiser le profit de la coopérative ?
Modélisez ce problème comme un programme linéaire.
La coopérative doit faire face à un effondrement des prix du vin. Pour aider l’entreprise en difficulté, l’Union
Européenne propose de racheter les stocks de la coopérative. Quel est le prix minimal que doit proposer l’UE
pour chaque cépage afin que les profits de l’entreprise restent constants ?
Modélisez ce problème comme un programme linéaire.
Donner la solution optimale du problème de production de vins que se pose la coopérative. Remarquer
qu’il est ici inutile de faire tourner un Simplexe !
Quelle est la solution optimale au problème de rachat que se pose l’UE ? Comment se simplifie le programme
linéaire par rapport à la question précédente ?

E XERCICE 11
On considère le programme linéaire suivant
max z = 2x1 + 3x2 + 4x3
2x1 + x2 ≤ 3
x3 ≥ 2
3x1 + x2 + x3 ≤ 2
x2 ≤ 1
x1 , x2 , x3 ≥ 0
Écrire son dual.
Écrire le dual du dual. Que remarquez-vous ?

E XERCICE 12
Transport
Voici la formulation d’un petit problème de transport impliquant 3 entrepôts et 2 clients :

min z = 3x11 + 2x12 + 4x21 + x22 + 2x31 +3x32

s.c. x11 + x12 ≤ 60

x21 + x22 ≤ 50
x31 + x32 ≤ 50
x11 + x21 + x31 = 90
x12 + x22 + x32 = 60

x11 , x12 , x21 , x22 , x31 , x32 ≥ 0

Ce problème a été mis sous forme standard en introduisant des variables d’écart s1 , s2 et s3 dans les trois
premières contraintes, puis résolu par un logiciel utilisant la méthode du simplexe. Dans la solution optimale,
les variables en base à l’optimum sont x11 , x12 , x22 , x31 et s1 .
Mettez le problème sous forme standard (comme suggéré ci-dessus).
Utilisez l’information donnée plus haut pour calculer la solution optimale du problème et le coût de transport
correspondant (expliquez les étapes du raisonnement).
Formulez le problème dual.
Resolvez le problème dual.
Montrer que la solution obtenue est bien optimale.
Le gestionnaire du troisième entrepôt s’aperçoit qu’il a commis une erreur en évaluant ses stocks : il possède
en fait 55 unités en stock. En supposant que la base optimale ne soit pas affectée, quel sera l’effet de cette
correction sur le coût de transport optimal ?

E XERCICE 13
L A FABRIQUE DE JOUETS ( D ’ APR ÈS O LIVIER B RIANT )
Un fabriquant produit actuellement quatre types de jouets : A, B, C et D vendus respectivement à 53, 56, 62,
et 82 =C pièce. Ces jouets doivent passer dans deux ateliers, dont les capacités maximales en minutes sont de
1700 et 2600. Les temps de fabrication des quatre types de jouets dans le premier atelier sont respectivement de
2, 3, 1, et 3 minutes, et dans le second atelier de 2, 2, 3, et 4 minutes.
Les quatre type de jouets partagent un composant commun livré par un fournisseur. Les approvisionnements
du fabriquant lui permettent de produire exactement 1000 jouets. Il veut donc savoir quels jouets fabriquer
pour maximiser son bénéfice.
Modélisez ce problème sous forme d’un programme linéaire (P ) (on fera abstraction du fait que les variables
doivent être entières).
Écrire le programme dual du programme linéaire (P ).
Pour résoudre son problème, le fabriquant a utilisé un logiciel commercial basé sur le simplexe. Ce logiciel a
fourni les informations suivantes sur la solution optimale (les xxx.xxxxxx proviennent d’une mauvaise sortie
de l’imprimante) :

Objective = 59500.00000

Rows Section
Number Row Value Slack Value Dual Value
L c1______ 1700.000000 xxx.xxxxxx 3.666667
L c2______ 2600.000000 xxx.xxxxxx 12.666667
E c3______ 1000.000000 xxx.xxxxxx 20.333333

Columns Section
Number Column Value Input Cost Reduced Cost
C X1______ 500.000000 53.000000 xxx.xxxxxx
C X2______ xxx.xxxxxx 56.000000 -0.666667
C X3______ 400.000000 62.000000 xxx.xxxxxx
C X4______ xxx.xxxxxx 82.000000 xxx.xxxxxx
Expliquer la signification des informations fournies, et donner, si possible, les valeurs qui devraient se
trouver à la place des xxx.xxxxxx.
Donner une interprétation économique des valeurs optimales des variables duales.
Très déçu de ne pas produire le jouet B qui lui tenait à coeur, le fabriquant aimerait savoir à quel prix
minimum il doit le vendre pour être rentable et ainsi l’inclure dans son plan de production optimal.
Pouvez-vous lui répondre au vu des résultats de l’optimisation ?
Jusqu’à quelle valeur peut-il augmenter ou diminuer le prix du jouet A sans que la solution optimale ne
change ?
En regardant les informations données par son logiciel, il a déterminé le prix maximum qu’il peut payer
chaque minute supplémentaire dans le premier atelier sans diminuer son bénéfice.
Quel est ce prix maximum ? Jusqu’à combien de minutes supplémentaires ce prix reste-t-il valable ?
Il souhaite créer un nouveau type de jouet, E, demandant 9 minutes dans le premier atelier et 10 minutes
dans le second.
A quel prix minimum a-t-il intérêt à le vendre s’il veut les incorporer parmi les 1000 jouets produits ?