Remerciez-le!

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

Université Cadi Ayyad Ecole Nationale des Sciences Appliquées – Marrakech Filiè

Université Cadi Ayyad Ecole Nationale des Sciences Appliquées – Marrakech Filière : Génie Industriel et Logistique Niveau : 2ème année du Cycle Ingénieur Année universitaire 2015/2016 Réalisé p Réalisé p Réalisé p Réalisé par ar ar ar : : : : Pr. Badr DAKKAK Pr. Badr DAKKAK Pr. Badr DAKKAK Pr. Badr DAKKAK Docteur en Génie Industriel Ecole Nationale des Sciences Appliquées - Marrakech Pr. Badr DAKKAK 2 Table des matières CHAPITRE 1 ............................................................................................................................................................................................3 INTRODUCTION A LA THEORIE DES GRAPHES ..................................................................................................................................3 1. 1. 1. 1. Introduction Introduction Introduction Introduction ..................................................................................................................................................................................3 2. 2. 2. 2. Exemples de situations pouvant être traduites en un graphe Exemples de situations pouvant être traduites en un graphe Exemples de situations pouvant être traduites en un graphe Exemples de situations pouvant être traduites en un graphe ....................................................................................................3 3. 3. 3. 3. Objectifs pédagogiques Objectifs pédagogiques Objectifs pédagogiques Objectifs pédagogiques .................................................................................................................................................................3 4. 4. 4. 4. Définition d’un graphe Définition d’un graphe Définition d’un graphe Définition d’un graphe ..................................................................................................................................................................3 4.1. 4.1. 4.1. 4.1. Remarques et définitions Remarques et définitions Remarques et définitions Remarques et définitions ....................................................................................................................................................4 5. 5. 5. 5. Représentation d’un Représentation d’un Représentation d’un Représentation d’un graphe graphe graphe graphe .........................................................................................................................................................5 5.1. 5.1. 5.1. 5.1. Représentation par dictionnaire Représentation par dictionnaire Représentation par dictionnaire Représentation par dictionnaire ........................................................................................................................................5 5.2. 5.2. 5.2. 5.2. Représentation matricielle Représentation matricielle Représentation matricielle Représentation matricielle .................................................................................................................................................5 5.3. 5.3. 5.3. 5.3. Degré d’un graphe Degré d’un graphe Degré d’un graphe Degré d’un graphe ...............................................................................................................................................................6 6. 6. 6. 6. Vocabulaire de la théorie des Graphes Vocabulaire de la théorie des Graphes Vocabulaire de la théorie des Graphes Vocabulaire de la théorie des Graphes .........................................................................................................................................7 6.1. 6.1. 6.1. 6.1. Chemin Chemin Chemin Chemin .................................................................................................................................................................................7 6.2. 6.2. 6.2. 6.2. Chemin hamiltonien Chemin hamiltonien Chemin hamiltonien Chemin hamiltonien ............................................................................................................................................................7 6.3. 6.3. 6.3. 6.3. Chemin simple Chemin simple Chemin simple Chemin simple .....................................................................................................................................................................7 6.4. 6.4. 6.4. 6.4. Circuit Circuit Circuit Circuit ..................................................................................................................................................................................7 6.5. 6.5. 6.5. 6.5. Chaîne Chaîne Chaîne Chaîne ..................................................................................................................................................................................7 6.7 6.7 6.7 6.7. . . . Graphe complet Graphe complet Graphe complet Graphe complet ...................................................................................................................................................................7 6.8. 6.8. 6.8. 6.8. Connexité Connexité Connexité Connexité .............................................................................................................................................................................8 7. 7. 7. 7. Recherche de niveau dans un graphe sans circuits Recherche de niveau dans un graphe sans circuits Recherche de niveau dans un graphe sans circuits Recherche de niveau dans un graphe sans circuits .....................................................................................................................9 8. 8. 8. 8. Chemin de longueur K Chemin de longueur K Chemin de longueur K Chemin de longueur K ................................................................................................................................................................10 8.1. 8.1. 8.1. 8.1. Matrice booléenne Matrice booléenne Matrice booléenne Matrice booléenne .............................................................................................................................................................10 8.2. 8.2. 8.2. 8.2. Matrice aux arcs Matrice aux arcs Matrice aux arcs Matrice aux arcs ................................................................................................................................................................11 9. 9. 9. 9. Chemins élémentaires Chemins élémentaires Chemins élémentaires Chemins élémentaires – – – – chemins hamiltoniens chemins hamiltoniens chemins hamiltoniens chemins hamiltoniens ........................................................................................................................11 9.1. 9.1. 9.1. 9.1. Définition Définition Définition Définition ...........................................................................................................................................................................11 9.2. 9.2. 9.2. 9.2. Chemin élémentaire de longueur 1 Chemin élémentaire de longueur 1 Chemin élémentaire de longueur 1 Chemin élémentaire de longueur 1 ..................................................................................................................................11 9.3. 9.3. 9.3. 9.3. Chemin élémentaire de longueur 2 Chemin élémentaire de longueur 2 Chemin élémentaire de longueur 2 Chemin élémentaire de longueur 2 ..................................................................................................................................11 9.4. 9.4. 9.4. 9.4. Chemin élémentaire de longueur 3 Chemin élémentaire de longueur 3 Chemin élémentaire de longueur 3 Chemin élémentaire de longueur 3 ..................................................................................................................................12 9.5. 9.5. 9.5. 9.5. Chemin élémentaire de longueur 4 Chemin élémentaire de longueur 4 Chemin élémentaire de longueur 4 Chemin élémentaire de longueur 4 ..................................................................................................................................12 10. 10. 10. 10. Fermeture transitive d’un graphe Fermeture transitive d’un graphe Fermeture transitive d’un graphe Fermeture transitive d’un graphe .........................................................................................................................................12 10.1. 10.1. 10.1. 10.1. Définition Définition Définition Définition ......................................................................................................................................................................12 10.2. 10.2. 10.2. 10.2. Exemple Exemple Exemple Exemple ........................................................................................................................................................................12 Exercice :...............................................................................................................................................................................................14 CHAPITRE 2 ..........................................................................................................................................................................................16 RECHERCHE DE CHEMINS OPTIMAUX DANS UN GRAPHE ..............................................................................................................16 1. 1. 1. 1. Introduction Introduction Introduction Introduction ................................................................................................................................................................................16 2. 2. 2. 2. Algorithme de Ford pour la recherch Algorithme de Ford pour la recherch Algorithme de Ford pour la recherch Algorithme de Ford pour la recherche de plus long chemin e de plus long chemin e de plus long chemin e de plus long chemin .....................................................................................................16 2.1. 2.1. 2.1. 2.1. Problème Problème Problème Problème ...........................................................................................................................................................................16 2.2. 2.2. 2.2. 2.2. Algorithme de Ford Algorithme de Ford Algorithme de Ford Algorithme de Ford ...........................................................................................................................................................16 3. 3. 3. 3. Algorithme de Ford pour la recherche du plus court chemin Algorithme de Ford pour la recherche du plus court chemin Algorithme de Ford pour la recherche du plus court chemin Algorithme de Ford pour la recherche du plus court chemin ...................................................................................................18 4. 4. 4. 4. Algorithme de Dijkstra (Cas des valeurs positives) Algorithme de Dijkstra (Cas des valeurs positives) Algorithme de Dijkstra (Cas des valeurs positives) Algorithme de Dijkstra (Cas des valeurs positives) ..................................................................................................................20 CHAPITRE 3 ..........................................................................................................................................................................................21 PROBLEMES D’ORDONNANCEMENT .................................................................................................................................................21 1. 1. 1. 1. Introduction Introduction Introduction Introduction ................................................................................................................................................................................21 2. 2. 2. 2. Données d’un problème d’ordonnancem Données d’un problème d’ordonnancem Données d’un problème d’ordonnancem Données d’un problème d’ordonnancement ent ent ent : : : :............................................................................................................................21 2.1. 2.1. 2.1. 2.1. Les tâches Les tâches Les tâches Les tâches ..........................................................................................................................................................................21 2.2. 2.2. 2.2. 2.2. Les ressources Les ressources Les ressources Les ressources ...................................................................................................................................................................22 3. 3. 3. 3. Résolution d’un problème d’ordonnancement Résolution d’un problème d’ordonnancement Résolution d’un problème d’ordonnancement Résolution d’un problème d’ordonnancement ..........................................................................................................................22 3.1. 3.1. 3.1. 3.1. Méthode PERT (Program Evaluation and Review Technique) Méthode PERT (Program Evaluation and Review Technique) Méthode PERT (Program Evaluation and Review Technique) Méthode PERT (Program Evaluation and Review Technique) .......................................................................................22 4. 4. 4. 4. Méthode des potentiels Métra (MPM) Méthode des potentiels Métra (MPM) Méthode des potentiels Métra (MPM) Méthode des potentiels Métra (MPM) .......................................................................................................................................28 4.1. 4.1. 4.1. 4.1. Représentation graphique du réseau MPM Représentation graphique du réseau MPM Représentation graphique du réseau MPM Représentation graphique du réseau MPM ......................................................................................................................28 4.2. 4.2. 4.2. 4.2. Construction du réseau MPM Construction du réseau MPM Construction du réseau MPM Construction du réseau MPM ...........................................................................................................................................28 5. 5. 5. 5. Méthode Méthode Méthode Méthode du tableau pour la recherche des chemins critiques et des dates attendues du tableau pour la recherche des chemins critiques et des dates attendues du tableau pour la recherche des chemins critiques et des dates attendues du tableau pour la recherche des chemins critiques et des dates attendues ............................................................29 CHAPITRE 4 ..........................................................................................................................................................................................30 PROBLEMES D’AFFECTATION ............................................................................................................................................................30 1. 1. 1. 1. Introduction Introduction Introduction Introduction ................................................................................................................................................................................30 2. 2. 2. 2. Méthode de résolution du problème d Méthode de résolution du problème d Méthode de résolution du problème d Méthode de résolution du problème d’affectation (Méthode Hongroise) ’affectation (Méthode Hongroise) ’affectation (Méthode Hongroise) ’affectation (Méthode Hongroise) ................................................................................30 CHAPITRE 5 ..........................................................................................................................................................................................34 LES PROGRAMMES DE TRANSPORT ..................................................................................................................................................34 1. 1. 1. 1. Position du problème Position du problème Position du problème Position du problème .................................................................................................................................................................34 Exemple : ..............................................................................................................................................................................................35 2. 2. 2. 2. Recherche d’une solution de base Recherche d’une solution de base Recherche d’une solution de base Recherche d’une solution de base ..............................................................................................................................................35 2.1. 2.1. 2.1. 2.1. Méthode du coin Nord Méthode du coin Nord Méthode du coin Nord Méthode du coin Nord- - - -Ouest Ouest Ouest Ouest ............................................................................................................................................35 2.2. 2.2. 2.2. 2.2. Méthode Méthode Méthode Méthode : Procédure MINILI (MINI : Procédure MINILI (MINI : Procédure MINILI (MINI : Procédure MINILI (MINI- - - -LINE) LINE) LINE) LINE) ......................................................................................................................36 2.3. 2.3. 2.3. 2.3. Mét Mét Mét Méthode MINICO (minimum des colonnes) hode MINICO (minimum des colonnes) hode MINICO (minimum des colonnes) hode MINICO (minimum des colonnes).....................................................................................................................36 2.4. 2.4. 2.4. 2.4. Méthode MINITAB Méthode MINITAB Méthode MINITAB Méthode MINITAB.............................................................................................................................................................36 2.5. 2.5. 2.5. 2.5. Méthode de la différence Méthode de la différence Méthode de la différence Méthode de la différence – – – – maximale ou de BALAS maximale ou de BALAS maximale ou de BALAS maximale ou de BALAS – – – – HAMMER HAMMER HAMMER HAMMER .....................................................................................36 CHAPITRE 1 INTRODUCTION A LA THEORIE DES GRAPHES 1 1 1 1. . . . Introduction Introduction Introduction Introduction La théorie des graphes née en 1736 quand Euler démontra qu’il était impossible de traverser chacun des sept ponts de la ville de Königsberg (figure 1) une fois exactement et y revenir au point de départ. Figure 1: Les sept ponts de la ville de Königsberg La théorie des graphes est un des instruments les plus courants et les plus efficaces pour résoudre des problèmes concrets à l’aide d’un graphe. La théorie des graphes est une tentative de visualisation concrète des faits au moyen de dessin permettant d’exprimer le problème posé. L’ingénieur moderne ne peut plus limiter ses préoccupations à l’organisation de la fabrication, ou la direction de la recherche, il est intégré à la gestion de l’entreprise toute entière et son souci doit être de fabriquer au meilleur prix et d’inventer au moindre coût. Il doit donc appliquer les méthodes de la RO et de la théorie des graphes. 2 2 2 2. . . . Exemples de situations pouvant ê Exemples de situations pouvant ê Exemples de situations pouvant ê Exemples de situations pouvant être traduites en un graphe tre traduites en un graphe tre traduites en un graphe tre traduites uploads/Science et Technologie/ cours-theorie-graphes-version-etudiant.pdf