Solutions
476
mn – (n + m – 1) = 5 × 4 – (5 + 4 – 1) = 12
x ij nuls (cases non affec tées).
Cette solu tion sera dési gnée par la
déno mi na tion : tableau 1.
Le cal cul des coûts mar gi naux des
subs ti tutions uni taires pos sibles à par tir de
cette solu tion de base, four nit (voir l’arbre
1) les résul tats sui vants (nous nous bor -
nons à indi quer les δ ij néga tifs) :
Rappel : δ ij = C ij – (v j – u i )
δ 21 = 51 + 27 – 113 = –35
δ 31 = 0 + 11 – 113 = –102
δ 32 = 0 + 47 – 103 = –56
δ 33 = 0 + 14 – 94 = –80
δ 41 = 39 + 52 – 113 = –22
Nombre d’uni tés
déplaçables (ν)
Influence sur le
coût total (ρ)
liaison
(2, 1)
343
– 12 005
liaison
(3, 1)
343
– 34 986
liaison
(3, 2)
343
– 19 208
liaison
(3, 3)
50
– 4 000
liaison
(4, 1)
343
– 7 546
On peut sup po ser qu’il est indi qué d’effec tuer d’abord
la subs ti tution dont l’influence sur le coût total est la
plus forte : (3, 1) – cf tableau 2 – et l’on peut consta ter
immé dia te ment que la subs ti tution (3, 3) peut être exé -
cu tée aus si tôt après – cf tableau 3.
Le tableau 3 (arbre 2) pré sente deux subs ti tutions utiles :
δ 14 = 0 + 49 – 90 = – 41 et δ 15 = 0 + 13 – 103 = –90
ν
ρ
(1, 4) 8
–328
(1, 5) 457
– 41 130
1
1
2
732
542
439
457
343
50
58
928
2
3
3
4
4
5
tableau 2
arbre 2
1
1
2
782
542
439
457
343
50
928
2
3
3
4
4
8
5
tableau 3
arbre 1
1
1
2
800 96
896
782
943
1 470
790
439
800
389
50
50
343
401 542
928 928
2
3
3
4
4
5
Coût total : 181 721
tableau 1
Pour le calcul des potentiels
des sommets de l’arbre associé à
la solution de base (Tab. 1), on a
posé a 3 = 0, puis calculé les autres
potentiels de proche en proche :
v j – u i = c ij pour tout arc de
l’arbre.