R EECCHHER RCHHE E … · Sciences.ch Recherche opérationnelle (solveurs) Serveur d'exercices 3/78 et nous le lançons. Il vient alors comme résultat au problème:

EXERCICES DE

RREECCHHEERRCCHHEE OOPPÉÉRRAATTIIOONNNNEELLLLEE ((SSOOLLVVEEUURRSS))

(version 2.6 Révision 8 du 06.09.2012)

Attention! Nous utilisons majoritairement MS Office Excel pour la résolution des exercices dans le présent

document car c'est le plus courant dans les entreprises.

Sciences.ch Recherche opérationnelle (solveurs)

Serveur d'exercices 2/78

EXERCICE 1.

Niveau: Gymnase (Lycée)

Auteur: Vincent Isoz ([email protected]

Mots-clés: recherche opérationnelle, choix

Énoncé:

Un chef de projet connaissant le prix auquel il peut facturer au maximum ses consultants

(concurrence oblige… 250.-/h.) et le prix qu'ils coûtent en interne (ressource la moins chère

160.-/h.) souhaite atteindre une marge commerciale de 15'000.- pour son futur projet client

nécessitant 600 heures de travail.

Jusqu'où le chef de projet peut-il baisser le montant du tarif horaire vendu au client tout en

cherchant la meilleure ressource interne possible (celle ayant le coût interne le plus élevé – le

niveau le plus expert - avec les contraintes définies), pour avoir une marge bénéficiaire de

15'000.- ?

Remarque: Evidemment il s'agit d'une simple équation du premier degré que l'on peut

résoudre à la main ou avec l'outil Cible de MS Excel mais l'idée ici est juste de se familiariser

avec le solveur.

Solution:

Dans MS Excel, nous construisons le tableau suivant:

avec dans B4 la relation suivante:

=B1*(B2-B3)

Nous paramétrons le solveur ainsi:



et nous le lançons. Il vient alors comme résultat au problème:

Nous pouvons donc facturer au minimum 217.50.-/h. au client et prendre un consultant

interne de type Junior B qui nous coûterait au plus 192.50.-/h.



EXERCICE 2.


Auteur: Vincent Isoz ([email protected]

Mots-clés: recherche opérationnelle, optimisation production

Énoncé:

Supposons qu'une usine fabrique 2 pièces P1 et P2 usinées dans deux ateliers A1 et A2.

Les temps d'usinage sont pour P1 de 3 heures dans l'atelier A1 et de 6 heures dans l'atelier A2

et pour P2 de 4 heures dans l'atelier A1 et de 3 heures dans l'atelier A2.

Le temps de disponibilité hebdomadaire de l'atelier A1 est de 160 heures et celui de l'atelier

A2 de 180 heures.

La marge bénéficiaire est de 1'200.- pour une pièce P1 et 1'000.- pour une pièce P2.

La question est: Quelle production de chaque type doit-on fabriquer pour maximiser la marge

hebdomadaire?

A résoudre en utilisant la représentation graphique et MS Office Excel!

Solution:

D'abord, il est possible de poser le système d'inéquations:

1: 3 1 4 2 160

2 : 6 1 3 2 180

1, 2 0

A X X

A X X

X X

Ensuite, la fonction économique:

1200 1 1000 2Z X X

Le tracé des deux droites dans MS Excel, donne le polygone des contraintes (c'est que l'on fait

dans les petites classes d'écoles):



où nous voyons de suite ou sont les maximums ainsi que l'optimum.

Pour résoudre le problème dans MS Excel (eh oui! MS Project n'est pas fait pour

l'optimisation… ce qui est logique!), créez un tableau du type suivant:

et ensuite, avec le solveur MS Excel, créez les contraintes adaptées du type (attention les

références de cellules ne sont pas données correctement ci-dessous afin de ne pas vous

mâcher tout le boulot!):



Les solutions seront alors après l'exécution du solveur:

1 16 . 2 28 .X pcs X pcs



EXERCICE 3.


Auteur: Vincent Isoz ([email protected])

Mots-clés: recherche opérationnelle, optimisation budget

Énoncé:

Soit le tableau ci-dessous dans MS Excel:

Auquel correspondent les formules ci-dessous:



Comment répartir équitablement sur les cellules B12 à E12 les 40 000 Francs (valeur à saisir

dans les contraintes pour la cellule F12) de budget pour optimiser (maximiser) au mieux les

bénéfices (cellule G16) ?

Solution:

Pour résoudre cet exercice il suffit de lancer le solveur et d'y saisir:

Afin d'obtenir le résultat ci-dessous:





EXERCICE 4.

Niveau: Université (Fac)

Auteur: Bertrand Julien

Mots-clés: recherche opérationnelle, optimisation de charge

Énoncé:

Une société fabrique trois types de pièces. Le processus de fabrication pour chaque produit

nécessite le passage par trois types de machines. L'ordre de passage par machine est le

suivant:

- Machine 1: pour les opérations de découpe du métal

- Machine 2: pour les opérations de roulage

- Machine 3: pour les opérations de soudage

Les trois ateliers sont regroupés par technologie et comprennent chacun un seul type de

machines. Les capacités nettes respectives de ces trois ateliers sont:

- pour l'atelier de découpage: 10'000 heures par mois

- pour l'atelier de roulage: 7'000 heures par mois

- pour l'atelier de soudage: 5'000 heures par mois

Les marges dégagées par ces trois produits sont de 0.30.- par pièces de type 1 appelé P1,

0.40.- par pièces P2, 0.20.- par pièce P3.

Les temps unitaires de fabrication par produit et par atelier sont exprimés en heures et sont

données ci-dessous par atelier et par type de pièce:

Atelier 1 Atelier 2 Atelier 3

P1 0.01 0.005 0.001

P2 0.002 0.01 0

P3 0 0.02 0.1

Pour le mois suivant, les commandes fermes en portefeuille représentent une quantité de

500'000 pièces P1, 250'000 pièces P2 et 50'000 pièces P3. Ces quantités sont à produire et à

livre pour le mois.

Le problème consiste à trouver la quantité mensuelle optimale à fabriquer par produit de

façon à maximiser la marge globale.

Hypothèses:

H1. Le taux de rebut est supposé nul



H2. La main d'œuvre n'est pas interchangeable

H3. Il n'existe pas d'encours ni de stock de sécurité.

Solution:

D'abord, un calcul simple nous donne en termes de charge:

1: 500'000 0.01 250'000 0.02 10'000 [ ]

2 : 500'000 0.005 250'000 0.01 50'000 0.02 6'000 [ ]

3 : 500'000 0.001 50'000 0.1 5'500 [ ]

A h

A h

A h

Nous constatons don que l'atelier 3 serait en surcharge de 500 heures, ce qui ne permettrait

pas de réaliser la totalité du carnet de commandes du mois sans avoir à augmenter la capacité

de production de cet atelier.

L'atelier 2 serait en sous-charge de 1'000 heures de travail et l'atelier 1 serait à l'équilibre de

charge.

Utilisons maintenant MS Excel pour optimiser la marge en connaissant cet état des faits:

avec les formules suivantes:



avec les paramètres suivants du solveur:

Nous obtenons alors:



Les résultats obtenus ne satisfont pas le carnet de commandes. Il reste, en effet, 5'000 P3 à

livrer pour le mois.

Trois choix au moins sont possible, soit livrer certains clients le mois suivant, soit augmenter

la capacité de produit, soit jouer avec les clients privilégiés en priorité.



EXERCICE 5.



Mots-clés: recherche opérationnelle, optimisation mélanges

Énoncé:

Une entreprise sidérurgique a reçu commande de cinq tonnes d'acier destiné à la fabrication

de carrosseries automobiles. Les teneurs de cet acier en différents éléments chimiques doivent

se trouver dans les fourchettes suivantes:

Elément chimique Teneur minimale

Teneur

maximale

Carbone ( C ) 2% 3%

Cuivre ( Cu ) 0.40% 0.60%

Manganèse ( Mn ) 1.20% 1.65%

Pour fabriquer cet acier, l'entreprise dispose de sept matières premières dont les teneurs, les

quantités disponibles et les cours d'achat sont donnés dans le tableau suivant:

Matière

première

Teneur

en C (%)

Teneur

en Cu (%)

Teneur

en Mn (%)

Stock disponible

(Kg) Coût (.-/Kg)

Ferraille 1 2.5 0 1.3 4000 0.2

Ferraille 2 3 0 0.8 3000 0.25

Ferraille 3 0 0.3 0 6000 0.15

Ferraile 4 0 90 0 5000 0.22

Ferraile 5 0 96 4 2000 0.26

Ferraille 6 0 0.4 1.2 3000 0.2

Ferraille 7 0 0.6 0 2500 0.17

Déterminer les quantités de ferrailles à mélanger pour obtenir la commande souhaitée par le

client au meilleur coût.

Le problème est à résoudre avec MS Office Excel!

Solution:

Pour résoudre ce problème le plus simple est de construire dans MS Excel une table du type

de la page suivante:



Avec les formules suivantes:

Dans D12: =SOMMEPROD($C$3:$C$9;D3:D9)/$D$13

Dans E12: =SOMMEPROD($C$3:$C$9;E3:E9)/$D$13

Dans F12: =SOMMEPROD($C$3:$C$9;F3:F9)/$D$13

Dans H12: =SOMMEPROD($C$3:$C$9;H3:H9)

Dans D14: =SOMME(C3:C9)

Ensuite, il faut lancer le solveur avec les paramètres suivants:

Pour obtenir les résultats:





EXERCICE 6.



Mots-clés: recherche opérationnelle, optimisation stocks

Énoncé:

Une entreprise dispose d'une usine et de cinq entrepôts implantés en fonction d'une clientèle

régionale à distribuer et chacun est considéré comme un centre de profit.

Les marges par produit sont différentes par région.

Pour le produit PA, les marges exprimées par rapport coût de revient du produit sont

respectivement de 120%, 130%, 120%, 150% et 140% pour les entrepôts E1, E2, E3, E4, E5.

Le coût de revient usine est de 1'000.- par unité de produit PA fabriqué.

Les prévisions des ventes pour la semaine à venir sont de:

- 2'500 PA pour l'entrepôt E1



- 500 PA pour l'entrepôt E4


Le stock initial en PA est nul dans chaque entrepôt. Le stock actuel de l'usine est de 7'000 PA.

Il n'est pas possible de fabriquer les produits manquant dans le délai restant, d'ores et déjà,

une perte prévisionnelle de chiffre d'affaires est constatée.

Pour minimiser cette perte et pour maximiser le chiffre d'affaires total, une répartition

optimale des quantités à fournir aux différents entrepôts est à rechercher.

A ce jour, le volume disponible dans les différents entrepôts est de:

- 1'500 [m3] pour l'entrepôt E1



- 200 [m3] pour l'entrepôt E4

- 600 [m3] pour l'entrepôt E1

Le volume d'une unité de produit PA est de 0.5 [m3].



Optimisez le problème avec MS Excel et OpenOffice Calc et discuter des différences

obtenues.

Solution:

D'abord, avec MS Excel nous créons la feuille suivante:




On para métrise le solveur:

avec la liste des contraintes complète suivante:

On lance la recherche et MS Excel trouve:



Ce qui satisfait les contraintes mais pas la demande…

La fonction économique vaut 8'910'000.-

Avec OpenOffice Calc, nous avons la même feuille mais le solveur sera paramétré ainsi:



avec la liste de toutes les contraintes:

En lançant la recherche nous obtenons:



Nous voyons donc que la fonction économique à la même valeur mais que la répartition des

livraisons ne se fera pas de la même manière. Ainsi les deux logiciels donnent une réponse

optimale mais pas identique… qui joue entre les entrepôts E1 et E3 qui ont la même marge et

suffisamment de volume pour stocker tout ce qui doit arriver.

Il est dommage qu'aucun des deux logiciels n'indique qu'il y ait plusieurs solutions (même si

on pouvait s'en douter à la vue de l'énoncé…).



EXERCICE 7.



Mots-clés: recherche opérationnelle, optimisation logistique, problème de transport

Énoncé:

Il s'agit de livrer un produit à trois clients européens (Client 1, 2 et 3) d'une entreprise qui

dispose de deux usines de fabrication (Usine1 et 2). Le transport est assuré par un système

logistique qui utilise un réseau de 5 plates-formes (PF1 à PF5). Les capacités de transport sur

chacun des liens du réseau sont limitées aux valeurs données dans le graphe suivant:

Les quantités de produit disponibles en stock dans les usines sont respectivement de 35 pour

Usine 1 et 25 pour Usine 2. Les demandes des trois clients sont respectivement de 15 pour

Client 1 et pour Client 2 et 20 pour Client 3.

Trouver un programme de transport qui satisfasse la demande des clients

Remarque: Il s'agit alors d’un problème de flot maximal que nous pouvons modéliser en

indiquant que la quantité de produit qui transite sur chaque arc doit rester inférieure à sa

capacité, que les flux sont conservés dans tous les sommets (sauf Source et Puits), et que la

somme des flux arrivant au Puits doit être maximale.




Solution:

Une technique possible consiste à créer un tableau de flot du type suivant:

et plus bas un autre tableau du type:

où dans Total reçu nous avons les somme des colonnes et dans Total émis la somme des

lignes.

La cellule Flot représente la somme des puits à maximiser.

Le solveur doit alors simplement (mais il fallait y penser) être configuré tel que présenté ci-

dessous:



Le solveur exprime ici simplement que:

1. Nous n'avons pas le droit de dépasser les maximaux des capacités des lignes de transport

spécifié dans le premier tableau via la contrainte: $C$19:$N$30<=$C$4:$N$15

2. Les flux doivent être conservés. En d'autres termes, tout ce qui sort doit entrer quelque part.

En d'autres termes, si nous avons 15+15+20=50 éléments demandés (puits) il faudra quelque

part que 50 élément soient fournis. Le flux devra être conservatif en chaque point du graphe.

Une fois le solveur lancé, vous aurez:

Nous voyons bien dans le résultat que tout ce qui est reçu par un élément est re-émis (on évite

le gaspillage) et que les maximaux par ligne de transport ne sont jamais dépassés. Le total des

puits vaut alors bien (forcément) 50.

Effectivement, le total des sources étant égal à 50, le maximum des puits sera alors de 50…





EXERCICE 8.

Niveau: Lycée (Gymnase)

Auteur: Vincent Isoz

Mots-clés: recherche opérationnelle, optimisation marge

Énoncé:

Un fabricant de montres fait un bénéfice de 15.- sur chaque montre d'une gamme 1 et un

bénéfice de 8.- sur chaque montre de gamme 2.

Pour satisfaire à la demande des vendeurs, la production journalière de montres de gamme 1

devrait se situer entre 30 et 80, et la production journalière de montres de gamme 2 entre 10 et

30.

Pour maintenir une bonne qualité, le nombre total de montres ne devrait pas dépasser 80 par

jour.

Combien de montres de chaque type faudrait-il fabriquer quotidiennement pour réaliser un

bénéfice maximum?


Remarque: Le problème peut être résolu très intuitivement sans le solveur mais bon… pour le

plaisir…

Solution:

Nous construisons par exemple la feuille suivante:

avec les relations suivantes:



et nous configurons le solveur ainsi:

ce qui nous donne:

et qui est la solution du problème!



EXERCICE 9.



Mots-clés: recherche opérationnelle, optimisation du choix des fournisseurs

Énoncé:

Une société importatrice de café achète des lots de grains de café en vrac, puis les sépare en

grains de premier choix, ordinaires et inutilisables.

La société a besoin d'au moins 280 tonnes de grains de premier choix et 200 tonnes de grains

ordinaires.

Elle peut acheter des grains non triés à volonté chez deux fournisseurs qui contiennent les

pourcentages suivants de grains de premier choix, ordinaires et inutilisables:

Fournisseur 1er choix Ordinaire Inutilisable

A 20% 50% 30%

B 40% 20% 40%

Chez le fournisseur A le coût à la tonne est de 125.- et chez le fournisseur B de 200.-.

Trouvez la combinaison optimale permettant de satisfaire les besoins tout en investissant un

minimum d'argent.

Solution:

Nous créons la feuille suivante:



Avec les relations suivantes:

et nous configurons le solveur ainsi:

ce qui nous donne:




EXERCICE 10.



Mots-clés: recherche opérationnelle, optimisation en investissement matériel

Énoncé:

Une entreprise désire acquérir des fraiseuses manuelles (FM) et automatisées (FA) pour sa

production.

L'entreprise ne peut dépenser plus de 200'000.- pour les machines et pas plus de 1'000.- par

mois la maintenance.

Les fraiseuses manuelles coûtent 20'000.-/pièce et en moyenne 200.- par mois pour la

maintenance.

Les fraiseuses automatisées coûtent 40'000.-/pièce et en moyenne 150.- par mois pour la

maintenance.

Sachant que chaque fraiseuse manuelle peut produire 15 unités et chaque automatisée 25,

trouver le nombre de chacune à acheter pour maximiser la capacité de production.

MS Excel ne pouvant résoudre ce problème à ce jour, nous utiliserons OpenOffice.org.

Solution:

Nous créons la feuille suivante:



avec les relations:



et nous configurons le solveur de OpenOffice.org Calc de la manière suivante:

ce qui nous donne:




EXERCICE 11.



Mots-clés: recherche opérationnelle, MRP (Material Requirements Planning)

Énoncé:

Dans une entreprise, nous avons les données suivantes:

Quelle est la meilleure manière de répartir la production sur les 6 mois afin de minimiser le

coût total sachant que nous avons un stock initial de 50 unités?

Solution:

Pour trouver la solution, dans un premier temps, nous construisons un tableau avec la

production effective et les stocks effectifs qui seront calculés:

Ensuite, nous devons aussi écrire la fonction de coût à optimiser:



Ensuite, nous lançons le solveur avec les paramètres suivants:

et nous obtenons:



et voilà pour un MRP I.



EXERCICE 12.



Mots-clés: recherche opérationnelle, optimisation de fonction de plan d'expérience

Énoncé:

Une entreprise produit des aliments dont une acidité est produite par des ferments qui

transforment le lactose en acide lactique. Nous avons souhaité diminuer le goût acide en

jouant sur trois facteurs:

1. Le taux de dilution (rapport volumique eau ajoutée/lait brut): [0.5%,2%] 1x

2. Le pH (suivant quantité de stabilisant injecté): [5,6] 2x

3. Taux de concentration du lait (rapport volumique lait brut/stabilisé): [1.5%,2.5%] 3x

A l'aide d'une régression linéaire multiple, nous avons obtenu l'équation quadratique complète

suivante de l'étude de l'appauvrissement en % en nous basant sur des valeurs factorielles des

intervalles:

2 2 21 2 3 1 2 1 3 2 3 1 2 350.1 0.07 0.11 0.06 4.22 0.32 2.2 0.07 3.6 9.1y x x x x x x x x x x x x

Le but est de maximiser y (c'est-à-dire l'appauvrissement en acide) car le produit sera meilleur

si l'appauvrissement est élevé.

Solution:

Nous partons du tableau MS Excel suivant dans lequel nous avons utilisée la relation de

transformation des unités centrées réduites dans la colonne C (cf. chapitre de Génie

Industriel):

Avec les paramètres suivants du solveur:



Ce qui donne:



EXERCICE 13.

Niveau: Fac (Université)


Mots-clés: recherche opérationnelle, optimisation de l'ordonnancement, algorithme

évolutionnaire

Énoncé:

Un employé à une série de tâches indépendantes à exécuté et pour lesquelles les informations

suivantes lui sont communiquées par son système informatique:

Nous souhaiterions savoir quel doit être l'ordonnancement des tâches afin de minimiser le

retard du travai (si retard il y a...).

Comme il y a:

6! 720

combinaisons possibles, nous n'allons pas faire cela à la main...

Solution:

D'abord, il faut oublier de trouver une solution et cela ne sera pas possible avec MS Excel

2007 ou antérieur... car il y manque dans le solveur une contrainte nommée "tous différents".

Nous utiliserons donc MS Excel 2010.

Pour résoudre ce problème avec MS Excel 2010, nous pouvons d'abord préparer un tableau du

type suivant quelques lignes plus bas dans la même feuille:



où l'idée est d'avoir dans le tableau en haut l'ordonnancement original (pour en garder une

trace et comparer le avant/après) et en bas le tableau optimisé.

Voici les formules classiques explicites du deuxième tableau:

Et ensuite nous lançons le solveur avec l'algorithme évolutionnaire (normalement ce problème

a peu de chances de trouver une solution avec l'algorithme GRG non linéaire, mais nous

constatons que MS Excel 2010 en trouvera quand même une, car nous le soupçonons d'utiliser

quand même l'algorithme évolutionnaire):



Ce qui donne:

Et il ne faut pas être surpris si pour l'alorithme évolutionnaire, à chaque exécution, et dans le

cas particulier présent, l'ordre des 4 premières tâches peut être permuté puisqu'elles

n'influencent pas sur le résultat final quel que soit leur ordonnancement.



EXERCICE 14.



Mots-clés: recherche opérationnelle, k-means, algorithme évolutionnaire

Énoncé:

Considérons les données suivantes:

Nous souhaitons utiliser le solveur évolutionnaire de MS Excel pour trouver trois centroïdes

et comparer le résultat à un logiciel spécialsié comme Minitab ou Tanagra.

Solution:

Nous créons sur la même feuille le tableau suivant:



avec les formules triviales pour les trois colonnes N, O, P où l'on retrouve la norme de la

distance euclidienne:



et les formules suivantes pour les deux colonnes restantes:

Ensuite, nous lançons le solveur de MS Excel (dans le présent cas il s'agit de la version 2010

du logiciel) avec les paramètres suivants en faisant bien attention à prendre l'algorithme

évolutionnaire ce qui fait que nous assumons qu'à chaque fois que nous pourrions avoir un

résultat différent:



et nous avons en lançant le solveur:



avec le tableau:

Des logiciels spécialisés de statistiques comme Minitab ou de Data Mining comme Tanagra

donnent en comparaison les valeurs des 3 centres et qui sont une fois reportées dans

MS Excel:



avec le tableau:



La différence s'explique assez simplement! Un logiciel comme MS Excel minimise la

distance des points aux centres mais est incapable en même temps de maximiser la distance

entre les centres. Par contre les logiciels de statistiques ont les algorithmes qu'il faut pour cela.

Minitab ne donne pas de graphique mais Tanagra lui donne:



EXERCICE 15.



Mots-clés: recherche opérationnelle, nomographe, algorithme évolutionnaire

Énoncé:

Dans le domaine du contrôle qualité à la réception, il est courant pour le respect des normes

international de faire appel à un nomographe pour calcul la taille du lot qui doit être contrôlée

et le nombre d'échantillons qu'il faut en tirer en fonction du niveau de qualité acceptable.

Malheureusement:

1. La lecture du nomographe est pas toujours aisée (et pas amusante)

2. Il n'y avait pas de solution avec le solveur des versions antérieures à Excel 2010

Voyons le problème:

Un lot de bouteilles est livré sous forme de lots de 10'000 unités correspondant à N. Nous

cherchons à mettre en place un plan de contrôle de la réception par attributs avec la

probabilité cumulée (risque) de 1% que le client rejette à tort le lot avec moins de 2.5%

( p ) de non conformes. De son côté le client souhaite une probabilité cumulée (risque) de

10% d'accepter à tort un lot avec plus de 5% ( p ) de non conformes.

Solution:

Le but est de déterminer donc la valeur de A et de n qui satisfont le système du système

suivant:

Il nous faudra d'abord transforme cela en un seul système car le solveur n'a qu'une valeur

cible. Nous faisons alors la somme:

0 0

1

Np N NpNp N NpA Ak n k k n k

N Nk kn n

C C C C

C C

Soit dans notre cas:



10'000 2.5% 10'000 10'000 2.5% 10'000 5% 10'000 10'00015%

10'000 10'0000 0

1 1% 10% 109%A A

k n k k n k

k kn n

C C C C

C C

Soit dans le langage MS Excel cela donnera:

Soit explicitement:

Maintenant, pour résourdre ce problème, il est clair et évidant qu'il faudra passer par un

algorithme évolutionnaire. Nous lançons alors le solveur avec les paramètres suivants (après

plusieurs heures d'essais pour être honnête):



La difficulté principale est de savoir que de par la convergence vers une loi binomiale pour N

grand (voir nomographe), n ne dépassera probablement jamais les 1'000 unités et n les 150

étant donné les niveaux de risques d'usage dans les entreprises (raison pour laquelle le

nomographe s'arrête à 1000 pour n et à 150 pour A). Donc il faut adapter les contraintes de

$B$12 et $B$9 en conséquence car sinon vous pouvez attendre parfois une journée entière de

sélection aléatoire sans avoir de résultat.

De plus, le solveur évolutionnaire ne trouvera tel quel jamais de réponse exacte pour la a

simple raison qu'il n'y en pas relativement au niveau de précision imposé par défaut dans les

option du solveur.

Il faut donc petit à petit augmenter les valeurs de la précision des contraintes. Dans le cas

présent, des solutions réalisables sont obtenus à partir d'une précision sur les contraintes de

0.00001:



En lançant le solveur, nous souvent des résultats différents ou égaux mais proche mais proche

de que ce que nous obtenons avec le nomographe binomial (A 30 et n 700).

Voici les résultats obtenus avec 9 essais différents:

Essai B9 (A) B12 (n)

1 24 623

2 23 603

3 23 603

4 20 533

5 24 623

6 27 691

7 26 667

8 22 579

9 27 691

Dans le doute, prenez le résultat qui maximise n et A.



EXERCICE 16.

Niveau : Université (Fac)

Auteur : Alain Boitel

Mots-clés : Frontière de Markowitz

Enoncé :

Considérons trois titres composants un portefeuille en proportions égales (que nous

supposerons dans des proportions égales dans le portefeuille) et les n observations de leur

rendement ,i jR saisis dans MS Excel (la composant j pouvant être vu comme une période

temporelle) :

Déterminez la frontière d'efficience du portefeuille selon le modèle de Markowitz ainsi que la

C.M.L. et la pondération des actifs qui minimise la variance pour une espérance maximum

pour une portefeuille composé d'un actif sans risque d'un rendement de 0.22.

Remarque :

Harry Max Markowitz (né le 24 août 1927 à Chicago) est un économiste américain. lauréat du

Prix Nobel d'économie en 1990. C'est donc l'auteur du modèle de diversification efficiente des

portefeuilles d'actifs financiers.

Markowitz développa la base mathématique et les conséquences de cette analyse dans sa

thèse, soutenue en 1954. Milton Friedman, qui faisait partie du jury, lui aurait déclaré :

"Harry, ceci n'est pas une thèse d'économie, et nous ne pouvons vous donner un doctorat

d'économie pour quelque chose qui n'est pas de l'économie. Ce n'est pas des maths, ce n'est

pas de l'économie, ce n'est même pas de la gestion."

Solution :

Dessous la table donnée précédemment nous allons créer dans MS Excel le tableau contenant

les proportions iX des titres (que nous supposerons équidistribuées, soit 1/3), nous

afficherons la moyenne du rendement i calculée bien évidemment selon l'estimateur :



,

1

( 2 : 6)

ˆ ( 2 : 6)

( 2 : 6)

n

i j

j

i i

R Moyenne B B

E R Moyenne C Cn

Moyenne D D

et la variance 2i calculée pour chaque titre par l'estimateur :

2

,

12

ˆ ( 2 : 6)

ˆ ( 2 : 6)1

( 2 : 6)

n

i j i

j

i

R Var B B

Var C Cn

Var D D

Ce qui nous donne le tableau suivant dans MS Excel :

Soit sous forme détaillée dans MS Excel toujours :

Nous devons maintenant calculer le rendement moyen du portefeuille selon :

1 1 2 1 3 1

1

ˆ ˆ ˆn

p i i

i

E R X R X X X

Cette relation est un peu longue à saisir, et le sera davantage si nous avons un nombre bien

plus important de titres.

Dans notre cas, il s'agit de faire la somme des produits terme à terme de deux plages de

cellules ( iX et ˆi ) ayant la même dimension (même nombre de lignes et même nombre de

colonnes). Nous pouvons alors utiliser la fonction suivant dans MS Excel :

SOMMEPROD(B14:D14;B15:D15)

Pour la variance du portefeuille, c'est un peu plus compliqué puisqu'il s'agira de calculer :



2 2

1

2 2

1

2 cov ,

2 cov ,

n

p p i i i j j i

i i j

n

i i i j j i

i i j

V R R X V R X X R R

X X X R R

La relation développée dans notre cas particulier donne :

2 2 2 2 2 2 21 1 2 2 3 3 1 2 1 2

1 3 1 3 2 3 2 3

2 cov ,

2 cov , 2 cov ,

pR X X X X X R R

X X R R X X R R

L'astuce pour appliquer ceci dans MS Excel consiste à utiliser l'algèbre linéaire et écrire cette

relation sous forme matricielle comme nous l'avons démontré :

2 Tp ijR X c X

Ce qui équivaut dans MS Excel à écrire :

=SOMMEPROD(PRODUITMAT(B14:D14;G14:I16);B14:D14)

Soit sous forme matricielle explicite :

21 2 1 3 1 1

2 21 2 3 1 2 2 3 2 2

231 3 2 3 3

cov , cov ,

cov , cov ,

cov , cov ,

p

R R R R X

R X X X R R R R X

XR R R R

Donc en se basant sur les tableaux précédents, il est simple dans MS Excel d'obtenir la

matrice de covariance :

Soit sous forme détaillée dans MS Excel toujours :



Rappel : La matrice des covariances est symétrique… (cf. chapitre de Statistiques).

Et pour l'espérance et la variance du portefeuille nous aurons donc le tableau suivant :

en appliquant donc les relations susmentionnées:

Le problème maintenant est de déterminer pour un rendement du portefeuille fixé (B19), les

proportions des différents titres qui minimisent le risque.

Après avoir ajouté les deux cellules B24 (rendement espéré/attendu du portefeuille) et B25

(nombre total des parts du portefeuille) :

Nous devons donc maintenant résoudre le problème d'optimisation non linéaire :

2min :

0.2

1

p

p

i

R

E R

X

et ceci ne peut que se faire (simplement) à l'aide du solveur :



Ce que nous allons faire à l'aide du solveur est de chercher et reporter les solutions pour des

rendements de 0.2 à 0.245 par pas de 0.05. A chaque résultat, nous noterons le numéro de

l'itération, la variance du portefeuille 2pR et l'espérance de rendement pE R qui était

exigée. Cela devrait donner (bon il faudrait automatiser dans l'idéal la procédure par du

VBA) :

Ce qui donne la frontière efficiente de Markowitz suivante sous forme graphique dans

MS Excel :



Maintenant il est aisé avec MS Excel de déterminer l'équation de cette parabole en utilisant

l'outil d'interpolation (nous sommes obligés dans MS Excel de tourner la parabole pour

cela…) :

Maintenant, nous allons déterminer la C.M.L (capital market line) qui est la droite formée par

l'ensemble des portefeuilles composés de l'actif sans risque, d'une part, et du portefeuille de

marché, d'autre part. Par construction, elle associe à chaque niveau de risque, la rentabilité

espérée la plus élevé.



Nous allons pour déterminer cette droite avec MS Excel nous fixer dans un premier temps un

taux de rendement sans risque que nous noterons fR et que nous prendrons arbitrairement

comme valant 0.22. Nous avons donc la courbe de Markowitz d'équation :

2 218.795 8.389 0.9384y x x ax bx c

et la droite :

' 'y a x b

avec la condition :

''

0.22

ba

Nous avons alors deux équations connues à deux inconnues pour résoudre ce problème

(l'intersection de la droite et la parabole pour la première et l'égalité de la pente de la parabole

et de la droite au point d'intersection) :

2 ' '

2 '

M M M

M

ax bx c a x b

ax b a

La deuxième équation nous donne :

'

' 0.22

2 2M

bb

a bx

a a

Injecté dans la première équation :



2' ' '

'0.22 0.22 0.22 '2 2 0.22 2

b b bb b b

ba b c b

a a a

Si nous résolvons ce polynôme du deuxième degré nous avons deux solutions réelles (Excel

n'arrive pas à déterminer les racines de ce polynôme) :

1 2' -0.6822748631 ' 0.1207634890b b

La solution 2 est à éliminer (nous le savons en essayant de la prendre comme solution). Nous

avons donc:

'' -0.6822748631 ' =0.3101249378

0.22

bb a

Ce qui donne sous forme graphique :

Soit sous forme traditionnelle :



Il vient aussi immédiatement :

'

0.22 0.23142657462

M

bb

xa

Ainsi, en réutilisant le solveur comme plus haut mais avec cette nouvelle valeur pour

l'espérance, nous obtenons pour un portefeuille du marché composé d'un actif sans risque de

rendement 0.22, un rendement global efficient de 0.2314276… avec la composition suivante

du portefeuille donnée par le solveur :

1

2

3

0.055

1.079

0.024

X

X

X



EXERCICE 17.


Auteur : Alain Boitel

Mots-clés : Frontière de Sharpe

Enoncé :

Considérons trois titres composants un portefeuille en proportions égales et les n observations

de leur rendement ,i jR saisis dans MS Excel. Ces rendements seront comparés à un indice de

référence I qui sera le rendement d'un portefeuille de marché de référence MPF :

Le but se de déterminer la frontière d'efficience du portefeuille avec le modèle de Sharpe.

Solution :

En détail sous forme graphique voici d'abord les bêta (rendement de l'actif en fonction du

rendement du portefeuille de marché/indice de référence) obtenus par MS Excel :



et le tableau de construction suivant pour le calcul des bêta, la variance et l'espérance des

différents titres :

Voici les détails du calcul (remarquez que les bêta sont obtenus à l'aide d'une simple

régression linéaire avec l'indice de référence qui est le portefeuille et les autres paramètres

avec les estimateurs non biaisés) :

L'espérance du rendement du portefeuille composé des trois titres est facile à calculer puisque

nous avons leur rendement. Donc :

1 1 2 1 3 1

1

ˆ ˆ ˆn

p i i

i

E R X R X X X

Ce qui donne sous MS Excel :

Soit de manière détaillée :

Maintenant, il nous faut calculer l'espérance en utilisant la relation démontrée dans la partie

théorique des paragraphes précédents :

2 2 Tp p I ijV R R X X



avec pour rappel dans notre cas particulier :

21

1 2 1 32

22

, 2 1 2 32

22

3 1 3 2 2

I

i j

I

I

avec dans notre exemple 2 0.039I (cellule B13).

Soit sous forme développée pour notre exemple :

2 2 2 2 2 2 21 1 2 2 3 3

2 2 21 2 1 2 1 3 1 3 2 3 2 32 2 2

p

I I I

R X X X

X X X X X X

Ce qui donne dans MS Excel pour notre matrice des bêta :

Soit sous forme développée (la matrice est symétrique) :

Et finalement le couple variance/espérance du portefeuille est donné par :

Soit sous forme détaillée :



Une fois ceci fait, nous procédons comme pour la frontière de Markowitz. Nous utilisons le

solveur en minimisant la variance tout en imposant une espérance et une contrainte comme

quoi la somme des parts des actifs financiers est égale à l'unité :

Ce qui donne le tableau variance/rendement suivant (à comparer avec le même tableau de

Markowitz) :

et le graphique suivant (comparaison directe avec Markowitz mise en évidence) :



La suite de l'exercice (C.M.L.) se fait de la même manière que dans le modèle de Markowitz.



EXERCICE 18.


Auteur : Vincent Isoz

Mots-clés : Modèle logistique, Lissage exponentiel

Enoncé :

Considérons le tableau suivant fait avec MS Excel (les ventes sont en centaines de millier

d'unités):

et le graphique associé:



qui pourrait être jugé comme linéaire suivant à quel moment commence l'analyse descriptive

des ventes dans l'entreprise.

Déterminer le modèle théorique prédictif des ventes avec le modèle logistique linéarisé, le

modèle logistique optimisé et le lissage exponentiel.

Solution :

Pour déterminer le modèle théorique, nous allons linéariser l'équation logistique en utilisant

un seuil hypothétique (objectif de ventes du marché) 800.

Donc:

Soit à calculer la nouvelle variable à expliquer:

et le modèle linéaire s'écrit donc:

avec donc:



Soit:

Dans notre exemple, la régression linéaire (cf. chapitre de Méthodes Numériques) donne:

Nous avons alors immédiatement:

Soit sous forme graphique:

avec ce modèle formel, nous avons une somme des carrés des écarts entre les mesures et le

modèle (cf. chapitre de Statistique) de:

Maintenant, entrons ces données dans MS Excel sous la forme suivante:



avec la structure suivante:

Si nous lançons le solveur avec les paramètres suivants:



Ce qui donne:

Soit:

avec:

soit nettement inférieur à notre approche utilisant la régression linéaire et donc meilleur.

Graphiquement cela donne:



Nous voyons nettement que le modèle du solveur (modèle numérique) est meilleur que le

modèle formel donné par une régression linéaire!

Maintenant, comparons à au lissage exponentiel. Pour cela créez une nouvelle colonne

comme indiqué ci-dessous:



et lancez l'outil de lissage exponentiel (exponential smoothing) de l'utilitaire d'analyse de

MS Excel:

et validez par OK. Vous aurez alors:



Nous voyons nettement l'infériorité du modèle de lissage par rapport au modèle logistique et

ce même graphiquement (bon objectivement il est injuste des les comparer car ils n'ont

absolument pas les mêmes fondements mathématiques):



EXERCICE 19.

Niveau : Gymnase (Lycée)

Auteur : Vincent Isoz ([email protected])

Mots-clés : Défaillance Weibull

Énoncé :

Nous avons dans MS Excel les données suivantes représentant les durées de vies de sept

machines données en années:

Nous avons calculé dans B13 la moyenne arithmétique (l'espérance) et dans B14 l'estimateur

de maximum de vraisemblance de l'écart-type de la loi Normale…. (hmm…):

Nous voulons modéliser la durée de vie par une loi de Weibull de paramètres:

0, ?, ?

Nous demandons:

1. De déterminer , en utilisant la méthode de Lloyd et Lipov

2. Déterminer MUT MTBF (suppose temps d'arrêt pour réparation négligeable)

3. De calculer la probabilité cumulée R que la machine tienne le coup plus de 20 mois.

4. La probabilité cumulée F que la machine tombe en panne entre le 15 et 30ème

mois.

5. La durée limite de garantie minimale assurant une probabilité cumulée de fonctionnement

(fiabilité) de 95%.

Solution :

S1. Nous avons démontré dans le chapitre Technique de Gestion que pour 0 :



1

1( ) 1E X

et :

2

2 21 1

2 1

Nous créons donc une zone dans la feuille Excel avec la structure suivante:

Avec les formules suivantes:

La fonction Gamma (à ne pas confondre avec la loi Gamma!) n'existant pas dans MS Excel

nous devons prendre l'exponentielle de la fonction du logarithme népérien de la fonction

Gamma qui elle est disponible O_o.

Une fois ceci fait, nous allons demander à l'aide du solveur de MS Excel de déterminer les

valeurs de E2 et E3 afin de faire correspondre l'espérance et l'écart-type de la loi de Weibull

aux valeurs obtenues dans B13 et B14.

Mais le solveur a besoin d'un objectif et il peut en avoir qu'un. Nous devons donc jouer avec

des paramètres supplémentaires qui en tant qu'objectif unique imposeront la détermination de

E2 et E3. Nous allons pour cela jouer avec la variation entre l'espérance calculée par le

solveur et l'espérance déterminée expérimentalement et idem avec l'écart-type. Cela nous

donne:




Nous pouvons maintenant lancer le solveur avec les paramètres:

L'exécution du solveur donne:

E2 3.59

E3 20.7

S2. L'exécution du solveur donne aussi:

1

1( ) 1 18.65E X MUT MTTF

S3. La probabilité que la machine tienne le coup plus de 20 mois est alors donnée par:

R=1-WEIBULL(20;beta;nu;1)=58.67%

et donc qu'elle tienne le coup au moins 20 mois:



=WEIBULL(20;beta;nu;1)=41.32%

S4. La probabilité que la machine tombe en panne entre le 15 et 30ème

mois:

F=WEIBULL(30;beta;nu;1)- WEIBULL(15;beta;nu;1)=70.78%

S5. Pour répondre à cette question nous reprenons les cellules suivantes nous d'abord les

cellules suivantes dans MS Excel nous ayant server pour le calcul de la deuxième partie de la

solution 3 (S3):

Soit avec les formules:

Maintenant nous utilisons l'outil cible de MS Excel dans Outils/Outil cible:

En validant par OK, nous obtenons alors à l'écran:

G15=9.07

années. Donc nous pouvons garantir nos machines 9 années sans avoir peu de perdre trop

d'argent en les commercialisant.

Documents

R EECCHHER RCHHE E … · Sciences.ch Recherche opérationnelle (solveurs) Serveur d'exercices 3/78 et nous le lançons. Il vient alors comme résultat au problème: