214
Recherche opérationnelle
9.5.3. Utilisation des flots
Dessinons pour le problème ci-dessus le réseau de transport :
- d'un somme t entrée partent des arcs de capacités et de coût nul vers autant
de sommets
qu'il y a d'origines dans le programme de transport.
- des arcs relient chaque sommet origine aux sommets destination
.
Ces arcs sont de capacité infinie et de coût .
- de chaque sommet-destination
part un arc vers un sommet de sortie de
capacité et de coût 0.
On a enfin ajouté l'arc-retour de capacité infinie et de coût nul.
On voit alors que résoudre le problème de transport revient à trouver un flot saturant les
arcs issus de
et les arcs arrivant en (un tel flot sera appelé saturant) et de coût
minimal.
Nous appellerons
le flot entre et , et
le coût associé au flot .
On pourrait appliquer à ce problème particulier l'algorithme de KLEIN, avec les
contraintes :
On aboutirait à l'algorithme le plus ancien permettant de résoudre le programme de
transport (algorithme dit du Stepping-Stone) mais on préférera ici une autre procédure,
fondée sur la notion de potentiels.
x 0
x 1
x i
x m
(a i , 0)
y j
y 1
y n
z
( , c ij )
(b j , 0)
( , 0)
capacité