Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
182
**4.10 Modi fi ca tions sur ve nant dans le dérou le ment d’un pro jet
On donne le graphe ci- dessous et l’on demande de rechercher le che min cri tique.
NB. Sur ce dia gramme les som mets sont des évé ne ments, les arcs des opé ra tions.
On intro    duit alors les modi    fi    ca    tions sui    vantes :
1. l’opé ra tion b ne peut débu ter que
lorsque les 2/3 de l’opé ra tion c ont été
ache vés ;
2. l’opé ra tion c ne peut débu ter qu’une
période après le début géné ral des opé ­
ra tions ;
3. l’opé ra tion k ne peut com men cer
que lorsque le pre mier tiers de l’opé ra tion j a été exé cuté ;
4. l’opé ra tion h ne peut débu ter qu’après l’exé cu tion aux 2/3 de l’opé ra ­
tion e ;
5. le début de l’opé ra tion m ne peut avoir lieu que deux périodes après
l’achè ve ment de l’opé ra tion f.
Cal cu ler le nou veau che min cri tique en uti li sant la méthode des poten tiels.
Étu    dier aussi la modi    fi    ca    tion du graphe PERT.
Com pa rer les deux méthodes.
iV FloTs, aFFEc Ta Tions ET Tran sPorT
*4.11 Pro blème de flot
Trois dépôts A, B, C dis posent res pec ti ve ment de 30, 20 et 45 tonnes de mar chan -
dises ; cinq des ti nations D, E, F, G et H en demandent des quan ti tés res pec tives de
10, 25, 20, 25 et 15 tonnes. Des camions, fai sant route entre les points dési gnés,
offrent les dis po ni bi li tés (tonnages) ci- contre.
Eta blir le meilleur plan de tran sport.