Mathématiques 2: Géométrie
Les graphes
L'optimisation par les graphes
Chemin critique

1. Introduction

Pour réaliser une tâche ou un projet, tel que préparer un examen, monter les pièces d'un véhicule, faire une recette, bâtir une maison, etc, on doit souvent réaliser plusieurs étapes.

Certaines étapes sont préalables à d’autres étapes et doivent donc obligatoirement être faites avant certaines autres . Plusieurs étapes peuvent se faire en même temps pour accomplir la réalisation d'un projet par des personnes ou des équipes différentes.

Le chemin critique, c'est le temps minimum requis pour exécuter la tâche ou le projet. Sous certaines contraintes, on doit attendre que certaines étapes soient terminées avant de passer aux étapes suivantes.

Le chemin critique, c'est donc la chaîne ayant la plus grande valeur entre le début et la fin du projet.

2. Algorithme du chemin critique

Pour trouver le chemin critique, la procédure est la suivante :

• On assigne à chaque sommet une lettre et à chaque arête ou arc un nombre ou une valeur,

• Le premier nombre retenu est la plus grande somme des valeurs pour se rendre du point de départ au premier sommet d'intersection,

• Le deuxième nombre retenu est la plus grande somme des valeurs pour se rendre du point de départ au deuxième sommet d'intersection,

• On continue le même processus jusqu'à la fin,

• La chaîne la plus longue est le chemin critique.

Exemple 1

Le chemin critique est le trajet le plus long de telle sorte qu'en est sûr que toutes les tâches ont été complétés.

Voici la répartition des délais qu'il faut pour les séries éliminatoires de hockey.

Avant 3 semaines, M dispute un match avec B et avant 4 semaines avec T. La gagnant jouera avec C dans une semaine.

Quel est le temps minimal que prendra cette série de matchs ?

Avant que C dispute un math, il faut s'assurer qu'un match entre M et B, entre B et T, et entre M et T a été complété. Ces trois matchs sont préalables à la rencontre de l'équipe C..

Au sommet T, pour être certain que les trois matchs ont eu lieu, le temps minimum qu'il faut est 3 + 2 = 5 semaines. C'est donc la valeur à considérer en T.

Le match entre M et T aura lieu une semaine plus tôt, mais il faudra attendre que les matchs M&B et B&T soient complétés avant de disputer un match avec C.

Le chemin crique pour avoir le résultat des séries éliminatoires est MBTC, de valeur 3 + 2 + 1 = 6 semaines.

Exemple 2

Voici une autre situation qui représente une organisation de la LNH pour les séries éliminatoires, détérminée par le graphe suivant:


Les valeurs des arcs représentent le temps, en semaines, entre deux matchs consécutifs.

Par exemple: Dans deux semaines il y aura un match T&W, après il faut attendre 3 semaines pour le match entre le gagnant et l'équipe TB, ...

À partir du sommet T, on calcule les valeurs des arêtes jusqu'au sommet B. Ce chemin T W TB B a pour valeur 2 + 3 + 5 = 10 semaines.

Maintenant, le deuxième chemin du sommet T au sommet B est T P O S B. Ce chemin a pour valeur 4 + 3 + 1 + 4 = 12 semaines.

Ainsi au sommet B, on retient le délai le plus long, c'est à dire 12 semaines du chemin T P O S B.

Au sommet M la valeur du chemin T P O S B M est de 12 + 3 = 15 semaines.

Maintenant, le chemin T P D M a pour valeur 4 + 6 + 3 = 13 semaines.

Ainsi au sommet M, on retient la plus grande valeur qui est celle du chemin T P O S B M, et qui vaut 15 semaines.

Au point C, on aura la valeur 15 + 2 = 17 semaines.

Le chemin critique est T P O S B M C. Il a pour valeur 17 semaines.

Pour être sûr que toutes les équipes ont joué, il faut un temps minimal de 17 semaines.

Exemple 3

On dit « Ne pas mettre la charrue devant les boeufs » d'une situation à l'envers ou dans le désordre.


On ne pourra jamais retirer une roue de l'essieu d'une voiture avant de desserrer les écrous, positionner le cric, dévisser les écrous et retirer la roue. Et dans cet ordre.

Voici les dix étapes à réaliser pour remplacer une roue de pneu crevé. Toutes les tâches sont préalables aux autres qui les suivent. Ici, une personne seule ne peut pas exécuter deux ou plus de tâches différentes en même temps, à part si on ajoute une vidéo de la situation pour Youtube.

On doit attendre que chaque étape soit terminée avant de passer à l'étape suivante.

1. Stationner le véhicule dans un endroit sécuritaire,
2. Immobiliser complètement le véhicule avec le frein de stationnement,
3. Enlevez l'enjoliveur s'il y en a, desserrer les écrous avec la manivelle du cric ou une clé en croix,
4. Positionner et actionner le cric ou le cric d’urgence,
5. Dévisser les écrous et retirer la roue à remplacer,
6. Placer une nouvelle roue ou la roue de secours,
7. Serrer les écrous,
8. Redescendre le cric,
9. Placer l'enjoliveur s'il y a lieu, et procéder au serrage final,
10. Ranger les outils et le pneu endommagé.

Ici la chaîne est linéaire. Le chemin critique est la somme des temps qu'il faut pour accomplir chaque étape. Par exemple, en secondes: 60 + 15 + 180 + 120 + 60 + 30 + 120 + 15 + 180 + 160 = 940 secondes, soit environ un quart d'heure.