UEM 1.2

Recherche Opérationnelle

Département
Second cycle
Année d étude
1ére Année
Semestre
1
Crédit
3
Coefficient
3
Enseignants du module
BENNABI SAKINA RIM

Pré requis :

Algèbre Linéaire, Analyse matricielle

OBJECTIFS :

Ce cours a pour objectif de présenter les principales méthodes et techniques utilisées dans la recherche opérationnelle. Cette dernière est à la croisée de trois disciplines : la résolution de problèmes, les mathématiques et l’informatique. Les graphes sont un instrument puissant pour modéliser de nombreux problèmes combinatoires. La programmation linéaire aide à résoudre un problème de maximisation ou minimisation d’une fonction objective sous un certain ensemble de contraintes. Ce cours propose des algorithmes très efficaces pour la résolution de nombreux problèmes connus, comme les
algorithmes de la recherche du plus court chemin ou le problème d’ordonnancement.

CONTENU DU MODULE :

I. Introduction à la Recherche Opérationnelle et à la modélisation (4H)
1. Introduction à la recherche opérationnelle
2. Méthodologie de résolution d’un problème de RO
3. Analyse du système
4. Modélisation et validation de modèle
5. Mise en œuvre
6. Etude de cas
II. Notions fondamentales de la théorie des graphes (4 H)
1. Introduction
2. Historique
3. Domaines d’application
4. Généralités et Définitions
5. Quelques types de graphe
6. Chaînes et Cycles
7. Graphe eulérien et Graphe semi eulérien
8. Graphe hamiltonien
9. Représentation d’un graphe sur machine
III. Coloration par graphe (4 H)
1. Introduction
2. Exemple d’application
3. Définitions et propriétés
4. L’algorithme de Welsh et Powell
5. Le théorème des quatre couleurs
IV. Arbres et Arborescence (4H)
1. Définitions
2. Codage de Prüfer
3. Problème de l’arbre de poids minimum

V. Problème du plus court chemin (6H)
1. Position du problème, théorie fondamentale
2. Propriétés et théorèmes
3. Algorithmes du plus court chemin : Djikstra, Dantzig, Ford et Floyd.
VI. Problème du flot maximum (4H)
1. Position du problème, théorie fondamentale
2. Amélioration des flots
3. Algorithme de Ford et Fulkerson
VII. Problème d’ordonnancement (4H)
1. Position du problème
2. Méthode MPM
3. Méthode PERT
VIII. Programmation linéaire (9H)
1.Définition
2. Forme canonique et forme standard d’un programme linéaire
3.Propriétés d’un programme linéaire
4. Résolution graphique
5. Méthode du simplexe
6. Dualité
IX. Problème de Transport (6H)
1. Position du problème de Transport
2. Formulation du problème
3. Résolution du problème de Transport :
4. Algorithme de BALAS-HAMER et STEPPING STONE
5. Le problème d’affectation et méthode hangroise

course

Consultez les ressources disponibles concernant ce module sur le moteur de recherche de la bibliothèque, ou accédez directement au cours de vos enseignants via la plateforme de téléenseignement de l’école « e-learn ».