Intitulé de la matière : Graphe et problèmes d’Optimisation
Intitulé de l’UE : UEM1
Crédits : 5
Coefficients : 3
Objectifs de l’enseignement
Etudier les bases dans les trois domaines d'optimisation : la théorie des files d’attente, la théorie des graphes et la programmation linéaire. Savoir modéliser et analyser des problèmes concrets d'optimisation et connaître les principales méthodes pour les résoudre.
Connaissances préalables recommandées: Notions en algorithmique.
Contenu de la matière
1. Rappel des éléments de recherche opérationnelle
2. Optimisation dans les graphes
- Graphes
- Ordonnancement: méthode potentiel-tâches, méthode potentiel-événements (PERT).
- Flots dans un graphe, algorithme de Ford-Fulkerson, flots maximum de coût minimum
- Programmation linéaire.
3. Programmation Linéaire en nombre entier (PLNE)
- Définitions
- Méthode de coupe
- Méthode de recherche arborescence
4. Approche par Contraintes
- Formalismes
- Algorithmes
Mode d’évaluation : (Continu :40%, EMD : 60%).
Références
- Faure, Lemaire et P couleau. Précis de recherche opérationnelle - Méthodes et exercices d'application. Dunod.
- Roseaux. Recherche opérationnelle - Tome 2, Phénomènes aléatoires en recherche opérationnelle. Dunod.