Recherche opérationnelle - Définition
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
La liste des auteurs de cet article est disponible ici.
Principales (classes de) méthodes
- Algorithmes polynomiaux
-
- Certains problèmes ont de bonnes caractéristiques qui permettent de les résoudre à l'aide d'une formule de récurrence. Les méthodes de programmation dynamique peuvent alors éventuellement permettre de résoudre le problème avec une complexité polynomiale ou pseudo-polynomiale.
- Processus stochastiques
-
- Les processus stochastiques concernent tous les problèmes aléatoires, en particulier des problèmes de fiabilité (de systèmes, de composants électroniques…) et des phénomènes d'attente.
- Simulation informatique
-
- La simulation est souvent employée pour résoudre des problèmes de RO, notamment dans le milieu non académique.
- Programmation linéaire et non linéaire
-
- La programmation linéaire est très souvent utilisée pour résoudre des problèmes combinatoires. Elle permet de résoudre très efficacement les problèmes dans lesquels les variables sont continues. Lorsqu'il y a des variables discrètes, programmation linéaire et méthodes arborescentes (voir ci-après) peuvent être combinées.
- La programmation non-linéaire peut aussi être utilisée. La possibilité d'utiliser des contraintes ou des fonctions objectifs non linéaires offre une puissance de modélisation très importante mais les algorithmes de résolution des programmes non linéaires sont significativement moins efficaces que ceux de la programmation linéaire.
- Méthodes arborescentes
-
- Les méthodes de type A* ou branch and bound sont couramment utilisées pour trouver la solution exacte d'un problème de recherche opérationnelle. Pour une résolution efficace, un soin particulier est apporté au calcul de bornes supérieures ou inférieures pour la valeur de la solution.
-
- La programmation par contraintes permet de mettre en œuvre rapidement et efficacement de telles méthodes de recherche arborescente. Plusieurs bibliothèques (logiciels) d'optimisation commerciales ou non reposent sur cette approche (ILOG Solver, Chip, Mozart/Oz, FaCiLe). De nombreux logiciels d'optimisation de problèmes réels utilisent ainsi cette technologie.
- Heuristiques et métaheuristiques
-
- Lorsque la solution optimale ne peut être obtenue en un temps raisonnable, on a souvent recours à des méthodes approchées de type heuristique ou métaheuristique.
