140
Recherche opérationnelle
Pour calculer ces dates au plus tard, il suffit de partir du sommet terminal, en lui
affectant la durée minimale déjà calculée (ici 33); puis on remontera dans le graphe vers
l'entrée, en affectant à chaque sommet la date au plus tard calculée de la façon suivante :
soient les dates au plus tard des sommets terminaux des arcs issus d'un sommet
considéré, on retranche à chacune de ces dates la valuation de l'arc correspondant. Le
plus petit des nombres obtenus est la date au plus tard du sommet examiné.
Formellement, si
indique les suivants du sommet , si
indique la valuation de
l'arc joignant le sommet au sommet , si désigne la date au plus tard du sommet , on
a :
)
(
=
ij
j
i
t
t
min
t
)
(i
j