Recherche opérationnelle

Organisation

Cours/TD/TP/projet/examen : Heures Cours/TD/TP/projet/Examen : 15,75h/15,75h/0h/0h/3,5h

Acquis d'apprentissage

A la fin du module, l'étudiant devra pouvoir :
1) exposer, expliquer les méthodes présentées pour résoudre des problèmes classiques de recherche opérationnelle,
2) mettre en œuvre ces méthodes,
3) identifier la méthode à mettre en œuvre pour résoudre un problème posé.

Compétences CDIO

• 1.1 - Connaissance des sciences de base, y compris mathématiques et autres
• 2.1 - Raisonnement analytique et résolution de problèmes
• 2.2.1 - Formulation d'hypothèses
• 2.2.4 - Tests d'hypothèses et argumentation critique

Prérequis

Algèbre linéaire

Mots-clés

Programmation linéaire, méthode du simplexe, dualité, séparation et évaluation (branch and bound), graphes, arbres, plus courts chemins, programmation dynamique, ordonnancement, flots.

Contenu

- Programmation linéaire, algorithme du simplexe, dualité
- Méthodes de séparation et évaluation
- Arbres couvrants de poids minimum
- Le problème central de l’ordonnancement
- Plus courts chemins
- Programmation dynamique
- Réseaux de flot.

Evaluation

CC : de 1h45 : Devoir sur table
CF1 de 1h45 : Devoir sur table
CF2 : Devoir sur table (3h30) ou rapport ou oral (1h).

Formule de l'évaluation

Note finale du module (sur 20) : CF = max((CC+CF1)/2, CF2)

Bibliographie

Polycopiés de cours.
M. Minoux, Programmation mathématique, Lavoisier 2008.
M. Gondran, M. Minoux, Graphes et algorithmes, Lavoisier 2009.