6. Le problème de flot à coût minimal
p. 238-302
Extrait
6.1 Définition du problème
1L’acheminement, dans un réseau orienté, de la plus grande quantité de flot possible a fait l’objet du chapitre précédent. Ce flot s’écoulait d’un sommet retenu comme source jusqu’à un sommet désigné comme puits. Dans le problème de flot maximal traité au chapitre 5, nous ne tenions pas compte des coûts éventuels, veillant seulement à ne pas excéder la capacité de chacun des arcs.
2Nous nous intéressons maintenant à la minimisation du coût total d’acheminement de la source au puits d’une quantité précise de flot. Cette situation a reçu le nom de problème de flot à coût minimal (PFCM). Le PFCM surgit dans de nombreuses applications de la recherche opérationnelle comme l’indiquent les exemples présentés à la section 6.8 et les nombreux exercices proposés en fin de chapitre. Plusieurs algorithmes ont été mis au point au cours des dernières décennies pour le résoudre rapidement de façon optimale, même lorsque le réseau sous-jacent comporte des milliers de
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
