Graphes et optimisation

Accueil > Généralités > Programme officiel

Programme officiel

lundi 18 juillet 2005, par

Présentation du cours : Les problèmes combinatoires : généralités, difficultés.

Théorie des graphes et algorithmes de base :

Introduction : vocabulaire et concepts de base (connexité, forte connexité, mise en ordre) ; nombre cyclomatique, arbres et arborescences.

Représentations des graphes : matricielles (adjacence, incidence) ; listes (successeurs, prédécesseurs). Les graphes en tant qu’outil de modélisation : exemples en Informatique et en Recherche Opérationnelle.

Parcours des graphes en largeur ; en profondeur ; application : tri topologique d’un graphe sans circuit ; détermination des composantes connexes.

Fermeture transitive ; déterminations, méthode matricielle (), algorithme de ROY-WARSHALL ; parcours en profondeur (cas d’un graphe sans circuit). Évaluation du nombre d’opérations ; initiation à la complexité dans ce cas polynomial.

Algorithmes d’optimisation dans les graphes valués :

Chemins optimaux dans un graphe valué : algorithmes de FORD, de DIJKSTRA.

Application : ordonnancement de projets (méthodes M.P.M. et P.E.R.T.)

Flots maximaux dans un réseau de transport : l’algorithme de FORD-FULKERSON (exemples, preuve, complexité). Notion de graphe d’écart et reformulation de cet algorithme.

Flot maximal à coût minimal : algorithme de ROY (en E.D.)

Programmes de transport (heuristiques et notion de ``regret’’ ; algorithme du stepping-stone).

Arbres couvrants de poids extrémal : algorithmes de KRUSKAL, SOLLIN.
Problèmes d’affectation : la méthode hongroise (lien avec les flots maximaux).

Recherches arborescentes : en profondeur d’abord (problème des reines sur l’échiquier) ; Branch and Bound : résolution du problème du voyageur de commerce (T.S.P.) par l’algorithme de LITTLE.

Programmation linéaire

Définition, historique ; panorama des applications industrielles, performances et rentabilité.

Approche géométrique : caractérisation géométrique du cheminement vers le sommet optimum. Caractérisation algébrique d’un sommet ; méthode algébrique du simplexe. Méthode des tableaux (en se limitant aux cas où le sommet 0 est admissible).