Solu tions des exer cices du cha pitre 4
477
© Dunod – Toute reproduction non autorisée est un délit.
On tombe sur le tableau 4 après avoir effec tué la seconde de ces subs ti tutions. Il ne com porte
(arbre 3) qu’une subs ti tution inté res sante: δ 12 = 0 + 47 – 91 = – 44, avec ν = 85 et ρ = –3 740
Après avoir effec tué cette subs ti tution, on obtient le tableau 5, dans lequel appa raît (arbre 4)
une seule rela tion de coût mar gi nal néga tif : δ 44 = 0 + 77 – 85 = –11, avec ν = 8 et ρ = – 88
On obtient fina le ment le tableau 6, pour lequel on vérifie que les coûts mar gi naux δ ij donnés
en petits chiffres sont tous stric te ment posi tifs ; il s’agit donc de l’unique solu tion opti male.
b) La règle de la dif fé rence maximale donne évi dem ment une solu tion de base ini tiale
bien meilleure que la règle du coin nord- ouest.
1
1
2
21
27
11
10
52
94
47
52
11
84
43
14
76
74
80
29
29
45
36
6
20
790 1470
50
439
800
29
39
12
69
49
13
13
42
93
54
2
2
13
2
2
2
2
20
928
782
896
943
2
3
3
3
3
4
4
5
8
II
II
IV
III
max
I
VI
V
VII et VIII
36
�
1
1
2
782
354
542
800
50
85
928
2
3
3
4
4
8
5
tableau 5
1
1
2
782
346
+46
+46
+36
+42
+57
+45
+17
+11
+44
+33
+106 +16
550
800
50
93
920
2
3
3
4
4
8
5
tableau 6
(coût : 97 777)
arbre 4
arbre 3
1
1
2
782
85
439
457
800
50
928
2
3
3
4
4
8
5
tableau 4