v1.13.2 (763)

Cours scientifique - SOD321 : 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.

Objectifs pédagogiques

 Connaissance des aspects théoriques et pratiques de la programmation en nombres entiers et de sa capacité de modélisation et de résolution de problèmes

nombre d'heure en présentiel

23

nombre de blocs

6

Volume horaire par type d'activité pédagogique : types d'activité

  • Travaux dirigés en salle info : 2
  • Contrôle Final : 2
  • Bloc de 1/2 journée 3h : 11
  • Bloc de 1/2 journée en salle info : 8

Diplôme(s) concerné(s)

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 Master 2 Recherche Opérationnelle

Vos modalités d'acquisition : contrôle continu, exposés. Pas de rattrapge

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.

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.

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.

Programme détaillé

  • Séance 1: Rappels de programmation linéaireLinear programming , 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 Programmation Linéaire en Nombres Entiers : 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

Méthodes pédagogiques

Cours, Exercices et Travaux Pratiques
Veuillez patienter