Optimisation Combinatoire & Aide à la Décision – M1

Dans cette première séance d’Optimisation Combinatoire – M1, nous étudions le problème du flot maximum dans un graphe, un problème fondamental de l’optimisation sur les réseaux. À travers des exemples graphiques et une formulation mathématique, nous construisons progressivement les notions nécessaires pour comprendre comment déterminer et améliorer un flot jusqu’à atteindre l’optimum. Au programme : Graphes orientés et graphes pondérés Capacités des arcs Matrices d’incidence et d’adjacence Listes des successeurs et prédécesseurs Flot et conservation du flot Flot réalisable et valeur du flot Formulation en programmation linéaire Coupure et capacité d’une coupe Théorème de Ford-Fulkerson Coupe minimale et flot maximum Chaînes augmentantes Algorithme de Ford-Fulkerson Parcours DFS et BFS Exemple détaillé d’amélioration du flot Complexité de Ford-Fulkerson Algorithme d’Edmonds-Karp Introduction au flot avec bornes inférieure et supérieure La séance s’arrête à l’introduction du problème du Maximum Flow with Lower and Upper Bounds, qui sera développé dans la suite.