COVID-19
COVID-19

Recherche Opérationnelle: graphes et algorithmes

ESI > Data science > Recherche Opérationnelle: graphes et algorithmes

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.

Pré-requis:

Algèbre Linéaire, Analyse matricielle

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

ID Cours
RO
Niveau
1ère année CS
Semestre
Semestre 1
Crédit
3
Volumes Horaires Cours
30.00
Coef
3
Volumes Horaires TD
15.00
Domaine

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

 

Contenu

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

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.

We are using cookies to give you the best experience. You can find out more about which cookies we are using or switch them off in privacy settings.
AcceptPrivacy Settings

GDPR