Contactez-nous
  • Recherche opérationnelle

Bases de l’optimisation dans les graphes

Mis à jour le

Responsable(s) : Mme Safia KEDAD SIDHOUM

  • Cours
Code Cnam : US331A

Envie d'en savoir plus sur cette formation ?

Afin d’obtenir les tarifs, le calendrier de la formation, en distanciel, en présentiel, le lieu de la formation et un contact, remplissez les critères suivants :

Afficher le centre adapté à mes besoins

Afin d’obtenir les tarifs, le calendrier de la formation et le lieu de la formation, remplissez les critères suivants :

  • Durée : 30 heures
  • Package
  • 3 crédits

Présentation

Public, conditions d'accès et prérequis

Prérequis

Couplages, Transversaux, Graphes Bipartis, Flots, Coupes, Programmation Linéaire, Méthodes primales-duales

Objectifs

  1. Apprendre les théorèmes de base en optimisation dans les graphes, et les techniques de preuve associées, et en particulier en ce qui concerne les notions essentielles que sont les couplages, les transversaux, les flots et les coupes.

  2. Apprendre et comprendre les liens entre l'optimisation dans les graphes et la programmation linéaire, notamment à travers l'utilisation des matrices totalement unimodulaires et des approches primales-duales.

Compétences et débouchés

Compétences

  • Savoir écrire et comprendre des preuves en optimisation dans les graphes, basées sur différentes méthodes (preuves constructives, preuves par l'absurde basées sur des contre-exemples minimaux au sens de l'inclusion, etc.).
  • Comprendre les liens entre les principaux théorèmes de base en optimisation dans les graphes.
  • Savoir interpréter le dual en variables entières d'un PL(NE) modélisant un problème d'optimisation dans les graphes.
  • Savoir utiliser la programmation linéaire pour résoudre certains problèmes d'optimisation dans les graphes (résolution via approches primales-duales ou solveur, lorsque la matrices des contraintes est totalement unimodulaire).

Parcours

Informations pratiques

Contact

Programme

Contenu

  • Définitions et propriétés des graphes bipartis, des couplages et des transversaux. Preuves du lemme de Berge, du théorème de König-Egerváry, et du théorème de Hall.

  • Définitions et propriétés des flots et des coupes dans les graphes orientés, et notion de graphe d'écart. Preuve détaillée du théorème de Ford-Fulkerson basée sur l'algorithme du même nom. Présentation synthétique de l'algorithme de Busacker-Gowen pour les flots à coût minimum, basé sur le calcul de plus courts chemins dans le graphe d'écart. Notion de $k$-connexité, et preuve du théorème de Menger comme conséquence du théorème de Ford-Fulkerson.

  • Introduction aux matrices totalement unimodulaires, preuves de quelques propriétés utiles, et conséquences en programmation linéaire. Preuve du théorème de König-Egerváry via la dualité en programmation linéaire et les matrices totalement unimodulaires.

  • Preuve du théorème de Ford-Fulkerson via la dualité en programmation linéaire et les matrices totalement unimodulaires, et conséquences (flots et coupes dans les graphes non orientés, plus court chemin, flot à coût minimum, affectation linéaire, etc.). Le théorème de König-Egerváry vu comme une conséquence du théorème de Ford-Fulkerson.

  • Introduction aux approches primales-duales en optimisation dans les graphes, et liens avec les relations d'exclusion en programmation linéaire. Application à la méthode hongroise pour le calcul d'un couplage parfait à coût minimum dans les graphes bipartis.

Ces formations pourraient vous intéresser