Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Logistique pert mpm gant cours de plannification 0

FACULTE DES SCIENCES ECONOMIQUES SOCIALES ET DE GESTION DE REIMS INSTITUT REMOIS DE GESTION Seconde année de Master Management Cours de Monsieur GAIGNETTE année universitair e - l RECHERCHE OPERATIONNELLE METHODES D'AIDE A LA DECISION Support de cours numéro RAPPELS ELEMENTS DE LA THBORIE DES GRAPHES Section I - Notion de base en théorie des graphes I - Graphes orientés I - Entrée sortie boucle chemin circuit etc I - Graphes non orientés Section II -Les di ?érentes représentations d'un graphe orienté II - Représentation sagittale II - Présentation algébrique II - Matrice booléenne II II - Dictionnaire Dictionnaire des des suivants - précéden s Section III - Niveaux ou rangs des sommets d'un graphe orienté Série d'exercices Université de Reims - Faculté des Sciences Economiques Sociales et de Gestion - Antonin Gaignette C- - ELEMENTS DE LA THEORIE DES GRAPHES Commençons par un exemple introductif un agent commercial part de Paris pour vendre des produits à des magasins situés dans trois villes de Province I conna? t la durée approximative des déplacements entre les villes en heures et cherche dans quel ordre il doit les visiter a ?n de perdre le moins de temps possible On peut représenter le problème sous la forme d'un schéma formé de points appelés sommets et de èches dénommées arcs fu Ir'rhoh- ç tA La durée du trajet aller peut di ?érer de celle du retour en raison de travaux etc Les longueurs des èches ne sont pas proportionnelles au temps Il est possible de représenter le problème de façon matricielle lecture dans le sens colonne - ligne PABC P A B C Toute une série de problèmes peut se représenter ainsi par un schéma formé de points réunis par des segments orientés ou non La résolution de ces problèmes problèmes de circulation dans un réseau ou problèmes de traitement complexe d'opérations successives a conduit à l'élaboration d'une théorie mathématique spéci ?que dans le cadre de la recherche opérationnelle la théorie des graphes C'est I'ensemble constitué des points et des segments que I'on appelle un graphe Le concept de graphe permet de schématiser les liaisons les possibilités de communication et les relations d'ordre d'une structure Il o ?re en plus la possibilité d'en étudier l'évolution Université de Reims - Faculté des Sciences Economiques Sociales et de Gestion - Antonin Gaignette Ct - - Section I - Notion de base en théorie des graphes I - Graphes orientés ' Un graplre orienté est dé ?ni par la connaissance de deux ensembles o le premier est constitué d'éléments appelés sommets o le second est composé d'arcs un axc étant un couple orienté de sommets Soit G un graphe On note G X Y X étant I'ensemble des sommets et Y celui des arcs Ainsi si o o yX A - AB C D A-B E B-C C-C C-B C-D C-E D-D D-E Il est possible de représenter le graphe G X de la manière suivante ' ' t A l r --z -r U- Dans cet