198
Recherche opérationnelle
9.2. PROBLEME DU FLOT MAXIMAL
Considérons un réseau de transport de sommet
et les arcs
de capacités
entières et positives. Nous adjoindrons à ce réseau un
arc fictif , de capacité infinie.
Le problème consiste à établir un flot sur le graphe de telle sorte que le flux total arrivant
en soit le plus grand possible avec pour tout :
)
(
)
(
0
u
c
u
si est le flux sur l'arc . Un flot obéissant à ces contraintes est appelé flot compatible.
On voit que l'addition de l'arc
permet d'avoir la loi des nœuds vérifiée en tous les
sommets.
Exemple de problème de flot maximal
On a un certain nombre d’entrepôts
, avec des quantités d'une certaine
marchandise
. Il s'agit de transporter cette marchandise en des points
où existent des demandes
. De l'entrepôt au demandeur , la
quantité maximale que l'on peut transporter est désignée par . On veut satisfaire
globalement la demande au maximum, c'est-à-dire que l'on cherche la quantité maximale
de marchandises à transporter, compte tenu des disponibilités, des demandes et des
limitations
. On voit que le problème consiste à chercher le flot qui maximise le flot
arrivant en dans le réseau de transport ci-dessous, où à chaque entrepôt correspond un
sommet
et à chaque destination un sommet
le sommet
est relié au sommet
par arc de capacité
: est relié à par un arc de capacité et est relié à par
un arc de capacité
x0
x1
x2
xi
xm
y1
y2
yi
ym
z
b1
b2
bj
bn
a1
a2
ai
am
c11
c12
c21
c22
cij
cmn