- Cours : Recherche Opérationnelle (SM502)
- Semestre : Septembre à janvier
- Prérequis : connaissances élémentaires en algèbre linéaire (méthode du pivot de Gauss, famille libre, famille génératrice)
- Heures : 30h en face à face

Résumé :
Un grand nombre de situations, dans des domaines très différents, mènent à des problèmes d'optimisation, c'est-à-dire à des problèmes où une certaine quantité doit être maximisée ou minimisée sous des contraintes particulières. Ce cours présente certaines méthodes classiques de recherche opérationnelle qui donnent la stratégie optimale à adopter (ou tout du moins aident à la prise de décision).

Objectifs pédagogiques :
- Résoudre un problème de transport grâce à la méthode du marche-pied (stepping stone)
- Formuler d'autres classes de problèmes comme des problèmes de transport
- Utiliser le tableau du simplexe pour résoudre un problème de programmation linéaire
- Reconnaître les problèmes d'optimisation qui peuvent être résolus grâce à la programmation linéaire
- Résoudre un problème de programmation linéaire entière avec la méthode des coupures
- Calculer le dual d'un programme linéaire et l'interpréter
- Travailler sur des jeux matriciels à somme nulle

Plan de cours :
1. Problèmes de transport (1 CM et 1 TD)
2. Programmation linéaire (2 CM et 3 TD)
3. La dualité (1 CM et 1 TD)
4. Programmation linéaire entière (1 CM et 1 TD)

Compétences visées :
- Analyser les besoins en vue de la conception ou de l'évolution de produits et services numériques (utiliser les connaissances scientifiques et techniques pour formaliser un problème, interpréter et reformuler un sujet)
- Concevoir des solutions numériques basées sur l'état de l'art (décomposer un problème en sous-problèmes)
- Mettre en œuvre des solutions numériques (concevoir et exécuter des tests)

---

Il y a potentiellement un cours en Théorie des graphes qui suit au second semestre (février à mai), à discuter avec l'école si cela vous intéresse aussi.

Résumé :
Dans un grand nombre de domaines et d'applications, la modélisation par des graphes représente un outil très puissant. Elle est rencontrée dans énormément d'applications quotidiennes (recherche de trajet dans le métro parisien, via Michelin, etc.). Ce module permet d'apprendre les possibilités de modélisation de problèmes en termes de graphes. Il contient l'apprentissage théorique des bases et une étude de domaines majeurs d'utilisation : recherche de chemins optimaux (méthode générique, arbre de chemins, algorithmes de Dijkstra, Bellman et Floyd), représentation des contraintes d'ordonnancement de tâches et calcul de calendriers (modélisations PERT et MPM, calculs au plus tôt et au plus tard), simplification d'une configuration au moyen d'un arbre couvrant et calcul d'arbre couvrant de poids minimum (méthodes de Kruskal et Prim).

Objectifs pédagogiques :
- Modéliser par des graphes des problèmes logiques, mathématiques et pratiques
- Expliquer les notions vues en cours (chemins, circuits, degrés, prédécesseurs, successeurs, application multivoque, application multivoque réciproque)
- Représenter un graphe par sa matrice d'adjacence, d'incidence ou par sa liste d'adjacence
- Expliquer le fonctionnement des algorithmes présentés en cours et en TD (Roy-Warshall, Dijkstra, Bellman, recherche de rang, Floyd, algorithme de l'ordonnancement, Prim, Kruskal) et les appliquer à des exemples concrets
- Résoudre des problèmes à l'aide des algorithmes de coloration
- Développer un projet basé sur un de ces algorithmes

Plan de cours :

1. Introduction à la terminologie de la théorie des graphes
- Arcs, arêtes, sommets, degrés
- Cycles, chemins, circuits
- Applications multivoques
2. Représentations des graphes
3. Recherche de circuits
4. Recherche de chemins optimum
5. Calcul de rangs
6. Graphes d'ordonnancement et calendriers
- Modélisations PERT et MPM
- Calculs au plus tôt et au plus tard
7. Arbres et arbres couvrants de poids minimum
- Méthodes de Kruskal et Prim
8. Coloration des graphes

Compétences visées :
- Analyser les besoins en vue de la conception ou de l'évolution de produits et services numériques (utiliser les connaissances scientifiques et techniques pour formaliser un problème, interpréter et reformuler un sujet)
- Concevoir des solutions numériques basées sur l'état de l'art (décomposer un problème en sous-problèmes, concevoir une interface ou un dispositif d'interaction)
- Mettre en œuvre des solutions numériques (concevoir et exécuter des tests)