Optimisation combinatoire

Objectifs: 

De nombreux problèmes concrets requièrent des solutions à valeurs entières (par exemple problèmes de transport, problèmes d'affectation, problèmes d'optimisation où l'on doit déterminer un nombre d'individus, un nombre d'avions,...). Pour de tels problèmes on ne peut pas utiliser les méthodes classiques de la programmation linéaire. On a besoin de méthodes spécifiques aux PLNE (programmes linéaires en nombres entiers).

On commencera par étudier des exemples de modélisation sous la forme de  PLNE. Nous verrons que la modélisation de certaines contraintes peut aussi nécessiter l'introduction de variables entières. Nous verrons ensuite les principales méthodes de résolution de ces problèmes.

 Contenu du cours:

1. Modélisation de problèmes d’optimisation en nombres entiers
2. Méthodes par séparation et évaluation
3. Méthodes par programmation dynamique
4. Méthode des coupes de Gomory

Références:

Sakarovitch, Optimisation combinatoire : méthodes mathématiques et algorithmiques