close

Se connecter

Se connecter avec OpenID

20XX-XX.TD.td4.sujet.opti2015-12-26 21:3423 KB

IntégréTéléchargement
L3
TD4 - Optimisation et complexité
Exercice 1 : adduction d'eau (algorithme de Ford-Fulkerson), Roseaux, tome 1
Trois villes J, K, L sont alimentées en eau grâce à 4 réserves A, B, C, D (nappes
souterraines, châteaux d'eau, usines de traitement...). Les réserves journalières disponibles sont de
15 milliers de m3 par an pour A, de 10 pour B, de 15 pour C et de 15 pour D. Le réseau de
distribution peut être schématisé par le graphe ci-dessous (les débits maximaux sont indiqués sur
chaque arc en milliers de m3 par jour) :
[7]
A
[5]
[5]
C
[30]
[15]
L
[5]
[7]
D
K
[7]
F
[10]
[10]
H
[15]
[5]
B
[10]
I
G
J
[7]
[4]
E
[4]
[15]
Ces 3 villes en pleine évolution désirent améliorer leur réseau d'alimentation afin de
satisfaire des besoins futurs plus importants. Une étude a été faite et a permis de déterminer les
demandes journalières maximales probables, à savoir 15 milliers de m3 pour la ville J, 20 pour la
ville K et 15 pour la ville L.
1. Déterminer la valeur du flot maximal pouvant passer dans le réseau actuel. On partira du flot au
jugé indiqué sur la feuille.
2. La valeur de ce flot est jugée nettement insuffisante, aussi le conseil intercommunal décide t-il de
refaire les canalisations (A,E) et (I,L). Déterminer les capacités à prévoir pour ces 2 canalisations
et la valeur du nouveau flot optimal.
3. Devant l'importance des travaux, le conseil intercommunal décide de ne pas refaire les 2
canalisations en même temps. Dans quel ordre doit-on entreprendre leur réfection de façon à
augmenter, après chaque tranche de travaux, la valeur du flot optimal passant dans le réseau ?
4. Quelles sont, après chaque tranche de travaux, les valeurs des flots optimaux.
flot au jugé :
7 [7]
A
5 [15]
E
0 [5]
2 [5]
O
7 [10]
3 [15]
F
10 [15]
3 [10]
C
5 [15]
4 [15]
L
I
7 [7]
D
4 [4]
12 [15]
G
5 [10]
S
16 [30]
8 [15]
0 [5]
10 [20]
K
3 [7]
13 [15]
6 [10]
H
5 [5]
B
J
7 [7]
4 [4]
flot complet :
[7]
A
E
[15]
[10]
O
[5]
[5]
H
[15]
[7]
[10]
C
[15]
L
I
[7]
D
[4]
[15]
G
[10]
S
[30]
[15]
[5]
[15]
[20]
K
F
[15]
[10]
[15]
[5]
B
J
[7]
[4]
flot maximal :
[7]
A
E
[15]
O
[5]
[5]
[10]
B
H
F
[15]
[10]
C
[15]
L
I
[7]
D
[4]
[15]
G
[10]
S
[30]
[15]
[5]
[15]
[20]
K
[7]
[15]
[10]
[15]
[5]
J
[7]
[4]
modification du flot :
[ ]
A
E
[15]
O
[10]
[5]
[5]
B
H
F
[15]
[10]
C
[15]
[5]
D
[10]
[15]
L
I
G
[30]
[15]
[7]
[15]
[20]
K
[7]
[15]
[10]
[15]
[5]
J
[7]
[4]
[ ]
S
Auteur
Документ
Catégorie
Без категории
Affichages
13
Taille du fichier
22 Кб
Étiquettes
1/--Pages
signaler