Remerciez-le!

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

Recherche Opérationnelle - Graphes Yves Correc 08/10/2007 0–1 Recherche Opérati

Recherche Opérationnelle - Graphes Yves Correc 08/10/2007 0–1 Recherche Opérationnelle Graphes Yves Correc Recherche Opérationnelle - Graphes Yves Correc 08/10/2007 0–2 Sommaire 0. INTRODUCTION .......................................................................................................................0–3 0.1. Les graphes ...........................................................................................................................0–3 0.2. La programmation linéaire .....................................................................................................0–5 1. ELEMENTS DE LA THEORIE DES GRAPHES........................................................................1–6 1.1. Représentations d'un graphe.................................................................................................1–6 1.1.1. Représentation graphique ..............................................................................................1–6 1.1.2. Dictionnaire des suivants................................................................................................1–6 1.1.3. Matrice d'adjacence........................................................................................................1–7 1.1.4. Matrice d'incidence sommets-arcs .................................................................................1–8 1.2. Définitions ............................................................................................................................1–10 1.3. Analyse de la structure d'un graphe ....................................................................................1–12 1.3.1. Recherche de circuits ...................................................................................................1–12 1.3.2. Décomposition en niveaux............................................................................................1–14 1.3.3. Fermeture transitive des sommets d'un graphe ...........................................................1–16 1.3.4. Composantes fortement connexes d’un graphe...........................................................1–19 1.3.5. Composantes connexes d'un graphe ...........................................................................1–22 Recherche Opérationnelle - Graphes Yves Correc 08/10/2007 0–3 0. INTRODUCTION 0.1. LES GRAPHES Les graphes donnent une représentation aisément manipulable des relations qui peuvent apparaître lors de l'analyse des phénomènes étudiés. Ces relations peuvent être spatiales (réseaux), temporelles (ordonnancement de projet) ou autres (routage, affectation, ...). Les modèles ainsi construits peuvent alors être utilisés pour rechercher une solution optimale (en un sens à préciser : coût, durée, qualité…) aux problèmes posés. Problème réel Ð position Ð Problème bien posé Ð analyse Ð Modèle mathématique Ð résolution Ð Solution On n'insistera jamais assez sur l'importance des deux premières étapes: il ne sert à rien de se précipiter pour résoudre ce que l'on croit être le problème mathématique posé, et trouver une solution fausse au problème physique originel !… On illustrera ce syndrome malheureusement trop répandu par un exemple classique: Un problème d'optimisation de porte-feuille (c'est à dire de répartition de ressources financières entre divers placements -actions, obligations, etc-) peut se ramener à un problème de programmation linéaire, ce qui revient à rechercher l'optimum d'une certaine fonction –le rendement global- à l'intérieur d'un polyèdre dont les facettes représentent les diverses contraintes qui s'appliquent à ce choix. La question posée habituellement s'énonce "déterminer la politique d'investissement optimale…", et appelle par conséquent une solution du genre " investir x en actions machin, y en actions truc, z en obligations…". Mais la contrainte sous-jacente, oubliée généralement par beaucoup d'étudiants, est que les ressources à investir ne sont pas infinies, même si l'on n'en a pas dit un mot auparavant. La seule solution consiste donc à raisonner en termes de pourcentages (x%, y%, z%… de l'investissement global), ce qui revient à inclure explicitement dans les contraintes du problème la contrainte implicite "x + y + z = 100" ,dont l'absence conduira à une solution tout à fait surréaliste !… En résumé, les trois étapes précitées sont indispensables, et passer rapidement sur les deux premières est un moyen très sûr de faire des bêtises. Donc: (1) Poser correctement le problème physique. Vérifier que l'on a bien compris le besoin du client, et que toutes les données sont sur la table, y compris les hypothèses implicites (c'est le non- dit qui tue!). (2) Analyser le problème pour le transformer en un problème mathématique que l'on sait résoudre, et dont les méthodes sont l'objet de ce cours. (3) Résoudre le problème mathématique ainsi construit, et ne pas oublier de revenir au problème physique de départ, pour en donner la solution dans les termes de celui qui vous l'a posé. C'est pour cela que la recherche opérationnelle est une discipline à part entière. Pour reprendre une citation du professeur Faure "les mathématiques sont une science, mais la recherche opérationnelle est un art…". Recherche Opérationnelle - Graphes Yves Correc 08/10/2007 0–4 Exemples Problème du plus court chemin Etant donné un graphe représentant un réseau, il s'agit de trouver le plus court chemin d'un point à un autre. Sur cet exemple, le plus court chemin du point A au point F passe par D et a pour longueur 6. A B C D E F G 5 4 3 10 6 4 1 5 2 2 6 3 2 Problème d'ordonnancement Il s'agit de réaliser "au mieux" un projet composé d'un certain nombre de tâches, soumis en outre à des contraintes de durée, de moyens ou de coût. Cela revient en particulier à trouver le chemin critique dans le graphe représentant le projet, c'est à dire le chemin tel que tout retard pris sur l'une des tâches qui le constituent se répercute sur l'ensemble du projet. Problème de l'arbre minimal Il s'agit de trouver dans un graphe représentant par exemple un réseau de distribution électrique le plus petit (longueur, coût) sous-ensemble de celui-ci qui en assure encore les fonctions. 3 B E 4 6 2 3 A 3 C F 5 4 D Problème du flot maximum Il s'agit de faire passer le flot maximum au travers d'un réseau dont les éléments ont une capacité donnée, limitée. Problème d'affectation Il s'agit d'affecter un ensemble de personnes à un ensemble de tâches de telle sorte que la satisfaction globale (somme des satisfactions individuelles) soit maximale. Recherche Opérationnelle - Graphes Yves Correc 08/10/2007 0–5 Problème de transport Il s'agit d'acheminer au coût minimal un certain nombre de marchandises à partir d'un certain nombre d'origines jusqu'à un certain nombre de destinations, compte tenu de contraintes de capacité sur les tronçons utilisés. Stock0 Destination1 Stock1 Destination2 Stock2 Destination3 Destination4 Problème de tournée Il s'agit de d'effectuer au moindre coût le ramassage d'une denrée quelconque sur l'ensemble des points d'un réseau, en respectant éventuellement des contraintes additionnelles de capacité de transport ou de distance parcourue. 0.2. LA PROGRAMMATION LINEAIRE Soit un processus contrôlé par n variables xj (j=1 à n), il en résulte des effets mesurables yi supposés proportionnels aux variables de contrôle xj (considérées comme causes). Les yi (i = 1,n) peuvent donc s'écrire comme combinaisons linéaires des xj: yi = ai1 x1 + ai2 x2 + ai3 x3 + …… + ain xn (i = 1,n) On cherche alors à minimiser un certain résultat y0 = ∑ ∑ ∑ ∑ cj xj sous les contraintes de bornes yi ≤ bi. Ce qui s'écrit sous forme matricielle: Min c x (c x : objectif, coût, fonction économique) A x ≤ b Avec l'écriture adéquate, les problèmes de graphes peuvent être traités comme des problèmes de programmation linéaire, mais son intérêt n'est évidemment pas là: Elle permet de traiter des problèmes beaucoup plus généraux, pourvu qu'ils résultent de la modélisation de processus linéaires, en variables continues, entières ou booléennes. exemple : Problème de production On fabrique x1 appareils sur une chaîne A, sur laquelle chaque appareil nécessite 3h de fabrication et 1h de finition pour un coût unitaire de 20kF. On fabrique x2 appareils sur une chaîne B, sur laquelle chaque appareil nécessite 1h de fabrication et 2h de finition pour un coût unitaire de 60kF. On dispose dans l'atelier de fabrication de 60h par mois, et dans l'atelier de finition de 70h par mois. La demande est de 30 appareils au moins par mois. Quelle doit être la production pour satisfaire la demande en minimisant le prix de revient ? (on n'oubliera pas les contraintes de production –ateliers-! ) La solution sera donnée par la résolution du problème d'optimisation linéaire suivant: Min 20 x1 + 60 x2 (coût = objectif à minimiser) 3 x1 + 1 x2 ≤ 60 (contrainte atelier de fabrication) 1 x1 + 2 x2 ≤ 70 (contrainte atelier de finition) x1 + x2 ≥ 30 (contrainte demande) Recherche Opérationnelle - Graphes Yves Correc 08/10/2007 1–6 1. ELEMENTS DE LA THEORIE DES GRAPHES 1.1. REPRESENTATIONS D'UN GRAPHE Un graphe est défini par un doublet (X,U), X étant un ensemble de points et U un ensemble de segments les joignant: G = (X,U) avec U ⊂ (X x X) 1.1.1. Représentation graphique X = {points} U = {segments joignants ces points} Un graphe est orienté ou non suivant que l'on impose ou non un sens de parcours sur ses branches. Exemple de graphe (orienté): u 1 u 4 u 2 u 6 u 3 u 5 u 7 u 8 u 9 x 4 x 1 x 5 x 6 x 3 x 2 On peut affecter à chaque branche, une ou plusieurs valeurs numériques qui la caractérisent (distance, capacité, durée, coût, ...). Il en est de même pour les noeuds. Il peut exister plusieurs branches joignant un point à un autre (cas où il existe par exemple plusieurs moyens de transport possibles): on parle dans ce cas de multigraphe. Les points du graphe sont appelés sommets, ou nœuds. Chaque branche joignant deux sommets est appelée arc (graphes orientés) ou arête (graphes non orientés). 1.1.2. Dictionnaire des suivants On définit l'application Γ : XÎX qui à chaque sommet x du graphe associe l'ensemble Γ(x) des sommets accessibles par un arc à partir de celui-ci. On peut alors représenter le graphe, en associant à chaque sommet, la liste de ses suivants: G=(X,Γ) Ce type de représentation est d'autant plus efficace que le graphe est peu dense (mémoire nécessaire ≅ nbsommets x nbarcs issus de chaque sommet) . La variante symétrique (dictionnaire des précédents) associe à chaque sommet la liste de ses "pères" Γ-1(x) (c'est à dire les sommets depuis lesquels on peut venir par un arc). Recherche Opérationnelle - Graphes Yves Correc 08/10/2007 1–7 uploads/Voyage/ rographes.pdf