4.9 Les pro grammes de tran sport
157
© Dunod – Toute reproduction non autorisée est un délit.
À titre de com pa rai son, le lec teur pourra essayer MINI LI, qui donne un coût
de 3 734 (pas de chance on a obtenu 3 700 par la méthode du coin Nord-Ouest !),
MINICO, pour laquelle le coût tombe à 3 658 et MINITAB qui four nit 3 634. La fai -
blesse de ces trois heu ris tiques gour mandes pro vient du fait qu’on ne modi fie pas le
pro blème en ajou tant à tous les coûts d’une même ligne i (ou d’une même colonne j)
une même quan tité u i (resp. v j ) ce qui revient à rem pla cer c ij par cr ij 5 c ij 1 u i 1 v j .
Cette trans for ma tion bou le verse le clas se ment des coûts c ij par valeur crois sante :
par exemple on peut ajouter 1 000 à tous les coûts d’une même ligne (ou d’une
même colonne) sans changer le classement des solutions suivant leur coût total. La
méthode sui vante n’a pas le même inconvé nient.
Une pro
cé dure, géné ra
le ment très effi cace, est celle de la dif fé rence maximale (ou
heu ris tique de Balas- Hammer) qui favo rise l’obten tion d’une solu tion ini tiale ayant
un coût total assez proche de l’opti mum.
Elle consiste à cal cu ler pour chaque ran gée (ligne ou colonne), la dif fé rence entre
le coût le plus petit et le coût immé dia te ment supé rieur ou égal. Puis à affec ter à la
rela tion de coût le plus petit dans la ran gée pré sen tant la dif fé rence maximale, la
quan tité la plus éle vée pos sible, ce qui a pour effet de « satu rer » une ligne ou une
colonne. Ensuite, de reprendre le pro ces sus jus qu’à ce que toutes les ran gées soient
satu rées. Si on sature à chaque fois une seule ligne ou une seule colonne, sauf au
der nier pas, où plu sieurs ran gées sont satu rées à la fois, on uti lise bien n 1 m 2 1
rela tions, dans le cas géné ral, et l’on obtient une solu tion de base. S’il arrive que
l’on sature à la fois une ligne et une colonne (excluons le der nier pas), alors la solu -
tion sera dégénérée. Ci-dessus, on note D , les différences en ligne et D c , celles en
colonne.
Don nons les pre miers pas pour la matrice pro po sée plus haut :
1 2 3 4 5 6
1 2 3 5 6
12 27 61 49 83 35
23 39 78 28 65 42
23 39 78 65 42
67 56 92 53 54
71 43 91 40 49
71 43 91 67 40 49
67 56 92 24
53 54
12 27 61
83 35
1
er
pas
2
e
pas
I
bj
b j
II
III
IV
I
II
III
IV
j i
c
c
9
ai
9 11 28 6 14 5 73
11 12 17 4 13 7
18
32
14
3
15
5
29
11 12 17 13 7
a 1
9 11 28 14 5 67
9
18
32
8
3
15
16
1
• 1
er
pas. La dif fé rence maximale 53 2 24 5 29 est rela tive à la ligne III. À la rela -
tion (III,4), cor res pon dant au coût le plus petit de la ligne III, on affecte la quan tité
6, ce qui sature la colonne 4, qui disparaît alors du problème.
Obser va tions. On remarque que c’est une idée de « regret » qui consti tue le fon de -
ment éco no mique de la méthode ; plu tôt que d’affec ter le maxi mum d’uni tés à tran -
157
© Dunod – Toute reproduction non autorisée est un délit.
À titre de com pa rai son, le lec teur pourra essayer MINI LI, qui donne un coût
de 3 734 (pas de chance on a obtenu 3 700 par la méthode du coin Nord-Ouest !),
MINICO, pour laquelle le coût tombe à 3 658 et MINITAB qui four nit 3 634. La fai -
blesse de ces trois heu ris tiques gour mandes pro vient du fait qu’on ne modi fie pas le
pro blème en ajou tant à tous les coûts d’une même ligne i (ou d’une même colonne j)
une même quan tité u i (resp. v j ) ce qui revient à rem pla cer c ij par cr ij 5 c ij 1 u i 1 v j .
Cette trans for ma tion bou le verse le clas se ment des coûts c ij par valeur crois sante :
par exemple on peut ajouter 1 000 à tous les coûts d’une même ligne (ou d’une
même colonne) sans changer le classement des solutions suivant leur coût total. La
méthode sui vante n’a pas le même inconvé nient.
Une pro
cé dure, géné ra
le ment très effi cace, est celle de la dif fé rence maximale (ou
heu ris tique de Balas- Hammer) qui favo rise l’obten tion d’une solu tion ini tiale ayant
un coût total assez proche de l’opti mum.
Elle consiste à cal cu ler pour chaque ran gée (ligne ou colonne), la dif fé rence entre
le coût le plus petit et le coût immé dia te ment supé rieur ou égal. Puis à affec ter à la
rela tion de coût le plus petit dans la ran gée pré sen tant la dif fé rence maximale, la
quan tité la plus éle vée pos sible, ce qui a pour effet de « satu rer » une ligne ou une
colonne. Ensuite, de reprendre le pro ces sus jus qu’à ce que toutes les ran gées soient
satu rées. Si on sature à chaque fois une seule ligne ou une seule colonne, sauf au
der nier pas, où plu sieurs ran gées sont satu rées à la fois, on uti lise bien n 1 m 2 1
rela tions, dans le cas géné ral, et l’on obtient une solu tion de base. S’il arrive que
l’on sature à la fois une ligne et une colonne (excluons le der nier pas), alors la solu -
tion sera dégénérée. Ci-dessus, on note D , les différences en ligne et D c , celles en
colonne.
Don nons les pre miers pas pour la matrice pro po sée plus haut :
1 2 3 4 5 6
1 2 3 5 6
12 27 61 49 83 35
23 39 78 28 65 42
23 39 78 65 42
67 56 92 53 54
71 43 91 40 49
71 43 91 67 40 49
67 56 92 24
53 54
12 27 61
83 35
1
er
pas
2
e
pas
I
bj
b j
II
III
IV
I
II
III
IV
j i
c
c
9
ai
9 11 28 6 14 5 73
11 12 17 4 13 7
18
32
14
3
15
5
29
11 12 17 13 7
a 1
9 11 28 14 5 67
9
18
32
8
3
15
16
1
• 1
er
pas. La dif fé rence maximale 53 2 24 5 29 est rela tive à la ligne III. À la rela -
tion (III,4), cor res pon dant au coût le plus petit de la ligne III, on affecte la quan tité
6, ce qui sature la colonne 4, qui disparaît alors du problème.
Obser va tions. On remarque que c’est une idée de « regret » qui consti tue le fon de -
ment éco no mique de la méthode ; plu tôt que d’affec ter le maxi mum d’uni tés à tran -