Programmation linéaire

Programmation linéaireCode de l'UE : HLIN606

Présentation

La programmation linéaire est un outil fondamental de la recherche opérationnelle.
Le cours est centré sur une introduction à la programmation linéaire et quelques unes de ces applications classiques: allocation de ressource, ordonnancement, réseaux de transport, flots, etc.
Les (très) grandes lignes du cours sont : l'algorithme du simplexe en deux phases, interprétation géométrique, le théorème de dualité, introduction à la notion de certificat d'optimalité, interprétation concrète du programme dual, application à des problèmes de graphes.
Suivant cette optique, ce cours peut être vu comme une suite ou un complément du cours "algorithmique de graphes" du Semestre 5.

Objectifs

- Modélisation via la programmation linéaire
- Algorithme du simplexe

Volume horaire

  • CM : 15
  • TD : 18
  • TP : 16.5

Syllabus

- Méthodes d'optimisation combinatoire - I. Charon, A. Germa, O. Hudry.
- Understanding and using linear programming - J. Matousek, B. Gartner.

Diplômes intégrant cette UE

En bref

Crédits ECTS 5

Langue d'enseignement
fr

Contact(s)

Contact(s) administratif(s)

Eric BOURREAU (eric.bourreau @ umontpellier.fr)