Operations Research (UGA)
Topic outline
-
Nadia Brauner - Hadrien Cambazard - Nicolas Catusse
-
Compétences à acquerir dans ce cours
Ces compétences sont détaillées dans les chapitres du cours et elles sont associées à des activités auto-évaluées qui vous permettent de vérifier que vous les avez acquises.
- RO
- Reconnaître une situation où les méthodes de la Recherche Opérationnelle sont pertinentes
- Disposer des éléments méthodologiques pour choisir, face à un problème pratique, les méthodes de résolution et les outils les plus adaptés
- Programmation linéaire
- Modéliser un problème décrit en langage naturel
- Résoudre graphiquement un PL à deux variables
- Comprendre et connaitre l'algorithme du simplexe (base, pivotage, critères d'arrêt)
- Dualité en programmation linéaire
- Enoncer les trois théorèmes de dualité et expliquer leur intérêt
- Interpréter les variables duales
- Mener une analyse de sensibilité
- Programmation linéaire en nombres entiers (techniques de modélisation, résolution avec Branch and Bound)
- Connaitre les principaux problèmes d'optimisation combinatoire et les modéliser en PLNE
- Modéliser un problème décrit en langage naturel
- Expliquer le principe de l'algorithme du branch and bound adapté à la PLNE
- Programmation dynamique
- Pouvoir expliquer les principes de base de la programmation dynamique
- Savoir mettre en place une solution de programmation dynamique pour un problème de type sac-à-dos
-
Algorithmes classiques (tri, diviser pour régner)
-
Calcul de complexité des algorithmes
-
Programmation : notions de base (variables, fonctions, if, for, while, tableaux)
-
Langage Python ou Java
-
Notions de base sur les matrices (multiplier des matrices, définition d'une matrice inversible)
-
Notions de base sur les graphes (Définitions de base, parcours de graphe en largeur et en profondeur, arbres, plus court chemin)