L'unité d'enseignement « Algorithmique appliquée à l'optimisation » est une UE de niveau (300) spécialisation relevant de la licence d'informatique. Elle possède un volume de 6 ECTS et s'étend sur 12 semaines. Elle est placée sous la responsabilité de Chrétienne, philippe.

Description

Ce module prolonge le module d'algorithmique générale en étudiant des algorithmes fondamentaux pour la résolution de problèmes d'optimisation dans les graphes. Ces problèmes sont issus des applications liées aux transports (routiers, ferroviaires...), aux flots (réseaux informatiques, fluides...), à l'affectation (de tâches à des machines...) et à l'ordonnancement (en production et/ou en informatique). Ces algorithmes puisent leur efficacité à la fois dans leur modélisation en termes de programmation linéaire et de graphes. C'est pourquoi une partie de cette UE consiste à présenter les bases de la programmation linéaire et des graphes de manière à comprendre en profondeur les algorithmes utilisés au niveau des applications.

1- Programmation linéaire : Modélisation; Algorithme du simplexe; Dualité; Introduction à la programmation linéaire en nombres entiers

2- Chemins optimaux et application à l'ordonnancement : Algorithme de Ford-Bellman, A*... ; Méthode Pert et CPM pour l'ordonnancement

3- Flots d'un réseau: Algorithme générique de Ford-Fulkerson; Algorithme d'Edmonds-Karp; Algorithme du préflot

4- Applications des flots: Problèmes de couplages; Problèmes d'affectation

Préalables et buts pédagogiques

Bibliographie

• Gondran et Minoux (1979) Graphes et algorithmes (Eyrolles)

• Cormen, Lieserson, Rivest et Stein (2002) Introduction à l'algorithmique (Dunod)

• Faure, Lemaire et Picouleau (2000) Précis de recherche opérationnelle (Dunod)

• ROSEAUX (1994) Exercices et problèmes résolus de recherche opérationnelle (Dunod)

Contenu indicatif par semaine

1. Programmation linéaire : Modélisation

2. Algorithme du simplexe

3. Dualité

4. Introduction à la programmation linéaire en nombres entiers

5. Chemins optimaux : Algorithme de Ford-Bellman, A*...

6. Application à l'ordonnancement : Méthode Pert et CPM pour l'ordonnancement

7. Flots d'un réseau: Algorithme générique de Ford-Fulkerson

8. Algorithme d'Edmonds-Karp

9. Applications des flots: Réseaux de transport

10. Applications des flots: Problèmes de couplages

11. Applications des flots: Problèmes d'affectation

12. Applications des flots: Problèmes d'ordonnancement