| Professeur | Prof. Friedrich Eisenbrand |
| Assistants | Adrian Bock |
| Chidambaram Annamalai | |
| Alfonso Cevallos | |
| Carsten Moldenhauer | |
| Franka Tholen | |
| Langue | Français |
Actualités
- L’information pour l’examen est disponible ici.
- Le corrigé de l’examen blanc est disponible.
- Le corrigé 10 et un examen blanc sont disponibles.
- La série 10 et le corrigé 9 sont disponibles.
- La série 9 et le corrigé 8 sont disponibles.
- Pour obtenir le bonus de 0.25, il faut avoir 50% du total des points (y compris l’examen final) du cours en ligne. Autrement dit, vous obtenez le bonus ssi les conditions du certificat Coursera sont remplies.
- La série 8 est disponible.
Description
Pour la première moitié du semestre, on suivra ce cours en ligne. Le jeudi entre 8h et 10h, vous êtes libre de choisir parmi les options suivantes:
- deux heures de cours en français qui traite le même contenu que le cours en ligne
- deux heures de consultation et une séance d’exercices prolongée
Pour la deuxième moitié du semestre, on propose de façon alternée deux heures de cours traditionnel (en français) avec la séance d’exercices (une heure) et une heure de cours avec la séance d’exercices de deux heures.
Horaires
Première moitié du semestre (du 18 Février au 11 Avril)
Séances d’exercices : Jeudi, de 8h à 11h dans les salles
CE 1100 (Franka), CE 1101 (Adrian), CM 012 (Chidambaram), CM 013 (Alfonso), MAA 331 (Carsten)
Cours (optionnel): Jeudi, de 8h15 à 10h, CO 1
Deuxième moitié du semestre (du 18 Avril au 30 Mai)
Cours : Jeudi, de 8h15 à 9h / 10h, CO 1
Séances d’exercices : Jeudi, de 10h / 9h à 11h dans les salles
CE 1100, CE 1101, CM 012, CM 013, MAA 331
Horaires de bureau
Adrian : Mardi 12h – 13h
Alfonso : Jeudi 14h – 15h
Carsten : Vendredi 13h – 14h
Chillu : Vendredi 13h – 14h
Objectifs
Familiariser les étudiants avec des modèles de programmation linéaire et des algorithmes. Leurs apprendre à développer et analyser des algorithmes.
Contenu
Algorithme du simplexe
Perturbations et règle lexicographique
Lemme de Farkas et dualité
Méthode duale du simplexe
Polyèdres
Couplages et flots dans les réseaux :
Couplage biparti et non-biparti
Polytope de couplage.
Matériel du cours
Vous trouvez ici des notes de Cours en anglais et ci-dessous les transparents utilisés dans le Cours.
| Contenu | Fichiers | |
|---|---|---|
| Leçon 1 | Programmation linéaire: Introduction et exemples | 21.02.2013 |
| Leçon 2 | La géométrie de la programmation linéaire | 28.02.2013 |
| Leçon 3 | L’algorithme du simplexe | 07.03.2013 |
| Leçon 4 | L’algorithme du simplexe est-il efficace ? | 14.03.2013 |
| Leçon 5 | Dualité, Programmation linéaire en nombres entiers | 21.03.2013 |
| Leçon 6 | Algorithme de parcours en largeur, Algorithme de Bellman-Ford | 28.03.2013 |
| Leçon 7 | Algorithme primal-dual | 11.04.2013 |
| Leçon 8 | Flots dans les réseaux : Introduction | |
| Leçon 9 | Flots et réseaux : l’algorithme de Ford-Fulkerson | 25.04.2013 |
| Leçon 10 | Flots et réseaux : Théorème flot-max/coupe-min, Edmonds-Karp | 02.05.2013 |
| Leçon 11 |
Flots et réseaux : Edmonds-Karp Programmation dynamique: problème du sac à dos |
16.05.2013 |
| Leçon 12 | Programmation dynamique: problème du sac à dos | 23.05.2013 |
| Leçon 13 | Indications pour l’examen | 30.05.2013 |
Exercices à rendre
| Semaine 1 | Problem 2 (optional assignments) |
| Semaine 2 | Problem 2 (optional assignments) |
| Semaine 3 | Problem 1 (optional assignments) |
| Semaine 4 | Problem 1 (optional assignments) |
| Semaine 5 | Problem 1 (optional assignments) |
| Semaine 6 | Problem 1 (optional assignments) |
| Semaine 7 | Problem 1 (optional assignments) |
Exercices
Pour les exercices à rendre, on choisit un groupe et on lui demande de présenter et expliquer sa solution.
Séries |
Solutions |
|---|---|
| série 08 | corrigé 08 |
| série 09 | corrigé 09 |
| série 10 | corrigé 10 |
Indications pour les exercices de programmation
Ordinateurs EPFL (dans la salle TP en math, c-à-d MA B1 486) :
1) Ouvrir un terminal
2) Accéder le classeur contenant le fichier avec le code
3) Exécuter python2.6 fichier.py
Installation sur Mac ou Linux :
1) installer python 2.7.3 (voir cette page)
2) download sympy-0.7.2.tar.gz (version python 2, voir cette page)
3) Ouvrir un terminal, accéder le classeur contenant sympy et exécuter python setup.py install
Windows ou Mac IDLE :
1) installer python 2.7.3 et sympy 0.7.2 (windows executable)
2) Lancer python.
3) Pour ouvrir et exécuter le code dans un fichier :
Ouvrir le fichier (File -> open in a new window)
Dans la nouvelle fenêtre avec le code, choisir Run -> Run module (ou appuyer simplement F5 )
En cas de problème, n’hésitez pas à venir voir les assistants pendant les horaires de bureau.
Examen et la note finale
Il y aura un examen écrit à la fin du semestre.
Il est possible d’obtenir un bonus pour la note finale sous conditions:
– un minimum de 50% des points sur les quiz (“assignments”) en ligne (bonus 0.25)
– un minimum de 70% des points sur les rendus et la présentation d’au moins une solution (bonus 0.5)
Références
Jiří Matousek and Bernd Gärtner. Understanding and using linear programming. Springer, 2006. ISBN 978-3-540-30697-9 (bibliothèque, en ligne (accessible seulement depuis le reseau de l’EPFL))
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. ISBN 0521833787 (disponible en ligne)
Jean-François Hêche, Thomas M. Liebling, Dominique de Werra, Recherche opérationnelle pour ingénieurs I (bibliothèque)
Dimitris Bertsimas and John N. Tsitsiklis. Introduction to linear optimization. Athena Scientific, 1997. ISBN 1-886529-19-1
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network flows : theory, algorithms, and applications. Prentice Hall, 1993. ISBN 0-13-617549-X
Thomas Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction à l’algorithmique. MIT Press, 2004. ISBN 978-0262032933 (bibliothèque, site web)