Optimisation combinatoire - 4MMOC

Objectif(s)

Dans le cours de recherche opérationnelle de première année nous avons étudié un certain nombre d’algorithmes d’optimisation sur les graphes : algorithmes de plus courts chemins dans des cas particuliers et algorithmes d’arbre de pois minimum. Dans ce cours nous étudions algorithmiquement d’autres problèmes sur les graphes, problèmes de flots maximum, problèmes de flots de coût minimum, problème du couplage de cardinalité et de poids maximum, problèmes de plus courts chemin dans le cas général. Nous donnerons de nombreux théorèmes de type min-max ou max-min. Ce cours a un double aspect algorithmique et modélisation.

Contenu(s)

1) Problème du flot maximum dans un graphe : Algorithme de Ford et Fulkerson et ses diverses variantes, algorithme des préflots et ses diverses variantes.
2) Problème du flot de coût minimum, algorithme primal simplexe et algorithme primal dual.
3) Problèmes de plus courts chemin, algorithme général avec détection de circuits absorbants
4) Problème du couplage de cardinalité maximum dans un graphe. Théorème d'Edmonds Gallai.
5) Modélisation de divers problèmes d’optimisation comme des problèmes de flots.
6) Des théorèmes min-max en liaison avec les problèmes de flots

Programmation linéaire (mais pas indispensable), éléments de théorie des graphes, c’est à dire le cours de recherche opérationnelle de première année.