Précédent Suivant

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 s

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.