Semestre 6 – Optimisation – Modélisation

Cette unité d’enseignement est composée de deux éléments constitutifs (EC) :

Optimisation

Objectifs – acquis d’apprentissage

Calculer le chemin de coût minimal dans un graphe.

Prérequis

Éléments de théorie des graphes.

Contenu pédagogique

Initiation aux différentes techniques de résolution de problèmes, comme les méthodes de simulation heuristiques (principe, construction, optimalité locale, voisinage…) et métaheuristiques (algorithmes évolutionnistes, méthodes de voisinage, recherche tabu, recuit simulé…) et les méthodes d’exploration implicite/arborescente.

Modélisation

Objectifs – acquis d’apprentissage

Modéliser les problèmes d’optimisation par des problèmes de flots dans les réseaux.

Prérequis

Éléments de théorie des graphes.

Contenu pédagogique

  • Modélisation de problèmes d’optimisation en théorie des graphes.
  • Graphes acycliques, décomposition d’un graphe en composantes fortement connexes.
  • Chemin de coût minimal contraint.
  • Flots maximum dans les réseaux.
  • Flots maximum de coût minimum dans les réseaux.