v2.2.4 (2114)

Cours scientifique - RO202 : Optimisation discrète

Domaine > Analyse et Calcul Scientifique, Probabilités et Statistiques, Optimisation, Recherche opérationnelle et Commande, Mathématiques et leurs applications.

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. Des TP seront dédiés à l'implémentation des méthodes de recherches classiques vues en cours. 

Objectifs pédagogiques

Ê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.

nombre d'heure en présentiel

21

Temps de travail global estimé pour l'étudiant

14

nombre de blocs

7

effectifs minimal / maximal

5/60

Diplôme(s) concerné(s)

Parcours de rattachement

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole nationale supérieure de techniques avancées

Aucun

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole nationale supérieure de techniques avancées

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 1.75 ECTS

Le coefficient de l'UE est : 1.75

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Programme détaillé

- Semaine 1 :
Programmation linéaire.
Algorithme du simplexe.

- Semaine 2 :
PL suite:
Dualité. Conditions de écarts complémentaires.

- Semaine 3
Fin PL. Programmation en nombres entiers: méthodes arborescentes.

- Semaine 4 
Fin PLNE.
Quelques idées sur la RO et ses applications.

- Semaine 5
Définitions de base des graphes.
Arbres couvrants et chemins.

- Semaine 6
Problèmes de flots.
Chaînes améliorantes.
Coupe minimale.
Algorithme de Ford-Fulkerson.

- Semaine 7
Examen écrit

Mots clés

optimisation discrète, programmation linéaire en nombres entiers, graphe

Méthodes pédagogiques

CM, TD, TP
Veuillez patienter