Recherche Opérationnelle: graphes et algorithmes

I. Introduction à la Recherche Opérationnelle et à la modélisation
Introduction à la recherche opérationnelle
Méthodologie de résolution d’un problème de RO
Modélisation et validation de modèle
Choix de la méthode de résolution
II. Notions fondamentales de la théorie des graphes
Définitions et généralités
Chaînes, cycles et connexité
Représentation matricielle d’un graphe
Problème de coloration (algorithmes Welch et Powel ;DSatur)
Problème de l’arbre couvrant de poids minimum (algorithmes kruskal et Prim)
III. Problème de cheminement
Parcours eulériens et hamiltoniens
Position du problème du plus court chemin
Propriétés des plus courts chemins
Algorithmes du plus court chemin : Djikstra, Bellman, Ford et algorithme de Floyd.

IV. Problème du flot maximum
Position du problème
Flots compatibles, complets
Amélioration de flots
Algorithme de Ford et Fulkerson
V. Problème d’ordonnancement
Position du problème
Réseau associé à un projet
Méthode MPM
Méthode PERT

VI. Programmation Linéaire
Problématique de la programmation Linéaire
Modélisation et résolution graphique
L’algorithme du Simplexe
Obtention d’une solution de base réalisable : Algorithme du simplexe de deux phases

VII. La dualité dans la Programmes Linéaire
La dualité et son interprétation
Propriétés de la dualité
Du problème dual au problème primal
L’algorithme dual du Simplexe