Dualité en PL. Théorème de la dualité. Théorème des écarts complémentaires.
Modélisation par les flots.
Approximation par arrondi des programmes linéaires.
Bigliographie:
J. Matousek, B. Gartner, Understanding and using linear programming, Springer 2007.
I. Charon, A. Germa, O. Hudry, Méthodes d'optimisation combinatoire, Masson 1996.
J. Erickson, Algorithms, 2019.
V. Vazirani, Algorithmes d'approximation, Springer, 2006.
Langue(s) d'enseignement
Français
Bibliographie
J. Matousek&B. Gartner, Understanding and using Linear Programming I. Charon, A. Germa, O. Hudry, Méthodes d'Optimisation Combinatoire Cormen et al., Introduction à l'Algorithmique Erickson, Algorithms
