Restez organisé à l'aide des collections
Enregistrez et classez les contenus selon vos préférences.
De nombreux problèmes en informatique peuvent être représentés par un graphe composé de nœuds et de liens entre eux. Les problèmes de flux de réseau impliquent le transport de biens ou de matériaux sur un réseau, par exemple un système ferroviaire.
Vous pouvez représenter un flux de réseau par un graphique dont les nœuds sont des villes et dont les arcs sont des lignes ferroviaires entre eux. (Ils sont appelés flux car leurs propriétés sont semblables à celles de l'eau qui coule à travers un réseau de tuyaux.)
Une contrainte clé dans les flux de réseau est que chaque arc possède une capacité, c'est-à-dire la quantité maximale pouvant être transportée dans l'arc sur une période fixe.
Le problème de flux maximal consiste à déterminer la quantité totale maximale pouvant être transportée dans tous les arcs du réseau, en fonction des contraintes de capacité.
La première personne à avoir étudié ce problème était le mathématicien russe Tolstoï, dans les années 1930. La carte ci-dessous montre le réseau ferroviaire réel pour lequel il souhaitait trouver un flux maximal.
OR-Tools propose plusieurs résolveurs pour les problèmes de flux réseau dans ses bibliothèques de graphes.
Les sections suivantes présentent des exemples de problèmes de flux réseau et montrent comment les résoudre:
Sauf indication contraire, le contenu de cette page est régi par une licence Creative Commons Attribution 4.0, et les échantillons de code sont régis par une licence Apache 2.0. Pour en savoir plus, consultez les Règles du site Google Developers. Java est une marque déposée d'Oracle et/ou de ses sociétés affiliées.
Dernière mise à jour le 2024/08/09 (UTC).
[[["Facile à comprendre","easyToUnderstand","thumb-up"],["J'ai pu résoudre mon problème","solvedMyProblem","thumb-up"],["Autre","otherUp","thumb-up"]],[["Il n'y a pas l'information dont j'ai besoin","missingTheInformationINeed","thumb-down"],["Trop compliqué/Trop d'étapes","tooComplicatedTooManySteps","thumb-down"],["Obsolète","outOfDate","thumb-down"],["Problème de traduction","translationIssue","thumb-down"],["Mauvais exemple/Erreur de code","samplesCodeIssue","thumb-down"],["Autre","otherDown","thumb-down"]],["Dernière mise à jour le 2024/08/09 (UTC)."],[],["Computer science utilizes graphs to model problems like network flow, where goods are transported across a network (e.g., railway). Each link (arc) in the network has a capacity, limiting transport volume. The maximum flow problem determines the highest total transport volume across all arcs, respecting these capacity constraints. This problem, first studied by A.N. Tolstoi, can be solved using solvers from the OR-Tools graph libraries, which are useful for problems such as maximum flows, minimum cost flows, and assignment problems.\n"]]
