Problèmes de flots
221
c'est à dire
On voit que l'on est limité par l'inégalité :
ce qui donne
Le nouveau graphe
relatif à la nouvelle fonction potentielle est le suivant :
On obtient un flot saturant ; on est donc à l'optimum (obtenu donc très rapidement par
cet algorithme) avec les flux transportés suivants :
, tous les autres flux étant nuls.
Remarque : lorsque l'on n'a pas l'égalité
, il est très facile de se ramener au
cas précédent. Il suffit de créer une origine (ou une destination) fictive de disponibilité
(ou demande)
et en ajoutant des coûts quelconques, mais
égaux à une même quantité entre toutes les destinations (ou origines) avec cette origine
(ou destination) fictive.
9.5.5 Algorithme de Stepping-Stone
Parmi les nombreuses méthodes existantes, la méthode de la « différence maximale » ou
méthode de Balas-Hammer permet d’obtenir une solution de base initiale. Elle repose
sur le critère économique du coût marginal et introduit la notion de manque à gagner.
Elle donne une solution de base souvent très proche de l’optimum et est avérée d’une
efficacité bien supérieure aux méthodes du « coin Nord-Ouest » ou de Houthakker.
Exemple :
Recherche d’une solution de base. Dans chaque ligne et dans chaque colonne, on
recherche le coût minimal et on fait la différence entre ce coût et le coût immédiatement
supérieur dans la même ligne ou dans la même colonne.
Par exemple, dans la colonne (1) du tableau ci-dessous, le coût minimal est 3 et le coût
immédiatement supérieur est 7, la différence est 4.
x 0
z
x 1
x 2
x 3
y 1
y 2
y 3
y 3
30
0
40
20
40
30
20
(40)
(60)
(20)
(+x 0 )
1
5
3
30 (30)
30 (30)
20 (20)
40 (40)
(+x 2 )
0
2
0
30