Remerciez-le!

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

Et grphe imp Graphes et Recherche Op ?erationnelle ESIAL eme ann ?ee Notes de cours de J -F Scheid - C CTable des mati eres Introduction g ?en ?erale Quelques exemples et domaines d ? applications de la R O Formalisation Contenu du cours El ?ements de bib

Graphes et Recherche Op ?erationnelle ESIAL eme ann ?ee Notes de cours de J -F Scheid - C CTable des mati eres Introduction g ?en ?erale Quelques exemples et domaines d ? applications de la R O Formalisation Contenu du cours El ?ements de bibliographie Programmation lin ?eaire Introduction Mod ?elisation R ?esolution graphique Formes g ?en ?erales d ? un programme lin ?eaire Forme canonique mixte Forme canonique pure Forme standard Variable d ? ?ecarts Solutions de base r ?ealisables Propri ?et ?es g ?eom ?etriques des solutions de base r ?ealisables Algorithme du simplexe L ? algorithme du simplexe proprement dit la phase M ?ethode des dictionnaires M ?ethode des tableaux Finitude du simplexe Initialisation et variables arti ?cielles la phase Analyse post-optimale Analyse post-optimale de l ? objectif Analyse post-optimale du second membre des contraintes Dualit ?e Introduction et d ?e ?nition Propri ?et ?es - Th ?eor emes de dualit ?e Conditions d ? optimalit ?e primal-dual COPD C TABLE DES MATIE RES CChapitre Introduction g ?en ?erale Une d ?e ?nition possible de la R O pourrait etre la suivante il s ? agit d ? un ensemble de m ?ethodes d ? analyse scienti ?que maths et info des ph ?enomenes d ? organisation qui traite de la maximisation d ? un pro ?t d ? une performance d ? un rendement ou bien de la minimisation d ? un cou t d ? une d ?epense La R O est avant tout un outil d ? aidea la d ?ecision Le sch ?ema g ?en ?eral suivi par ces m ?ethodes est Probl eme concret de type R O ? mod ?elisation ? r ?esolution par une m ?ethode de R O ? interpr ?etation des r ?esultats ? prise de d ?ecision Quelques exemples et domaines d ? applications de la R O Un premier exemple Les ponts de K ?onigsberg Euler Deux les de la ville sont reli ?ees entre elles par pont D ? autre part autres ponts relient les les ala ville La question pos ?ee est la suivante a partir d ? un point de d ?epart quelconque existe-t-il un chemin passant une et une seule fois par chaque pont et qui revient au point de d ?epart Fig ?? La ville de Ko ?nigsberg et ses ponts La r ?eponse apport ?ee par Euler est NON La preuve utilise un graphe les ar etes du graphe repr ?esentent les ponts et les sommets correspondent aux di ? ?erents endroits de la ville les rives gauche et droite et les deux les cf Figure Supposons qu ? un tel chemin existe Un tel chemin est appel ?e chemin eul ?erien Alors n ?ecessairement en chacun des noeuds du graphe il y a toujours un nombre pair d ? ar etes reli ?ees au noeud s ? il y a une ar ete qui arrive au noeud il y en a n ?ecessairement une autre di ? ?erente qui