Problèmes de flots
225
La fonction peut s'écrire :
kj
kj
j
ij
ij
j
k
i
x
c
x
c
C
,
=
Ajoutons aux
une quantité algébrique quelconque, la fonction de coût devient :
kj
j
kj
kj
j
ij
ij
j
k
i
'
x
d
x
c
x
c
C
,
=
Mais comme :
1
=
kj
j
x
On en déduit :
En conséquence, minimiser revient à minimiser
Le même raisonnement s'applique sur les colonnes de la matrice .
9.6.3. Algorithme hongrois
Cet algorithme consiste essentiellement à utiliser le résultat précédent pour transformer
progressivement la matrice afin d'y faire apparaître l'affectation optimale.
Nous allons l'expliquer sur un exemple, pour simplifier l'exposé.
Soit alors le problème d'affectation suivant :
; les moyens seront notés
et les tâches
. La matrice sera :
Phase 1- Apparition d'un zéro par ligne et par colonne
Soustrayons à chaque ligne le plus petit élément de cette ligne ; on en a le droit d'après le
théorème ci-dessus ; on obtient la nouvelle matrice.
a
b
c
d
e
f
A
25
19
24
15
19
30
B
40
27
28
20
31
29
C
17
14
11
12
18
16
D
32
28
27
20
31
30
E
29
25
28
18
24
27
F
30
32
35
22
30
28
Matrice 1