Une société de distribution doit effectuer le transport d’un produit de trois centres de production , , vers trois points de vente , , . Le schéma ci-dessous donne la localisation de ces centres et la configuration du réseau de communication constitué d’une voie ferrée et de routes. est un simple point intermédiaire.

Exercice 19

On suppose que :

• le transport d’une tonne de produit par voie ferrée coûte 2 unités monétaires/km
• le transport d’une tonne de produit par route coûte 3 unités monétaires/km
• le transfert d’une tonne de produit de la voie ferrée vers la route et inversement coûte 20 unités monétaires

1. Vérifier la valeur, couple par couple (centre de production, point de vente) du chemin de moindre coût, par comparaison des divers chemins possibles et indiquer les points ou centres par lesquels passe ce chemin de moindre coût.

Comment pourrait-on procéder de façon systématique si le réseau était de plus grande taille ? (introduire un graphe valué - le tracer pour l’exemple ci-dessus - et proposer une méthode de résolution adaptée.

2. Les productions des trois centres , , sur la période étudiée sont :

• A : 300 tonnes
• B : 400 tonnes
• C : 300 tonnes

Les demandes des trois points de vente , , , pendant le même temps, sont respectivement :

• 270 tonnes
• 310 tonnes
• 420 tonnes

Comment organiser le transport pour que les demandes de , , soient exactement satisfaites et que le coût de ce transport soit le plus petit possible ? On utilisera un algorithme approprié sur un réseau de transport dans lequel tout chemin de moindre coût obtenu à la question précédente sera figuré par un arc : (centre de production, point de vente) valué convenablement.