Problème du vendeur de journaux

Le problème dit « problème du vendeur de journaux » est un modèle mathématique simple en recherche opérationnelle (microéconomie) concernant le volume économiquement optimal du stock d’un bien qui sera proposé à une demande aléatoire.

L’analyse de ce problème académique montre que, lorsque des phénomènes stochastiques interviennent dans les données d’un problème d’optimisation, le fait de remplacer ces variables aléatoires par leurs espérances respectives dénature les résultats et conduit à une sous-optimisation. La simplification avantageuse (en termes de résolution) d’une formulation déterministe d’un problème qui ne l’est pas peut induire des prises de décision erronées et coûteuses.

Cadre du problèmeModifier

Au début de sa journée, un vendeur itinérant achète un certain nombre   de journaux au prix unitaire   afin de les vendre à la criée aux passants des rues, ceci à un prix unitaire   (hypothèse).

Ne connaissant pas précisément le volume de ses ventes, le vendeur cherche à déterminer la quantité   lui permettant de maximiser l’espérance de son profit acquis durant sa journée :

  • s’il choisit   trop grand, il lui restera des journaux invendus qu’il aura acheté au prix   pour les jeter en fin de journée.
  • s’il choisit   trop petit, il restera des acheteurs potentiels, soit autant de ventes perdues.

FormulationsModifier

StochastiqueModifier

La fonction objectif (à maximiser) est l’espérance du profit qui, en fonction de la quantité   choisie, s’écrit

 

  la densité de probabilité de la variable aléatoire de la demande.

Les deux premiers termes répertorient les situations où la demande est inférieure (respectivement supérieure) aux disponibilités; le troisième terme concerne les coûts d’acquisition.

Le maximum de   est atteint pour le choix optimal   défini par la relation implicite :

 

  est la fonction de répartition cumulative de la demande   définie par  

En effet, pour tout  , on vérifie :

 

Dans cette dernière relation, en posant   (avec  ), on déduit le profit espéré maximal :

 

Conséquemment, il existe un choix conduisant à un profit espéré positif.

DéterministeModifier

Bien que la demande soit aléatoire, on suppose qu’elle est déterministe, égale à sa valeur espérée notée   et de variance nulle. Dans un contexte plus général (et plus complexe), le but d’une telle approximation est de simplifier la résolution. Pour le vendeur de journaux, la fonction objectif (d'une formulation déterministe) s’écrit alors[1] :

 

dont la solution est naturellement   et le profit maximal est  .

Puisque  , la solution de cette formulation déterministe érode le profit espéré maximal : elle est sous-optimale.

Exemple numériqueModifier

Afin de quantifier la perte de profit espéré causée par la formulation déterministe, admettons les hypothèses suivantes :

  • la demande   suit une loi log-normale (choisie pour assurer des valeurs positives) d’espérance   100 et d’écart type   considéré comme un paramètre libre pour l’étude,
  • le prix d’achat :  1.0,
  • le prix de vente :  1.1.
 
Dégradation du profit de la solution obtenue en formulation déterministe

Sous ces conditions, pour toute valeur de  , il est possible de déterminer :

  • la solution  ,
  • le profit espéré associé  ,
  • le profit espéré   qui prévaudrait avec la solution de la formulation déterministe.

La figure ci-contre visualise ces résultats associés aux deux formulations en fonction de   :

  • Lorsque la variabilité (sigma) de la demande augmente, la quantité optimale   décroît (courbe noire, échelle de gauche) afin d’éviter l’achat de journaux qui seront perdus en cas de faible demande.
  • Le profit espéré de la solution de la formulation stochastique   décroît également (courbe bleue, échelle de droite).
  • Le profit espéré de la solution de la formulation déterministe   décroît plus rapidement (courbe rouge, échelle de droite). Il prend même des valeurs négatives à partir d’un sigma relatif   excédant 25 %.
  • Même pour un faible sigma relatif de 10 % (valeur 10 sur les abscisses), la formulation déterministe conduit à une érosion significative du profit espéré, soit une perte de l’ordre de 25 %.

Ce simple exemple atteste des dangers encourus par l’application d’une formulation déterministe à un problème qui ne l’est pas. En pratique, il est généralement préférable d’utiliser une distribution   mal connue au lieu de l’ignorer.

Intérêt économique des prévisionsModifier

Un outil de prévision s’appuyant sur des données statistiques des événements enregistrés par le passé apporte deux contributions essentielles aux données du problème :

  • une modification des espérances des données aléatoires   au lieu de   qui découle du potentiel « explicatif » des variables externes ou exogènes (espérance conditionnelle),
  • une réduction du sigma de ces données   dû au caractère projectif de la prévision.

Dans le contexte de l’exemple, le profit espéré du vendeur augmentera s’il peut saisir les relations (régression linéaire par exemple) entre la demande et certaines variables exogènes comme la météo (peu d'acheteurs potentiels s’il pleut), l’intérêt des nouvelles du journal, le type de jour, etc. Un vendeur expérimenté sait interpréter les conditions qui influencent le volume de ses ventes et quantifier intuitivement leurs effets.

Même si, dans un cas particulier où les variables exogènes ne modifient pas l’espérance  , un coefficient de corrélation   est suffisant pour réduire   d’un facteur 2. En reprenant les résultats de l’exemple précédent, si   20 peut être réduit à 10 grâce à une prévision, le profit espéré augmentera de 20 %.

Voir aussiModifier

NotesModifier

  1. On obtient ce même résultat en partant de la formulation générale dans laquelle   est remplacé par une distribution de Dirac translatée de  , ce qui implique une répartition cumulative   du type fonction de Heaviside