220
Recherche opérationnelle
Appliquons cet algorithme sur l'exemple suivant, représenté par la matrice des coûts ,
les disponibilités et les demandes .
a) Détermination de la fonction de départ
Pour partir d'une fonction potentielle convenable, on peut partir du coût unitaire
minimal, soit
.
On peut poser
,
;
Ensuite on sélectionne l'autre coût égal à soit
; posons
,
;
Puis le coût immédiatement supérieur
. on pose
,
.
Enfin
donne
. On a ainsi une fonction potentielle possible.
On a alors le graphe
suivant dans lequel on détermine facilement le flot maximal.
(Les capacités non infinies sont indiquées entre parenthèses. Les flots sont indiqués hors
des parenthèses).
Les seuls sommets marqués sont
.
On augmente donc
et on diminue d'une même quantité. On doit toujours avoir :
bj
30
30
20
40
ai 40
10
5
8
4
60
3
7
9
8
20
4
11
3
9
Disponibilités
Demandes
Coûts
x 0
z
x 1
x 2
x 3
y 1
y 2
y 3
y 3
30
30
10
20
40
30
20
(40)
(60)
(20)
(+x 0 )
3
5
3
4
30 (30)
30 (30)
20 (20)
10 (40)
(+x 2 )