Description

Ce cours est conçu pour se développer à partir des connaissances acquises en Licence concernant l'algorithmique de base sur les graphes. Le cours a un double objectif :
 - apprendre à modéliser des problèmes concrets à partir d'un certain nombre de modèles de graphes utiles dans de nombreuses applications en RO, Décision et IA ;
 - comprendre les principaux algorithmes utilisables pour résoudre les problèmes posés, savoir les mettre en oeuvre de façon efficace et évaluer leur complexité. L'accent sera mis sur les modèles d'optimisation sur les graphes, sujet seulement ébauché en Licence.

• Programmation dynamique discrète et lien avec le problème du plus court chemin. Applications diverses (problème de sac-à-dos, plus court chemin avec contraintes supplémentaires) ;
• Problème de flot maximum. Exemples d'applications et algorithmes ;
• Le problème d'affectation et sa résolution par l'algorithme Hongrois. Exemples d'applications ;
• Le problème de transport et sa résolution par l'algorithme de Klein ;
  Le problème de transport et sa formulation en programmation linéaire.
  Résolution du problème de transport par l'algorithme du simplexe (forme révisée) ;
• Problèmes généraux de flot à coût minimum. Algorithme des arcs non conformes. Liens avec la programmation linéaire
• Applications des modèles de flots: problèmes d'ordonnancement (PERT) avec coûts et durées des tâches variables ; minimisation des en-cours dans des ateliers de fabrication.
• Problèmes de tournées de livraison et recherche de chemins eulériens ou hamiltoniens dans les graphes. Résolution du problème de voyageur de commerce par Branch & Bound avec diverses fonctions d'évaluation simples (par résolution du problème d'affectation, du problème de plus court chemin avec contraintes, du problème de l'arbre minimum). Méthodes heuristiques de résolution de problèmes d'optimisation sur les graphes.

Bibliographie

• M. Gondran et M. Minoux Graphes et algorithmes Eyrolles 1995

Contenu indicatif par semaine

• Rappels sur le probleme de plus court chemin et les principaux algorithmes de résolution

• Programmation dynamique discrète et lien avec le problème du plus court chemin

• applications de la programmation dynamique

• Le problème du flot maximum. Algorithme de résolution

• flot maximum et coupe minimale. Applications

• Le problème d'affectation. Algorithme Hongrois.

• Le problème du transport. Algorithme primal. Applications

• Le problème du transport. Algorithme primal-dual

• Résolution du problème du transport par l'algorithme du simplexe

• Problèmes généraux de flot à coût minimum. Algorithme des arcs non conformes.