71 CHAPITRE 5.
FLOTS ET COUPES
T + T0
T 0 := T . Sinon, c’est que T était trop petit, et on pose T :=
2
et on laisse T 0 := T 0 .
La solution optimale x∗ est telle T ≤ T (x∗ ) ≤ T 0 . On peut s’arrêter dès que T 0 − T est
plus petit qu’une quantité fixée au préalable.
On a résolu un problème d’optimisation par une recherche binaire, chaque étape étant
un problème de décision.
Cette façon de procéder est très efficace en pratique, plus que l’autre solution consistant
à voir le problème de l’affectation de tâches comme un programme linéaire.
On peut se demander si, dans le cas où les ti sont entiers, on a nécessairement alors une
solution optimale entière. L’auteur de ce polycopié ne sait pas. L’intérêt pourrait être de
montrer que la recherche binaire termine en un nombre fini d’étapes.
5.2 Flot de coût minimum
5.2.1 Généralités
Soit un graphe orienté D = (V, A), muni de capacités
P `, u : A → R+ tels que `(a) ≤ u(a)
pour tout a ∈ A, et des nombres b : V → R tels que v∈V b(v) = 0. Une fonction f : A → R+
est un b-flot si pour tout arc a ∈ A, on a `(a) ≤ f (a) ≤ u(a) et si pour tout sommet v ∈ V ,
la loi de conservation X X
f (a) − f (a) = b(v)
a∈δ + (v) a∈δ − (v)
est respectée.
Les sommets v tels que b(v) > 0 sont appelés sources et les sommets v tels que b(v) < 0
sont appelés puits. Pour une source, b(v) est l’offre ; pour un puits, b(v) est la demande.
Dans le cas particulier où tous les b(v) sont nuls, on parle de circulation.
Proposition 5.3. Soit f un b-flot. Notons P l’ensemble des chemins élémentaires reliant
les sources aux puits et C l’ensemble des circuits élémentaires. Il existe alors des coefficients
réels positifs (λP )P ∈P et (µC )C∈C tels que
X X
f= λP χP + µC χC .
P ∈P C∈C
De plus, si f est entier, alors ces coefficients peuvent être choisis entiers.
Il peut alors être facilement vérifié que pour tout v ∈ V
X X
b(v) = λP − λP .
P ∈P : P quitte v P ∈P : P arrive en v
CHAPITRE 5. FLOTS ET COUPES 72
5.2.2 Le problème
On suppose que l’on a une fonction de coût c : A → R.
On peut alors se demander, parmi tous les b-flots, lequel est de plus petit coût, où le coût
d’un b-flot f est défini par X
c(a)f (a).
a∈A
Les applications des flots de coût minimum sont innombrables. Nous verrons ce que
cela peut apporter au problème d’affectation de tâches vu précédemment. Tout comme le
problème de flot maximum, le problème du b-flot de coût minimum se formule comme un
programme linéaire et peut donc être résolu avec ma méthode des points intérieurs (en temps
polynomial donc) ou par l’algorithme du simplexe.
En 1985, Goldberg et Tarjan [12] ont montré qu’il existait un algorithme particulièrement
efficace pour résoudre le problème flot de coût minimum. L’algorithme travaille encore sur
le graphe résiduel, en définissant c(a−1 ) := −c(a) pour a ∈ D et
Af := {a : a ∈ A et f (a) < u(a)} ∪ {a−1 : a ∈ A et f (a) > `(a)}.
Le graphe résiduel Df est donc maintenant muni de coûts.
5.2.3 Algorithme de Goldberg et Tarjan
On commence par fixer un b-flot (voir ci-dessous : comment trouver un b-flot réalisable).
Le coût moyen d’un circuit C est défini par
P
a∈C c(a)
,
|C|
somme des coûts des arcs du circuit C divisée par le nombre d’arcs du circuit C.
On repète
Repérer un circuit C de coût moyen minimum dans Df . S’il n’y en a
pas, alors f est optimal. Sinon, on calcule µ le plus grand possible qui
permette d’ augmenter f le long de C et on augmente f de la
quantité µ.
Le calcul de µ se formalise par µ := mina∈C uf (a). Augmenter f le long de C se fait de
la manière suivante : si a ∈ C est dans le même sens dans A (i.e. a ∈ A), alors on pose
f (a) := f (a) + µ ; sinon (i.e. a−1 ∈ A), alors on pose f (a) := f (a) − µ.
La difficulté de cet algorithme est de trouver un circuit de coût moyen minimum dans le
graphe résiduel Df . En fait, pour cela, on peut faire appel à un algorithme de Karp [18] qui
trouve un tel circuit en O(nm).
Théorème 5.5. On peut trouver un b-flot de coût minimum en O(n2 m3 log n).