Version classiqueVersion mobile

Méthodes de planification en transport

 | 
Yves Nobert
, 
Roch Ouellet
, 
Régis Parent

6. Le problème de flot à coût minimal

Les formats HTML, PDF et ePub de cet ouvrage sont accessibles aux usagers des bibliothèques et institutions 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.

Extrait du texte

6.1 Définition du problème

L’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.

Nous 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 sommets ...

© Presses de l’Université de Montréal, 2014

Conditions d’utilisation : http://www.openedition.org/6540

Acheter

Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search