Problème de flot

à
coût minimum
Énoncé du problème

Exemples d’application

Adaptation de l’algorithme du simplexe

Énoncé du problème de flot à coût minimal
Soit un réseau R = (N, A) où N représente les sommets du réseau et
A l’ensemble des arcs.
On désigne aussi par
K(x, y) : capacité maximale de l’arc (x, y), (x, y)  A,

f(x, y) : quantité de flot passant par l’arc (x, y), (x, y)  A,

S : {s  N | s est une source avec une disponibilité de vs unités},

P : {p  N | p est un puits avec une demande de vp unités},

c(x, y) : coût unitaire du flot dans l’arc (x, y), (x, y)  A.

Le problème consiste à déterminer la valeur du flot n’excédant pas la

capacité dans chaque arc pour satisfaire la demande à P à partir de la
2
disponibilité à S tout en minimisant le coût total.
Le problème s’énonce alors comme suit :

Min  c(x, y) f(x, y)

(x, y)  A vx si x  S
 f(x, y) -  f(y, x) = 0 si x  SP
{y  N | (x, y)  A} {y  N | (y, x)  A} -vx si x  P

0  f(x, y)  K(x, y), (x, y)  A.

Note :
Pour l'instant, nous supposerons que la somme des disponibilités
égale la somme des demandes. Cette hypothèse sera relâchée par
la suite.
3
Exemple d’application Réseau de transbordement d’un bien
Tiré de B. T. Smith, "Introduction à la théorie des graphes et des réseaux". Tome II,
Département de Génie industriel, École Polytechnique de Montréal, Sept. 1983.

S = {2, 3} : des usines de production avec une capacité de production

de 6 et 8 unités resp. pendant une période fixe de temps.
P = {5, 6} : des entrepôts locaux ayant des demandes de 9 et 5 resp.
4
 Les sommets 1 et 4 représentent des points de transbordement
(sommets intermédiaires), par exemple des entrepôts régionaux.
Les unités ne restent pas à ces endroits mais sont acheminées
directement vers d'autres destinations (sources, puits ou sommets
intermédiaires).

À côté de chaque voie de transport (arc), on indique le coût de

transporter une unité à travers l'arc.
Le problème consiste à faire passer 8 + 6 = 14 unités de flot des
sources jusqu'aux puits tel que
(1) toutes les demandes soient satisfaites;
(2) la conservation de flot soit satisfaite à chaque sommet
intermédiaire;
(3) le coût total de transport soit minimum.
Il n’y a aucune contrainte sur la quantité de flot qui peut traverser un
arc dans cet exemple. De façon générale, il en est autrement. 5
Contrairement au problème de flot maximal, nous ne voulons pas
maximiser un flot (car cette valeur est fixée d'office à la somme des
disponibilités) mais nous cherchons le vecteur de flot le moins cher
qui satisfasse les demandes.

Voici un flot réalisable dont le coût total est: 8x7 + 6x8 + 1x1 = 105
(les arcs en gras portent un flot positif, les autres arcs un flot nul) :

6
Voyons maintenant un autre exemple de flot réalisable moins cher
que le précédent.

Le coût total est: 8x3 +8x3 + 6x5 + 5x1 = 83.

7
Exemple d’application
Tiré de B. T. Smith, "Introduction à la théorie des graphes et des réseaux". Tome II, Département de Génie industriel,
École Polytechnique de Montréal, Sept. 1983.

10 étudiants inscrits dans un cours,

12 projets de fin d’études disponibles,

1 projet par étudiant,

les projets de 1 à 4 sont assignés à au plus 1 étudiant,

les projets de 5 à 8 sont assignés à au plus 2 étudiants,
les projets de 9 à 12 sont assignés à au plus 3 étudiants,

les projets sont éliminés s’il n’y a pas d’étudiants qui leur sont affectés,

6 professeurs au total sont disponibles pour diriger les projets.

8
un sous-ensemble de professeurs peuvent diriger chaque projet :

Chaque étudiant travaillant sur un projet doit être dirigé par un

professeur dans le sous-ensemble de ceux affectés au projet.
9
Chaque professeur peut diriger un nombre maximum d’étudiants :

Chaque étudiant choisit un sous-ensemble des projets sur lesquels il

aimerait travailler et il classe les projets dans ce sous-ensemble en
ordre décroissant de préférence comme dans le tableau suivant :

10
Objectif collectif :
Affecter les étudiants
aux projets et
aux professeurs
afin de minimiser
la somme
des classements
des projets
sur lesquels
travailleront
les étudiants.

Il s’agit d’un problème

de flot à coût minimum:

11
 (10) (12) (6) Si un professeur j
peut diriger le projet i

capacité
coût
Demande de 10
étudiants au puits
Note :
Certains arcs seulement
Sont indiqués pour
éviter la confusion.

Limite le # d’étudiants
affectés au professeur j.

Limite le # d’étudiants
affectés au projet i.
Numéro Un arc entre chaque
de étudiant et chaque projet
classement qu’il préfère.
Propriétés de la matrice des contraintes de conservation du flot

Portons notre attention sur les contraintes suivantes :

vx si x  S
 f(x, y) -  f(y, x) = 0 si x  SP
{y  N | (x, y)  A} {y  N | (y, x)  A} -vx si x  P

ou sur une forme succincte :

Af=b où A est la matrice d’incidence du réseau orienté,

f est le vecteur de flot,
b est le vecteur colonne des disponibilités et des
demandes.
Théorème :
La matrice d’incidence A d’un graphe orienté simple et connexe
composé de m sommets et n arcs est de rang m – 1. 13
Théorème :
Soit la matrice d’incidence A d’un graphe orienté simple et connexe
composé de m sommets et n arcs,

une sous-matrice de A carré d’ordre m – 1 est non singulière

(forme une base)

les arcs associés aux colonnes de cette sous-matrice sont ceux d’un
arbre partiel du graphe orienté.

Théorème :

N'importe quel flot réalisable dans un réseau peut être transformé en

un flot réalisable tel que les arcs portant un flot positif fasse partie
d'un arbre partiel du graphe orienté.

14
Preuve du théorème précédent :

15
Exemple de transformation d’un flot réalisable en un autre tel que les
arcs portant un flot positif fasse partie d’un arbre partiel du graphe :
Réseau de transbordement d’un bien

Par la suite, seulement les arcs portant un flot positif sont illustrés,
avec la valeur du flot indiqué à côté de chaque arc; les autres arcs du
16
réseau portent un flot nul.
Considérons le flot réalisable suivant :

But : Rechercher un flot réalisable avec au plus m – 1 = 5 arcs

portant un flot positif où ceux-ci ne forment pas de circuit.
17
Or, pour ce flot réalisable, il y a 9 arcs portant un flot positif.
Choisissons comme premier circuit 1, 2, 4, 3, 1 avec l'orientation dans
le sens de l'arc (1,2).
Le seul arc inverse du circuit est (3,4) avec le flot f34 = 3.

On ajoute 3 unités de flot aux arcs (1, 2), (2,4) et (3,1) et on soustrait 3
unités de flot de l'arc
(3,4), on a alors:

18
 19
Le circuit 2, 5, 6, 2 permet de transformer le flot comme suit :
Enfin, le circuit 2, 4, 6, 2 donne lieu à un flot positif dans un arbre
partiel comme suit: 20
21
On aurait pu arriver au flot indiqué par les arcs en gras de la figure
ci-dessous, où 4 arcs portent un flot positif et un arc (2,4) porte un flot
nul, mais fait partie de l'arbre partiel de G.

22
Ce flot réalisable est dégénéré.
 BREF
Tout arbre partiel du graphe G correspond
à une soln de base du programme linéaire
et inversement,
toute soln de base du programme linéaire peut se ramener
à une soln réalisable n'utilisant que les arcs d'un arbre partiel du graphe.

Pour résoudre le problème de flot à coût minimum,

il s’agit donc de ne s’occuper que des arbres partiels du graphe
(les solutions de base).

S’il existe une solution optimale au problème de flot à coût minimum,

il en existe une qui correspond au flot dans un arbre partiel de G.

23
 Adaptation de la méthode du simplexe
Il s’agit d’exploiter le fait que A est la matrice d’incidence du graphe.

Note : Considérons d’abord le cas où le flot est sans borne supérieure.

Illustrons à travers un exemple. coût flot réalisable

destination
source

24
La valeur du flot sur chacun des arcs correspond à une solution de base
réalisable dont la base associée correspond à un arbre partiel T :

Cette solution de base est dégénérée puisque le flot à l’arc (s,1) est nul.

25
Cette adaptation du simplexe repose sur l'utilisation des multiplicateurs
du simplexe.

Dénotons par πi le multiplicateur associé à la iième ligne de la matrice

d'incidence A, i.e. associé au iième sommet du réseau orienté.
Se référant à la définition d’un vecteur de coût relatif, on peut écrire:
c(x,y) = c(x,y) – x + y (x, y)  A.
Pour évaluer ces multiplicateurs, il suffit de trouver une solution au
système :
c(x,y) = c(x,y) – x + y = 0 (x, y)  T.
Puisqu’un arbre comporte exactement un nombre d’arcs égal au
nombre de sommets –1, ce système comporte un nombre d’inconnus
supérieur de 1 au nombre d’équations.
Il suffit de fixer la valeur d’un des multiplicateurs et d’évaluer
26
facilement les autres à l’aide du système.
Si on pose t = 0, alors 3 = c(3,t) + t = 2 + 0 = 2,
2 = c(2,3) + 3 = 3 + 2 = 5,
s = c(s,2) + 2 = 5 + 1 = 6,
1 = s - c(s,1) = 6 - 4 = 2.
Évaluons maintenant le coût relatif des variables hors-base :
c(2,1) = c(2,1) - 2 + 1 = 2 – 5 + 2 = -1
27
c(1,t) = c(1,t) - 1 + t = 1 – 2 + 0 = -1.
Puisque c(2,1) = c(1,t) = -1, les 2 variables sont admissibles comme
variable d’entrée. Choisissons l’arc (2,1) comme variable d’entrée.

Critère de sortie : déterminer le cycle fondamental p/r à l'arbre partiel

correspondant à la variable d'entrée puisque seul le flot dans les arcs
de ce cycle est influencé par une variation du flot dans l'arc associé à
la variable d'entrée.

Si f(2,1) augmente, f(s,1) doit diminuer et f(s,2) augmenter.

28
Or, f(s,1) = 0 (solution dégénérée)  f(2,1) reste égale à 0.
Cette solution réalisable demeure inchangée :

L’arbre correspondant à cette solution de base réalisable est :

29
Si on pose t = 0, alors 3 = c(3,t) + t = 2 + 0 = 2,
2 = c(2,3) + 3 = 3 + 2 = 5,
s = c(s,2) + 2 = 1 + 5 = 6,
1 = 2 - c(2,1) = 5 - 2 = 3.
Évaluons maintenant le coût relatif des variables hors-base :
c(s,1) = c(s,1) - s + 1 = 4 – 6 + 3 = 1
c(1,t) = c(1,t) - 1 + t = 1 – 3 + 0 = -2.
L’arc (1,t) devient variable d’entrée avec comme cycle fondamental :

+ -

-
30
On peut donc augmenter le flot à l’arc (1,t) de 4 et mettre à jour les
autres arcs du cycle en conséquence.
On considère l’arc (3,t) comme étant la variable de sortie pour
retrouver la base suivante :

Si on pose t = 0, alors
1 = c(1,t) + t = 1, 2 = c(2,1) + 1 = 2 + 1 = 3,
31
s = c(s,2) + 2 = 1 + 3 = 4, 3 = 2 - c(2,3) = 3 – 3 = 0.
 Évaluons maintenant le coût relatif des variables hors-base :
c(s,1) = c(s,1) - s + 1 = 4 – 4 + 1 = 1
c(3,t) = c(3,t) - 3 + t = 2 - 0 = 2.
Donc, la solution est optimale.

Remarques :

La méthode du simplexe est grandement simplifiée grâce à la

structure particulière du problème.

Il y a beaucoup de dégénérescences dans les problèmes de flots

dans les réseaux. À cause de cela, il est parfois nécessaire de changer
de base sans changer les valeurs des variables d’une itération à l’autre.
Cunningham (1976) :
Des résultats existent pour guider le choix des solutions
de base réalisables dans le but d’éviter de telles itérations
32
dégénérées.
 Énoncé de l’algorithme du simplexe adapté
(absence de bornes supérieures sur les arcs)

0. Générer un flot réalisable de base où T est l’arbre partiel du graphe

G associé à cette base.
1. Calculer les valeurs des variables duales i, i=1, 2, …, n en posant
n = 0 et en résolvant c(i,j) - i + j = 0 (i,j)  T.

2. Test d’optimalité La soln

courante
Si c(i,j) - i + j  0 (i,j)  T, alors terminer. est
optimale.
3. Choix de l’arc d’entrée
(i*, j*) = arg Min {c(i,j) - i + j}
(i,j)  T
Ajouter cet arc à l’arbre partiel T pour former un circuit
33
fondamental C dans T  {(i*, j*)}.
4. Choix de l’arc de sortie

Choisir l’arc de sortie (i', j') inverse par rapport à (i*, j*) dans C :
(i', j') = arg Min f(i,j)
(i,j)  C
(i, j) est l’inverse de (i*, j*)
5. Pivot
Effectuer un pivot pour passer de l’arbre T à l’arbre
T  {(i*, j*)} – {(i', j')} avec comme flot :

f(i, j) si (i, j)  C
f(i, j) + f (i', j') si (i, j)  C et direct p/r à (i*, j*)

f(i, j) - f (i', j') si (i, j)  C et inverse p/r à (i*, j*).

Mettre T  T  {(i*, j*)} – {(i', j')} et passer à l’étape 1. 34

 Méthode "GRAND M"
Calcul d’un flot réalisable de base initial

1. Ajouter un sommet fictif n + 1 au réseau,

des arcs (i, n + 1) avec un flot f(i, n+1) = vi i  S,
des arcs (n + 1, i) avec un flot f(n+1, i) = vi i  P,
des arcs (n + 1, i) avec un flot f(n+1, i) = 0 i  S  P.

Tous ces nouveaux arcs sont appelés artificiels et

le flot dans ces arcs y compris un flot de zéro dans tous les arcs
originaux du réseau constituent un flot réalisable dans un arbre
partiel du graphe G augmenté.

2. Affecter le coût M >> 0 (une valeur beaucoup plus grande que

celle des c(i,j) du problème original) aux arcs artificiels du réseau
augmenté.
35
3. Résoudre le problème de flot à coût minimum sur le réseau
augmenté par l'algorithme du simplexe en éliminant les arcs
artificiels au fur et à mesure qu'ils sortent des arbres partiels.

4. Lorsque l'algorithme du simplexe termine, deux cas sont possibles:

si l'arbre partiel obtenu ne contient pas d'arcs artificiels ou
contient des arcs artificiels à flot nul,
alors c’est un flot optimal du problème original.

si l'arbre partiel obtenu contient des arcs artificiels portant

un flot positif
alors le problème original n'a pas de flot réalisable.

36
Exemple : v = 4, s est la source et t la destination.
À chaque arc (i, j) est associé le coût cij.

Supposons qu’aucun flot réalisable initial n’est disponible.

Appliquons la méthode M.
37
Considérons donc le réseau augmenté suivant où à chaque arc (i, j) est
associé le couple cij, fij:

38
La valeur du flot sur chacun des arcs correspond à une solution de base
réalisable dont la base associée correspond à un arbre partiel T :

Cette soln de base est dégénérée puisque fA2 = fA1 = fA3 = 0. 39

Calcul des multiplicateurs du simplexe :

40
Calcul du coût relatif des variables hors-base

Coût négatif

Nous choisissons donc la variable fs2 comme variable d’entrée avec

comme cycle fondamental :
41
 -
-

On peut donc augmenter le flot à l’arc (s,2) de 0 car la soln est

42
dégénérée (fA2 = 0). fA2 est la variable de sortie.
L’arbre correspondant à cette solution de base réalisable est :

43
 Coût
négatif

f21 devient variable d’entrée avec comme cycle fondamental :

44
 - -

+ +

On peut donc augmenter le flot à l’arc (2,1) de 0 car la soln est

45
encore dégénérée (fA1 = 0). fA1 est la variable de sortie.
46
 Coût
négatif

f1t est choisie arbitrairement comme variable d’entrée avec comme

cycle fondamental :

47
 -

+ +

On peut donc augmenter le flot à l’arc (1, t) de 4; ceci est accompagné

48
d’une augmentation à fs2 et f21 et d’une diminution à fsA et fAt.
fAt est la variable de sortie.

49
 Coût
négatif

f23 50
Le cycle fondamental obtenu en ajoutant la variable d’entrée f23 est :

+ 51
Augmentation de f23 de 0.
On choisit fA3 comme étant la variable de sortie.

52
Les multiplicateurs sont obtenus en posant :

53
Extensions possibles :

1.  vi >  vi
iS iP

Rajouter un puits fictif n + 1 avec une demande

vn+1 =  vi -  vi
iS iP
et des arcs (i, n+ 1) i  S avec comme borne supérieure  et
un coût nul.

Lorsque l’algorithme du simplexe termine, enlever le sommet

fictif n + 1 ainsi que le flot dans les arcs (i, n + 1), i  S.

54
2.  vi <  vi
iS iP

Rajouter une source fictive n + 1 avec une disponibilité

vn+1 =  vi -  vi
iP iS
et des arcs (n+ 1, i) i  P avec comme borne supérieure  et
un coût nul.

Lorsque l’algorithme du simplexe termine, enlever le sommet

fictif n + 1 ainsi que le flot dans les arcs (n + 1, i), i  P.

55
3. Présence d’une borne supérieure finie sur le flot dans un arc

Rappel :
à chaque itération du simplexe, le flot positif est restreint aux arcs
d’un arbre partiel T (solution de base);

fij = 0 (i, j)  T

un arc (i,j)  T est candidat pour entrer dans la base si cij -i +j < 0

un arc (k, l)  C est candidat pour sortir de la base si :

(i) (k, l) est un arc inverse dans C.
(ii) fkl devient nul le premier lorsque le flot fij augmente.

Lorsqu’il y a des bornes supérieures sur le flot de certains arcs,

la méthode du simplexe conserve toujours le vecteur de flot dans un
arbre T, mais (i, j)  T, ou bien fij = 0 ou bien fij = Kij. 56
Théorème :
Soit une solution de base réalisable f* = (f*ij) et l’arbre partiel T
qui lui est associé tel que (i, j)  T, on a :
(i) f*ij = Kij si cij -i +j < 0

(ii) f*ij = 0 si cij -i +j > 0

alors f* est un flot optimal.

Nouveau critère d’entrée :

Choisir l’arc (i, j)  T qui satisfait :

Min {| cij -i +j |}

(i, j)  T
57
Nouveau critère de sortie :
(1) Si (i, j) est l’arc d’entrée et fij = Kij, alors le changement au flot
de l’arc (i, j) est une diminution de t unités où
t = min {fij | (i, j) est direct, Kij – fij | (i, j) est inverse}

L’arc de sortie est celui de C dont le flot atteint le premier soit 0

58
soit sa borne supérieure.
(2) Si (i, j) est l’arc d’entrée et fij = 0, alors le changement au flot
de l’arc (i, j) est une augmentation de t unités où
t = min {fij | (i, j) est inverse, Kij – fij | (i, j) est direct}.
t unités sont ajoutées à tout arc direct de C et
soustraites à tout arc inverse de C.

L’arc de sortie est celui de C dont le flot atteint le premier soit 0

soit sa borne supérieure.

Note : Pour trouver l’arbre initial de flot réalisable, utiliser la

méthode « grand M » en remarquant que les arcs artificiels
ont une borne supérieure infinie.

Dans l’exemple suivant, on associe à chaque arc le triplet Kij, cij

fij 59
Exemple : v = 4

Le vecteur de flot correspond à une solution de base réalisable

dont la base associée correspond à un arbre partiel T :
60
Cette solution de base est dégénérée puisque fs1 = f1t = 0.
Les multiplicateurs du simplexe sont évalués :

61
Les coûts relatifs des variables hors-base sont :

Puisque f21 = 0 et f3t = 4 = K3t, les deux variables sont admissibles

comme variable d'entrée.

Nous choisissons de diminuer la valeur de la variable f3t avec comme

cycle fondamental :

+ +

- -

- 62
On peut donc diminuer la valeur de f3t de 2 et alors f23 = fs2 = f3t = 2
et fsl = flt = 2. C'est la plus grande modification possible puisque flt
atteint sa borne supérieure Klt = 2.
Cette solution réalisable est :

63
L’arbre correspondant à cette solution de base réalisable est :

admissible comme variable

d’entrée : f21 = 0.
non admissible comme
variable d’entrée : f1t = 2 = K1t.
64
Le cycle fondamental correspondant à la variable f21 est :
 -

+
+

On peut augmenter la valeur de f21 de 2, et alors f21 = 2, fs2 = 4, fsl = 0.

L'augmentation de f21 est limitée à la fois par la variable fsl qui devient
égale à 0 et par la variable d'entrée qui atteint sa borne supérieure.

On pourrait donc conserver la même base et entreprendre une nouvelle

itération. On préfère considérer fsl comme étant la variable de sortie
pour retrouver la base dont l'arbre partiel est illustré ci-dessous :

65
Les coûts relatifs des variables hors-base sont donc

csl = csl - πs + πl = 4 - 6 + 3 = 1
clt = clt - πl + πt = 1 - 3 = -2.

Donc la solution de base est optimale puisque fsl = 0 et flt = 2 = K66lt.