Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
122
Nous lais sons au lec teur le soin de véri fier le cal cul du che min cri tique (unique,
ici) : (0, 3, 4, 5, 8, 9, 11) de durée 63 jours qui est la durée mini male pour ce pro jet ;
les tâches cri tiques étant C (écla tée ici en C 1 et C 2 ), F et G ; le che min cri tique com -
porte aussi deux tâches fic tives, ce qui n’a pas d’inter pré ta tion concrète.
4.3.2 Méthode des poten tiels (MPM)
Contrai re ment à la pré cé dente, cette méthode ne néces site aucune défi ni tion préa
lable d’évé ne ments ni de tâches fictives. Conceptuellement elle repose sur un graphe
G 5 (X, U) dans lequel les som mets repré sentent les tâches (opérations) du pro jet
(ainsi qu’une tâche « début » : D, et une tâche « fin » : F), et les arcs repré sentent les
contraintes. La notion de tâche fic tive n’existe pas ici et on n’a pas non plus à créer
des événements. Voici, pour notre pre mier exemple, le graphe MPM (fig 4.16).
Par exemple, l’opé ra tion d pré cède e, g et h, et, comme elle est de durée 2, on
a créé les arcs (d, e), (d, g) et (d, h), cha cun valué par 2. Le (ou les) che min(s) de
valeur maximale entre le som met D et le som met F repré sente(nt) le (ou les) che -
min(s) cri tique(s). Ici il y en a deux : (D, a, b, c, d, e, f, k, ,, m, n, o, p, s, w, F) et (D,
a, b, c, d, h, i, j, m, n, o, q, s, w, F) de durée 31,5. Le lec teur tra cera sans dif fi culté le
graphe MPM de notre second exemple et retrou vera le che min cri tique (D, c, f, g, F)
de durée 63 jours.
Figure 4.16
Dans la recherche du (ou des) che min(s) cri tique(s) par la méthode MPM, il suf fit
pour « cal cu ler » un som met (c’est- à-dire déter mi ner la date au plus tôt de l’opé ra -
tion (tâche) asso ciée à ce som met), de connaître quels sont les pré dé ces seurs de ce
som met.
Aussi, pour ce cal cul, peut- on s’affran chir du tracé du graphe MPM, que l’on
repré sente alors sous forme d’un tableau de pré dé ces seurs : à chaque opé ra tion k
cor res pond une colonne du tableau, dans laquelle on ins crit les opé ra tions qui doivent
pré cé der immé dia te ment k ; on indique aussi, en regard de cha cune de ces opé ra tions
préa lables, sa durée. On ajoute à la liste des opé ra tions, l’opé ra tion « début » (notée ici
D) et l’opé ra tion fin (notée F). Quand une opé ra tion , n’est pré cé dée par aucune autre
122
Nous lais sons au lec teur le soin de véri fier le cal cul du che min cri tique (unique,
ici) : (0, 3, 4, 5, 8, 9, 11) de durée 63 jours qui est la durée mini male pour ce pro jet ;
les tâches cri tiques étant C (écla tée ici en C 1 et C 2 ), F et G ; le che min cri tique com -
porte aussi deux tâches fic tives, ce qui n’a pas d’inter pré ta tion concrète.
4.3.2 Méthode des poten tiels (MPM)
Contrai re ment à la pré cé dente, cette méthode ne néces site aucune défi ni tion préa
lable d’évé ne ments ni de tâches fictives. Conceptuellement elle repose sur un graphe
G 5 (X, U) dans lequel les som mets repré sentent les tâches (opérations) du pro jet
(ainsi qu’une tâche « début » : D, et une tâche « fin » : F), et les arcs repré sentent les
contraintes. La notion de tâche fic tive n’existe pas ici et on n’a pas non plus à créer
des événements. Voici, pour notre pre mier exemple, le graphe MPM (fig 4.16).
Par exemple, l’opé ra tion d pré cède e, g et h, et, comme elle est de durée 2, on
a créé les arcs (d, e), (d, g) et (d, h), cha cun valué par 2. Le (ou les) che min(s) de
valeur maximale entre le som met D et le som met F repré sente(nt) le (ou les) che -
min(s) cri tique(s). Ici il y en a deux : (D, a, b, c, d, e, f, k, ,, m, n, o, p, s, w, F) et (D,
a, b, c, d, h, i, j, m, n, o, q, s, w, F) de durée 31,5. Le lec teur tra cera sans dif fi culté le
graphe MPM de notre second exemple et retrou vera le che min cri tique (D, c, f, g, F)
de durée 63 jours.
Figure 4.16
Dans la recherche du (ou des) che min(s) cri tique(s) par la méthode MPM, il suf fit
pour « cal cu ler » un som met (c’est- à-dire déter mi ner la date au plus tôt de l’opé ra -
tion (tâche) asso ciée à ce som met), de connaître quels sont les pré dé ces seurs de ce
som met.
Aussi, pour ce cal cul, peut- on s’affran chir du tracé du graphe MPM, que l’on
repré sente alors sous forme d’un tableau de pré dé ces seurs : à chaque opé ra tion k
cor res pond une colonne du tableau, dans laquelle on ins crit les opé ra tions qui doivent
pré cé der immé dia te ment k ; on indique aussi, en regard de cha cune de ces opé ra tions
préa lables, sa durée. On ajoute à la liste des opé ra tions, l’opé ra tion « début » (notée ici
D) et l’opé ra tion fin (notée F). Quand une opé ra tion , n’est pré cé dée par aucune autre