• Votre sélection est vide.

    Enregistrez les diplômes, parcours ou enseignements de votre choix.

Optimisation combinatoire

  • ECTS

    4 crédits

  • Composante

    UFR de mathématiques et informatique (UFR27)

  • Volume horaire

    42h

  • Période de l'année

    Printemps

Description

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

Lire plus