136
Recherche opérationnelle
On ne peut proposer la représentation suivante :
car cela impliquerait que F précède E, ce qui n'apparaît pas dans les contraintes.
On introduit alors une tâche fictive, de durée nulle, de la façon suivante :
qui exprime bien que G suit D sans que F précède E.
Si alors, on essaie de tracer le graphe complet correspondant au tableau des contraintes
ci-dessus, on peut proposer le dessin suivant : (les valuations des arcs sont portées entre
parenthèses).
Les arcs n'ayant pas d'antécédents ont leurs extrémités initiales confondues et ceux
n'ayant pas de successions ont leurs extrémités finales confondues. Le graphe a ainsi une
entrée et une sortie.
D
E
G
F
D
E
F
G
0