Précédent Suivant

7. Le problème de transport classique

p. 303-352


Extrait

7.1 Définition du problème

1Le problème de transport classique (PTC) constitue un cas particulier du PFCM traité au chapitre précédent :

  • il n’y a pas de sommet de transbordement ;

  • le flot sur chaque arc admet une borne inférieure égale à 0, sans se voir imposer de borne supérieure.

2Tout PTC s’illustre de la façon indiquée à la figure 7.1.

FIGURE 7.1. Illustration d’un PTC

Image 1000000000000289000001A233C86593.jpg

3Dans le cas d’un PTC, on appelle origine chacun des sommets émetteurs et destination chacun des sommets récepteurs. Chaque sommet émetteur i expédie une quantité fixe de flot, dénotée Si dans la figure 7.1 et appelée disponibilité (supply) de l’origine i. Chaque sommet récepteur j cherche à recevoir une quantité fixe de flot, dénotée Dj et qualifiée de demande de la destination j. Le coût de transport d’une unité de flot sur l’arc ij du réseau est dénoté cij. Les données pertinentes au PTC se résument dans le tableau 7.1. Résoudre un PTC consiste à minimiser le total des coûts à encourir pour convoyer le flot part

Les formats HTML, PDF et ePub de cet ouvrage sont accessibles aux usagers des bibliothèques qui l’ont acquis dans le cadre de l’offre OpenEdition Freemium for Books. L’ouvrage pourra également être acheté sur les sites des libraires partenaires, aux formats PDF et ePub, si l’éditeur a fait le choix de cette diffusion commerciale. Si l’édition papier est disponible, des liens vers les librairies sont proposés sur cette page.

Précédent Suivant

Le texte seul est utilisable sous licence Licence OpenEdition Books. Les autres éléments (illustrations, fichiers annexes importés) sont « Tous droits réservés », sauf mention contraire.