| Une société organise le transport de céréales des villes
vers les villes
. La disponibilité en tonnes des villes est de Les besoins en tonnes des villes sont de Le tableau suivant donne les capacités de transport, en tonnes, entre les villes : On désire modéliser le problème. Pour cela, on introduit un graphe valué avec des capacités. Quelles capacités doit-on mettre sur chaque arête ? |
|
| Une société organise le transport de céréales des villes
vers les villes
. La disponibilité en tonnes des villes est de Les besoins en tonnes des villes sont de Le tableau suivant donne les capacités de transport, en tonnes, entre les villes : On a modélisé le problème par le graphe valué avec capacités suivantes. Déterminer les quantités à transporter de chaque ville d'origine vers chaque ville d'arrivée pour satisfaire au mieux la demande totale. |
|
| Arc | |
|---|---|
| Flot | |
| Capacité |
Cliquer sur les chaînes qui ne sont pas des chemins :
.
On se demande si le flot peut être amélioré en utilisant . Pour cela, on calcule pour chacun des arcs la capacité résiduelle :
Peut-on améliorer le flot à l'aide de ? si oui, de combien ? sinon répondre 0.
| Arc | |
|---|---|
| Flot | |
| Capacité |
Cliquer sur les chemins du graphe :
.
On se demande si le flot peut être amélioré en utilisant . Pour cela, on calcule pour chacun des arcs la capacité résiduelle :
Peut-on améliorer le flot à l'aide de ? si oui, de combien ? sinon répondre 0.
| Arc | |
|---|---|
| Flot | |
| Capacité |
L'arc Les arcs , a été saturé. ont été saturés. Il reste encore à examiner les arcs Il ne reste plus que l'arc à examiner.
L'arc est-il saturé ?
Répondre oui ou non. Saturez l'arc en donnant les nouvelles valeurs du flot :
| Arc | |
|---|---|
| Flot | |
| Capacité |
L'arc Les arcs , a été saturé. ont été saturés. Il reste encore à examiner les arcs Il ne reste plus que l'arc à examiner.
L'arc est-il saturé ?
Répondre oui ou non. Saturez l'arc en donnant les nouvelles valeurs du flot :
du flot valué de
à
représenté ci-dessous :
| Arc | |
|---|---|
| Flot | |
| Capacité |
| Arc | |
|---|---|
| Flot | |
| Capacité |
La capacité minimale des coupures est obtenue pour la coupure suivante (indiquer le sous-ensemble choisi contenant ) et vaut .
La valeur du flot maximal possible est de et le flot représenté
à condition de bien compléter les valeurs manquantes :
| Arc | |
|---|---|
| Flot | |
| Capacité |
à condition de bien compléter le tableau suivant :
| Arc | |
|---|---|
| Flot | |
| Capacité |
La valeur du flot est
.
The most recent version
Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.
Description: collection d'exercices sur la recherche de flot maximum. interactive exercises, online calculators and plotters, mathematical recreation and games
Keywords: interactive mathematics, interactive math, server side interactivity, operational_research, graph,algorithmics,informatics, maximum_flow, scheduling