v2.11.0 (5354)

Cours scientifiques - OROC-RO-PM : Programmation mathématique

Domaine > Mathématiques et leurs applications.

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.

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)

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

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
L'UE est acquise si Note finale >= 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
L'UE est acquise si Note finale >= 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

Mots clés

Optimisation combinatoire, programmation linéaire, relaxation lagrangienne, génération de colonnes, décomposition
Veuillez patienter