Logo ESI
Bannière
ESI talents

Bienvenue



Retour - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Syllabus RO
Télécharger



Crédits : 3

RO
Recherche Opérationnelle: graphes et algorithmes
Operations Research and Graph Theory

Coef : 3
VH Cours : 30.00
VH TD : 15.00
Pré-requis :
Algèbre Linéaire, Analyse matricielle

Ingénierie des Compétences

Familles de Compétences
  • CF2 : Modéliser des systèmes complexes
Type de compétence: TEC : Technique, MET : Méthodologique, MOD : Modélisation, OPE : Opérationnel,
Niveau de compétence:
Base Intermédiaire Avancé


Famille de Compétence Compétence Elément de Compétence Type
CF2 C2.2: Modéliser et optimiser un système complexe C22.1: Exploiter la théorie des graphes pour modéliser un système de systèmes complexe MOD
C22.2: Exploiter la programmation linéaire pour modéliser et chercher une solution à un problème MOD

Description du programme de la matière

Objectifs:

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.

Contenu:

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

Travail Personnel:

TP optionnel

Bibliographie:

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.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -