Aller au menu Aller au contenu
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

Optimisation combinatoire - 4MMOC6

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In
  • Volumes horaires

    • CM : 16.5
    • TD : 16.5
    • TP : -
    • Projet : -
    • Stage : -
    • DS : -
    Crédits ECTS : 3.0
  • Responsables : Zoltan SZIGETI

Objectifs

Dans le cours de recherche opérationnelle de première année nous avons étudié un certain nombre d’algorithmes d’optimisation sur les graphes : algorithmes de plus courts chemins dans des cas particuliers et algorithmes d’arbre de pois minimum. Dans ce cours nous étudions algorithmiquement d’autres problèmes sur les graphes, problèmes de flots maximum, problèmes de flots de coût minimum, problème du couplage de cardinalité et de poids maximum, problèmes de plus courts chemin dans le cas général. Nous donnerons de nombreux théorèmes de type min-max ou max-min. Ce cours a un double aspect algorithmique et modélisation.

Contenu

1) Problème du flot maximum dans un graphe : Algorithme de Ford et Fulkerson et ses diverses variantes, algorithme des préflots et ses diverses variantes.
2) Problème du flot de coût minimum, algorithme primal simplexe et algorithme primal dual.
3) Problèmes de plus courts chemin, algorithme général avec détection de circuits absorbants
4) Problème du couplage de cardinalité maximum dans un graphe. Théorème d'Edmonds Gallai.
5) Modélisation de divers problèmes d’optimisation comme des problèmes de flots.
6) Des théorèmes min-max en liaison avec les problèmes de flots

Prérequis

Programmation linéaire (mais pas indispensable), éléments de théorie des graphes, c’est à dire le cours de recherche opérationnelle de première année.

Contrôles des connaissances

CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) : --

SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : écrit
Salle spécifique : --
Durée : 3h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) :
Manuscrits (notes de cours), feuilles d'exercices distribuées
Documents interdits (ex : livres, tous documents) : livres
Matériel (ex : calculatrices):

  • matériel autorisé, préciser : --
  • matériel interdit, préciser : calculatrices, téléphones portables, ordinateurs
    Commentaires :

SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : écrit
Salle spécifique : --
Durée : 2h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) :
Manuscrits (notes de cours), feuilles d'exercices distribuées
Documents interdits (ex : livres, tous documents) : livres
Matériel (ex : calculatrices):

  • matériel autorisé, préciser : --
  • matériel interdit, préciser : calculatrices, téléphones portables, ordinateurs
    Commentaires :

  • MCC en présentiel et distantiel
    N1=E1
    N2=E2

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Filière MMIS - Semestre 7
cf. l'emploi du temps 2022/2023

Informations complémentaires

Code de l'enseignement : 4MMOC6
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

Linear programming by Vacek Chvatal, (editeur Freeman)
Network flows by Ahuja, Magnati and Orlin (editeur Prentice Hall)

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

mise à jour le 15 janvier 2017

anglais
Grenoble INP - Ensimag
École nationale supérieure d'informatique et de mathématiques appliquées
681, rue de la passerelle - Domaine universitaire - BP 72
38402 SAINT MARTIN D'HERES
 
 
République Française         Groupe INP Logo de la Commission des titres d'ingénieur (CTI)
    Université Grenoble Alpes