MA3007 - 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. Il a principalement deux objectifs :
- proposer un ensemble de modélisations classiques, à l'aide de la programmation linéaire et, de la théorie des graphes, deux langages formels;
- décrire 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 ce cours, l'étudiant sera capable de reconnaître et modéliser un problème d’optimisation, de différencier la modélisation d’un problème de sa résolution (c'est-à-dire de son optimisation), de résoudre un problème de programmation linéaire et certains problèmes sur les graphes.

L'étudiant se constituera, entre autres :
- une collection de problèmes d’optimisation classiques (notamment à l’aide de graphe),
- une collection d’algorithmes de résolution pour ces problèmes d’optimisation.