Descriptif
Ce cours traite des méthodes de résolution de problèmes d’optimisation combinatoire fondées sur la programmation mathématique. Après une introduction générale on montre que de nombreux problèmes de Recherche Opérationnelle peuvent être modélisés puis résolus à l’aide de la Programmation Linéaire (PL) où la fonction objectif et les contraintes sont toutes linéaires et les variables sont continues. Le cours présente les principes de base de la PL et les principaux algorithmes de résolution. L’approche par PL fournit également une aide à la résolution de problèmes plus difficiles (non linéaires, en variables entières,…) en particulier en fournissant des bornes de la solution optimale. On étudiera les méthodes de relaxations continues et lagrangiennes ainsi que l'amélioration des bornes par des méthodes de coupes. Le cours sera illustré par des applications concrètes (tournées de véhicules, localisation, ordonnancement). Enfin, on abordera la résolution de problèmes en univers incertain.
Un apprentissage à des logiciels de modélisation et de PL est proposé en TP puis approfondi dans la réalisation d’un projet.
Un apprentissage à des logiciels de modélisation et de PL est proposé en TP puis approfondi dans la réalisation d’un projet.
23 heures en présentiel (6 blocs ou créneaux)
réparties en:
- Travaux dirigés en salle info : 2
- Contrôle : 2
- Stage de communication : 11
- Cours d'improvisation et théatre : 8
Diplôme(s) concerné(s)
- Master 2 Recherche Opérationnelle
- Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Parcours de rattachement
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
MAP-RO
MAE41
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 :
Examen et soutenance du projet.
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
- Crédits ECTS acquis : 1.5 ECTS
- Scientifique acquis : 1.5
Le coefficient de l'UE est : 1.5
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 2 Recherche Opérationnelle
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 10
- Crédits ECTS acquis : 4 ECTS
Le coefficient de l'UE est : 4
La note obtenue rentre dans le calcul de votre GPA.
Programme détaillé
- Séance 1: Rappels de PL, Dualité, Programmation en nombres entiers. Exercices
- Séance 2: Modélisation des problèmes par la programmation linéaire en nombres entiers, notion de bonne formulation
- Séance 3: Prise en main des aspects informatiques. Présentation du projet
- Séance 4: Méthoes de décomposition, Relaxation lagrangienne, génération de colonnes. Exercices
- Séance 5: Point sur le projet. Aspects polyédriques de la PLNE : inégalités valides, algorithmes de plans coupants. Exercices.
- Séance 6: Contrôle écrit
- TD: Soutenance de projet