138
Recherche opérationnelle
On voit que le tracé de cet arc ne nécessite pas l'introduction d'arcs fictifs.
6.4.2.3. Détermination de la durée minimale des travaux.
Pour déterminer la durée minimale des travaux, prenons d'abord le graphe de PERT.
Cette durée est donnée par la valeur totale du chemin de valeur maximale entre l'entrée
et la sortie du graphe.
En effet, étant donné que toutes les tâches doivent être exécutées, tous les chemins du
graphe doivent être parcourus, et la durée minimale de chacun des chemins est obtenue
si l'on considère que les tâches sont exécutées sans temps-mort entre deux d'entre elles.
La valeur du plus long de ces chemins est alors la durée minimale que l'on peut attendre
pour l'ensemble du projet.
Pour trouver le chemin de valeur maximale, on peut utiliser l'algorithme de Ford, tel
qu'il a été modifié pour ce type de problème. On obtient ainsi le chemin suivant (en traits
doubles), ainsi que le délai minimum total des travaux (33).
y
C
D
E
O
A
B
F
G
H
Z
J
K
L
M
N
I
0
6
5
6
2
6
4
7
4
4
6
8
2
3
5
4
6
7
7
8
5
7
8