Mathématiques 514

Chemin Critique

Le chemin critique est beaucoup utilisé en recherche opérationnelle.  Cela consiste à analyser le temps nécessaire pour chaque tâche et de déterminer le temps minimal que cela prendra à effectuer le projet. Par exemple, dans le domaine de la construction, c'est important de respecter les délais et pour y arriver, il faut prévoir le nombre de jours que chaque tâche prendra.  il faut alors construire un graphe qui est logique.  Par exemple, on ne fera pas l'électricité avant d'avoir érigé les murs!

Alors, pour obtenir le chemin critique, il faudra prendra la valeur maximale à chaque sommet.  Ceci nous donnera le temps le plus court pour compléter toutes les tâches et ainsi réaliser le projet.  Ceci peut sembler paradoxale mais voici un exemple qui vous aidera à comprendre ce concept.

Avant de faire le plâtre dans ce projet, il faut s'assurer que l'électricité, la plomberie et le système de chauffage aient été complétés. Au sommet C, la valeur à considérer sera 6 car c'est le temps minimal qu'il faudra pour être sûr que les trois tâches aient été exécutés. Au mieux, le plombier aura fini une journée plus tôt que l'électricien mais il faudra attendre que ce dernier ait fini l'électricité et l'installation du chauffage avant de commencer le plâtre.

Maintenant, voyons comment résoudre un problème avec le chemin critique.

À partir du sommet A, calculons les valeurs jusqu'au sommet G.  Si on prend le chemin A-B-F-G, cela donne 30.  Maintenant, en passant par A-D-C-G, cela donne 33.  Alors, au sommet G, la valeur retenue sera la plus grande qui est 33. Si on continue jusqu'au sommet H, cela donne 38.  Maintenant, analysons le chemin A-D-E-H.  Cela donne 35.  donc, au sommet H, la plus grande valeur est 38. Si on ajoute la valeur de 9 entre H et I, cela donne 47. 

Le chemin critique est A-D-C-G-H-I pour une valeur de 47.  Ceci est la valeur minimale pour réaliser ce projet.  Si on veut réduire la valeur de ce projet, on aura tout simplement à diminuer la longueur du chemin critique.

Dernière mise à jour effectuée le 23 décembre 2005