Semestre 6 – Introduction à la recherche opérationnelle : modélisation et optimisation

Objectifs

L’objectif de ce cours est d’initier les étudiants aux connaissances de base en Recherche Opérationnelle sur les deux facettes Modélisation et Optimisation.

Prérequis

Mathématiques Discrètes 2 du semestre 4.

Contenu pédagogique de l’UE

Cette unité d’enseignement vise à présenter les éléments de base de la Recherche Opérationnelle. Elle s’articule autour de deux parties : Modélisation et Optimisation.

Modélisation

Dans la première partie on s’intéressera à la présentation de différentes techniques de modélisation des problèmes classiques de la RO (graphes, programmation mathématique, …). Les points qui seront abordés dans le cadre de ce cours sont :

  • La difficulté et la complexité des problèmes fondamentaux de la RO.
  • La modélisation des problèmes classiques (comme l’argent de poche, le sac-à-dos, l’emploi du temps, la gestion de stock…) sous forme d’une programmation linéaire / linéaire en nombres entiers et l’utilisation du logiciel XPRESS pour trouver la solution (notons que les méthodes numériques pour la programmation linéaire seront enseignées en Master 1).
  • La modélisation des mêmes problèmes en exploitant les techniques basées sur les graphes vues en L2 (chemins optimaux, PERT, arbre de recouvrant de coût minimum…).
Optimisation

Dans la deuxième partie on s’intéressera à l’initiation aux différentes techniques de résolution des problèmes présentés dans la première par tie (méthodes de simulation heuristiques et métaheuristiques et méthodes d’exploration implicite…). Les points qui seront abordés dans le cadre de ce cours sont :

  • Les méthodes heuristiques (principe, construction, optimalité locale, voisinage…).
  • Les méthodes métaheuristiques (algorithmes évolutionnistes, méthodes de voisinage, recherche tabou, recuit simulé…).
  • Les méthodes exactes (branch-and-bound, programmation dynamique, programmation en nombres mixtes…).

Exemple de réalisation

Projet « Placement des lettres d’un clavier » : réalisé dans le cadre de Optimisation. Le placement des lettres se fait par un algorithme de recherche itérative par voisinage. Plus d’informations peuvent être trouvées ici.

Umut