RECHERCHE OPÉRATIONNELLE ET OPTIMISATION DISCRÈTE

1. Informations pratiques

Enseignant: Nicolas M. Thiéry Email: nthiery@users.sourceforge.net

Page web: http://www.lapcs.univ-lyon1.fr/~nthiery/

Horaire: Jeudi 14h-17h (13h-17h pour les TP), Vendredi 14h-15h (cours +

TD + TP)

Page web du cours: http://www.lapcs.univ-lyon1.fr/~nthiery/RO/

2. Programme

Semaine 1: Rappels de complexité ; Introduction à la programmation li-

néaire Semaine 2: Algorithme du simplex ; TP : résolution de programmes linéaires Semaine 3: Pièges et cas pathologiques dans l’algorithme du simplex Semaine 4: Théorème de dualité ; applications à l’optimisation locale Semaine 5: Applications, jeux matriciels Semaine 6: Partiel Semaine 7: Problèmes de transports Semaine 8: Applications, combinatoire polyhédrale Semaine 9: Problèmes de flots et applications Semaine 10: Couplages dans les graphes bipartis, Algorithme de Ford-Fulkerson Semaine 11: Ordonnancements (introduction)

3. Examens

Un partiel, un examen final, quelques TPs

4. Organisation, règles du jeu et conseils

– Travailler efficacement :

– Lire les notes à l’avance

– Être curieux

– Être actif en cours

– Travailler en groupe

– Interactivité :

– Ne pas hésiter à poser des questions

– Me prévenir immédiatement en cas de problèmes

– Tout commentaires et suggestions sur le déroulement du cours bienvenus

– Bavardage inutile -> dehors pendant 5 minutes

2 RECHERCHE OPÉRATIONNELLE ET OPTIMISATION DISCRÈTE

5. Références

Linear Programming: V. Chvátal, 1983, Freeman and Company How to solve it: G. Pólya, 1988, Princeton University Press

Linear Programming FAQ: http://rutcor.rutgers.edu/~mnk/lp-faq.html

Linear Programming ; Foundations and Extensions: R. Vanderbie http://www.princeton.edu/~rvdb/LPbook/index.html

Netlib: www.netlib.org
Liens divers: http://www.fundp.ac.be/~becolson/students.html#num