GP74 - Optimisation

* L'étudiant apprendra des méthodes exactes et approchées pour résoudre des problèmes d'optimisation et de gestion des flux dans les systèmes de production et de transport logistique. L'étudiant sera capable de: * Formuler mathématiquement le problème d'optimisation et d'analyser sa difficulté, * Choisir, en fonction de la difficulté, une méthode pour le résoudre, * Implémenter la méthode choisie.

CM : 15, TD : 26, TP : 35, THE : 24
Crédits : 4 ECTS

Programme

Programmation dynamique (Algorithme de Bellman)

Flot maximum dans un graphe (Algorithme de Ford-Fulkerson)

Flot à coût minimum dans un graphe (Méthode de Stepping Stone)

Problème d'affectation (Méthode Hongroise)

Plus court chemin dans un graphe (Algorithme de Dijkstra)

Problème du voyageur de commerce (Algorithme de Little)

Introduction aux méthodes approchées (Algorithmes glouton, Méthode de descente, Recuit simulé, Méthode Tabou, Algorithme génétique, ...)

Compétences

Résoudre un problème de programmation dynamique:

  • Reconnaitre un problème de programmation dynamique.
  • Expliquer l'algorithme de Bellman et l'appliquer à des problèmes concrets (planification de production, gestion de stocks, problème d'affectation, ...)

    Résoudre un problème par application d'algorithmes spécifiques:

  • Décrire les algorithmes spécifiques aux problèmes de transport (flot maximum, flot à coût minimum, affectation, plus court chemin, voyageur de commerce) : Ford-Fulkerson, Stepping stone, Méthode hongroise, Dijkstra, Little, méthodes approchées
  • Expliquer les cas d'application de chaque algorithme.
  • Appliquer ces algorithmes.

    Adapter l'algorithme au problème:

  • Reconnaitre le type de problème
  • Choisir et justifier la méthode la plus adaptée : algorithme général (programmation linéaire, dynamique, en nombres entiers), algorithme spécifique ou méthode approchée.