Skip to content
Retour aux résultats

Programmation Linéaire Stochastique — Optimisation sous Incertitude avec Paramètres Aléatoires

Introduite par
George B. Dantzig
Année
1955
Type
Stochastic optimization model
Famille
Simulation / optimization

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La Programmation Linéaire Stochastique (PLS) étend la programmation linéaire classique aux situations où certains paramètres du modèle — coûts, demandes, disponibilité des ressources — sont incertains et modélisés comme des variables aléatoires.

En optimisant les coûts attendus sur une distribution de probabilité de scénarios, la PLS produit des décisions qui restent réalisables et quasi-optimales pour une gamme de futurs possibles, plutôt que pour un seul état du monde supposé.

L’intuition derrière la méthode

La programmation linéaire classique suppose que chaque coefficient est connu avec précision. En pratique, la demande future, les prix et les rendements sont incertains. La PLS intègre cette incertitude directement dans le modèle : au lieu d'optimiser pour un scénario fixe, le planificateur choisit des actions de premier stade maintenant, observe quel scénario se matérialise, puis prend des actions de recours pour corriger tout déficit ou surplus. L'objectif minimise le coût total attendu sur tous les scénarios, équilibrant les coûts d'engagement par rapport aux coûts de recours attendus. Ceci reflète la logique managériale réelle — vous décidez aujourd'hui ce qu'il faut pré-commander, et demain vous pouvez acheter plus à un prix fort ou vendre le surplus à prix réduit.

Histoire

La programmation stochastique a été pionnière George Dantzig, qui a introduit le modèle à deux stades en 1955 peu après avoir développé la méthode du simplexe. Beale (1955) a indépendamment proposé des idées similaires. Le domaine a été systématisé par le livre influent de Birge et Louveaux en 1997 et par le développement de l'algorithme de décomposition en L (Benders) dans les années 1960-1980. La PLS sous-tend maintenant les décisions opérationnelles dans l'énergie, la logistique et la finance dans le monde entier.

Quand l’utiliser

Utiliser la PLS lorsque : (1) les paramètres d'entrée clés sont véritablement incertains et peuvent être caractérisés par une distribution de probabilité ou un ensemble de scénarios empiriques ; (2) les décisions doivent être prises avant que l'incertitude ne se résolve, mais des actions correctives sont possibles par la suite moyennant un coût ; (3) l'objectif et les contraintes sont linéaires par rapport aux variables de décision. Les applications typiques incluent la planification de la production, la conception de chaînes d'approvisionnement, la gestion de l'énergie, et l'optimisation de portefeuille. NE PAS utiliser la PLS lorsque : l'incertitude ne peut être quantifiée probabilistiquement (utiliser l'optimisation robuste à la place) ; la relation entre les décisions et les résultats est non linéaire ou entière (utiliser la programmation entière stochastique ou la programmation dynamique stochastique) ; l'ensemble de scénarios est trop grand pour être énuméré et la décomposition est calculatoirement infaisable ; ou lorsqu'une analyse de sensibilité déterministe plus simple suffit à comprendre l'impact de l'incertitude.

Limites et points d’attention

  • Nécessite de spécifier une distribution de probabilité ou un ensemble de scénarios pour les paramètres incertains — cette hypothèse distributionnelle est souvent difficile à valider.
  • La charge de calcul croît rapidement avec le nombre de scénarios et les variables de premier stade ; les grands problèmes nécessitent la décomposition et des ressources de solveur importantes.
  • Restreinte à des objectifs et contraintes linéaires ; les structures non linéaires ou entières nécessitent des extensions qui ajoutent une complexité supplémentaire.
  • L'objectif de valeur attendue peut ignorer les risques extrêmes ; les variantes averses au risque (CVaR, contraintes de chance) ajoutent une surcharge de modélisation et de calcul.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Incorpore directement l'incertitude probabiliste dans l'optimisation, produisant des décisions robustes à travers les scénarios plutôt que pour un seul futur supposé.
  • Le cadre à deux stades reflète étroitement les processus de décision réels : s'engager maintenant, s'adapter plus tard avec recours.
  • La Valeur de la Solution Stochastique (VSS) et l'EVPI fournissent des métriques fondées pour communiquer le bénéfice de la modélisation de l'incertitude.
  • Bien supportée par des algorithmes matures (méthode en L / décomposition de Benders) et des solveurs commerciaux (CPLEX, Gurobi).
  • Évolue vers de grands problèmes pratiques via la décomposition ; parallélisable à travers les scénarios.

Applications

  • Planification des systèmes d'énergie électrique et engagement des unités sous la production renouvelable et la demande incertaines.
  • Conception de réseaux de chaînes d'approvisionnement avec une demande client, des délais de livraison ou des coûts de transport incertains.
  • Planification des cultures et de l'irrigation sous des précipitations et des prix des matières premières incertains.
  • Optimisation de portefeuille financier avec des rendements d'actifs incertains sous contraintes budgétaires et réglementaires.
  • Gestion des revenus des compagnies aériennes et planification des équipages sous une demande de passagers incertaine.
  • Pré-positionnement de fournitures de secours en logistique humanitaire avant des scénarios de catastrophe incertains.

Comment ça marche

Comment ça marche

1

Formuler le modèle à deux stades : les variables de premier stade x représentent les décisions ici et maintenant prises avant que l'incertitude ne soit résolue ; l'objectif minimise le coût de premier stade c^T x plus le coût de recours attendu E[Q(x,xi)] sur le vecteur aléatoire xi. Les contraintes Ax = b doivent être respectées pour les décisions de premier stade, quel que soit le scénario.

Formule
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0
2

Représenter le vecteur aléatoire xi via un ensemble discret de scénarios {xi_1, ..., xi_S} chacun avec une probabilité p_s dont la somme est 1. Les scénarios peuvent être tirés de données historiques, d'avis d'experts, ou d'échantillonnage Monte Carlo. La qualité de l'ensemble de scénarios détermine de manière critique la qualité de la solution ; des techniques de réduction de scénarios (par exemple, le clustering par distance de Wasserstein) sont couramment appliquées pour maintenir la taille du problème traitable.

3

Pour chaque scénario xi_s, résoudre le sous-problème de recours : étant donné la décision de premier stade x, trouver l'action corrective la moins chère y_s satisfaisant W y_s = h(xi_s) - T(xi_s) x, y_s >= 0. Si aucun recours réalisable n'existe, une pénalité importante (ou l'inadmissibilité) est encourue, signalant que la décision de premier stade était trop agressive.

Formule
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0
4

Résoudre la forme extensive complète (tous les scénarios empilés en un grand PL) pour des ensembles de scénarios petits à moyens, ou appliquer la décomposition de Benders (méthode en L) pour de grands ensembles. La méthode en L ajoute itérativement des coupes d'optimalité et de faisabilité à un problème maître jusqu'à convergence, exploitant la structure bloc-diagonale des sous-problèmes de scénarios.

5

Évaluer la qualité de la solution via la Valeur de la Solution Stochastique (VSS) — le gain par rapport à la solution déterministe de la valeur moyenne — et la Valeur Attendue de l'Information Parfaite (EVPI) — la borne supérieure de ce que vaudrait une connaissance parfaite du futur. Rapporter la décision de premier stade x*, le coût total attendu, et les coûts de recours par scénario pour communiquer le profil de risque aux décideurs.

Pièges courants

  • Utiliser trop peu de scénarios produit une solution biaisée qui fonctionne mal hors échantillon ; toujours valider avec des tests hors échantillon.
  • Confondre la solution déterministe de valeur moyenne (en utilisant les valeurs moyennes) avec la solution stochastique — la VSS peut être importante même lorsque les paramètres semblent stables.
  • Ignorer la faisabilité du recours : si le sous-problème de second stade peut être infaisable pour certains scénarios, le modèle nécessite des contraintes de recours complètes ou des pénalités explicites.
  • Sur-ajustement à la distribution historique des scénarios sans tests de résistance contre les scénarios extrêmes ou adverses, en particulier dans les applications de chaîne d'approvisionnement ou financières.
  • Traiter la PLS comme un remplacement direct de l'optimisation robuste lorsque le décideur est en fait neutre à l'incertitude plutôt qu'averse à la valeur attendue.

Questions fréquentes

Quelle est la différence entre la programmation linéaire stochastique et l'optimisation robuste ?

La PLS minimise le coût attendu sur une distribution de probabilité de scénarios et autorise des actions de recours après la résolution de l'incertitude. L'optimisation robuste optimise plutôt le pire cas sur un ensemble d'incertitude sans supposer de distribution de probabilité et produit généralement une solution fixe unique qui est réalisable pour tous les scénarios. La PLS est préférable lorsque les probabilités peuvent être estimées ; l'optimisation robuste est préférable lorsque seul l'ensemble d'incertitude est connu ou lorsque la protection contre les risques extrêmes est primordiale.

Combien de scénarios sont typiquement nécessaires ?

Cela dépend de la dimension du problème et de la complexité distributionnelle. Des dizaines à quelques centaines de scénarios suffisent souvent pour les problèmes de planification s'ils sont générés intelligemment (par exemple, via l'appariement des moments ou la réduction de scénarios). L'approximation par moyenne d'échantillon (SAA) basée sur Monte Carlo peut nécessiter des milliers de scénarios pour des solutions de haute précision, avec des intervalles de confiance guidant la convergence.

La PLS peut-elle gérer des décisions entières ou binaires ?

Pas directement — les variables entières nécessitent la Programmation Entière Stochastique (PES) ou la Programmation Mixte Entière Stochastique (PMES), qui sont considérablement plus difficiles sur le plan calculatoire. La PLS s'applique uniquement lorsque toutes les variables de décision sont continues.

Que mesure la Valeur de la Solution Stochastique (VSS) ?

VSS = EEV - RP, où EEV est le coût attendu de la solution déterministe de valeur moyenne évaluée sur tous les scénarios, et RP est l'optimum stochastique réel (problème de recours). Une VSS élevée indique qu'ignorer l'incertitude et utiliser les paramètres moyens conduit à des résultats considérablement moins bons.

Quels solveurs et logiciels supportent la programmation linéaire stochastique ?

Les solveurs commerciaux tels que CPLEX et Gurobi peuvent résoudre directement la forme extensive. Les frameworks open-source incluent les lecteurs de format SMPS, PySP (partie de Pyomo), et le package Julia StochasticPrograms.jl. Pour les problèmes à grande échelle, des implémentations personnalisées de décomposition en L sont courantes dans la recherche et l'industrie.

Méthodes associées

Sources

  1. Dantzig, G. B., & Madansky, A. (1961). On the solution of two-stage linear programs under uncertainty. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1, 165–176.

    Ouvrir la référence de la publication
    Copié.
  2. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN : 9780387982175
    Copié.