Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
184
*4.14 Pro gramme de tran sport
En des dépôts 1, 2, 3, et 4 existent des quan ti tés res pec tives de 500, 600, 200 et
900 tonnes de mine rai à tran spor ter. Les dis tances mutuelles des clients, au nombre
de 6, aux dépôts 1, 2, 3, et 4 sont don nées par la matrice ci- dessous.
1
2
3
4
5
6
9
7
6
6
8
5
3
7
9
6
7
5
9
5
9
3
2
2
10
11
10
11
11
12
3
1
2
4
Éta blir le plan de tran sport le plus éco no mique de manière à faire par ve nir, aux
points de vente 1, 2, 3, 4, 5 et 6, les quan ti tés res pec tives : 400, 300, 700, 200, 400
et 200 tonnes.
*4.15 com pa rai son d’heu ris tiques pour les pro grammes
de tran sport
On donne la matrice d’un programme de tran sport ci- dessous, com por tant quatre
ori    gines et cinq des    ti    nations. Véri    fier que la somme des dis    po    ni    bi    li    tés égale celle des 
demandes.
On demande de chercher la (ou les) solu tions opti males(s) en uti li sant, pour obte -
nir la pre mière solu tion de base :
a) la règle du coin nord- ouest ;
b) la règle de la dif fé rence maximale (méthode de Balas- Hammer).
Com pa rer ces deux méthodes du point de vue de la lon gueur des cal culs.