212
Recherche opérationnelle
Algorithme de KLEIN
Les étapes sont les suivantes :
a) Trouver un flot compatible sur . On peut utiliser à ce titre l'algorithme précédent. Si
l'on ne trouve pas de flot compatible, on arrête : le problème est impossible.
b) Soit un flot compatible. On pratique un marquage classique type Ford-Fulkerson.
1) on marque
2) si est marqué et si
, on marque
3) si est marqué et si
, on marque
c) On cherche un cycle élémentaire de sommets marqués, tels que si on appelle
les
arcs tels que
et
les arcs tels que
, on ait
On peut alors améliorer le coût total en augmentant d'une certaine quantité les flots sur
les arcs
et en diminuant de la même quantité les flots sur les arcs
(de telle façon
que le flot soit compatible).
d) On revient en b) jusqu'à ce qu'on ne puisse plus trouver de tels cycles améliorants.
Le principe de cet algorithme est donc simple : il est en effet tout à fait évident que les
procédures b) et c) améliorent le flot total. On démontre, de façon moins simple, qu'une
condition suffisante pour que le flot soit optimal est qu'il n'existe pas de tels cycles, ce
qui finit de justifier l'ensemble de la procédure.
Nous allons voir maintenant un cas particulier du problème du flot à coût minimal, qui
est constitué par le programme de transport.
9.5. LE PROGRAMME DE TRANSPORT
9.5.1. Position du problème
Il s'agit de transporter entre
origines
et
destinations certaines
quantités (de marchandises par exemple ). En chaque origine existe une disponibilité
et en chaque destination une demande . Par ailleurs, entre une origine et une
destination le coût de transport d'une unité est une constante égale à
(qui peut être
infinie s'il n'y a pas de liaison entre et ). On supposera dans la suite que
(la disponibilité totale est égale à la demande totale, contrainte qui ne diminue pas, on le
verra, la généralité du problème).