Recherche opérationnelle et Optimisation Discrète

Rappels de complexité

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 liné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

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

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

Recherche opérationnelle et Optimisation Discrète

Rappels de complexité