Optimisation

Organisation

Cours/TD/TP/projet/examen : Heures Cours/TD/TP/CF1 : 0/28.5/0/3

Acquis d'apprentissage

Au terme du module MAT 3602, l’étudiant de première année sera capable de :
- démontrer des résultats de base en théorie des graphes et théorie de l'optimisation;
- modéliser des situations pratiques par des problèmes d’optimisation dans des graphes ou sous la forme de programmes mathématiques en variables continues;
- proposer et mettre en œuvre des méthodes pour résoudre ces problèmes.

Compétences CDIO

• 1.1.1 - Mathematics (including statistics)
• 2.1.1 - Problem Identification and Formulation
• 2.1.2 - Modeling

Prérequis

Programme de mathématiques des classes préparatoires aux grandes écoles

Mots-clés

Optimisation, modélisation, graphes, programmation mathématique (linéaire et non linéaire).

Contenu

-CI 1 (3h) : introduction à la théorie des graphes
-CI 2 (3h) : problème de l’arbre couvrant de poids minimal : algorithmes de Kruskal et Prim
-CI 3 (3h) : problème du plus court chemin : algorithmes de Moore-Dijkstra et Bellman-Ford
-CI 4 (3h) : flots dans les réseaux de transport : algorithme de Ford-Fulkerson
-CI 5 (3h) : algorithme de Busacker- Gowen. Ordonnancements
-CI 6 (3h) : programmation linéaire
-CI 7 (1h30) : dualité
-CI 8 (3h) : éléments d’analyse convexe
-CI 9 (3h) : programmation non linéaire sans contrainte
-CI 10 (3h) : programmation non linéaire avec contraintes

Evaluation

- 1re session : contrôle continu par une note de participation (B : bonus de 1,5 points maximum - questionnaire) et un contrôle écrit 3h (C1), documents autorisés : polycopiés distribués
- 2e session : Contrôle écrit 3 heures (C2), documents autorisés : polycopiés distribués
- Note finale : NF = max (C1+B, min(C2+B,13))

Bibliographie

T. Cormen, C. Leiseron et R. Rivest, Introduction à l’algorithmique, Dunod, 2002
J. C. Culioli, Introduction à l'optimisation, Ellipses, 2012
M. Gondran et M. Minoux, Graphes et algorithmes, Tec & Doc Lavoisier, 2009
M. Minoux, Programmation mathématique, Tec & Doc Lavoisier, 2007