Court Flot Maximal [PDF]

Zitiervorschau

PROBLEME DU FLOT MAXIMAL

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

1 / 172

Les ‡ots permettent de modéliser une très large classe de problèmes. Leur interprétation correspond à la circulation de ‡ux physiques sur un réseau : distribution électrique, réseau d’adduction, acheminement de paquets sur Internet, ... Il s’agit d’acheminer la plus grande quantité possible de matière entre une source s et une destination t. Les liens permettant d’acheminer les ‡ux ont une capacité limitée, et il n’y a ni perte ni création de matière lors de l’acheminement : pour chaque noeud intermédiaire du réseau, le ‡ux entrant (ce qui arrive) doit être égal au ‡ux sortant (ce qui repart).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

2 / 172

Exemples de modélisation par des graphes liés au ‡ot:

De nombreux problèmes relatifs à l’étude des ‡ots dans les réseaux pourront donc être résolus par la théorie des graphes : -réseaux aériens (entre aéroports) -réseaux ferroviaires (entre gares) -réseaux routiers: les sommets sont les intersections des routes, les aretes représentent les routes. -réseaux téléphoniques, informatiques, ... -cheminement dans un réseau informatique . -Web modelisé par un graphe. Les sommets sont les pages Web et les aretes sont les liens hypertexte entre ces di¤erentes pages.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

3 / 172

L’histoire du ‡ot maximal: Intuitivement cela fait référence aux problèmes de plomberie ou de tra…c routier. On distingue sur le graphe des types de noeuds di¤érents: deux sommets particuliers : une source s et une destination t. Les autres sommets sont les noeuds intermédiaires du réseau. On dispose d’une source (noued de dépard) et d’un puits (noued d’arrivée) et le ‡ot doit s’écouler de la source vers le puits et il doit être maximum en fonction de la capacité des arcs.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

4 / 172

Variantes ( à titre de rappel) Graphe non orienté : on remplace chaque arete par deux aretes orientés (une dans chaque sens). Plusieurs sources (ou puits) : on crée une super-source virtuelle (super-puit virtuel), avec capacité in…nie vers toutes les sources (depuis tous les puits). On peut ajouter des couts (unitaires par aretes), et rechercher un ‡ot maximal de moindre cout.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

5 / 172

Dé…nition (réseau): ! ( G , c, s, t ) est un réseau ssi ! G est un graphe orienté connexe sans boucle; ce graphe est valué: chaque arc (u, v ) du graphe a une capacité c (u, v ); la source s de degré entrant nul; et, le puit t de degré sortant nul.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

6 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

7 / 172

Remarquer: -ce qui entre est égal à ce qui sort pour chaque noeud. (compter pour s’assurer). -ce qui entre dans le réseau par s est récupéré à la …n par t

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

8 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

9 / 172

Autre dé…nition possible: (avec capacités inf & sup et arc st retour) Un graphe G = (X , U ) est un réseau si : - il est connexe, - il possède deux sommets particuliers s et p appelés source et puits. - les arcs sont munis de capacités inférieures bu et supérieures cu avec bu c u - l’arc (p, s ) existe. Il est appelé arc de retour et noté u0 .

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

10 / 172

R«eseau : (dé…nition de précision) Un réseau est un graphe orienté N = (V , A) avec une valuation positive de ses arcs. La valuation c (x, y ) d’un arc (x, y ) est appelée la capacité de l’arc. On distingue sur N deux sommets particuliers : une source s et une destination t. Les autres sommets sont les noeuds intermédiaires du réseau. Le choix d’une source et d’une destination est arbitraire et dépend simplement du problème que nous avons à traiter sur le réseau.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

11 / 172

Exemple: de réseau. Le réseau comporte 5 noeuds intermédiaires. La capacité de l’arc (c, e ) est de 2, celle de l’arc (e, t ) est de 4

Remarque: Nous pouvons supposer que tous les arcs (x, y ) entre 2 sommets sont présents dans le réseau. Si un arc est absent, il est en e¤et possible de le rajouter en lui attribuant une capacité nulle sans changer le problème du LST IGI GISeuls () problème du ‡ot maximal May 25, 2012 12 / 172 ‡ot CHERTI maximum. les arcs de capacité non nulle seront représentés sur

Vocabulaire Flot... Un ‡ot représente l’acheminement d’un ‡ux de matière depuis une source s vers une destination t. Le ‡ot est ainsi décrit par la quantité de matière transitant sur chacun des arcs du réseau. Cette quantité doit être inférieure à la capacité de l’arc, qui limite ainsi le ‡ux pouvant transiter par lui. De plus il n’est pas possible de stocker ou de produire de la matière aux noeud intermédiaires : un ‡ot véri…e localement une loi de conservation analogue aux lois de Kirsho¤ en électricité.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

13 / 172

Les réseaux de transports. Réseau de transport : graphe orienté avec pour chaque arc une capacité. La capacité c (u, v ) est un entier positif ou nul. Il y a aussi une source s et un puits t. Aucun arc n’arrive à la source et aucun arc ne quitte le puits. Un ‡ot est une fonction entière positive ou nulle f dé…nie sur les arcs satisfaisant : Contrainte de capacité : f (u, v ) c (u, v ) ; Symétrie : f (u, v ) = f (v , u ) ; Conservation du ‡ot : pour tout sommet autre que s et t, la somme des ‡ots sur les arcs entrants et la somme des ‡ots sur les arcs sortants sont égales ("Loi de Kirchho¤"). Exemples : circuits électriques ou hydrauliques, réseaux de communication, modélisation de transports. Le choix d’une source et d’une destination est arbitraire et dépend simplement du problème que nous avons à traiter sur le réseau. CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

14 / 172

Dé…nition (‡ot à travers un réseau) Un ‡ot est une fonction f : E (V ) ! R qui véri…e la loi des noeuds: (( ce qui rentre égal ce qui sort )). Conservation du ‡ux: Loi de Kirchho¤ (1847, circuits électriques) Dé…nition plus détaillée: Flot Un ‡ot F sur un réseau N = (V , A) est une valuation positive des arcs, c’est à dire une application de A dans R + , qui véri…e les deux propriétés suivantes : 1. Pour tout arc a 2 A, 0 F (a ) c (a ). 2. Pour tout sommet intermédiaire x 2 V nfs, t g, ∑ F (y , x ) = ∑ F (x, y ) y

CHERTI LST IGI GI ()

y

problème du ‡ot maximal

May 25, 2012

15 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

16 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

17 / 172

Réseau de transport:

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

18 / 172

Exemple de réseau de transport avec les capacités:

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

19 / 172

Un ‡ot sur le réseau de transport:

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

20 / 172

Exemple: Réseau avec ses capacités

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

21 / 172

la valeur du ‡ot sur chaque arc est inférieure à la valeur de la capacité la loi de Kirchho¤ est véri…ée en chaque sommet. la valeur du ‡ot est égale à : 11 (le ‡ot entre par trois aretes sortantes de S et resort par trois aretes entrantes en P)

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

22 / 172

Un exemple de ‡ot sur notre réseau. Le ‡ot entrant en b a une valeur de 3. La valeur du ‡ot est dé…nie comme le ‡ux net sortant de s ou entrant dans t. Sur cet exemple le ‡ot a une valeur de 2.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

23 / 172

Dé…nition: Flot Maximum (MaxFlow): La somme F (x ) = ∑ F (y , x ) est le ‡ot entrant au sommet x. y

La somme F + (x ) = ∑ F (x, y ) est le ‡ot sortant du sommet x. y

La valeur jF j d’un ‡ot F est dé…nie comme le ‡ot sortant moins le ‡ot entrant en s : jF j = F + (s ) F (s ) Le problème du Flot Maximum consiste à trouver un ‡ot Fmax de valeur maximale sur le réseau N.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

24 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

25 / 172

Par Dé…nition (Flot réalisable): Si pour tout arc la valeur du ‡ot est inférieure ou égale à la capacité de l’arc alors on dit que le ‡ot est réalisable. Dé…nition (valeur du ‡ot): On ajoute un arc de retour (…ctif) depuis t vers s. On dé…nit alors la valeur du ‡ot comme celle du ‡ux qui passe par cet arc …ctif.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

26 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

27 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

28 / 172

Flot dans un graphe. Problèmes de circulation d’objets (voiture, information ...) dans un réseau (routier, informatique ...). Dé…nition: Soit G = (S, U, C ) un graphe valué comportant un seul sommet source s et un seul sommet puits t. S : les sommets du graphe. U :les arcs du graphe. C : les valuations des arcs (ici les capacités) Un ‡ot de s à t est une fonction f : U ! R telle que: ∑ f (i, j ) =

i 2P (j )

CHERTI LST IGI GI ()

∑ f (j, k )

k 2S (j )

problème du ‡ot maximal

May 25, 2012

29 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

30 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

31 / 172

Notre premier essai d’optimisation locale, l’algorithme Saturation, avait en fait tout d’un algorithme glouton : la saturation d’un chemin n’est jamais remise en cause, le ‡ot sur un arc ne peut qu’augmenter au cours de l’algorithme. Pour éviter l’approche gloutonne, il nous faut être capable non seulement d’augmenter, mais aussi de diminuer la valeur du ‡ot sur un arc (x, y ). Une solution serait de faire transiter un ‡ot négatif sur (x, y ).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

32 / 172

Cependant nous avons dé…ni un ‡ot comme une valuation positive des arcs, correspondant à un transit de matière. Pour faire diminuer par exemple de 1 le ‡ot sur l’arc (x, y ), nous faisons passer un ‡ot de 1 dans l’autre sens, sur l’arc (y , x ). En terme de bilan de matière, si un ‡ot de 3 transite sur (x, y ) et un ‡ot de 1 sur (y , x ), cela revient en e¤et à n’acheminer qu’un ‡ot de 2 de x à y . Cependant l’arc (y , x ) peut ne pas exister,... ou être déjà saturé par le ‡ot. Aussi allons nous changer de réseau : nous associons à un ‡ot F sur un réseau N le réseau résiduel NF composé d’arcs forward (avant) et backward (arrière) .

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

33 / 172

A un arc (x, y ) du réseau N est associé dans le réseau résiduel NF l’arc forward noté de capacité c (x, y ) F (x, y ) La capacité de l’arc forward traduit que l’on peut encore augmenter le ‡ot F sur (x, y ), d’au plus c (x, y ) F (x, y ) qui correspond à la saturation de l’arc. Un arc forward "existe" (il est de capacité non nulle) donc dans NF si et seulement si il n’est pas saturé dans N.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

34 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

35 / 172

A un arc (x, y ) du réseau N est associé dans le réseau résiduel NF l’arc backward noté de capacité F (x, y ). La capacité de l’arc backward traduit que l’on peut diminuer lavaleur du ‡ot F allant de x à y , d’au plus F (x, y ) qui correspond à annuler le ‡ot. Un arc backward "existe" (il est de capacité non nulle) donc dans NF si et seulement si le ‡ot F n’est pas nulle sur l’arc (x, y ). Réseau résiduel.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

36 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

37 / 172

Dé…nition: Réseau résiduel.

!

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

38 / 172

Reprenons l’exemple du ‡ot F sur le réseau N. Les capacités sont représentées dans les carrés à coté des arcs; les valeurs du ‡ot apparaissent en orange.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

39 / 172

Le réseau résiduel associé à F est représenté ci contre. Les arcs forward apparaissent en gris, les arcs backward sont en bleu. Les arcs de capacité nulle n’ont pas été représentés.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

40 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

41 / 172

Dans le réseau N, l’arc (s, a) est saturé : seul apparaît dans le réseau résiduel son arc backward (a, s ), de capacité 1 (capacité de l’arc d’origine). Dans le réseau N, aucun ‡ot ne passe par l’arc (s, c ) : seul apparaît dans le réseau résiduel l’arc forward (s, c ), de capacité 1 (capacité de l’arc d’origine) En…n prenons l’exemple de l’arc (d, t ). Sa capacité est de 5 dans le réseau N et un ‡ot de 3 y circule. Dans le réseau résiduel lui sont alors associés :

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

42 / 172

La coupe: Quand deux arcs en sens inverse relient deux sommets, on peut toujours annuler la fonction ‡ot sur l’un des deux.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

43 / 172

la somme des ‡ots sur les arcs sortant de la source et la somme des ‡ots sur les arcs arrivant au puits sont égales ; cette valeur est la valeur du ‡ot jf j ; si on sépare les sommets en deux sous-ensembles E contenant s et F = A E contenant t, alors la somme des valeurs du ‡ot sur les arcs de E vers F moins la somme des valeurs du ‡ot sur les arcs de F vers E vaut aussi jf j. Exemple: réseau de deux groupes de banques et déplacement des fonds d’argent dans ce réseau...

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

44 / 172

Une telle séparation en deux sous ensembles des sommets est appelée une coupe et cette di¤érence de sommes de ‡ots est appelée ‡ot net traversant la coupe. ————— La capacité de la coupe est égale à la somme des capacités des arcs qui ont une origine dans C et une extrémité dans S /C . c (C , S /C ) = ∑

∑ cij

i 2C j 2S /C

avec cij la capacité de l’arc ij. _________

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

45 / 172

Dé…nition théorique de la Coupe: Une coupe du graphe G est une partition des sommets : (C , S nC ), avec le source s dans C , et le puit t dans S nC . En bref on parle de la coupe C . Une arete sortante deC est une arete (u, v ) avec u 2 C et v2 / C. La capacité de la coupe est la somme des capacités des aretes sortantes : elle majore le ‡ot.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

46 / 172

Encore plus: Coupe Soit G = (S; A), et R = (G ; c; s; p ), une coupe est une e , tels que : partition de S en deux ensembles V et V e =S V [V e s 2 V et p 2 V la capacité de la coupe est égale à la somme des capacités des arcs qui font la coupe.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

47 / 172

Enoncé du problème. Recherche du Flot maximum. Le support: un graphe orienté G = (S; A) dont chaque arête est valuée par une capacité, un sommet source et un sommet puits. Quel est le ‡ot maximum qu’il est possible de faire passer dans ce réseau depuis la source vers le puits ?

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

48 / 172

Connectivité. Pour un graphe connexe, la connectivité est dé…nie comme le nombre minimum de sommets dont la suppression entraîne la perte de connexité. Théorème de Menger (1927) : Pour deux sommets non adjacents quelconques d’un graphe connexe G , le nombre minimum d’arêtes dont la suppression entraîne leur déconnexion est égal au nombre maximum de chaînes deux-à-deux arêtes disjointes les connectant dans G . -

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

49 / 172

Ce résultat a été re-formulé en termes de réseaux en 1956 par Ford et Fulkerson et est connu sous le nom de théorème maximum ‡ow/minimum cut ou max ‡ow-min cut.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

50 / 172

Max Flow/Min Cut Pour comprendre intuitivement le rapport entre le théorème de Menger et le ‡ot maximum considérons un réseau de transport dont les capacités sont des nombres entiers, et le réseau de transport équivalent au premier mais dont tous les arcs sont dupliqués autant de fois que la valeur de la capacité du réseau d’origine. Tous les arcs du nouveau réseau de transport sont de capacité unitaire.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

51 / 172

Dans ce nouveau réseau, le ‡ot maximum entre la source et le puits est égal au nombre maximum de chemins deux-à-deux arêtes disjointes permettant de relier la source au puits. la suppression sur chacun de ces chemins d’un arc constitue une coupe. Ce nombre est le nombre minimum d’arcs qu’il est possible de supprimer pour obtenir une coupe puisqu’il est égal au nombre de chemins indépendants permettant de lier la source au puits.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

52 / 172

Max Flow/Min Cut. C’est des capacités...

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

53 / 172

Pour mieux visualiser

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

54 / 172

Propriété: (ni min ni max) La capacité de toute coupe est supérieur ou égale à la valeur de tout ‡ot. Coupe minimal-‡ot maximal: Théorème : Un ‡ot est maximal si et seulement s’il est égal à la capacité d’une coupe. Le ‡ot maximal est donc égal à la coupe minimale. Preuve : un ‡ot qui sature la capacité d’une coupe est maximal. Il reste à voir qu’un tel ‡ot existe (et à le construire).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

55 / 172

Graphe résiduel et coupe: Etant donné un ‡ot f , à chaque arete a = (u, v ) on associe : la capacité résiduelle avant r + (a ) = c (a )

f (a )

, et la capacité résiduelle arrière r

(a ) = f (a )

.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

56 / 172

Le graphe d’écart est constitué avec les aretes a = (i, j ) de capacité résiduelle avant non nulle, complété avec les aretes opposées a = (j, i ) lorsque la capacité résiduelle arrière est non nulle. Un chemin augmentant est un chemin de s à t sur le graphe d’écart.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

57 / 172

Etant donné un chemin augmentant on peut améliorer le ‡ot en changeant chaque arete du chemin augmentant de la valeur minimale des capacités résiduelles le long du chemin (en plus ou en moins suivant qu’on emprunte l’arete en avant ou en arrière. S’il n’existe pas de chemin augmentant, alors il existe une coupe de capacité égale au ‡ot (coupe saturée).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

58 / 172

Exemple:

Voici une chaîne augmentante de A à E faisant partie d’un réseau de transport.

Dans cette chaîne, on peut augmenter le ‡ot de: 3 entre A et B,(sens direct: on prends la capacité moins le ‡ot) 2 entre B et C,(///) 1 entre C et D,(car sens contraire: on prends le ‡ot) 5 entre D et E.(sens direct) On augmentera donc de 1 le ‡ot dans cette chaîne. Ce qui signi…e: CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

59 / 172

augmenter de 1 le ‡ot entre A et B, augmenter de 1 le ‡ot entre B et C, diminuer de 1 le ‡ot entre D et C, augmenter de 1 le ‡ot entre D et E.

On remarque que pour les arcs en sens inverse, augmenter le ‡ot signi…e réduire le ‡ot dans le sens direct. Entre D et C , le ‡ot est réduit de 1 pour permettre l’arrivée d’une unité de ‡ot sur C par B tout en conservant l’équilibre du noeud. D ayant une unité de trop, son équilibre n’est pas respecté. C’est pourquoi une unité de ‡ot supplémentaire circule entre D et E .

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

60 / 172

Exemple: Augmenter le ‡ot.

un réseau de transport ou circule un ‡ot

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

61 / 172

Le graphe d’écart correspondant:

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

62 / 172

(A, B, C , D, F , G ) est un chemin pour aller de A à G . On peut augmenter le ‡ot de: 2 entre A et B, 3 entre B et C, 1 entre C et D, 4 entre D et F, 2 entre F et G.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

63 / 172

On augmentera donc le ‡ot de 1 sur ce chemin, ce qui signi…e: -augmenter de 1 entre A et B, -réduire de 1 entre C et B, -augmenter de 1 entre C et D, -augmenter de 1 entre D et F, -augmenter de 1 entre F et G.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

64 / 172

On remarque que le chemin (A, B, C , D, F , G ) trouvé correspondait à la chaîne augmentante (A, B, C , D, F , G ).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

65 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

66 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

67 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

68 / 172

pour tout sommet j 6= s, t. On dit qu’il y a conservation du ‡ux au sommet j ("ce qui rentre egale ce qui sort"). def

La valeur fij = f (i; j ) est le ‡ot dans l’arete (i; j ).

Notons Bien: La valeur du ‡ot est égale à la somme des ‡ots sortants de s.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

69 / 172

Exemple:

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

70 / 172

Une dé…nition: Un ‡ot saturé est un ‡ot tel que sur tout chemin de s à t il existe un arc ayant un ‡ot égal à sa capacité. Sur le meme graphe : Un ‡ot saturé non maximal

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

71 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

72 / 172

Flot maximal ? Descriptif du problème à traiter: Les données: un réseau ( à capacité biensur) Le but à réaliser: trouver un ‡ot réalisable maximal (dont la valeur est maximale). Outils de traitement: Algorithme de Ford-Fulkerson (1956)

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

73 / 172

Principe: Procéder par marquage successifs des sommets depuis la source vers le puit. On traite chaque sommet u marqué successivement. On marque tout successeur positivement si l’arc n’est pas à pleine capacité et tout prédécesseur négativement si l’arc a un ‡ux non nul. Ceci permet de trouver des chemins augmentant.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

74 / 172

la recherche d’un ‡ot maximal. On se donne une capacité maximale sur chaque arc qui sera une borne supérieure du ‡ot autorisé sur cet arc. Le problème du ‡ot maximal consiste à déterminer un ‡ot dont la valeur en un certain "lieu" est maximale. On peut, de plus, se donner un cout de transport d’une unité de ‡ot sur chaque arc et chercher le ‡ot maximal de cout minimal. Problème de ‡ot maximal dans un graphe. On veut par exemple trouver le tra…c maximal entre deux villes d’un réseau routier dont on connait la capacité (nombre de voiture par heure sur chaque troncon)

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

75 / 172

Max V ?

Problème de ‡ot maximal: Etant donné un graphe valué possédant une seule source et un seul puits , trouver un ‡ot réalisable maximal (i.e. dont la valeur est maximale). Flot maximal et programmation linéaire:

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

76 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

77 / 172

Remarque :les inconnues sont les fij et la valeur V du ‡ot.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

78 / 172

Dé…nition: On appelle réseau de transport un graphe orienté antisymétrique valué G = (X ; A; C ),sans boucle et dans lequel il existe : -un sommet x1 sans prédécesseur (Γ 1 (x1 ) = ?) nommé entrée ou source du réseau, -un sommet xn sans successeur (Γ (xn ) = ?) nommé sortie ou puits du réseau, et tel qu’au moins un chemin unisse x1 a xn dans G . La fonction de pondération C est supposée positive et l’on nomme capacité de l’arc a le nombre C (a).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

79 / 172

DEFINITION D’UN FLOT: Soit Ax l’ensemble des arcs sortants du sommet x et Ax+ l’ensemble des arcs entrants de ce meme sommet x, on dit qu’une fonction ϕ(a) dé…nie sur A (ensemble des arcs) et à valeurs réelles est un ‡ot pour le réseau de transport si : – ϕ(a) 0, 8a 2 A, – il véri…e la loi des noeuds de Kirchho¤ : (ce qui entre égal ce qui sort en un noeud). 8x 6= x1 et x 6= xn ∑ ϕ (a ) ∑ ϕ (a ) = 0 a 2A x

a 2A x+

– il ne dépasse pas la capacité des arcs : ϕ(a)

CHERTI LST IGI GI ()

problème du ‡ot maximal

C (a), 8a 2 A.

May 25, 2012

80 / 172

Pour un ‡ot ϕ dans un réseau de transport G = (X , A, C ), on dit qu’un arc est saturé si on a ϕ(a) = C (a). Le ‡ot est dit complet si tout chemin allant de x1 à xn contient au moins un arc saturé.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

81 / 172

Remarque: Pour un réseau de transport donné on peut déterminer un ‡ot de valeur maximale ainsi que les ‡ots le long de chaque arc. Il arrive fréquemment que l’on doive considérer des réseaux avec des capacités localisées non seulement sur les arétes mais également sur les sommets. C’est notamment le cas pour les réseaux téléphoniques pour lesquels la limite de capacité est autant due aux lignes qu’aux centraux.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

82 / 172

Recherche d’un ‡ot complet: Pour un ‡ot ϕ dans un réseau de transport G = (X , A, C ), on dit qu’un arc est saturé si on a ϕ(a) = C (a). Le ‡ot est dit complet si tout chemin allant de x1 à xn contient au moins un arc saturé. Si l’on considère le graphe partiel engendré par les arcs non saturés par le ‡ot et si le ‡ot n’est pas complet, il existe un chemin µ allant de l’entrée à la sortie.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

83 / 172

On peut alors dé…nir un nouveau ‡ot pour le réseau en augmentant de 1 le ‡ot de chacun des arcs constituant le chemin µ ; la valeur du ‡ot est alors également augmentée de 1. On peut donc progressivement augmenter la valeur d’un ‡ot incomplet jusqu’à ce qu’il soit complet. En tenant compte des di¤érences entre les capacités et la valeur du ‡ot sur les arcs de µ, on peut connaitre d’avance l’augmentation possible du ‡ot. Cependant, le ‡ot complet ainsi obtenu n’est pas, en général, le ‡ot maximal.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

84 / 172

Exemple: Un réseau

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

85 / 172

Exercice: (en TD) un ‡ot réalisable pour ce réseau: (les valeurs du ‡ot sont inférieurs aux capacités des arcs). Remarquer qu’il entre un ‡ot de (15 = 7 + 8) par la source et qu’il sort par le puits (15 = 6 + 9) sans pertes.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

86 / 172

On initialise à 0 (on peut eventuellement trouver à la main un ‡ot meilleur). Plusieurs stratégies sont possibles pour construire marque : en largeur, en …le,... On choisit ici de construire Marque comme une pile (on developpe le dernier arrivé), on écrit en meme temps la valeur de marque(x ), les élements qui sont dans Vu sont écrits en gras : Marque = f(s, +∞)g, Vu = ? Marque = f(s, +∞), (b, 1), (c, 7)g, Vu = fs g Marque = f(s, +∞), (b, 1), (c, 7), (e, 3)g, Vu = fs, c g Marque = f(s, +∞), (b, 1), (c, 7), (e, 3), (t, 2)g, Vu = fs, c, e g On a une chaine s, c, e, t augmentant le ‡ot de 1. La chaine suivante est : s, c, e, d, t qui augmente de 1. Ensuite la nouvelle chaine est s, b, d, t qui augmente de 1 et donne le ‡ot maximal. CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

87 / 172

Amélioration du ‡ot: Soit ϕ un ‡ot complet. On va identi…er et marquer tous les sommets du graphe ou il est possible de faire transiter une unité de ‡ot supplémentaire. On dé…nit un processus d’étiquetage de certains sommets du graphe. En x1 , on place une étiquette + . Soit x un sommet déja marqué : – on marque avec une étiquette +x tout successeur y non marqué de x pour lequel le ‡ot n’est pas à son maximum ((x, y ) 2 A et ϕ(x, y ) < C (x, y )). – on marque avec une étiquette x tout prédécesseur y non marqué de x pour lequel le ‡ot n’est pas nul ((x, y ) 2 A et ϕ(y , x ) > 0).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

88 / 172

L’étiquette donne le nom d’un prédécesseur ou d’un successeur d’un sommet donné en indiquant si le ‡ot peut etre augmenté dans le sens de parcours (étiquette +x ) ou diminué s’il est dans le sens contraire (étiquette x ). Si l’on parvient jusqu’au marquage du sommet xn avec cette procédure, c’est qu’il existe une chaine µ de x1 à xn dont tous les sommets sont marqués avec l’indice du sommet précédent au signe près. l’objectif est d’élaborer une chaine marquée de x1 à xn .

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

89 / 172

Soit alors : (un nouveau ‡ot...) ϕ0(a) = ϕ(a) si a 2 /µ ϕ0(a) = ϕ(a) + 1 si a 2 µ et si a est orientée dans le sens de µ ϕ0(a) = ϕ(a) 1 si a 2 µ et si a est orientée dans le sens contraire de µ On véri…e aisément que ϕ0 est encore un ‡ot. Comme ϕx0 n = ϕxn +1, la valeur du ‡ot ϕ0 est supérieure, donc meilleure que celle de ϕ.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

90 / 172

Graphe d’écart ou réseau résiduel: Dé…nition Soit un réseau de transport G = (X , A, C ) possédant un ‡ot complet ϕ. On appelle graphe d’écart ou réseau résiduel, le réseau G ( ϕ) = (X , A, C ) tel que : – si a 2 A et ϕ(a) < C (a) alors a 2 A et C (a) = C (a) ϕ(a) – si a = (x, y ) 2 A et ϕ(a) > 0 alors a 1 = (y , x ) 2 A et C (a 1 ) = ϕ(a) Le réseau résiduel indique le long de quels arcs on peut augmenter ou diminuer le ‡ot.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

91 / 172

Théorème:Flot maximal: Soit ϕ un ‡ot de G (de x1 à xn ) et G ( ϕ) le réseau résiduel associé à ϕ. Une condition nécessaire et su¢ sante pour que le ‡ot ϕ soit maximal est qu’il n’existe pas de chemin de x1 à xn dans G ( ϕ).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

92 / 172

Algorithme (Ford et Fulkerson) Recherche d’un ‡ot maximum. (a) - Itération k = 0 ‡ot initial ϕ0 (compatible avec les contraintes de capacité), par exemple ϕ0 = (0, 0, ..., 0). (b) - A l’itération k, soit ϕk le ‡ot courant. Rechercher un chemin µk de x1 à xn dans le graphe d’écart G ( ϕk ). S’il n’en existe pas, FIN : le ‡ot ϕk est maximal. (c) - Soit εk la capacité résiduelle du chemin µk (minimum des capacités résiduelles des arcs du chemin). Dé…nir le ‡ot ϕk +1 par : ϕka +1 = ϕka + εk si a 2 µ et si a est orientée dans le sens de µ ϕka +1 = ϕka εk si a 2 µ et si a est orientée dans le sens contraire de µ Faire k k + 1 et retourner en (b).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

93 / 172

Traitons un exemple: Soit le graphe élémentaire orienté suivant:

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

94 / 172

Début Itération O: Flot initial

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

95 / 172

graphe d’écart (suivant le ‡ot initial) On commence le traitement suivant les arcs 12

24

47.

Fin itération 0.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

96 / 172

Début itération 1: Ceci nous permet d’avoir: Flot à l’itération 1 (c’est suivant la plus petite valeur sur les arcs du parcours traité au dessus)

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

97 / 172

Il en résulte un graphe d’écart: Graphe d’écart à la première itération:(suivant le ‡ot à l’itération1) On a deux choses à noter: -Le ‡ot de l’itération 1 est retranché en ‡èches inverses sur les arcs: 12 24 47. -Presentation du prochain parcours à traiter: 12 25 57.

Fin itération1. CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

98 / 172

Début itération 2. Ceci nous permet d’avoir: Flot à l’itération 2 (c’est suivant la plus petite valeur sur les arcs du parcours traité au dessus)

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

99 / 172

Il en résulte un graphe d’écart: Graphe d’écart à la deuxième itération :(suivant le ‡ot à l’itération 2) On a deux choses à noter: -Le ‡ot de l’itération 2 est retranché en ‡èches inverses sur les arcs: 12 25 57. -Presentation du prochain parcours à traiter: 13 35 57 ( en pointillé). Graphe d’écart (suivant le ‡ot à l’itération deux) c’est un état temporaire

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

100 / 172

Ceci nous donne: Flot à l’itération 3: (c’est suivant la plus petite valeur sur les arcs du parcours traité au dessus)

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

101 / 172

Il en résulte un graphe d’écart: Graphe d’écart à la troisième itération :(suivant le ‡ot à l’itération 3) On a deux choses à noter encore: -Le ‡ot de l’itération 3 est retranché en ‡èches inverses sur les arcs: 13 35 57. -Presentation du prochain parcours à traiter: 13 36 67 ( en pointillé). Graphe d’écart (suivant le ‡ot à l’itération deux) c’est un état temporaire

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

102 / 172

Ceci nous donne: Flot à l’itération 4 (c’est suivant la plus petite valeur sur les arcs du parcours traité au dessus)

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

103 / 172

Il en résulte un graphe d’écart: Graphe d’écart à la quatrième itération :(suivant le ‡ot à l’itération 4)

On a deux choses à noter encore: -Le ‡ot de l’itération 4 est retranché en ‡èches inverses sur les arcs: 13 36 67. -Presentation du prochain parcours à traiter ? CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

104 / 172

Après l’itération numéro 4, on constate qu’il n’existe plus de chemin joignant le sommet 1 au sommet 7 dans le graphe d’écart. L’algorithme s’achève donc et le ‡ot maximal est celui obtenu lors de cette dernière étape ϕ1 = ϕ7 = 9. Comment ? On revient au graphe du ‡ot à l’itération 4 au dessus: D’une part, il y a deux arcs sortants à valeur 5 + 4 de la source (noeud 1). D’autre part, on récupére trois arcs entrants 4 + 3 + 2 au puits (noeud 7). C’est un ‡ot de valeur 9 qui entre par la source 1 dans le réseau et il en sort par le puits de meme valeur 9. (sans pertes).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

105 / 172

Remarque: l’algorithme peut etre adapté au cas ou les capacités des arcs ont des bornes inférieures non nulles (positives,et meme négatives). En pratique, on associe à la plupart des réseaux de transport, une notion de cout unitaire du transport qui se traduit par l’association, à chaque arc a du réseau, d’un nombre réel représentant ce cout unitaire. Le cout total d’un ‡ot ϕ est dé…ni comme la somme des couts associés aux ‡ots élémentaires: W ( ϕ ) = ∑ w (a ) ϕ (a ) a 2A

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

106 / 172

On peut alors se poser le problème consistant à rechercher, parmi les ‡ots à valeur maximale, celui qui est à cout minimal. L’algorithme de Ford et Fulkerson peut également etre adapté à cette situation.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

107 / 172

Regardons encore les étapes une nouvelle fois:

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

108 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

109 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

110 / 172

Problème de circulation: Représentation graphique décrite comme suit: – le sommet S est de niveau 0 (pas d’antécédents) ; – les sommets 1 et 2 sont de niveau 1 (n’ont que des antécédents de niveau inférieur ou égal à 0 dont au moins un antécédent de niveau égal à 0) ; – les sommets 3 et 5 sont de niveau 2 (n’ont que des antécédents de niveau inférieur ou égal à 1 dont au moins un antécédent de niveau égal à 1) ;

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

111 / 172

– le sommet 4 est de niveau 3 (n ’a que des antécédents de niveau inférieur ou égal à 2 dont au moins un antécédent de niveau égal à 2) ; – les sommets 6 et 7 sont de niveau 4 (n’ont que des antécédents de niveau inférieur ou égal à 3 dont au moins un antécédent de niveau égal à 3) ; – le sommet P est de niveau 5 (n’a que des antécédents de niveau inférieur ou égal à 4 dont au moins un antécédent de niveau égal à 4). En utilisant cet ordre on obtient la représentation suivante :

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

112 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

113 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

114 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

115 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

116 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

117 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

118 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

119 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

120 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

121 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

122 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

123 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

124 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

125 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

126 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

127 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

128 / 172

Recherche d’un ‡ot maximal à cout minimal: La recherche d’un ‡ot maximal à cout minimal peut etre résolue à l’aide de l’algorithme de Busacker-Gowen qui permet de déterminer la famille complète de tous les ‡ots de cout minimal d’un sommet x1 à un sommet xn et de valeur ϕ = 1, 2, ..., v . On donne les principes de cet algorithme (à implementer en exercice ultétieurement).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

129 / 172

A l’itération numéro k, le ‡ot courant ϕk est supposé etre un ‡ot de valeur ϕk0 et de cout minimal parmi l’ensemble de tous les ‡ots de valeur ϕk0 . Soit G (ϕk ) le graphe d’écart relatif à ϕk ; on attribue aux arcs de G (ϕk ) les couts w et les capacités c suivantes : – si a = (xi , xj ) 2 A et ϕ(a) < c (a), l’arc a+ = (xi , xj ) a un cout w (a) = w (a) et une capacité c (a) = c (a) ϕ(a) > 0, – si a = (xi , xj ) 2 A et ϕ(a) > 0, l’arc a = (xj , xi ) a un cout w (a) = w (a) et une capacité c(a) = ϕ(a).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

130 / 172

Soit alors µk un chemin de cout minimal relativement aux couts w entre x1 et xn sur le graphe d’écart G (ϕk ) ; on note cr k la capacité résiduelle de ce chemin. On dé…nit alors le ‡ot ϕk +1 comme dans l’algorithme de Ford-Kulkerson. Si µ est le vecteur associé au chemin µk (c’est-à-dire tel queµa = 1 si a+ 2 µk et µa = 1 si a 2 µk ), on a ϕk +1 = ϕk + cr k µ et le ‡ot ϕk +1 est un ‡ot de cout minimal de valeur ϕk0 + cr k .

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

131 / 172

On notera qu’à chaque itération, on doit rechercher le plus court chemin (au sens du chemin de cout minimal) de x1 à xn dans un graphe ou la longueur (le cout) des arcs peut etre négative ; il conviendra donc d’employer un algorithme adapté à cette situation (l’algorithme de Dijkstra ne convient pas). Il existe cependant une amélioration de cet algorithme proposée par Edmonds et Karp et basée sur une technique de modi…cation des couts permettant de les rendre tous positifs en conservant cependant la meme hiérarchie de chemin sur le graphe d’écart ; dans cette situation l’algorithme de Dijkstra peut etre utilisé.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

132 / 172

Couplages: Les problèmes de couplage dans les graphes quelconques (ou dans les graphes bipartis) ont un double interet. Le premier, le plus évident, vient de leurs applications : ils généralisent directement les probl‘emes d’a¤ectation et ils interviennent dans certains problèmes importants de la théorie de graphes : problèmes de tournées, détermination de plus courtes chaines dans un graphe non orienté, etc. Le second, d’ordre théorique, vient de ce qu’ils se rattachent à une classe de problèmes de programmation linéaire en nombres entiers.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

133 / 172

Dé…nition: Etant donné un graphe simple non orienté G = (X , A),

couplage

un

est un sous ensemble d’aretes K A tel que deux aretes quelconques de K ne sont pas adjacentes. Un sommet i 2 X est dit saturé par le couplage K A s’il existe une arete de K incidente à i. Un couplage K qui sature tous les sommets du graphe est appelé couplage parfait. Un couplage maximal est un couplage de cardinalité maximale.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

134 / 172

Le problème du couplage maximal: Dé…nition: Si K A est un couplage de G = (X , A), on appelle chaine alternée (relativement à K) une chaine élémentaire de G dont les aretes appartiennent alternativement à K et K = A K . Une chaine alternée augmentante ou chaine améliorante est une chaine alternée joignant deux sommets insaturés. En convenant de dessiner les arétes d’un couplage par des traits épais, les arétes de K = A K restant en traits …ns, une chaine alternée est une chaine élémentaire dont les aretes sont alternativement …nes et épaisses.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

135 / 172

Dé…nition: Etant donné un couplage K A, considérons une chaine alternée L dont chaque extrémité est un sommet insaturé ou est telle que l’unique aréte de K qui lui est incidente soit dans L. Alors le couplage K 0 obtenu en échangeant le role des aretes …nes et épaisses le long de la chaine L est encore un couplage de G . Cette opération qui fait passer du couplage K au couplage K 0 est appelée transfert le long de la chaine alternée L. Une opération de transfert le long d’une chaine alternée augmentante, augmente la cardinalité du couplage d’une unité.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

136 / 172

Par exemple, sur le graphe de la …gure suivante

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

137 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

138 / 172

les aretes (2, 3) et (5, 6), dessinées en traits épais, forment un couplage K de cardinalité égale à 2. La chaine L = f1, 2, 3, 4g est une chaine alternée dont les extrémités sont des sommets insaturés. C’est donc une chaine alternée augmentante. Un transfert le long de cette chaine produit le nouveau couplage K 0 = f(1, 2), (3, 4), (5, 6)g de cardinalité égale à 3.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

139 / 172

Pour cet exemple particulier, ce couplage est maximal, car, pour un graphe d’ordre n, la cardinalité d’un couplage maximal est égale à la partie entière de n/2. Le théorème suivant permet de caractériser un couplage maximal. Théorème: Un couplage K est maximal si et seulement s’il n’existe pas de chaine alternée augmentante relativement à K .

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

140 / 172

Problèmes d’a¤ectation. c’est: n taches à réaliser et n machines pour les réaliser sachant que l’on connait le cout de réalisation Cij de la tache ti par la machine mj . (pour tous les couples (ti , mj ) possibles, si la tache ti ne peut etre e¤ectuée par la machine mj , on pose Cij = ∞) on cherche une permutation σ de f1, 2, ..., n g n

conduisant à un cout total : ∑ Ci i =1

σ (i )

minimum ( n! permutations σ

possibles).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

141 / 172

Le problème d’a¤ectation est un cas particulier du problème de transport (sans capacité). L’algorithme Hongrois: façon de résoudre proposé par Kuhn repose sur le fait qu’on ne change pas la ou les solutions optimales en augmentant ou en diminuant d’une meme quantité λ tous les éléments d’une meme ligne (ou d’une meme colonne) de la matrice des Cij (les valeurs in…nies restant in…nies). Après une telle opération, la valeur totale est augmentée ou diminuée de λ.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

142 / 172

Par conséquent, si l’on fait apparaitre, par des transformations de ce type, su¢ samment de zéros dans le tableau, mais pas de couts négatifs, et qu’il existe n zéros “indépendants” (c’est- à-dire un seul zéro dans chaque ligne et dans chaque colonne), on aura alors trouvé l’a¤ectation optimale. Cela se fait en trois phases

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

143 / 172

Soit l’exemple décrit par la matrice des couts suivante :

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

144 / 172

Phase I : Obtention de valeurs nulles A tous les éléments de chacune des colonnes, on enlève le plus petit élément de cette colonne, puis, dans la matrice ainsi obtenue, on enlève, à tous les éléments d’une meme ligne, le plus petit élément de la ligne. On obtient de la sorte une matrice (C1,ij ) ayant au moins un zéro par ligne et par colonne.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

145 / 172

après traitement des colonnes

puis des lignes

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

146 / 172

Phase II : recherche du maximum d’a¤ectations possibles: A partir de la matrice (C1,ij ), on cherche à former une solution de cout nul (un seul zéro dans chaque ligne et dans chaque colonne). Si c’est le cas, on a la solution optimale, sinon on cherche un ensemble maximum de zéros “indépendants” : ceci revient à chercher un ‡ot maximal sur le

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

147 / 172

graphe G 0 constitué par les arcs de cout (réduit) nul. Sur la matrice (C1,ij ) , cela correspond au traitement suivant. On considère la ligne ayant un nombre minimal de zéros (pour l’exemple, cela peut etre la première). On encadre l’un des zéros de cette ligne (ici, C1 ,A2), puis on barre les zéros qui se trouvent sur la meme ligne ou la meme colonne que le zéros encadré (ici, C1 ,D2). On procède de meme pour toutes les lignes, en tenant compte des étapes précédentes.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

148 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

149 / 172

phase III : détermination des a¤ectations “intéressantes”: Pour avoir ces a¤ectations, on procède la manière suivante : – On marque (d’une étoile) toutes les lignes qui ne contiennent aucun zéro encadré – sommet non a¤ecté – (ligne D de l’exemple) ; – On marque les lignes qui ont un zéro encadré dans une colonne marquée (ligne A de l’exemple) ; – On marque les colonnes qui ont un ou plusieurs zéros barrés dans une ligne marquée – possibilité non exploitée – (colonne 2 de l’exemple).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

150 / 172

On répéte ces trois marquages successifs jusqu’à ce que l’on ne puisse plus e¤ectuer de nouveaux marquages. Les a¤ectations intéressantes à considérer sont celles issues des sommets correspondant aux lignes marquées ; on barre donc les lignes non marquées. Les sommets correspondant aux colonnes marquées ne sont pas intéressants car ils ne peuvent etre réa¤ectés ; on barre donc les colonnes marquées.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

151 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

152 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

153 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

154 / 172

On note (C2,ij ) la matrice ainsi obtenue et l’on poursuit la procédure de traitement en reprenant à la seconde phase. Lorsqu’une solution optimale est obtenue (un zéro par ligne et par colonne), on arrete ; sinon on recommence et on dé…nit successivement les matrices (C3,ij ), (C4,ij ), ......, (Cn,ij ).

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

155 / 172

Sur le tableau (C2,ij ) de l’exemple, on est amené à encadrer C2,D2 et barrer C2,A2, encadrer C2,E4, encadrer C2,A1 et barrer C2,B1 et C2,C1, encadrer C2,B5 et en…n encadrer C2,C3 :

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

156 / 172

La solution optimale est alors obtenue grace aux éléments : C2,A1 = C2,B5 = C2,C3 = C2,D2 = C2,E4 = 0 et à la permutation σ = (ABCDE 15324 ) Si l’on revient aux données initiales, on obtient : CA1 = CB5 = CC3 = CD2 = CE4 = 7 + 7 + 1 + 4 + 2 = 21

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

157 / 172

Problèmes d’ordonnancement: L’objet d’un problème d’ordonnancement est de faciliter la mise en oeuvre et de guider l’exécution d’un ensemble complexe de taches (programme de recherche ou de production, lancement d’un produit, construction d’un édi…ce ...). La technique d’analyse la plus connue, appelée méthode PERT (Program Evaluation and Review Technique) a été introduite aux Etats-Unis en 1958 pour la conduite du programme de recherche et de construction des fusées Polaris.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

158 / 172

Etant donné un objectif qu’on se propose d’atteindre et dont la réalisation suppose l’exécution préalable de multiples taches, soumises à de nombreuses contraintes, déterminer l’ordre et le calendrier d’exécution des diverses taches.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

159 / 172

Le critère d’optimalité peut porter sur la minimisation de la durée et/ou du cout de la réalisation du projet. Nous supposerons que le projet est décomposable en un nombre …ni de taches, caractérisées par leur durée d’exécution (généralement …xe, parfois aléatoire), éventuellement aussi par leur cout d’exécution, et soumises à des contraintes de postériorité stricte (une tache ne peut commencer que si certaines autres taches sont complétement terminées). Ce type de problème se nomme problème central de l’ordonnancement.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

160 / 172

La représentation par un graphe d’un problème d’ordonnancement permet une bonne appréhension globale du problème. L’´ etude de ce graphe conduit à l’identi…cation des taches prioritaires et la détection des retards ou des dépassements de moyens a…n de prendre les mesures correctives nécessaires.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

161 / 172

Le problème central de l’ordonnancement s’énonce comme suit : étant donné un projet constitué de n taches de durées d’exécution …xes et soumises à des contraintes de postériorité stricte, déterminer un “calendrier d’exécution” ou ordonnancement qui minimise la durée de réalisation totale du projet.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

162 / 172

Recherche du plus long chemin: Graphes et plani…cation Un problème de plani…cation: étant donné un travail à e¤ectuer (un projet à faire) nécessitant un (grand) nombre de tâches coordonnées entre elles Trouver le temps minimum pour terminer le travail Trouver les tâches critiques

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

163 / 172

Algorithme: trouver le chemin le plus long Pour chaque noeuds x, …xer x.max = 0 …ni = faux Tant que (non …ni) { …ni = vrai Pour chaque arc a du graphe { si (a.origine.max + a.longueur > a.destination.max) { a.destination.max = a.origine.max + a.longueur; …ni = faux; } } }

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

164 / 172

Modèle PERT: Les tâches sont représentées par des arcs La durée de la tâche est associée à l’arc Les noeuds représentent des instants (début - …n de tâches) 2 instants particuliers : début travail - …n travail Représentation de la dépendance "terminer A avant de commencer B"

1. Véri…er que le graphe est sans cycle 2. Durée minimum du travail = somme des durées le long du plus long chemin de début à …n.

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

165 / 172

Exemple:

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

166 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

167 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

168 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

169 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

170 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

171 / 172

CHERTI LST IGI GI ()

problème du ‡ot maximal

May 25, 2012

172 / 172