ESPRIT Programmation linéaire UP-MATH/UE-RO
2018/2019 Série N:1 Si… Sami
Exercice 1
Un conseiller …nancier doit choisir pour ses clients (club d’investissement) un certain nombre
d’actions dans lesquelles investir. Ses clients souhaitent investir 100 000 DT dans 6 actions
di¤érentes. Le conseiller leur indique le retour d’investissement (taux de retour) qu’ils peu-
vent espérer pour une période de six mois. Le tableau suivant donne pour chaque action son
nom, sa catégorie (T : technologique, N : non technologique) et le taux de retour espéré.
N Nom Catégorie Retour
1 Dash Associates (UK) T 5.3 %
2 Ilog France (F) T 6.2 %
3 France Telecom (F) T 5.1 %
4 General Motors (USA) N 4.9 %
5 Elf (F) N 6.5 %
6 BNP (F) N 3.4 %
Les clients …xent certaines contraintes au conseiller. Ils veulent investir au moins 5000
DT et au plus 40 000 DT dans chaque action. Le club d’investissement désire investir au
minimum la moitié de leur capital dans des actions françaises et au plus 30 % dans des
valeurs technologiques.
Donner le programme linéaire qui permet de répartir le capital investi de façon optimale.
Exercice 2
Une ra¢nerie fabrique deux qualités d’essence (A et B) en mélangeant dans certaines pro-
portions deux produits semi-…nis (P1 et P2). Les indices d’octane et les quantités disponibles
par jour pour ces deux produits sont indiqués dans le tableau suivant :
Indice d’octane Nombre de barils par jours
P1 71 3900
P2 99 5000
L’indice d’octane de l’essence A doit être d’au moins 96 et celui de l’essence B d’au moins
85. La ra¢nerie vend toute sa production de A et B aux prix respectifs de 3,75 $ et 2,75
$ par baril. Les excédents éventuels de P1 sont revendus au prix de 1,25 $ par baril à une
fabrique de goudron et ceux de P2 sont revendus à un terrain d’aviation au prix de 2,25 $
par baril.
On notera x1 et x2 (resp. x1 et x2 ) le nombre de barils de P1 et de P2 utilisés pour
fabriquer A (resp. B).
1- Calculer, en fonction de x1 et x2 , l’indice d’octane de A.
2- Ecrire le programme correspondant à l’optimisation du pro…t de la ra¢nerie.
Exercice 3
Une usine de pièces électroniques produit trois types de produits P1, P2 et P3. Les prix
unitaires et les contraintes de production sont les suivantes :
Produit Prix unitaire (TND)
P1 25
P2 75
P3 110
1
Contrainte 1 : La production d’une unité du produit P1 nécessite deux heures de main
d’œuvre.
Contrainte 2 : La production d’une unité du produit P2 nécessite trois heures de main
d’œuvre en plus de deux unités du produit P1
Contrainte 3 : La production d’une unité du produit P3 nécessite quatre heures de main
d’œuvre en plus d’une unité du produit P2
Contrainte 4 : L’usine dispose de 40 heures de main d’œuvre par semaine.
Donner le programme linéaire qui permet à l’usine de déterminer le nombre optimal de
produits (P1, P2, P3) à produire a…n de maximiser son chi¤re d’a¤aire.
Exercice 4 :
Un gestionnaire de fonds en bourse veut investir 1 million de dollars dans une combinaison
d’obligations, actions, dépôts à terme, épargne, immobilier et or. Les valeurs estimées des
facteurs de risque et les augmentations prévues des valeurs de l’investissement sont présentées
dans le tableau suivant :
Type d’investissement Taux de risque (%) Taux de croissance (%)
Obligation 3 0
Action 10 7
Dépôt à terme 2 0
Immobilier 5 7
Or 20 11
Par exemple, la valeur de l’immobilier devrait augmenter de 7% par an. D’autre part, les
actions sont prévues d’augmenter de 7%.
L’objectif est de déterminer la meilleure stratégie d’investissement a…n de maximiser le mon-
tant généré tout en respectant les restrictions suivantes :
² Au moins 30% du montant total investi doit correspondre à des obligations, pas plus
de 10% à des actions et au moins 10% à des dépôts à terme.
² Jusqu’à 50% de l’argent total investi dans l’immobilier peut être emprunté sous forme
d’hypothèque à un taux d’intérêt de 6%. Le montant emprunté ne dépasse pas 150 000
$.
² Le taux de risque moyen de l’investissement est au maximum égal à 4.5%.
² Le montant d’argent investi en « Or » ne peut pas dépasser 100 000 $ ou encore 8%
du Montant total disponible.
Exercice 5 :
Un …nancier dispose d’un capital de 20 milles dinars, qu’il peut placer dans deux types
d’investissements A et B. Le type A est disponible tous les ans et rapporte un intêret de 6%
par an. Le type B nécessite un placement de deux ans et rapporte un intêret de 10%.
Déterminer un plan d’invesstisement pour le …nancier sachant qu’il désire récupérer tout son
capital après trois années tout en le maximisant.
Exercice 6 :
Une compagnie produit deux types d’engrais M1 et M2, qui doivent faire l’objet d’un traite-
ment dans les trois ateliers de la compagnie. Le tableau suivant a¢che les données relatives
au problème de production du mois prochain.
2
Durée du traitement (en heures / tonne)
Atelier Engrais M1 Engrais M2 Temps disp (en heures)
A1 4 6 250
A2 2 5 180
A3 3 3 180
Pro…t (mille DT / tonne) 4 6.5
1- Formuler le programme linéaire (P) qui permet de maximiser le pro…t de la compagnie,
et écrire les deux premiers tableaux simplexe associés au problème (P).
3- À une itération donnée, on obtient le tableau suivant ( : la quantité d’engrais Mi) :
1 2 1 2 3
? 1 ? 0 0.625 -0.75 ? 21.25
? ? ? 1 -0.250 0.5 ? 27.50
? 3 ? 0 -1.125 0.75 ? 33.75
? ? ? ? ? Z=?
a- Compléter ce tableau et dire s’il correspond à la solution optimale.
b- Indiquer les ateliers qui sont utilisés à pleine capacité.
Exercice 7 :
Résoudre le programme linéaire suivant, en utilisant la méthode du simplex :
= 21 + 2
8:
>
> 1 · 3
<
2 · 6
>
> ¡1 + 2 ¸ 2
:
¸ 0
Exercice 8 :
On considère le programme linéaire (P) suivant:
max = 21 + 2
8
>
> 1 · 5
<
31 + 2 · 25
>
> 1 + 52 ¸ 5
:
1 ¸ 0 2 ¸ 0
1- Résoudre graphiquement le programme linéaire (P).
2- En utilisant l’algorithme du simplexe, déterminer une SBR initiale SBR0 du problème
(P).
3- D’après le graphique, quel est le point extrême qui correspond à SBR0
4- Dresser le tableau du Simplexe qui correspond à SBR0
5- Quelle est la variable entrante qui permet d’obtenir la solution optimale en une seule
itération.
