Programmation par objectifs stochastique — Optimisation de buts multiples en situation d'incertitude
- Introduite par
- Contini, B. (building on Charnes & Cooper's chance-constrained programming)
- Année
- 1968
- Type
- Stochastic multi-goal optimization
- Famille
- Simulation / optimization
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La programmation par objectifs stochastique (SGP) étend la programmation par objectifs classique pour gérer l'incertitude dans les cibles des objectifs, les coefficients des contraintes ou les paramètres du membre de droite.
En intégrant des contraintes probabilistes et des composantes stochastiques dans la fonction objectif, elle trouve des solutions qui satisfont plusieurs objectifs à des niveaux de probabilité acceptables, la rendant ainsi appropriée pour les problèmes de décision où les données sont intrinsèquement incertaines ou variables.
L’intuition derrière la méthode
La programmation par objectifs classique pose la question : pouvons-nous nous rapprocher simultanément de chaque objectif ? La programmation par objectifs stochastique pose la même question mais reconnaît que le monde est incertain — les objectifs peuvent changer, les ressources peuvent varier et les données peuvent être bruitées. Plutôt que d'optimiser pour un scénario fixe unique, la SGP recherche des solutions qui performent bien en moyenne ou qui atteignent chaque objectif avec une probabilité spécifiée. Considérez-la comme l'élaboration du meilleur plan possible tout en tenant compte honnêtement de ce que vous ignorez.
Histoire
La programmation par objectifs a été introduite par Charnes et Cooper à la fin des années 1950. Contini (1968) l'a formellement étendue aux contextes stochastiques en utilisant des idées de programmation par contraintes de chance. Les décennies suivantes ont vu des applications croissantes en finance, agriculture et politique publique. La méthode a acquis une assise théorique plus solide grâce à ses liens avec l'optimisation robuste développée dans les années 1990 et 2000.
Quand l’utiliser
Utiliser la programmation par objectifs stochastique lorsqu'un problème de décision comporte plusieurs objectifs conflictuels, qu'au moins certains paramètres (demandes, coûts, rendements) sont incertains et peuvent être caractérisés par des distributions de probabilité, et que les décideurs ont besoin de garanties exprimées en niveaux de confiance plutôt qu'en bornes du pire cas. Elle est bien adaptée à la planification de la chaîne d'approvisionnement, à l'allocation des ressources de santé, à la gestion de portefeuille financier avec des objectifs multiples et à la planification agricole en situation d'incertitude météorologique. NE PAS l'utiliser lorsque les objectifs sont véritablement incommensurables et ne peuvent être pondérés, lorsqu'aucune information distributionnelle n'est disponible (utiliser l'optimisation robuste à la place), lorsque le problème n'a qu'un seul objectif (utiliser la programmation stochastique), ou lorsque le nombre de scénarios est si grand que les reformulations déterministes deviennent intraitable.
Limites et points d’attention
- Nécessite la connaissance des paramètres distributionnels (moyennes, variances) qui peuvent être difficiles à estimer avec précision.
- Les distributions non normales ou les contraintes de chance conjointes peuvent rendre la reformulation déterministe intraitable, nécessitant des approches basées sur des scénarios ou des simulations.
- Le choix des niveaux de confiance alpha_i et des poids d'objectifs w_i est intrinsèquement subjectif et peut fortement influencer les résultats.
- Plus exigeante en calcul que la programmation par objectifs déterministe, surtout pour les problèmes à grande échelle ou non linéaires.
- L'interprétation des compromis entre objectifs probabilistes peut être difficile pour les parties prenantes non techniques.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Gère simultanément plusieurs objectifs conflictuels dans un cadre d'optimisation unique.
- Permet la spécification explicite des niveaux de risque acceptables (confiance) pour chaque objectif ou contrainte.
- Sous des hypothèses de normalité, les contraintes de chance se réduisent à des contraintes de cône de second ordre traitables, résolubles avec des solveurs standards.
- Fournit aux décideurs la probabilité d'atteinte des objectifs, offrant une information plus riche qu'une solution à scénario unique.
- Englobe la programmation par objectifs déterministe comme cas particulier (niveau de confiance = 1 avec des paramètres fixes).
- Théoriquement bien fondée, reliant les littératures sur la programmation par contraintes de chance et l'optimisation robuste.
Applications
- Planification agricole : allocation de terres et de ressources entre cultures en situation d'incertitude pluviométrique et de prix.
- Allocation des ressources de santé : planification du personnel et des lits tout en atteignant les objectifs de niveau de service en situation de demande de patients incertaine.
- Gestion de la chaîne d'approvisionnement : planification de la production et des stocks avec des rendements, des délais et des demandes incertains.
- Optimisation de portefeuille financier avec des objectifs multiples (rendement, risque, liquidité) en situation d'incertitude de marché.
- Planification des systèmes énergétiques : équilibrage des objectifs de coût, de fiabilité et d'émissions compte tenu de la production renouvelable incertaine.
- Budgétisation municipale : allocation des fonds publics entre départements avec des revenus et des dépenses incertains.
Comment ça marche
Comment ça marche
Définir les variables de décision, les objectifs aspirationnels multiples (cibles) et toute contrainte stricte. Chaque objectif i est exprimé comme : f_i(x) + d_i^- - d_i^+ = g_i, où d_i^- et d_i^+ sont les variables d'écart négatif et positif par rapport à la cible g_i. Attribuer des poids de priorité reflétant l'importance relative de l'atteinte de chaque objectif.
Identifier quels paramètres sont incertains : les cibles d'objectifs g_i, les coefficients des contraintes ou les coefficients de la fonction objectif peuvent être modélisés comme des variables aléatoires avec des distributions connues ou estimées (par exemple, normale, uniforme, empirique). Spécifier les hypothèses distributionnelles basées sur des données historiques ou un jugement d'expert.
Convertir les contraintes incertaines en contraintes de chance (probabilistes). Pour une contrainte stochastique impliquant un paramètre aléatoire b_i avec une distribution F, exiger P(g_i(x) <= b_i) >= alpha_i, où alpha_i est un niveau de confiance spécifié par l'utilisateur (par exemple, 0,90 ou 0,95). Sous des hypothèses de normalité, celles-ci peuvent être reformulées en contraintes déterministes de cône de second ordre.
Formule
P(g_i(x) \leq b_i) \geq \alpha_i
Résoudre le problème d'optimisation résultant (éventuellement reformulé) : minimiser la somme pondérée des écarts min sum_i (w_i^+ d_i^+ + w_i^- d_i^-) sous réserve des équivalents déterministes des contraintes de chance et de toute contrainte stricte restante. Utiliser des solveurs LP, MILP ou non linéaires en fonction de la structure du problème.
Formule
\min \sum_{i} (w_i^+ d_i^+ + w_i^- d_i^-)Évaluer la solution en vérifiant les niveaux d'atteinte des objectifs, la probabilité de satisfaction des contraintes et la sensibilité aux hypothèses distributionnelles. Effectuer une validation post-hoc par simulation de Monte-Carlo en échantillonnant des réalisations de paramètres et en vérifiant que la solution atteint les objectifs aux niveaux de confiance indiqués dans des scénarios simulés.
Pièges courants
- Supposer la normalité des paramètres incertains sans validation empirique peut produire des garanties de confiance trompeuses.
- Définir des niveaux de confiance trop élevés (par exemple, 0,999) ramène effectivement le modèle à une formulation déterministe conservatrice, annulant l'objectif de la modélisation stochastique.
- Confondre la programmation par objectifs sous contraintes de chance avec la programmation par objectifs robuste — les deux traitent l'incertitude différemment et ne sont pas interchangeables.
- Ne pas valider la solution stochastique par simulation de Monte-Carlo laisse le risque réel de violation des objectifs inconnu.
- Ignorer la corrélation entre les paramètres incertains peut produire des solutions infaisables ou trop optimistes.
Questions fréquentes
En quoi la programmation par objectifs stochastique diffère-t-elle de la programmation par objectifs classique ?
La programmation par objectifs classique suppose que tous les paramètres (objectifs, contraintes, coûts) sont connus avec certitude. La programmation par objectifs stochastique permet à certains paramètres d'être des variables aléatoires, en intégrant des contraintes probabilistes qui exigent que les objectifs soient satisfaits avec un niveau de confiance spécifié plutôt qu'exactement.
Quelle hypothèse distributionnelle est la plus couramment utilisée ?
La normalité est l'hypothèse la plus courante car elle permet de reformuler exactement les contraintes de chance en contraintes déterministes de cône de second ordre. Lorsque les données suggèrent des distributions non normales, des approches basées sur des scénarios ou des simulations sont utilisées à la place.
Comment choisir les niveaux de confiance alpha_i pour chaque contrainte de chance ?
Les niveaux de confiance reflètent la tolérance au risque du décideur pour chaque objectif. Des valeurs de 0,90 à 0,95 sont courantes en pratique. Des valeurs plus élevées rendent le problème plus conservateur et peuvent nécessiter de relâcher d'autres objectifs ; des valeurs plus faibles autorisent plus de risque mais peuvent conduire à des résultats inacceptables.
La programmation par objectifs stochastique peut-elle gérer des variables de décision entières ?
Oui. Lorsqu'elle est combinée avec des variables entières, le problème devient la programmation par objectifs stochastique entière, qui est plus difficile à résoudre mais reste traitable pour des instances de taille modérée en utilisant la méthode de séparation et d'évaluation avec des reformulations de contraintes de chance.
Dois-je utiliser la programmation par objectifs stochastique ou l'optimisation robuste lorsque j'ai des paramètres incertains ?
Si vous disposez d'informations distributionnelles fiables et souhaitez des garanties probabilistes, la SGP est appropriée. Si vous ne connaissez que des ensembles d'incertitude (bornes) et souhaitez des garanties du pire cas sans hypothèses distributionnelles, l'optimisation robuste est préférable. Lorsque les deux sont réalisables, comparer les solutions des deux approches est une bonne pratique.
Méthodes associées
Sources
Contini, B. (1968). A stochastic approach to goal programming. Operations Research, 16(3), 576–586.
Ouvrir la référence DOICopié.Charnes, A., Cooper, W. W. (1959). Chance-constrained programming. Management Science, 6(1), 73–79.
Ouvrir la référence DOICopié.