Théorie des graphes : Tp1graphescalculpluscourtchemin
Télécharger PDFRecherche Opérationnelle : Travaux Pratiques sur les Graphes et Ordonnancement (PERT)
Partie 1 (Graphe)
Réaliser un programme en C/C++ permettant de : 1) Représenter un graphe orienté en mémoire. 2) Lire le graphe suivant depuis un fichier texte : - Les sommets sont numérotés de 1 à 9. - Les arêtes sont définies avec leurs poids respectifs. 3) Calculer le plus court chemin du nœud 1 au nœud 9 en utilisant l'algorithme de Dijkstra.
Le programme doit afficher les calculs intermédiaires pour visualiser le processus.
Partie 2 (Plus court chemin)
Calculer le plus court chemin entre le nœud 1 et le nœud 210 dans un graphe représentant un réseau routier où les distances ne sont pas euclidiennes (d(i,j) ≠ d(j,i)).
Question 1 : Implémentation des algorithmes de Dijkstra et Bellman
Créer un code C++ optimisé pour calculer le plus court chemin entre le nœud 1 et le nœud 210 en utilisant : 1) L'algorithme de Dijkstra. 2) L'algorithme de Bellman-Ford avec deux ordres de sommets : - Ordre lexicographique : 1, 2, ..., 209, 210. - Ordre inverse : 1, 209, ..., 2, 210.
Question 2 : Étude comparative des performances
Pour les 13 sommets suivants : 8, 26, 41, 58, 60, 95, 114, 148, 155, 168, 199, 207.
Calculer le plus court chemin entre chacun de ces sommets et le nœud 1 en utilisant : - L'algorithme de Dijkstra. - L'algorithme de Bellman-Ford avec deux ordres de sommets : - Ordre lexicographique (exemple : 8-26, 41-58, etc.). - Ordre inverse (exemple : 207-199, 168-148, etc.).
Relever pour chaque couple (somme, nœud 1) : - La valeur du chemin le plus court. - Le temps de calcul total.
Analyse des résultats
Conclure sur la performance relative des deux algorithmes pour ce graphe à valeurs positives. Vérifier si l'ordre de passage des sommets dans Bellman-Ford influence les performances.
Partie 3 (Ordonnancement de type PERT)
Les opérations nécessaires à la mise en exploitation d'un nouveau gisement minier sont définies par les tâches suivantes avec leurs durées (en jours) :
- Tâche (a) : Obtention d'un permis d'exploitation — 120 jours.
- Tâche (b) : Établissement d'une piste de 6 km — 180 jours.
- Tâche (c) : Installation de deux sondeuses — 30 jours.
- Tâche (d) : Création des bâtiments provisoires — 30 jours.
- Tâche (e) : Goudronnage de la piste — 60 jours.
- Tâche (f) : Conduction d'eau — 90 jours.
- Tâche (g) : Campagne de sondage — 240 jours.
- Tâche (h) : Équipement des puits — 180 jours.
- Tâche (i) : Transport et installation du matériel d'exploitation — 30 jours.
- Tâche (j) : Construction des bureaux — 240 jours.
- Tâche (k) : Aménagement du fond — 360 jours.
- Tâche (l) : Construction d'une laverie — 240 jours.
Contraintes de dépendance
- La tâche (b) succède à la tâche (a).
- Les tâches (c), (d) et (e) débutent au moins 400 jours après le début des travaux et nécessitent la fin de la tâche (b).
- La tâche (f) ne peut débuter que 450 jours après le début des travaux et 50 jours après le début de la tâche (b).
- Les tâches (j) et (h) ne peuvent débuter que lorsque les tâches (d), (e), (f) et (g) sont achevées.
- Les tâches (i), (k) et (l) ne peuvent débuter que lorsque les tâches (h) et (j) sont achevées.
Travail à réaliser
- Représenter le problème sous forme d'un graphe orienté.
-
a. Format du fichier d'entrée
Définir un fichier texte décrivant le problème selon un format structuré, par exemple :
- Liste des tâches avec leur description et durée (exemple :
1 120 obtention d'un permis d'exploitation). - Liste des dépendances (exemple :
1 0 2signifie que la tâche 2 dépend de la tâche 1 avec un délai de 0 jour).
- Liste des tâches avec leur description et durée (exemple :
-
b. Structure de données pour le graphe
Concevoir une structure efficace pour stocker le graphe, par exemple : - Un tableau de tâches où chaque tâche contient son identifiant, sa durée, sa description et ses dépendances. - Une matrice ou une liste d'adjacence pour représenter les relations entre tâches.
-
c. Calcul des dates et marges
Implémenter un programme optimisé pour calculer : - Les dates de début au plus tôt (DDE). - Les dates de fin au plus tard (DFM). - Les marges (totales et libres). - Le chemin critique.
-
d. Impact d'une modification de durée
Analyser l'effet si la durée de la tâche (e) passe de 60 à 120 jours. Mettre à jour les calculs et vérifier les modifications sur les dates et marges.
-
e. Retard maximal sur une tâche
Déterminer le retard maximal acceptable sur la tâche (j) sans affecter la date de fin des autres opérations dans le graphe.
Représentation graphique
Le programme doit générer un diagramme Gantt pour visualiser les opérations et leurs durées.
FAQ
1. Quels sont les algorithmes à implémenter pour la partie 2 ?
Il faut implémenter l'algorithme de Dijkstra et l'algorithme de Bellman-Ford avec deux ordres de sommets différents.
2. Comment représenter les dépendances dans un graphe PERT ?
Les dépendances sont représentées par des arêtes orientées entre les tâches. Par exemple, si la tâche (b) dépend de la tâche (a), une arête va de (a) à (b) avec un poids correspondant au délai éventuel.
3. Quel est l'objectif du chemin critique dans un graphe PERT ?
Le chemin critique identifie la séquence de tâches qui détermine la durée minimale totale du projet. Toute perturbation sur ces tâches impacte directement la date de fin globale.