4.5 Flot de valeur maximale à coût mini mal
135
© Dunod – Toute reproduction non autorisée est un délit.
fré quem ment de nom breux flots dif fé rents de même valeur V
*
; parmi ceux- ci, il est
inté res sant d’en trou ver un de moindre coût. Ce pro blème se for ma lise de la manière
sui vante : R est un réseau de tran sport où s et p dési gnent res pec ti ve ment la source et
le puits. À chaque arc (i, j) sont asso ciées deux valeurs posi tives : 3c ij , p ij 4 où c ij est la
capa cité et p ij est le coût uni taire asso ciés à l’arc. Le coût d’un flot F s’obtient de la
façon sui vante : w ij # p ij est le coût du flux w ij circulant le long de l’arc (i, j) ; le coût de
est alors la somme de ces coûts sur tous les arcs du réseau : a
1i, j2
w ij # p ij .
La par tie gauche de la figure 4.25 montre un réseau de tran sport dans lequel un
flot de valeur 5 et de coût 20 est déter
miné.
Avant de don ner un algo rithme de réso lu tion pour ce pro blème, nous allons reve nir
au pro blème du flot maximal
1
. Pour tout réseau de tran sport R nous défi nis sons G
e
F , le
graphe d’écart asso cié au flot (nous sup po se rons R anti sy mé trique : il ne com porte
pas de couple d’arcs (i, j) et (j, i) ; (si tel n’était pas le cas, nous pour rions y remé dier en
scin dant l’arc (i, j) en deux arcs (i, k) et (k, j), tous deux de capa cité c ij et de coût
1
2 p ij 2 .
Le graphe d’écart G
e
F et le réseau de tran sport R ont les mêmes som mets. Pour
tout arc (i, j) de R, les arcs du graphe d’écart et leur valuation sont obte nus de la
façon sui vante :
1. si 0 , w ij , c ij , alors G
e
F com porte un arc (i, j) de valuation r ij 5 c ij 2 w ij et un
arc (j, i) de valuation r ji 5 w ij
2. si w ij 5 0, G
e
F com porte un arc (i, j) de valuation r ij 5 c ij , mais pas d’arc (j, i)
3. si w ij 5 c ij , G
e
F com porte un arc (j, i) de valuation r ji 5 w ij , mais pas d’arc (i, j).
Nous pou vons remar quer que pour le flot nul : F 5 (0, c , 0), le graphe d’écart
et le réseau de tran sport coïn cident.
Figure 4.25 À gauche, un flot F avec 4 arcs saturés ; à droite G
e
F le graphe d’écart asso cié
D’autre part il est aisé de consta ter qu’à une chaîne amé lio rante pour R cor res -
pond un che min de la source au puits dans G
e
F et réci pro que ment. Ainsi un flot est
maximal si et seule ment si il n’existe pas de che min de s à p dans G
e
F .
1. Par abré via tion, nous appe lons ici flot maximal, tout flot de valeur maximale.
135
© Dunod – Toute reproduction non autorisée est un délit.
fré quem ment de nom breux flots dif fé rents de même valeur V
*
; parmi ceux- ci, il est
inté res sant d’en trou ver un de moindre coût. Ce pro blème se for ma lise de la manière
sui vante : R est un réseau de tran sport où s et p dési gnent res pec ti ve ment la source et
le puits. À chaque arc (i, j) sont asso ciées deux valeurs posi tives : 3c ij , p ij 4 où c ij est la
capa cité et p ij est le coût uni taire asso ciés à l’arc. Le coût d’un flot F s’obtient de la
façon sui vante : w ij # p ij est le coût du flux w ij circulant le long de l’arc (i, j) ; le coût de
est alors la somme de ces coûts sur tous les arcs du réseau : a
1i, j2
w ij # p ij .
La par tie gauche de la figure 4.25 montre un réseau de tran sport dans lequel un
flot de valeur 5 et de coût 20 est déter
miné.
Avant de don ner un algo rithme de réso lu tion pour ce pro blème, nous allons reve nir
au pro blème du flot maximal
1
. Pour tout réseau de tran sport R nous défi nis sons G
e
F , le
graphe d’écart asso cié au flot (nous sup po se rons R anti sy mé trique : il ne com porte
pas de couple d’arcs (i, j) et (j, i) ; (si tel n’était pas le cas, nous pour rions y remé dier en
scin dant l’arc (i, j) en deux arcs (i, k) et (k, j), tous deux de capa cité c ij et de coût
1
2 p ij 2 .
Le graphe d’écart G
e
F et le réseau de tran sport R ont les mêmes som mets. Pour
tout arc (i, j) de R, les arcs du graphe d’écart et leur valuation sont obte nus de la
façon sui vante :
1. si 0 , w ij , c ij , alors G
e
F com porte un arc (i, j) de valuation r ij 5 c ij 2 w ij et un
arc (j, i) de valuation r ji 5 w ij
2. si w ij 5 0, G
e
F com porte un arc (i, j) de valuation r ij 5 c ij , mais pas d’arc (j, i)
3. si w ij 5 c ij , G
e
F com porte un arc (j, i) de valuation r ji 5 w ij , mais pas d’arc (i, j).
Nous pou vons remar quer que pour le flot nul : F 5 (0, c , 0), le graphe d’écart
et le réseau de tran sport coïn cident.
Figure 4.25 À gauche, un flot F avec 4 arcs saturés ; à droite G
e
F le graphe d’écart asso cié
D’autre part il est aisé de consta ter qu’à une chaîne amé lio rante pour R cor res -
pond un che min de la source au puits dans G
e
F et réci pro que ment. Ainsi un flot est
maximal si et seule ment si il n’existe pas de che min de s à p dans G
e
F .
1. Par abré via tion, nous appe lons ici flot maximal, tout flot de valeur maximale.