Aller au contenu  Aller au menu Aller à la recherche

accès rapides, services personnalisés

Rechercher

Recherche détaillée

Contact

Jacqueline Collet-Narboni
Responsable administrative

courriel : jacqueline.collet-narboni@upmc.fr

Cette page est la page de garde du site consacré à l' unité d'enseignement « Modélisation, Optimisation, Graphes, et Programmation Linéaire (NW411) »

Ressources annuelles

Responsable de l'UE : Perny, patrice



Description de l'UE :

Cette UE est destinée à introduire les graphes et la programmation linéaire comme outils de modélisation et de résolution de problèmes d'optimisation ou de décision. Elle a pour objet l'étude de modèles et l'analyse d'algorithmes fondamentaux de l'optimisation combinatoire. Elle constitue une base nécessaire à tout étudiant en informatique souhaitant acquérir une bonne maîtrise des modèles et algorithmes pour la résolution de problèmes d'optimisation, qu'il s'agisse de problèmes réels rencontrés dans un contexte industriel, ou de problèmes de recherche académique. Les étudiants auront aussi l'occasion de mettre en pratique les modèles étudiés d'une part en utilisant un solveur de programme linéaire et d'autre part en développant certains algorithmes de graphe pour résoudre des problèmes concrets.

Dans la partie concernant les graphes, on s'intéressera à la modélisation et la résolution de problèmes de chemins optimaux, d'arbres couvrants, de flots, d'affectation, de transports, à des méthodes générales de résolution de problèmes d'optimisation telles que la programmation dynamique et le branch and bound. Dans la partie concernant la programmation linaire, on apprend à formaliser des problèmes d'optimisation comme des programmes linéaires, puis à les résoudre par l'algorithme du Simplexe et quelques variantes. On aborde ensuite la dualité en programmation linéaire et l'analyse post-optimale et l'optimisation linéaire en nombre entiers. Les travaux dirigés sont l'occasion de s'exercer à la modélisation de problèmes standard par les graphes et la programmation linéaire pour en permettre une résolution efficace par la machine. Des travaux encadrés et un projet viennent compléter la formation en donnant aux étudiants l'occasion de mettre en pratique ces notions sur des problèmes concrets en utilisant un solveur de programme linéaire ou en développant des algorithmes de graphes.


Bibliographie :

  • Graphes et Algorithmes", Michel Gondran, Michel Minoux, Lavoisier, 2009.
  • Programmation mathématique : Théorie et algorithmes", Michel Minoux, Lavoisier, 2008.
  • Recherche Opérationnelle, méthodes d'optimisation", Jacques Teghem, Ellipses, 2012.
  • "Aide à la décision, une approche par les cas , Gestion, mathématiques, informatique", Philippe Vallin, Daniel Vanderpooten, 2002.

Semainier indicatif :

  • Semaine 1 : Modélisation par la PL, résolution graphique, base associées à un sommet
  • Semaine 2 : Méthode du simplexe, méthodes des tableaux, méthode révisée du simplexe
  • Semaine 3 : méthodes d'initialisation, dualité
  • Semaine 4 : Applications de la dualité : analyse post-optimale, résolution de jeux
  • Semaine 5 : PLNE, PL 0-1, résolution par séparation évaluation
  • Semaine 6 : Rappels de graphe, chemins extremaux
  • Semaine 7 : Programmation dynamique : applications aux problemes de sac-à-dos, de gestion de stock et d'ordonnancement
  • Semaine 8 : Problèmes de circulations dans les graphes, flot max
  • Semaine 9 : Problèmes d'affectation
  • Semaine 10 : Flots max à coût minimum, Pbs de transport (Klein, Busacker et Gowen, Primal-Dual)