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
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 par
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.
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.
L'éducation aux médias à l'ère numérique
Entre fondations et renouvellement
Anne-Sophie Letellier et Normand Landry (dir.)
2016
L'intégration des services en santé
Une approche populationnelle
Lucie Bonin, Louise Belzile et Yves Couturier
2016
Les enjeux éthiques de la limite des ressources en santé
Jean-Christophe Bélisle Pipon, Béatrice Godard et Jocelyne Saint-Arnaud (dir.)
2016
La détention avant jugement au Canada
Une pratique controversée
Fernanda Prates et Marion Vacheret (dir.)
2015
La Réussite éducative des élèves issus de l'immigration
Dix ans de recherche et d'intervention au Québec
Marie McAndrew (dir.)
2015
Agriculture et paysage
Aménager autrement les territoires ruraux
Gérald Domon et Julie Ruiz (dir.)
2014
L'éducation aux médias à l'ère numérique
Entre fondations et renouvellement
Anne-Sophie Letellier et Normand Landry (dir.)
2016
L'intégration des services en santé
Une approche populationnelle
Lucie Bonin, Louise Belzile et Yves Couturier
2016
Les enjeux éthiques de la limite des ressources en santé
Jean-Christophe Bélisle Pipon, Béatrice Godard et Jocelyne Saint-Arnaud (dir.)
2016
La détention avant jugement au Canada
Une pratique controversée
Fernanda Prates et Marion Vacheret (dir.)
2015
La Réussite éducative des élèves issus de l'immigration
Dix ans de recherche et d'intervention au Québec
Marie McAndrew (dir.)
2015
Agriculture et paysage
Aménager autrement les territoires ruraux
Gérald Domon et Julie Ruiz (dir.)
2014
