EC0707SI0204A - RECHERCHE OPERATIONNELLE

Objectifs

Ce cours aborde les problèmes de recherche de solution et de prise de décision dans des contextes où il s'agit de trouver des valeurs numériques à un ensemble de variables de décision. On s'intéressera d'abord au cas des domains continus (valeurs réelles) à travers la méthode classique du Simplexe. On se focalisera ensuite sur les problèmes dits d'optimisation combinatoire, c'est-à-dire à la fois discrets (variables à valeurs entières) et difficiles (nombre de « combinaisons » possibles exponentiel). 
Ces problèmes qui se retrouvent dans de nombreuses applications industrielles présentant des enjeux  économiques majeurs : positionnement d'antennes, agencement d'ateliers, tournées de ramassage des déchets, choix d'investissement pour une entreprise, etc.  Ces applications sont des exemples de problèmes académiques bien identifiés, dont on proposera une modélisation mathématique. Après quoi on se concentrera sur quelques problèmes types qui serviront d'illustrations aux méthodes abordées. Les avantages et inconvénients de ces diverses méthodes seront comparés, en termes d'efficacité, d'optimalité, de simplicité d'implémentation, etc

Présentation

- Méthode du Simplexe
- Méthodes de recherche arborescente et problèmes de satisfaction de contraintes
- Optimisation combinatoire : problèmes types, modélisation mathématique, applications industrielles
- le sac-à-dos, extension au bin-packing
- le voyageur de commerce, extension aux tournées de véhicule
- autres : affectation -  localisation - couverture d'ensemble
- Méthodes constructives exactes pour l'optimisation combinatoire
- méthodes exactes : le Branch & Bound (relaxation linéaire, algorithme de Little, etc) et l'algorithme A*
- méthodes approchées : recherche heuristique gloutonne ; amélioration par Recherche à Divergence Limitée

Pré-requis obligatoires

Examens

(1*DS1)/1

DS1 : Devoir Surveillé 1

Syllabus

- J. Dréo, A. Pétrowski, P. Siayy, E. Taillard, Méta-heuristiques pour l'optimisation difficile, Eyrolles, 2003.
- Vidal Cohen, La Recherche Opérationnelle, Que-sais-je ?, 1995.
- Jean-Baptiste Miriart-Urruty, L'Optimisation, Que sais-je ?, 1996.