Programmation stochastique

Programmation stochastique (en anglais stochastic programming) est une branche de la programmation mathématique qui développe des modèles et des méthodes pour résoudre des problèmes d'optimisation en conditions d'incertitude, lorsque certains paramètres du modèle ne sont pas connus avec certitude, mais sont représentés par des variables aléatoires dont les distributions de probabilité sont connues ou estimées.

Contrairement aux problèmes déterministes, où toutes les données sont considérées comme des constantes fixes, la programmation stochastique vise à trouver une solution (ou une politique de décision) qui est optimale dans un certain sens statistique. Le plus souvent, cela signifie minimiser ou maximiser l'espérance mathématique de la fonction objectif. L'idée clé est de trouver une politique de décision qui soit la meilleure « en moyenne » sur toutes les réalisations possibles des paramètres aléatoires, ce qui est particulièrement pertinent pour les problèmes où les décisions sont prises de manière répétée dans des conditions similaires (par exemple, dans la gestion des stocks ou des systèmes énergétiques).

Formulation mathématique du problème

De manière générale, un problème de programmation stochastique peut être formulé comme suit : $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ où :

• $x$ — le vecteur des variables de décision (solutions) à déterminer.
• $X$ — l'ensemble des solutions admissibles pour $x$, défini par des contraintes déterministes.
• $\xi$ — un vecteur aléatoire représentant les paramètres incertains du problème (par exemple, la demande, les prix, les conditions météorologiques).
• $f(x,\xi )$ — la fonction objectif, dont la valeur dépend à la fois de la décision $x$ prise et de la réalisation du vecteur aléatoire $\xi$.
• $\mathbb{𝔼}[\cdot ]$ — l'opérateur d'espérance mathématique, calculé sur la distribution de probabilité du vecteur $\xi$.

Un principe fondamental des modèles stochastiques multi-étapes est le principe de non-anticipation (en anglais non-anticipativity principle). Il stipule que les décisions prises à une étape donnée ne peuvent dépendre que de l'information disponible à ce moment-là et ne peuvent pas « anticiper le futur ».

Problème à deux étapes avec recours

Le modèle le plus courant est le problème stochastique à deux étapes avec recours (en anglais two-stage stochastic program with recourse). Le processus de prise de décision est divisé en deux étapes :

1. Première étape : Une décision est prise « ici et maintenant » (here-and-now) — le vecteur $x$ est déterminé. Cette décision doit être prise avant que la réalisation concrète du vecteur aléatoire $\xi$ ne soit connue.
2. Deuxième étape : Une fois que l'événement aléatoire s'est produit, une décision corrective ou de recours (recourse decision) est prise — le vecteur $y(\xi )$, visant à minimiser les conséquences négatives ou à exploiter les opportunités favorables résultant de la combinaison de la décision de première étape $x$ et de la réalisation $\xi$.

Mathématiquement, un problème de programmation linéaire stochastique à deux étapes est formulé comme suit : $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ sous les contraintes de première étape : $Ax=b,x\ge 0$. Ici, $Q(x,\xi )$ est la fonction de recours (recourse function), qui représente la valeur optimale du problème de deuxième étape : $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ où $\xi$ est un vecteur aléatoire qui inclut les paramètres $q(\xi ),T(\xi )$ et $h(\xi )$ ; et $c,A,b$ et $W$ sont des paramètres déterministes.

Propriétés clés et théorèmes

• Convexité : L'un des résultats fondamentaux de la théorie est que pour un problème de programmation linéaire stochastique à deux étapes, la fonction de recours espérée $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ est une fonction convexe. Cette propriété est d'une grande importance, car elle garantit que le problème global de première étape est un problème de programmation convexe, pour lequel il existe des méthodes de résolution efficaces et où l'optimum global coïncide avec l'optimum local.
• Équivalent déterministe : Si le vecteur aléatoire $\xi$ a un nombre fini de réalisations possibles (scénarios) ${\xi }_1,\dots ,{\xi }_K$ avec des probabilités $p_1,\dots ,p_K$, le problème de programmation stochastique peut être reformulé comme un unique grand problème d'optimisation déterministe. Dans ce cas, l'espérance mathématique est remplacée par une somme pondérée sur tous les scénarios. Cependant, la taille de ce problème croît linéairement avec le nombre de scénarios, ce qui conduit au « fléau de la dimensionnalité » et rend cette approche infaisable sur le plan calculatoire pour un grand nombre de scénarios.

Comparaison avec l'optimisation robuste

La programmation stochastique est l'une des plusieurs approches de l'optimisation en conditions d'incertitude. Sa principale différence avec l'optimisation robuste réside dans la manière de modéliser l'incertitude et dans le critère d'optimalité.

Comparaison des approches d'optimisation en conditions d'incertitude

Critère	Optimisation stochastique	Optimisation robuste
Représentation de l'incertitude	Les paramètres sont des variables aléatoires avec une distribution de probabilité connue	Les paramètres appartiennent à un ensemble d'incertitude défini, aucune distribution n'est requise
Critère d'optimalité	Optimisation de l'espérance mathématique de la fonction objectif	Optimisation pour le pire des cas (minimax)
Nature de la solution	Une politique optimale « en moyenne », peut être non admissible pour des scénarios rares	Une solution garantie d'être admissible pour toutes les réalisations ; peut être conservatrice

Exemples

• Problème du vendeur de journaux (en anglais newsvendor problem) : Un problème classique de gestion des stocks où un vendeur doit décider quelle quantité d'un produit acheter sans connaître la demande future exacte. La solution consiste à trouver un équilibre entre le risque de pertes dues à un surplus et le risque de manque à gagner dû à une pénurie.
• Problème du fermier : Un fermier décide combien d'hectares de terre allouer à différentes cultures sur sa superficie totale, sans connaître les conditions météorologiques futures qui affecteront les rendements. Une fois les conditions météorologiques connues, le fermier peut prendre des mesures correctives (par exemple, vendre les excédents ou acheter les récoltes manquantes sur le marché).

Voir aussi

• Programmation mathématique
• Recherche opérationnelle
• Optimisation robuste
• Programmation dynamique
• Théorie du contrôle