La première partie de ce cours se propose de rendre compte des trois composantes qui s’entremêlent en théorie des graphes : Résolution des problèmes, mathématiques discrètes et algorithmiques. La deuxième partie de ce cours s’intéresse à la programmation linéaire qui est un des domaines les plus utilisés de la RO. Elle permet de traiter un vaste ensemble de problèmes d’optimisation dans des contextes divers comme la gestion de stocks, flux de transport, distribution de tâches à des personnels, recherche de plans de fabrication etc. . . La modélisation de ces problèmes débouche sur des équations ou inéquations linéaires (exprimant les différentes contraintes) dont on cherche les solutions permettant d’optimiser une fonction économique elle-même linéaire.

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

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

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

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

TP optionnel

L. R. Ford et D. R.Fulkerson, “Flows and networks”, Princeton University Press.
M. Gondron et M. Minoux, ” Graphs and Algorithms” Wiley Interscience, 1984.
R. Bronson, ”Operations Research ” Série Shaum, 1982.
Dantzig G. Linear programming and extensions. Princeton university press; 2016 Aug 10.