4.6 Pro blèmes d’affec ta tion
139
© Dunod – Toute reproduction non autorisée est un délit.
Voici, sur le réseau de tran    sport, le flot opti    mal  f
(1)
:
Figure 4.31 Flot opti mal f
(1) avec la coupe minimale (S, S)
Notes.  •  L’arc (B, D) ne tra verse pas en fait la coupe mini male puisque B et D H S.
•  À la coupe mini male du réseau de transport R cor res pond un « co- circuit »
dans G
e
1 f
*
2 . L’ensemble des arcs du graphe d’écart allant des som mets de S
vers ceux de S est vide : U
1
S 5 [. Tout arc ayant une extré mité et une seule dans
S est orienté dans le sens de S vers S. Ici S 5 5s, A, C6 et S 5 5B, D, p6.
4.6 pro blèmes d ’ Affec tA tion
Nous les pré sen tons ici comme une appli ca tion de l’algo rithme de Ford- Fulkerson.
Exemple. On désire pro cé der aux muta tions de cinq per sonnes A, B, C, D et Ε, et on
leur offre les postes a, b, c, d et e. Ces per sonnes dési rant maxi mi ser leur satis faction,
décident cha cune de noter de 1 à 5 les postes offerts et obtiennent le tableau sui vant
regrou pant leurs avis (tableau 4.1) ; la note 1 est don née au poste pré féré, …, la note
5 à celui le moins appré cié :
Il est évident qu’il convient, pour
maxi mi ser la satis faction géné rale, de
choi sir un chiffre et un seul par ligne
et par colonne, de manière à ce que la
somme des cinq chiffres choi sis soit
mini male (si cha cun pou vait obte nir
le poste qu’il a classé n° 1, la somme
mini male serait 5) ; mais c’est ici
impos sible : trois per sonnes ont classé
le poste a en pre mier.
On ne change pas le pro blème en sous trayant, ligne par ligne, puis colonne par
colonne, le plus petit élé ment de la ligne ou de la colonne (ceci se prouve aisé ment).
a
b
c
d
e
A
1
2
3
4
5
1
4
2
5
3
3
2
1
5
4
1
2
3
5
4
2
1
4
3
5
B
C
D
E
Tableau 4.1