Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Exercice supplémentaire On considère un réseau d’adduction d’eau potable modéli

Exercice supplémentaire On considère un réseau d’adduction d’eau potable modélisé par le graphe orienté valué G = (X, U, C) suivant : Les arcs correspondent à des conduites d’eau, et les valeurs sur les arcs désignent les capacités en m3/heure. Le nœud 1 correspond à une source limitée à 10 m3/heure, et le nœud 2 à une station de pompage dans un fleuve, limitée à 15 m3/heure. Les nœuds 6, 7 et 8 correspondent à 3 villes dont les demandes respectives sont de 9, 10 et 6 m3/heure. A cause de la gravité, l’écoulement entre deux nœuds se fait dans un seul sens, sauf entre les nœuds 3 et 5 où une pompe permet, si nécessaire, de ramener de l’eau du nœud 5 au nœud 3. a. Déterminer un flot de débit maximal dans ce réseau en expliquant les différentes étapes de la méthode utilisée. Le réseau suffira-t-il à satisfaire les besoins des 3 villes 6, 7 et 8 ? b. Donner la coupe minimale. c. Quelles sont les conduites qui doivent être élargies pour augmenter le débit ? Justifier. d. On crée une conduite du nœud 4 au nœud 7 de capacité 5 m3/heure. Que devient le flot maximal ? NB : continuer le calcul à partir du flot maximal trouvé en (a). Corrigé Pour tenir compte des capacités des sources 1 et 2 et des demandes des villes 6, 7 et 8, on ajoute une super source et un super puits comme le montre le graphe suivant : a. La solution optimale est donnée par le graphe suivant où sur chaque arc, la première indique la capacité de l’arc et la deuxième valeur indique la quantité de flot à faire passer à travers cet arc. φ* = 24. Le graphe d’écart associé à cette solution est le suivant : Le réseau ne suffira pas à satisfaire les besoins des 3 villes 6, 7 et 8 puisque le flot maximal est inférieur à la demande totale (9 + 10 + 6 = 25 > 24) b. La coupe minimale est la suivante XS = {S, 1, 2, 3, 4} c. Les conduites à élargir pour augmenter le débit sont (3,6), (3,5), (4,5) et (4,8) car elles appartiennent à la coupe minimale. d. La solution optimale devient : φ* = 25. uploads/Geographie/ flot-exercice-supplementaire 1 .pdf