Remerciez-le!

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

Le problème du flot maximal/exercices/corrigé/p1 Le problème du flot maximal– E

Le problème du flot maximal/exercices/corrigé/p1 Le problème du flot maximal– Exercices -corrigé I Déterminer sur le réseau suivant, .......(reprendre le graphe sur l'énoncé) On procède successivement aux marquages suivants : (d'autres suites sont possibles, ici on prend systématiquement le premier sommet susceptible d'être marqué) Première itération de l'algorithme de Ford Fulkerson : Procédure de marquage : s+ a+ b+ e- (car le flux sur (e,b) est >0) c+ f + p+ : p est marqué. Modification du flot : ε+ = 2 (arc (a,b)) ε- = 1 (arc (e,b) ) ; on peut donc envoyer un flot de valeur 1 le long de la chaîne s a b e c f p : le flux augmente de 1 sur tous les arcs sauf sur (e,b) où il diminue de 1. La valeur du flot passe à 39. s p u0 (10) (10) (10) (10) (20) (20) (20) (5) (18) (15) (3)3 (15) (2) (2) (4) (9) (8) (30) (8) (10) (4) a b c d e f g h i 7 3 4 1 4 20 13 10 4 10 2 8 10 11 8 10 20 10 38 0 0 + + + - + + +1 +1 -1 +1 +1 +1 +1 + Deuxième itération Procédure de marquage : s + a+ b+ , on ne peut aller plus loin ; on repart de s. On marque alors g+ h + d- e + c+ f+ p+ . p est marqué. Modification du flot : ε+ = 4 (arc (e,c) ε- = 10 (arc (d,h) ) on peut donc envoyer un flot de 4 le long de la chaîne s g h d e c f p : le flux augmente de 4 sur tous les arcs sauf sur (d ,h) où il diminue de 4. La valeur du flot passe à 43. Le problème du flot maximal/exercices/corrigé/p2 s p u0 (10) (10) (10) (10) (20) (20) (20) (5) (18) (15) (3)3 (15) (2) (2) (4) (9) (8) (30) (8) (10) (4) a b c d e f g h i 7 3 4 1 4 20 13 10 4 10 2 8 10 11 8 10 20 10 38 0 0 + + + - + + +1 +1 -1 +1 +1 +1 + + +4 +4 -4 +4 +4 +4 +4 +4 +1 Troisième itération Procédure de marquage : s+ a + b+ puis à nouveau à partir de s : g+ h+ d- e + on ne peut rien marquer d'autres, le flot est maximal. s p u0 (10) (10) (10) (10) (20) (20) (20) (5) (18) (15) (3)3 (15) (2) (2) (4) (9) (8) (30) (8) (10) (4) a b c d e f g h i 7 3 4 1 4 20 13 10 4 10 2 8 10 11 8 10 20 10 38 0 0 + + + - +1 +1 -1 +1 +1 +1 + +4 +4 -4 +4 +4 +4 +4 +4 + + +1 L'ensemble des sommets marqués est { s, a , b , d , e , g , h} La coupe associée est constituée des arcs dont l'origine est marquée et l'extrémité non marquée : (b,c) (e,c) (e,f) (h, f) (h, i) . La capacité de cette coupe est : 4 + 9 +10 + 10 = 10 = 43 Ceci confirme que le flot précédent est optimal. Le problème du flot maximal/exercices/corrigé/p3 II Une raffinerie de pétrole........ a) On complète le graphe par une "supersource" s et les arcs (s,S1) , (s,S2) , (s,S3) que l'on munit d'une capacité supérieure égale à la quantité qui peut être délivrée par chacun des puits. La conservation des flux aux sommets S1, S2, S3 permet de limiter ce qui part de chacun des puits à ce qu'ils peuvent fournir. S1 S2 S3 T1 T2 T3 T4 T5 R (raffinerie) (3000) 3000 (2000) 2000 (2000) 0 (1000) 1000 (1000) 1000 (2000) 2000 (3000) 1000 (2000) 1000 (2000) 2000 (1500) 1000 (1000) 1000 2000 (4000) 4000 (7000) 6000 (8000) 1000 (3000) s p (5000) (4000) (3000) 3000 3000 2000 8000 Actuellement il arrive une quantité de 8000 à la raffinerie. Pour voir si cette quantité est maximale, on recherche s'il existe une chaîne améliorante qui permettrait d'augmenter la valeur du flot. Marquage 1 : s, S1, S2 , S3 (-) , T3, T2, T5, p . Le long de cette chaîne on peut envoyer un flot de 500, la limitation est due à l'arc (T2,T5). S1 S2 S3 T1 T2 T3 T4 T5 R (raffinerie) (3000) 3000 (2000) 2000 (2000) 0 (1000) 1000 (1000) 1000 (2000) 2000 (3000) 1000 (2000) 1000 (2000) 2000 (1500) 1000 (1000) 1000 2000 (4000) 4000 (7000) 6000 (8000) 1000 (3000) s p (5000) (4000) (3000) 3000 3000 2000 8000 -500 +500 +500 +500 +500 +500 +500 +500 + + + - + + + + Le problème du flot maximal/exercices/corrigé/p4 Marquage 2 s, S1, S2, S3(-), T3, T2, T1 (-), T4, p Le long de cette chaîne on peut envoyer un flot de 1000, la limitation est due à l'arc (T1,T2) sur lequel le flux ne peut pas diminuer de plus de 1000. S1 S2 S3 T1 T2 T3 T4 T5 R (raffinerie) (3000) 3000 (2000) 2000 (2000) 0 (1000) 1000 (1000) 1000 (2000) 2000 (3000) 1000 (2000) 1000 (2000) 2000 (1500) 1000 (1000) 1000 2000 (4000) 4000 (7000) 6000 (8000) 1000 (3000) s p (5000) (4000) (3000) 3000 3000 2000 8000 -500 +500 +500 +500 +500 +500 +500 +500 -1000 +1000 +1000 +1000 +1000 +1000 +1000 +1000 -1000 + + + - + + _ + + Marquage 3 s, S1, S2, S3,T3, T2 .... et c'est tout. Arcs de la coupe (S1,T1) (S2,T1) (T2,T4) (T2,T5) (T3,T5) Capacité = 3000 + 2000 + 2000 + 1500 + 1000 = 9 500 S1 S2 S3 T1 T2 T3 T4 T5 (3000) 3000 (2000) 2000 (2000) 0 (1000) 1000 (1000) 1000 (2000) 2000 (3000) 1000 (2000) 1000 (2000) 2000 (1500) 1000 (1000) 1000 2000 (4000) 4000 (7000) 6000 (8000) 1000 (3000) s p (5000) (4000) (3000) 3000 3000 2000 8000 -500 +500 +500 +500 +500 +500 +500 +500 -1000 +1000 +1000 +1000 +1000 +1000 +1000 +1000 -1000 b) Afin d'augmenter encore cette quantité, doit-on augmenter la capacité des sources, ou celle de certains éléments de pipe-line? Dans l'un ou l'autre cas préciser lesquels. Pour augmenter la quantité envoyée à la raffinerie, il faut impérativement augmenter la capacité d'au moins un des arcs de cette coupe. Le problème du flot maximal/exercices/corrigé/p5 III Cet exercice correspond à un problème connu sous le nom de " La promenade des demoiselles". Le responsable d’un ......... a) Ce problème peut être modélisé par un problème de flot maximal sur le graphe suivant : justifier ce résultat. Compte tenu de la contrainte de capacité supérieure de 1 sur les arcs (s,Gi) et (Fj,p) et de la conservation des flux aux sommets Gi et Fj un flot sur le graphe précédent est tel que le flux ne peut être égal à 1 que sur un seul arc issu de chaque sommet Gi et sur un seul arc d’extrémité Fj : on pourra donc associer à un arc (Gi,Fj) sur lequel le flux vaut 1 un couple (Gi,Fj). Pour avoir le maximum de couples il faut donc déterminer le nombre maximum d’arcs sur lequel le flux vaudra 1. Ce nombre d’arcs est comptabilisé sur l’arc de retour. Il s’agit donc de déterminer le flot maximal sur le réseau proposé. b) Le responsable du ......... *s p G1 G2 G3 G4 G5 F1 F2 F3 F4 F5 (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) 1 1 1 1 1 1 1 1 3 1 * * * * * +1 +1 -1 +1 +1 +1 @ @ @ @ @ @ @ @ Les arcs de type (s,i) et (j,p) sont munis de capacité supérieure égale à 1 (entre parenthèses sur le graphe) et inférieure nulle. Les arcs (i,j) sont uniquement munis de capacité inférieure nulle. Les seuls flux mentionnés sur ce graphique sont les flux non nuls. Initialement le flux est égal à 1 sur les arcs (s,G1) (s,G2) et (s,G3) , (G1,F1) ,(G2,F2) ,(G3,F4) , (F1,p) (F2,p) (F4,p) . Il a pour valeur 3 et représente la situation actuelle. Pour voir si on peut constituer d'autres couples on cherche à augmenter ce flot. L'application de l'algorithme de Ford Fulkerson conduit à deux itérations correspondant aux marquages indiqués sur le graphe par : * = premier marquage @ = deuxième marquage On procède au marquage des sommets : Premier marquage : s , G4 ,F1 , G1( marquage à partir de F1 possible car le flux est égal à 1) ,F3 , p p étant marqué on a mis en évidence une chaîne augmentante à partir de laquelle on peut augmenter le flot de 1 : augmentation de 1 sur (s,G4) (G4,F1) (G3 , p ) et l’arc (p , s) et diminution de 1 sur (G1, F1) . La uploads/s1/ cor-exercice-s-6.pdf