Problèmes de flots
227
Si l'on pouvait alors affecter sur cette matrice un zéro par ligne et par colonne, le
problème serait résolu; en effet la fonction économique , avec ses nouveaux coûts tous
positifs ou nuls, serait alors nulle, donc la plus faible possible.
Une telle affectation existe-t-elle ? Pour en décider nous allons appeler couplage un
ensemble de zéros de la matrice des coûts tel que deux zéros quelconques du couplage
correspondent à deux lignes différentes et deux colonnes différentes, la taille du
couplage sera alors le nombre de ses zéros.
Ainsi, sur la matrice 3, les zéros
forment un couplage de taille ; par
contre les zéros
, ne forment pas de couplage (colonne commune
aux deux premiers).
La taille d'un couplage est évidemment limitée par dans le cas général et sur l'exemple
présent par .
Dans ces conditions, si nous recherchons le couplage de taille maximale sur la matrice ,
et si nous trouvons que ce couplage a pour taille 6, le problème est résolu : on a trouvé
l'optimum; si la taille du couplage obtenu est inférieure à , il faudra transformer de
nouveau la matrice, de façon à faire apparaître un couplage de taille .
Phase 2 - Recherche du couplage maximal
Pour chercher ce couplage maximal (i.e de taille maximale), nous allons nous aider de
l'algorithme de Ford-Fulkerson.
Pour cela, nous allons faire correspondre à la matrice le graphe ci-dessous, qui est
un réseau de transport :
Ce graphe a :
- une entrée
reliée par un arc de capacité 1 à chacun des sommets
(les moyens, qui constituent l'ensemble ).
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z
X
Y
1
1
1
1
1
1
1
1
1
1
1
1