Programmation stochastique : choisir aujourd'hui, subir demain.
Une décision doit souvent être prise avant que le hasard ne se prononce. Le boulanger fixe sa production le soir pour le lendemain ; l'usine réserve sa capacité des mois avant de connaître ses commandes ; le transporteur affrète ses camions sans savoir ce qui sera à charger. Dans tous les cas la structure est la même : une décision de première étape, puis la réalisation de l'aléa, puis un recours — ce qu'on peut encore ajuster une fois qu'on sait.
La tentation est de remplacer l'aléa par sa moyenne et de résoudre le problème déterministe qui en résulte. Cette page montre pourquoi c'est presque toujours une erreur, comment mesurer le prix de cette erreur, combien de scénarios il faut simuler pour ne plus la commettre, et ce que vaut exactement une prévision imparfaite. Les probabilités sont ici supposées connues — le cas où elles ne le sont pas relève d'un autre outillage.
Un produit périssable : on en fabrique q au coût c, on le vend au prix p tant qu'il y a des clients, et l'invendu part à la valeur de rebut s. La demande D est aléatoire. Le profit s'écrit :
Π(q,D) = p·min(q,D) + s·(q−D)+ − c q = (p−c)q − (p−s)·(q−D)+
Dériver l'espérance donne une condition d'une simplicité remarquable : produire jusqu'au quantile de la demande correspondant au fractile critique, rapport du manque à gagner d'une unité vendue en moins au coût d'une unité invendue.
P(D ≤ q*) = (p − c) / (p − s)
Deux boulangers côte à côte : l'un produit la demande moyenne, l'autre le quantile critique. Sur un seul jour, le second a souvent tort. Sur une saison, il gagne.
Passons à deux produits qui se disputent une même capacité de four. La décision de première étape est le couple (q1, q2) avec q1 + q2 ≤ C ; le recours consiste simplement à vendre ce qu'on peut et à solder le reste. Trois quantités structurent tout le domaine :
RP = maxq E[Π(q,D)] — la vraie solution stochastique
EEV = E[Π(qEV,D)] — ce que vaut réellement la solution du scénario moyen
WS = E[maxq Π(q,D)] — ce qu'on gagnerait en connaissant l'avenir
Elles se rangent toujours dans cet ordre : EEV ≤ RP ≤ WS. Leurs différences portent des noms : VSS = RP − EEV, la valeur de la solution stochastique, c'est-à-dire ce que rapporte le fait de raisonner en scénarios ; EVPI = WS − RP, la valeur de l'information parfaite, c'est-à-dire ce qu'on paierait au maximum pour une boule de cristal.
Le scénario moyen donne ici une solution de coin : il alloue toute la capacité disponible au produit de plus forte marge jusqu'à concurrence de sa demande moyenne, puis le reste à l'autre. C'est rigoureusement optimal dans un monde sans hasard, et franchement mauvais dans le vrai. Faites varier la capacité : la VSS n'est pas une constante, elle dépend de la configuration — et s'annule quand le hasard ne change rien à la décision.
En pratique on ne connaît pas la loi : on dispose d'un échantillon. On résout alors le problème sur ces N scénarios — c'est l'approximation par échantillon moyen. Deux choses se produisent simultanément, et elles vont en sens contraire.
La décision obtenue est un peu fausse, donc sa vraie valeur est inférieure à l'optimum. Mais la valeur qu'on lit sur l'échantillon est, elle, supérieure à l'optimum : en optimisant sur un tirage particulier, on épouse ses accidents. L'optimisation est optimiste, et d'autant plus que l'échantillon est petit. L'écart entre les deux courbes est un intervalle qui encadre l'optimum inconnu.
Le biais d'optimisation est le piège classique de l'optimisation sur données : le chiffre qu'annonce le modèle est meilleur que ce qu'on obtiendra. La seule parade honnête est celle qui est faite ici — évaluer la décision sur un autre échantillon que celui qui l'a produite.
L'espérance ignore la forme de la distribution. Deux décisions de même profit moyen peuvent avoir des mauvais jours très différents, et le boulanger qui doit payer son loyer ne s'intéresse pas qu'à la moyenne. On mesure le bas de la distribution par deux quantités : la VaR au niveau α, qui est le quantile α du profit, et la CVaR, moyenne des α % de scénarios les pires — plus informative, et surtout mathématiquement plus commode, car elle se met sous forme d'un simple problème de minimisation.
CVaRα = − mint { t + (1/α)·E[(−Π − t)+] }
L'optimum prudent produit nettement moins que l'optimum en espérance, et la différence n'est pas marginale : au niveau α = 10 %, il descend d'environ 45 %. C'est la traduction chiffrée d'une intuition de commerçant — quand on craint les mauvais jours, on ne remplit pas le four.
L'EVPI de la planche 2 dit ce que vaudrait une prévision parfaite. Mais aucune prévision ne l'est. Supposons qu'on dispose d'un indicateur Y — météo, réservations, tendance de la veille — corrélé à la demande au coefficient ρ. On peut alors décider en connaissance de cause : conditionnellement à Y, la demande reste normale, de moyenne recentrée et d'écart-type réduit à σ√(1−ρ²). Il suffit d'appliquer le fractile critique à cette loi conditionnelle.
Le calcul se referme complètement. La valeur espérée avec une prévision de corrélation ρ vaut :
V(ρ) = (p−c)μ − (p−s)·σ·φ(z*)·√(1−ρ²) soit V(ρ) = RP + EVPI·(1 − √(1−ρ²))
La courbe est plate au départ et ne se redresse qu'à l'approche de ρ = 1. Une prévision corrélée à 50 % à la demande — ce qui serait déjà un très bon outil — ne capture que 13 % de la valeur d'une prévision parfaite ; il faut atteindre ρ = 0,866 pour en récupérer la moitié. La leçon est brutale et utile : avant de payer cher un système de prévision, il faut savoir de quelle corrélation on part, car les premiers points de corrélation ne rapportent presque rien.