Détails du cours MAP-RO1

Discrete Optimisation

Cette page est essentiellement destinée aux enseignants et regroupe toutes les informations nécessaires à la gestion d'un cours ENSTA.

Identité du cours

Sigle : MAP-RO1
Titre français : Initiation à la recherche opérationnelle [V3D]
Titre anglais : Discrete Optimisation
Méta infos : modifiée le : 31/01/2017   par : mcosta   Nb de visiteurs : 536   annee : 2A      periode : 1      Rattachement/module : voie      unités : 1      ECTS : 2      type : unknown     
ouvert : Oui     modif. autorisée : Oui     email auto. au responsable : Oui     à évaluer : Oui     en ligne : Non    
domaine ParisTech : 1,1a,1b,2a    

Equipe pédagogique

Responsable (login) :
Professeur principal :
Professeurs participants : Marie-Christine COSTA,   
Maitres de conférences : Marie-Christine COSTA,    Matthieu CHARDY,    Adrien LOSEILLE,    Dominique QUADRI,    Arnaud LAZARE,    Eric SOUTIL,    Dimitri WATEL,   

Contenu

a pour prérequis : AO101
est prérequis pour : Les cours de 3ème année OROC-RO-PM, OROC-RO-DM, OROC-RO-CP, OROC-RO-MH
Master de Recherche opérationnelle: MPRO
Objectifs :

1. Descriptif


La Recherche Opérationnelle (R.O.) est la discipline des méthodes
scientifiques utilisables pour élaborer de meilleures décisions. Elle permet
de rationaliser, de simuler et d’optimiser l’architecture et le
fonctionnement des systèmes de production ou d’organisation. La R.O.
apparaît comme une discipline-carrefour associant les mathématiques,
l’économie et l’informatique.
Les apports de la R.O. sont visibles dans les domaines les plus divers : de
l’organisation des lignes de production de véhicules à la planification des
missions spatiales, de l’optimisation de portefeuilles bancaires à l’aide
au séquençage de l’ADN ou à l’organisation de la couverture satellite des
téléphones portables…
Tous ces problèmes sont de nature discrète ou combinatoire. Si l'existence
d'une solution optimale est en général triviale, sa recherche de manière
énumérative, même effectuée par les ordinateurs les plus puissants, pourrait
demander plusieurs siècles de calcul.

Le but du cours est de familiariser les élèves avec l’optimisation
combinatoire et de leur faire connaître des outils qui permettent de résoudre
les problèmes les plus faciles, en particulier les graphes et la programmation
mathématique.

2. Compétences à acquérir


Être capable, grâce à ses connaissances en optimisation combinatoire, de
mettre en œuvre:
- les outils basiques de résolution de problèmes d’optimisation
combinatoire;
- les rudiments de la théorie des graphes;
- la programmation mathématique.


3. Programme des séances

Mots clés : Optimisation combinatoire, algorithmes de graphes, programmation linéaire.
Objectives : Finding optimal solutions to combinatorial problems would require centuries with
a naive enumerative approach. This course presents tools to efficiently solve
these problems. These methods are based both on discrete mathematics (especially
graph theory) and on algorithmics. The practical use of the methods will be
presented on "real-life" problems.
Keywords : Combinatorial optimization, Graph algorithms, linear programming
Supports : Photocopies des vues utilisées en cours.
Liens : http://www.roadef.org, http://www.ensta.fr/~diam/ro/,
Biblio : Précis de Recherche Opérationnelle. R. Faure, B. Lemaire et C. Picouleau. Ed
2007. Dunod.

Recherche opérationnelle pour ingénieurs - I Dominique de Werra , Thomas M.
Liebling , Jean-François Hêche 2003 Presses Polytechniques et Universitaires
Romandes (PPUR) /Eyrolles.

Introduction à l'algorithmique (2nde édition)
Cours et exercices corrigés - 2e cycle - Écoles d'ingénieurs
Thomas Cormen , Charles Leiserson , Ronald Rivest , Clifford Stein
Dunod, 2002.

Optimisation discrète- De la modélisation à la résolution par les logiciels
de programmation mathématique. Alain Billionnet. Dunod,2007.
Contrôle : Examen final. Documents autorisés: polycopié du cours et notes manuscrites.
Aucun livre.

Besoins particuliers et remarques éventuelles

Moyens :
Commentaires :

Séances

ven. 27 janv. 2017   - 09:00 à 12:15 : Cours Magistral (CM)
programme : Définitions de base des graphes. Arbres couvrants et chemins. Problèmes de flots. Chaînes améliorantes. Algorithme de Ford-Fulkerson.
besoin : Vidéo,
Intervenants : Marie-Christine COSTA,
ven. 03 févr. 2017   - 09:00 à 10:00 : Cours Magistral (CM)
programme : Fin des Problèmes de flots. Coupe minimale. Programmation linéaire: début
besoin : Vidéo,
Intervenants : Marie-Christine COSTA,
ven. 03 févr. 2017   - 10:15 à 12:15 : Petite Classe (PC)
programme : Exercices arbres et chemins.
besoin :
Intervenants : Marie-Christine COSTA, Matthieu CHARDY, Adrien LOSEILLE, Dominique QUADRI, Arnaud LAZARE, Eric SOUTIL,
ven. 10 févr. 2017   - 09:00 à 10:00 : Cours Magistral (CM)
programme : Programmation linéaire. Algorithme du simplexe.
besoin : Vidéo,
Intervenants : Marie-Christine COSTA,
ven. 10 févr. 2017   - 10:15 à 12:15 : Petite Classe (PC)
programme : Exercices Flots
besoin :
Intervenants : Marie-Christine COSTA, Matthieu CHARDY, Dominique QUADRI, Arnaud LAZARE, Eric SOUTIL, Dimitri WATEL,
ven. 24 févr. 2017   - 09:00 à 10:00 : Cours Magistral (CM)
programme : Dualité. Conditions de écarts complémentaires. Programmation en nombres entiers: méthodes arborescentes.
besoin : Vidéo,
Intervenants : Marie-Christine COSTA,
ven. 24 févr. 2017   - 10:15 à 12:15 : Petite Classe (PC)
programme : Exercices PL
besoin :
Intervenants : Marie-Christine COSTA, Matthieu CHARDY, Adrien LOSEILLE, Dominique QUADRI, Arnaud LAZARE, Eric SOUTIL,
ven. 10 mars 2017   - 09:00 à 10:00 : Cours Magistral (CM)
programme : Fin PLNE. Quelques idées sur la RO et ses applications.
besoin : Vidéo,
Intervenants : Marie-Christine COSTA,
ven. 10 mars 2017   - 10:15 à 12:15 : Petite Classe (PC)
programme : Exercices PL-PLNE
besoin :
Intervenants : Marie-Christine COSTA, Matthieu CHARDY, Adrien LOSEILLE, Dominique QUADRI, Arnaud LAZARE, Eric SOUTIL,
ven. 17 mars 2017   - 09:00 à 12:15 : Petite Classe (PC)
programme : Exercices. Révision.
besoin :
Intervenants : Marie-Christine COSTA, Matthieu CHARDY, Adrien LOSEILLE, Dominique QUADRI, Arnaud LAZARE,
ven. 24 mars 2017   - 09:00 à 12:00 : Contrôle (CC)
programme : Examen écrit
besoin :
Intervenants : Marie-Christine COSTA, Arnaud LAZARE,