EMN - Ecole des Mines de Nantes

Contexte

La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l'ensemble des méthodes et techniques rationnelles d'analyse et de synthèse des phénomènes d’organisation utilisables pour élaborer de meilleures décisions. Le corpus de la recherche opérationnelle se présente comme une « boîte à outils », un ensemble d’ « objets » qu’il faut savoir combiner afin de modéliser puis résoudre un problème concret. La recherche opérationnelle peut aider le décideur lorsque celui-ci est confronté à un problème d’optimisation combinatoire (comprenant un grand nombre de solutions admissibles parmi lesquelles on cherche une solution optimale ou proche de l'optimum) ou continue, ou encore à un problème aléatoire (consistant à trouver une solution optimale face à un problème qui se pose en termes incertains).

Apprendre à appréhender ce genre de problèmes est essentiel pour un ingénieur en génie des systèmes industriels puisqu’il aura comme mission principale d'éliminer les pertes de temps, d'argent, de matériels, d'énergie et d'autres matières premières des organisations.

Cette UV est consacrée principalement à la modélisation et à la résolution de problèmes combinatoires difficiles. On notera qu’une première classe de méthodes de Recherche Opérationnelle a été vue en FI2 dans l’UV Automatique et Optimisation (module de programmation linéaire). Des méthodes permettant de résoudre des problèmes aléatoires seront passées en revue dans le module « Optimisation dans l’incertain » de l’UV «Recherche Opérationnelle 2 » de 4ième année pour l’option GOPL.

Objectifs

Objectifs généraux

L’objectif de cette UV est de faire connaître les outils standards de la recherche opérationnelle, d’apprendre aux élèves comment modéliser un problème avec les outils appropriés, comment le résoudre par diverses techniques et méthodes d’optimisation, et comment analyser et interpréter les résultats obtenus. Les problèmes abordés resteront « académiques », pour bien mettre l'accent sur les méthodes (des applications plus complexes seront vues dans d'autres cours faisant suite à cette UV).

Objectifs operationnels

A l’issue de l’UV, les élèves seront capables de reconnaître des situations où la RO pourrait se révéler un instrument utile. Ils maîtriseront un certain nombre de méthodes de modélisation et de résolution, et seront capables de mieux comprendre les possibilités et les limitations des approches classiques.

Competences requises

Compétences requises

- Mathématique de base (algèbre linéaire, analyse)
- Algorithmique de base
- Programmation linéaire

Unites de valeurs cibles

Codes UVs cibles

MAT03 : UV Mathématiques (CB1), pour les aspects mathématiques
INF03 : UV Informatique (CB1), pour les aspects algorithmiques
AEP05 : UV Automatique électronique et productique (CB2), pour la programmation linéaire

UVs cibles

Les compétences et connaissances acquises dans cette UV seront développées et appliquées, en particulier dans les domaines de la logistique et de la production, lors des UV :
- « Management des opérations » (FI3) ;
- « Recherche Opérationnelle 2 » (FI4) ;
- « Management de la logistique » (FI4).

Contenu et organisation pedagogique

Contenu de l'UV

0) « Introduction à la Recherche Opérationnelle » (2h30)
- déroulement de l'UV
- panorama général de l'optimisation et la RO
- notions de base de l'optimisation

1) « Complexité » (6h15)
- complexité d'un algorithme
- complexité d'un problème

2) « Modèles et algorithmes de graphes » (23h45)
- terminologie de base en théorie des graphes
- manipulations de base : tri topologique, exploration, tests de structure
- problèmes « faciles » (arbres couvrants, chemins optimaux, ...)
- problèmes « difficiles » (voyageur de commerce, coloration, ...)

3) « Programmation Linéaire 2 » (11h15)
- modélisation en PLNE
- un mot sur la programmation non linéaire

4) « Méthodes de résolutions » (11h15)
- bornes (calcul, utilité)
- méthodes approchées
. heuristiques, approximations
. recherche locale et méta-heuristiques
- méthodes exactes
. programmation dynamique
. méthodes arborescentes, évaluation/séparation, etc

5) Résolution de problèmes (30h)
- travaux dirigés (10h)
- travaux pratiques (10h)
- projet (10h)

Activités pédagogiques

- Complexité : cours-TD
- Modèles et algorithmes de graphes : cours et TD
- Programmation linéaire : cours et TP
- Méthodes de résolutions : TD, TP, projet
- Projet : Ap/TP

Supports pédagogiques

Les supports de cours diffusés sont disponibles sur Campus. En, particulier, dans l'« Introduction à la Recherche Opérationnelle », on trouvera une sélection d'ouvrages pertinents pour l'UV, disponibles au CDI de l'EMN.

Critere et mode d'evaluation

Critères d"évaluation

Les évaluations (prévisionnelles) seront réparties comme suit :
- un DS pour le cours Complexité
- un DS pour le cours Modèles et Algorithmes de Graphes
- un TP noté pour le cours Programmation Linéaire 2
- un DS commun pour les cours Programmation Linéaire 2 et Méthodes de résolution
- un TP sanctionné par un rapport écrit pour la partie Résolution de problèmes
- un projet sanctionné par une soutenance orale pour la partie Résolution de problèmes

Nombre d'évaluations

6