Programmes des modules

Optimisation et étude de cas M2, MF

- Concept de modèle en aide à la décision

- Description du processus de modélisation et de ses différentes phases

- Présentation de modélisations non triviales de problèmes de décision utilisant divers cadres de modélisation (Programmation linéaire, files d’attentes, …)

- Analyse multicritère

- Etude de cas

- Optimisation

- Applications aux données financières

Bibliographie

- J Birge and F Louveaux, Introduction to Stochastic Programming, Springer, 1997

- S Bradley, A. Hax and T. Magnanti, Applied Mathematical Programming, Addison-Wesley, 1977

- Ph. Vallin, et D Vanderpooten, Aide à la décision : une approche par les cas, Ellipses, paris, 2002

- Y. Colette, P. Siarry, L’Optimisation multiobjectif et ses applications, Eyrolles 2002

- J. Dreo et al : Métaheuristiques pour l’optimisation difficile, Eyrolles, 2003

- B. Roy, Méthodologie multicritère d’aide à la décision, Economica

Intitulé de la Matière : Optimisation combinatoire
Crédits : 4
Coefficients : 3
Objectifs de l’enseignement (Décrire ce que l’étudiant est censé avoir acquis comme
compétences après le succès à cette matière – maximum 3 lignes).
Cette matière permet aux étudiants de maîtriser les principales techniques d’optimisation combinatoire. Ces techniques jouent un rôle important dans les secteurs économiques et industriels. C’est ainsi que des exemples concrets (sac-à-dos, voyageur de commerce, atelier, planification, …etc.) sont souvent traités afin d’illustrer ces techniques.
Connaissances préalables recommandées (descriptif succinct des connaissances
requises pour pouvoir suivre cet enseignement – Maximum 2 lignes).
un bagage de base en programmation linéaire et théorie des graphes acquis
généralement en licence.
Contenu de la matière :
Introduction générale - Programmation linéaire en nombres entiers - Méthode par
séparation et évaluation – approche polyédrale - Algorithme A* - Méthodes approchées - Méthodes de décomposition –algorithmes de réduction.
Mode d’évaluation : Contrôle continu, Examen, etc. (la pondération est à l'appréciation de l'équipe de formation)…………CC, E et TP………………………
Références (Livres et polycopiés, sites Internet, etc).
- I. Charon, A. Germa, O. Hudry. Méthodes d’optimisation combinatoire. Masson.
- http://www.amazon.fr/Optimisation-combinatoire-MichelSakarovitch/dp/2705659765
- Paschos Vangelis Th. / Optimisation combinatoire 1 : concepts fondamentaux (Traité IC2, série Informatique et systèmes d'information) / 2005 / Lavoisier / 348p

Intitulé de la Matière : Complexité algorithmique
Crédits : 6
Coefficients : 3
Objectifs de l’enseignement (Décrire ce que l’étudiant est censé avoir acquis comme
compétences après le succès à cette matière – maximum 3 lignes).
Maîtriser les notions de cette matière en vue de leur exploitation dans l’étude de problèmes types ou
problèmes concrets.
Connaissances préalables recommandées (descriptif succinct des connaissances
requises pour pouvoir suivre cet enseignement – Maximum 2 lignes).
Algèbre et analyse de 1ère année universitaire ainsi qu’un bagage de base en
programmation linéaire et théorie des graphes acquis généralement en licence.
Contenu de la matière :
Introduction générale – Complexité des algorithmes (coût d'un algorithme, Ordres de grandeurs,
Complexité en temps et en espace, illustrations) - complexité des problèmes( Problèmes
d'optimisation, de décision. Classes P, NP, NP-dur. Preuves de NP-difficulté, réduction, Stratégies
de "contournement" de problèmes NP-difficiles, Autres classes de complexité, PTAS) – études de
cas.
Mode d’évaluation : Contrôle continu, Examen, etc.(la pondération est à l'appréciation
de l'équipe de formation)…………CC, E et TP………………………
Références (Livres et polycopiés, sites internet, etc).
- I. Lavallée / Complexité et algorithmique avancée - Une introduction / Hermann,
2008.
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M.
Protasi
Complexity and Approximation - Combinatorial Optimization Problems and Their
Approximability Properties Springer, 2003.

Intitulé du Master : Recherche Opérationnelle, Management, Risque et Négociation «ROMARIN»
Semestre : 03
Intitulé de l’UE1 : Fondamentale
Matière2 : Optimisation discrète numérique
Crédits : 4
Coefficients : 3
Objectifs de l’enseignement (Décrire ce que l’étudiant est censé avoir acquis comme
compétences après le succès à cette matière – maximum 3 lignes).
Cette matière permet aux étudiants de maîtriser les principales techniques d’optimisation
combinatoire. Ces techniques jouent un rôle important dans les secteurs économiques et industriels.
Connaissances préalables recommandées (descriptif succinct des connaissances
requises pour pouvoir suivre cet enseignement – Maximum 2 lignes).
Algèbre et analyse de 1ère année universitaire ainsi qu’un bagage de base en
programmation linéaire et théorie des graphes acquis généralement en licence.
Contenu de la matière :
Introduction générale- Programmation linéaire et programmation quadratique convexe –
complément de la Programmation linéaire en variables mixtes - Techniques de base pour modéliser
un problème d'optimisation discret par un programme linéaire ou quadratique convexe en variables
mixtes - Résolution de problèmes non linéaires continus par la programmation linéaire mixte –
complément de l’optimisation combinatoire.
Mode d’évaluation : Contrôle continu, Examen, etc.(la pondération est à l'appréciation
de l'équipe de formation)…………CC, E et TP………………………
Références (Livres et polycopiés, sites internet, etc).
- M. Sakarovitch / Optimisation / Dunod / 1997.
- A. Billionnet. Optimisation Discrète. Dunod. 2007.
- Voir l’Internet pour des références plus récentes.

Intitulé du Master : Mathématiques et Informatique Décisionnelle Semestre : S2 Module : Etude de complexité Enseignant responsable de l’UE : Enseignant responsable de la matière : Ouafi Rachid Objectifs de l’enseignement : Acquérir des notions et outils pour mesurer l'efficacité d'une algorithme pour résoudre un problème : Comprendre la notion de complexité d'un algorithme, savoir évaluer la complexité d'un algorithme itératif et récursif (Coût d'un algorithme , ordre de grandeur). Complexité des problèmes de décision, réduction polynomiales et preuve de Np-complétude Connaissances préalables recommandées Algorithmique, combinatoire, logique. Contenu de la matière : - Introduction générale - Complexité des algorithmes (coût d'un algorithme, Ordres de grandeurs, Complexité en temps et en espace, illustrations) - Complexité d'un algorithme itératif et récursif - Complexité des problèmes de décision. Classe P, Classe NP, Réduction polynomiale, Classe NPComplet. - Complexité des problèmes d’optimisation Mode d’évaluation : ……continu & examen………………………………………… Références - I. Lavallée, Complexité et algorithmique avancée - Une introduction, Hermann, 2008. - G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability Properties, Springer, 2003. - M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, Macmillan Higher Education, 1979