Problème du vendeur de journaux

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

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

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

Summarize Timeline Top Qs Fact Check

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

${\displaystyle \Phi _{S}(q)=p\int _{0}^{q}v\,\rho (v)\,dv+p\,q\int _{q}^{\infty }\rho (v)\,dv\,-c\,q}$

où ${\displaystyle \displaystyle \rho (v)}$ 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 ${\displaystyle \displaystyle \Phi _{S}(q)}$ est atteint pour le choix optimal ${\displaystyle {\hat {q}}}$ défini par la relation implicite :

${\displaystyle F({\hat {q}})=1-c/p}$

où ${\displaystyle \displaystyle F(v)}$ est la fonction de répartition cumulative de la demande ${\displaystyle \displaystyle v}$ définie par ${\displaystyle F(v)=\int _{0}^{v}\rho (w)\,dw.}$

En effet, pour tout ${\displaystyle q\geqslant 0}$, on vérifie :

${\displaystyle \Phi _{S}({\hat {q}})-\Phi _{S}(q)=p\int _{q}^{\hat {q}}(v-q)\,\rho (v)\,dv\geqslant 0.}$

Dans cette dernière relation, en posant ${\displaystyle \displaystyle q=0}$ (avec ${\displaystyle \displaystyle \Phi _{S}(0)=0}$), on déduit le profit espéré maximal :

${\displaystyle \Phi _{S}({\hat {q}})=p\int _{0}^{\hat {q}}v\,\rho (v)\,dv\geqslant 0.}$

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

Bien que la demande soit aléatoire, on suppose qu’elle est déterministe, égale à sa valeur espérée notée ${\displaystyle {\bar {v}}}$ 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] :

${\displaystyle \Phi _{D}(q)=p\,\min(q,{\bar {v}})-c\,q}$

dont la solution est naturellement ${\displaystyle q={\bar {v}}}$ et le profit maximal est ${\displaystyle \Phi _{D}({\bar {v}})=(p-c){\bar {v}}}$.

Puisque ${\displaystyle \Phi _{S}({\hat {q}})\geqslant \Phi _{S}({\bar {v}})}$, la solution de cette formulation déterministe érode le profit espéré maximal : elle est sous-optimale.

Summarize Timeline Fact Check

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

• la demande ${\displaystyle \displaystyle v}$ suit une loi log-normale (choisie pour assurer des valeurs positives) d’espérance ${\displaystyle {\bar {v}}=}$ 100 et d’écart type ${\displaystyle \displaystyle \sigma (v)}$ considéré comme un paramètre libre pour l’étude,
• le prix d’achat : ${\displaystyle \displaystyle c=}$1.0,
• le prix de vente : ${\displaystyle \displaystyle p=}$1.1.

Sous ces conditions, pour toute valeur de ${\displaystyle \sigma (v)}$, il est possible de déterminer :

• la solution ${\displaystyle {\hat {q}}}$,
• le profit espéré associé ${\displaystyle \Phi _{S}({\hat {q}})}$,
• le profit espéré ${\displaystyle \Phi _{S}({\bar {v}})}$ 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 ${\displaystyle \displaystyle \sigma (v)}$ :

• Lorsque la variabilité (sigma) de la demande augmente, la quantité optimale ${\displaystyle {\hat {q}}}$ 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 ${\displaystyle (\Phi _{S}({\hat {q}}))}$ décroît également (courbe bleue, échelle de droite).
• Le profit espéré de la solution de la formulation déterministe ${\displaystyle (\Phi _{S}({\bar {v}}))}$ décroît plus rapidement (courbe rouge, échelle de droite). Il prend même des valeurs négatives à partir d’un sigma relatif ${\displaystyle (\sigma (v)/{\bar {v}})}$ 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 ${\displaystyle \displaystyle \rho (v)}$ mal connue au lieu de l’ignorer.