Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
128
Pour les dates au plus tard, il vient : t
*
t 5 30,75 et t
*
p 5 29,75. (rap pel : t p 5 25).
D’où la marge totale : M p 5 29,75 2 25 5 4,75. On a, bien sûr, retrouvé les
mêmes valeurs que celles obte nues dans la méthode PERT.
4.4 pro blème du flot de vAleur mAximAle
4.4.1 Flot dans un réseau de tran sport
On appelle réseau de tran sport un graphe fini, de p sommets, sans boucle com por tant
une entrée x 1 et une sor tie x p telles que : depuis x 1 il existe un che min vers tout autre
som met x k et de tout som met x k il existe un che min vers x p (on dit alors que x 1 est une
« source » et x p , un « puits »). Tout arc u est valué par un entier posi tif c(u), nommé
« capa cité » de l’arc u, qui repré sente une capa cité de tran sport asso ciée à la liai son
figu
rée par cet arc : ces capa ci tés de tran sport peuvent représenter des ton nages dis po
nibles sur des bateaux, des camions, des wagons, ou encore des débits dans des cana -
li sa tions, oléo ducs, voies de trans mis sion, etc.
Le pro blème à résoudre, étant donné un réseau de tran sport, consiste à ache mi ner
une quan tité maximale de x 1 à x p , en tenant compte des capa ci tés de tran sport. La
quan tité w(u) tran spor tée sur chaque arc u est nom mée « flux sur l’arc u » ; elle véri fie
donc : 0 < w1 u 2 < c 1 u2 .
En tout som met x, dif fé rent de la source x 1 et du puits x p , on a une loi de conser va -
tion (ana logue à la loi des nœuds en élec tri cité, ou « loi de Kirchhoff ») : la somme des
flux arri vant sur le som met x est égale à la somme des flux par
tant du som
met x :
a
yPG
2 (x)
w(y, x) 5 a
yPG
1 (x)
w(x, y), où x 2 x 1 , x p .
Un flot f est déter miné par la don née du flux pour tous les arcs du réseau de tran -
sport ; la « valeur d’un flot », notée V(f), est par défi ni tion la somme des flux par
tant
de la source x 1 (on montre aisé ment que V(f) est aussi égale à la somme des flux des
arcs arri vant sur le puits x p ).
Voici un exemple.
Soient trois châ teaux d’eau, A, B et C, gérés par un syn di cat inter com mu nal, ali -
men tant quatre villages D, E, F et G. Le châ teau d’eau A béné fi cie d’une ali men ta tion
et d’une réserve capables de débi ter 45 l/s ; le châ teau d’eau B peut seule ment débi -
ter 25 1/s et le châ teau d’eau C, 20 1/s. Plu sieurs cana li sa tions existent et leur débit
maximal, en 1/s, est men tionné, pour cha cune, sur la figure (figure 4.20). Le village D
aurait besoin d’un débit de 30 1/s, le village E, 10 1/s, le village F, 20 1/s et, enfin, le
village G, 30 1/s. On demande d’éta blir la meilleure ali men ta tion pos sible et de déter -
mi ner, s’il y a lieu, entre quels points il convien drait de construire des cana li sa tions
sup plé men taires.
Consta tons tout d’abord que, si nous ajou tons au graphe repré sen tant les cana li -
sa tions avec leur débit, une source Ο et un puits P, toutes deux fic tives, on obtient un
réseau de tran sport. On value les arcs (O, A), (O, B) et (O, C) en leur attri buant comme
capa cité les dis po ni bi li tés res pec tives en A, B et C. De même, on value les arcs (D, P),
(E, P), (F, P) et (G, P) par les besoins res pec tifs en D, E, F et G.
128
Pour les dates au plus tard, il vient : t
*
t 5 30,75 et t
*
p 5 29,75. (rap pel : t p 5 25).
D’où la marge totale : M p 5 29,75 2 25 5 4,75. On a, bien sûr, retrouvé les
mêmes valeurs que celles obte nues dans la méthode PERT.
4.4 pro blème du flot de vAleur mAximAle
4.4.1 Flot dans un réseau de tran sport
On appelle réseau de tran sport un graphe fini, de p sommets, sans boucle com por tant
une entrée x 1 et une sor tie x p telles que : depuis x 1 il existe un che min vers tout autre
som met x k et de tout som met x k il existe un che min vers x p (on dit alors que x 1 est une
« source » et x p , un « puits »). Tout arc u est valué par un entier posi tif c(u), nommé
« capa cité » de l’arc u, qui repré sente une capa cité de tran sport asso ciée à la liai son
figu
rée par cet arc : ces capa ci tés de tran sport peuvent représenter des ton nages dis po
nibles sur des bateaux, des camions, des wagons, ou encore des débits dans des cana -
li sa tions, oléo ducs, voies de trans mis sion, etc.
Le pro blème à résoudre, étant donné un réseau de tran sport, consiste à ache mi ner
une quan tité maximale de x 1 à x p , en tenant compte des capa ci tés de tran sport. La
quan tité w(u) tran spor tée sur chaque arc u est nom mée « flux sur l’arc u » ; elle véri fie
donc : 0 < w1 u 2 < c 1 u2 .
En tout som met x, dif fé rent de la source x 1 et du puits x p , on a une loi de conser va -
tion (ana logue à la loi des nœuds en élec tri cité, ou « loi de Kirchhoff ») : la somme des
flux arri vant sur le som met x est égale à la somme des flux par
tant du som
met x :
a
yPG
2 (x)
w(y, x) 5 a
yPG
1 (x)
w(x, y), où x 2 x 1 , x p .
Un flot f est déter miné par la don née du flux pour tous les arcs du réseau de tran -
sport ; la « valeur d’un flot », notée V(f), est par défi ni tion la somme des flux par
tant
de la source x 1 (on montre aisé ment que V(f) est aussi égale à la somme des flux des
arcs arri vant sur le puits x p ).
Voici un exemple.
Soient trois châ teaux d’eau, A, B et C, gérés par un syn di cat inter com mu nal, ali -
men tant quatre villages D, E, F et G. Le châ teau d’eau A béné fi cie d’une ali men ta tion
et d’une réserve capables de débi ter 45 l/s ; le châ teau d’eau B peut seule ment débi -
ter 25 1/s et le châ teau d’eau C, 20 1/s. Plu sieurs cana li sa tions existent et leur débit
maximal, en 1/s, est men tionné, pour cha cune, sur la figure (figure 4.20). Le village D
aurait besoin d’un débit de 30 1/s, le village E, 10 1/s, le village F, 20 1/s et, enfin, le
village G, 30 1/s. On demande d’éta blir la meilleure ali men ta tion pos sible et de déter -
mi ner, s’il y a lieu, entre quels points il convien drait de construire des cana li sa tions
sup plé men taires.
Consta tons tout d’abord que, si nous ajou tons au graphe repré sen tant les cana li -
sa tions avec leur débit, une source Ο et un puits P, toutes deux fic tives, on obtient un
réseau de tran sport. On value les arcs (O, A), (O, B) et (O, C) en leur attri buant comme
capa cité les dis po ni bi li tés res pec tives en A, B et C. De même, on value les arcs (D, P),
(E, P), (F, P) et (G, P) par les besoins res pec tifs en D, E, F et G.