Solution optimale
Solution optimale — en recherche opérationnelle, en optimisation et en théorie de la décision, il s'agit d'une solution réalisable (c'est-à-dire qui satisfait toutes les contraintes du problème) qui fournit une valeur extrémale (maximale ou minimale, selon la formulation du problème) pour la fonction objectif.
La recherche de la solution optimale est l'objectif principal de la résolution de la plupart des problèmes d'optimisation.
Essence et caractéristiques
Une solution optimale possède deux caractéristiques clés :
- Réalisabilité : Elle doit satisfaire toutes les contraintes imposées aux variables du modèle. En d'autres termes, une solution optimale appartient toujours à l'ensemble des solutions réalisables (ESR).
- Optimalité par rapport à la fonction objectif : Parmi toutes les solutions réalisables, elle assure la meilleure valeur (maximale ou minimale) de la fonction objectif, qui formalise le critère d'optimalité.
Toute solution réalisable n'est pas nécessairement optimale, mais toute solution optimale doit obligatoirement être réalisable.
Lien avec l'ensemble des solutions réalisables
L'ensemble des solutions réalisables (ESR) représente l'ensemble de toutes les alternatives (ensembles de valeurs pour les variables) qui satisfont les contraintes du problème. La solution optimale est un point (ou des points) dans cet ensemble où la fonction objectif atteint son extremum. Si l'ESR est vide, le problème n'a ni solution réalisable, ni, par conséquent, de solution optimale.
Rôle de la fonction objectif et des contraintes
- Les contraintes définissent l'ensemble des solutions possibles (l'ESR).
- La fonction objectif détermine laquelle de ces solutions possibles est la meilleure (optimale).
Sans fonction objectif, il est impossible de déterminer laquelle des solutions réalisables est optimale. Sans contraintes, le problème peut être trivial ou ne pas avoir de solution optimale finie (par exemple, la maximisation d'une fonction linéaire sans contraintes).
Unicité de la solution optimale
La solution optimale n'est pas toujours unique. Dans certains problèmes (par exemple, en programmation linéaire, si la fonction objectif est parallèle à l'une des contraintes actives), il peut exister une infinité de solutions optimales ayant la même valeur de la fonction objectif. Cependant, la valeur de la fonction objectif au point (ou aux points) optimal est toujours unique (si un optimum existe).
Méthodes de recherche
Pour trouver des solutions optimales en recherche opérationnelle, diverses méthodes mathématiques sont utilisées, en fonction du type de modèle :
- Algorithme du simplexe (pour la programmation linéaire)
- Méthodes de descente de gradient et autres méthodes numériques (pour la programmation non linéaire)
- Méthode de séparation et évaluation, méthodes des plans coupants (pour la programmation en nombres entiers)
- Méthodes de programmation dynamique
Dépendance au modèle
Il est important de comprendre qu'une solution est optimale uniquement dans le cadre du modèle mathématique adopté. Si le modèle ne reflète pas adéquatement la situation réelle (la fonction objectif est mal choisie, des contraintes ou des dépendances importantes n'ont pas été prises en compte), alors la solution optimale formellement trouvée peut s'avérer inefficace, voire erronée en pratique.
Optimalité dans les problèmes multicritères
Dans les problèmes avec plusieurs fonctions objectif (optimisation multiobjectif), la notion de solution optimale unique est souvent remplacée par la notion d' optimalité de Pareto. Une solution Pareto-optimale est une solution réalisable pour laquelle il est impossible d'améliorer la valeur d'une fonction objectif sans détériorer la valeur d'au moins une autre.
Voir aussi
- Recherche opérationnelle
- Optimisation
- Modèle mathématique
- Fonction objectif
- Contraintes
- Ensemble des solutions réalisables
- Solution réalisable
- Critère
- Théorie de la décision
- Optimisation multiobjectif
- Optimalité de Pareto
- Extremum
Bibliographie
- Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)