URL originale : https://books.openedition.org/pum/5080

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.
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.
Méthodes de planification en transport
Ce livre est diffusé en accès limité. L’accès à la lecture en ligne ainsi qu’aux versions PDF et ePub est réservé aux bibliothèques l’ayant acquis. Vous pouvez vous connecter à votre bibliothèque à l’adresse suivante : https://freemium.openedition.org/oebooks
Si vous avez des questions, vous pouvez nous écrire à access[at]openedition.org
Méthodes de planification en transport
Vérifiez si votre bibliothèque a déjà acquis ce livre : authentifiez-vous à OpenEdition Freemium for Books.
Vous pouvez suggérer à votre bibliothèque d’acquérir un ou plusieurs livres publiés sur OpenEdition Books. N’hésitez pas à lui indiquer nos coordonnées : access[at]openedition.org
Vous pouvez également nous indiquer, à l’aide du formulaire suivant, les coordonnées de votre bibliothèque afin que nous la contactions pour lui suggérer l’achat de ce livre. Les champs suivis de (*) sont obligatoires.
Veuillez, s’il vous plaît, remplir tous les champs.
La syntaxe de l’email est incorrecte.
Référence numérique du chapitre
Format
Référence numérique du livre
Format
1 / 3