Remerciez-le!

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

Optimisation dans les Réseaux - L3 RO A Page 1 USTHB, Faculté de Mathématiques

Optimisation dans les Réseaux - L3 RO A Page 1 USTHB, Faculté de Mathématiques Année 2000/2021 Optimisation dans les Réseaux L3 RO (A) Corrigé de l’exercice proposé en TD le 16.06.21 (Problème du flot maximum) Exercice Trouver le débit maximal de véhicules pouvant circuler de la ville s à la ville p dans le réseau routier suivant. 0(7) 0(7) 0(5) 0(10) 0(10) 0(8) 0(4) 0(10) 0(2) 0(6) 0(1) 0(2) 0(8) 0(2) 0(6) 0(4) 0 Appliquons l’algorithme de Ford & Fulkerson pour la recherche d’un flot maximum. D’abord, on rajoute l’arc de retour ur = (p, s) avec c(ur) = + Initialisation : On démarre du flot nul, i.e. f(u) = 0,  u  U  {ur}. Dans chaque itération de l’algorithme, on donnera P insaturée par le flot actuel. Cette chaîne forme avec ur un cycle . Le flot devient f :=f + f(ur) la nouvelle valeur du flot est f :=f + où  = min ( minu + (c(u)-f(ur)) ; min u - ( f( ur)) s f a b g d h e p Optimisation dans les Réseaux - L3 RO A Page 2 0(7) (5,7)(0,7) 0(7) (5,7) (7,7) 0(5) (5,5) 0(10) (5,10) 0(10) (5,10)(7,10)(9,10) 0(8)(5,8)(7,8) 0(4)(2,4) 0(10)(5,10) (7,10)(9,10) 0(2)(2,2) 0(6) (5,6) 0,1 0(2)(2,2) 0(8)(4,8) (6,8) 0(2)(2,2) 0(6)(4,6) (6,6) 0(4)(4,4) 0 5 10 12 14 18 20 Itération 1 : P1= s-a-b-f-p 1= P1 + ur  = min (5-0,7-0, 7-0 ,10-0) =5 1  =  ( circuit) f(ur) = 0 +  = 5 Itération 2 : P2= s-d-b-a-e-p 2= P2 + ur 2  = {(a,b)}  = min(10-0, 8-0,5,10-0,6-0) =5; f(ur):= f(ur)+5=10 Itération 3 : P3= s-d-b-f-p 3= P3 + ur 3  =   = min(10-5, 8-5, 7-5, 10-5)=2 f(ur) := 10 + 2 = 12 Itération 4 : P4= s-d-e-f-p 4= P4 + ur 4  =   = min(10-7, 2-0, 4-0, 10-7)=2 f(ur) = 12 + 2 = 14 Itération 5 : P5= s-g-h-p 5= P5 + ur 5  =   = min(8-0, 4-0, 6-0)=2 f(ur) = 14 + 4 = 18 Itération 6 : P6= s-g-e-h-p 6= P6 + ur 5  =   = min(8-4, 2-0, 2-0,6-4)=2 f(ur) = 18 + 2 = 20 Itération 7: L’ensemble des sommets marqués Y = {s, b, d, g}, p  Y (p ne peut être marqué, donc pas de chaine insaturée par le flot trouvé en it. 6). Stop. La valeur de flot maximum est f(ur) = 20. Donc le débit maximal de véhicules pouvant circuler de s à p est de 20 U.M. Vérification : Soit la coupe K = w+(Y) = {u  U / I(u)  Y, T(u)  Y} = {sa, bf, de, ge, gh} On a la capacité de la coupe K : c(K) = uK c(u) = 5 + 7 + 2 + 2 + 4 = 20 On a c(K*) = v(f*)=f(ur) = 20, donc on est bien à l’optimum : f est un flot maximum de s à p, et K est une coupe minimum séparant s de p (théorème de la dualité). s f a b g d h e p f(u) +  si u  + f(u): = f(u) -  si u  - f(u) sinon Optimisation dans les Réseaux - L3 RO A Page 3 Les résultats finaux sont résumés comme suit : 0(7) 7(7) 5(5) 5(10) 9(10) 7(8) 2(4) 9(10) 2(2) 5(6) 6(8) 0(1) 2(2) 2(2) 6(6) 4(4) - Les sommets en bleu sont les sommets marqués à la fin de l’algorithme ( Y). - Les arcs en bleu sont les arcs de la coupe minimum séparant p de s, ces arcs sont saturés i.e. f(u) = c(u)  u  K, ce qui empêche d’aller plus loin dans la procédure de marquage. - Les valeurs en rouge représentent le vecteur flot optimal (il existe d’autres solutions optimales). On vérifie bien à la fin la conservation du flot sur chaque sommet intermédiaire (autre que s et p). ________________________________________________________________________________ COMMENTAIRES ________________________________________________________________________________ Lors des évaluations, la rédaction de chaque itération de l’algorithme se fait comme suit : Itération k : Donner la chaîne insaturée par le flot et epsilon (sans les détails des soustractions, je l’ai fait ici pour pouvoir suivre) Dans le réseau cocher la valeur du flot d’un arc. Comme je viens de le faire. Citer le test d’arrêt : à la dernière itération donner Y où p n’y appartient pas. Bon courage. s f a b g d h e p uploads/Ingenierie_Lourd/ flot-max-exo-corr-td-16-06-21.pdf