Semestre 7 – Optimisation combinatoire

Objectifs

Fournir les principes généraux (la théorie et l’algorithmique) de la programmation linéaire en variables continues et en variables discrètes pour établir les algorithmes fondamentaux de résolution exacte et approchée.

Prérequis

Les bases de l’algèbre linéaire.

Contenu pédagogique de l’UE

Programmation linéaire : 16h CM et 16h TD
Techniques de l’optimisation combinatoire : 8h CM et 8h TD

Programmation linéaire

  • Modélisation et formulation d’un programme linéaire en variables réelles (PL) et en variables binaires ou entières (PLNE).
  • Théorèmes fondamentaux de la programmation linéaire et dualité.
  • Algorithmes (primal et dual) du simplexe.
  • Analyse post-optimisation (analyses de sensibilité).

Techniques de l’optimisation combinatoire

  • Programmation Linéaire PL versus PLNE.
  • Résolution approchée d’un problème d’OC.
  • Résolution exacte d’un problème d’OC : énumération implicite, PLNE, méthodes de coupes, …