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
Rechercher une formation
Chargement du résultat...
![Patientez Patientez](/images/ajax-loader.gif)
Intitulé de la formation |
Type |
Modalité(s) |
Lieu(x) |
|
---|---|---|---|---|
Intitulé de la formation
Master Sciences, technologies, santé mention Informatique Parcours Recherche opérationnelle
|
Lieu(x)
Package
|
Lieu(x)
Paris
|
||
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
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é
Code UE : US331A
- Cours
- 3 crédits
Responsable(s)
Safia KEDAD SIDHOUM
Dans la même rubrique
- Accueil
- Actualités de la formation
- Comment se former et se financer?
- Rechercher par discipline
- Rechercher par métier
- Rechercher par région
- Catalogue national des formations
- Catalogue de la formation ouverte à distance
- Catalogue des stages
- Catalogue de l'alternance
- Valider ses acquis
- Notre engagement qualité
- Micro-certifications