Portail nationalFormationRechercher par discipline

Bases de l’optimisation dans les graphes

Code UE : US331A

  • Cours
  • 3 crédits

Responsable(s)

Safia KEDAD SIDHOUM

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

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

Présence et réussite aux examens

Pour l'année universitaire 2022-2023 :

  • Nombre d'inscrits : 21
  • Taux de présence à l'évaluation : 100%
  • Taux de réussite parmi les présents : 90%

Objectifs pédagogiques

  • 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.
  • 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 visées

  • 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).

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.

Modalité d'évaluation

  • Examen final

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Intitulé de la formation Master Sciences, technologies, santé mention Informatique Parcours Recherche opérationnelle
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x) Package
Lieu(x) Paris
Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

Recherche opérationnelle
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr
Voir le site

Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.

Enseignement non encore programmé