Descriptif
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.
Objectifs pédagogiques
- les outils basiques de résolution de problèmes d’optimisation combinatoire;
- les rudiments de la théorie des graphes;
- la programmation mathématique.
- Cours magistral : 6
- Petite classe : 12
- Contrôle : 3
effectifs minimal / maximal:
10/100Diplôme(s) concerné(s)
- Master 1 Parisien de Recherche Opérationnelle
- Master 1 Applied Mathematics ans statistics - Orsay
- Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Parcours de rattachement
Pour les étudiants du diplôme Master 1 Applied Mathematics ans statistics - Orsay
AO101
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
AO101
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Vos modalités d'acquisition :
- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 2 ECTS
- Scientifique acquis : 2
Le coefficient de l'UE est : 1
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Pour les étudiants du diplôme Master 1 Parisien de Recherche Opérationnelle
Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)- le rattrapage est obligatoire si :
- Note initiale < 7
- Crédits ECTS acquis : 2.5 ECTS
Le coefficient de l'UE est : 1
Pour les étudiants du diplôme Master 1 Mathématiques Appliquées
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 7
- le rattrapage peut être demandé par l'étudiant si :
- 7 ≤ note initiale < 10
- Crédits ECTS acquis : 2 ECTS
Le coefficient de l'UE est : 1
Pour les étudiants du diplôme Master 1 Applied Mathematics ans statistics - Orsay
Vos modalités d'acquisition :
Examen écrit
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 7
- le rattrapage peut être demandé par l'étudiant si :
- 7 ≤ note initiale < 10
- Crédits ECTS acquis : 2 ECTS
- Scientifique acquis : 2
Le coefficient de l'UE est : 1
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Programme détaillé
1. Cours magistral:
Définitions de base des graphes.
Arbres couvrants et chemins.
2. PC:
Exercices.
3. Cours magistral:
Problèmes de flots.
Chaînes améliorantes.
Coupe minimale.
Algorithme de Ford-Fulkerson.
4. PC:
Exercices.
5. Cours magistral:
Fin des flots.
Programmation linéaire.
Algorithme du simplexe.
6. PC:
Exercices
7. Cours magistral:
Programmation linéaire - suite:
Dualité. Conditions de écarts complémentaires.
8. PC:
Exercices
9. Cours magistral:
Fin programmation linéaire. Programmation en nombres entiers. Méthodes arborescentes.
10. PC:
Exercices.
11. Cours magistral:
Fin Programmation en nombres entiers.
Quelques idées sur la RO et ses applications.
12. PC:
Exercices.
13. Contrôle:
Examen écrit