MA3009 - Optimisation combinatoire

Vous êtes ici :

MA3009 - Optimisation combinatoire

Objectifs

Objectif général :

Planifier l’installation de lignes de bus dans une ville. Allouer des créneaux de décollage aux avions dans un aéroport. Résoudre une grille de Suduku. Trouver le plus court chemin pour un vol transatlantique. Développer un réseau de fibre optique à l'échelle de la France. Transporter des milliers de passagers de Toulouse à Jakarta à travers les vols d'une compagnie aérienne. Ordonnancer les différentes tâches à effectuer lors de l'escale d'un avion dans un aéroport... Voilà autant de problèmes industriels qu'il est possible de modéliser et résoudre grâce à l'optimisation combinatoire. Ce cours propose une introduction aux méthodes utilisées dans le domaine de l’optimisation combinatoire, en s'appuyant essentiellement sur deux axes : - la présentation d'un ensemble de modélisations classiques, à l'aide des formalismes de la programmation linéaire et de la théorie des graphes ; - la description d'un ensemble de méthodes (c'est-à-dire d'algorithmes) pour résoudre les problèmes d'optimisation ainsi modélisés. A l'issue de cet enseignement, l'étudiant sera capable d'identifier et de modéliser des problèmes réalistes simples d’optimisation, de différencier la modélisation d’un problème de sa résolution (c'est-à-dire de son optimisation), et de résoudre les problèmes de programmation linéaire, de programmation linéaire en nombres entiers et certains problèmes de graphes. L'étudiant se constituera, entre autres : - une collection de problèmes d’optimisation classiques, - une collection d’algorithmes exacts de résolution pour ces problèmes d’optimisation, - une collection d'exemples d'application de ces problèmes et algorithmes au domaine du Transport Aérien

Objectifs détaillés :

A l'issue de cet enseignement, l'étudiant sera capable de : -Reconnaître et formuler un problème d'optimisation (combinatoire ou non), en particulier dans le domaine du Transport Aérien -Identifier le type d'un problème d'optimisation simple (programme linéaire, programme linéaire en nombres entiers, problème de plus court chemin dans un graphe, problème d'arbre couvrant de poids minimum, problème de flot maximal, ...), -Énumérer des algorithmes exacts d'optimisation combinatoire et leur domaine d'application (Simplexe et règles de dualité, Séparation-Évaluation, Prim, Kruskal, Dijkstra, Bellman, Ford-Fulkerson, ...) -Décrire le fonctionnement de ces algorithmes, -Modéliser des problèmes simples dans un formalisme précis (programme mathématique ou problème de graphe), -Choisir et utiliser (exécuter "à la main") un algorithme adéquat pour les résoudre.

Volume horaire (h)

  • Cours magistraux : 32

Examens

Nombre total d'heures d’évaluation : 2

Ce cours fait partie de la formation

En bref

Crédits ECTS : Cf UE

Nombre d'heures 34

Contact(s)