Problème de flot maximal Problème de flot maximal dans un réseau Formulation du problème de flot...

Problème de flot maximal

dansun réseau

Formulation du problème de flot maximal. Notions de coupe etde chaînes d’augmentation par rapport à un flot f. Algorithme deFord et Fulkerson. Théorème d’intégrité. Généralisation au cas deplusieurs sources et plusieurs destinations. Présence de contraintesde capacité sur les arcs et les sommets. Détermination d’un flotréalisable.

Problème de flot maximal 2

Une compagnie possède 6 postes T1, T2, T3, T4, T5 et T6 deretransmission des appels téléphoniques des Laurentides vers lesCantons de l’Est.

T6Laurentides Cantons de

l’Est

Les capacités maximales en milliers d’appels par minute.

Introduction

Ce réseau de communication a été construit de telle façon qu’ilsatisfasse aux conditions suivantes :

Chaque poste intermédiaire T2, T3, T4, T5 conserve les appels i.e.tout appel arrivant à l’un de ces postes est immédiatement acheminévers un autre poste (il ne se perd pas d’appels à un poste donné).

Le # d’appels passant entre 2 postes est évidemment une quantiténon négative et est au plus égal à la capacité maximale des lignestéléphoniques reliant ces 2 postes.

Les appels des Laurentides passent tous par le poste T1 qui lesachemine vers les autres postes.

Les appels arrivant au poste T6 sont tous acheminés dans lesCantons de l’Est.

Problème: Soit v le # d’appels passant dans le réseau de T1 (la source)à T6 (la destination), comment répartir les appels dans leréseau de façon à maximiser v ?

Énoncé du problème de flot maximal

Soit un réseau R = (N, A) où N représente les sommets du réseau etA l’ensemble des arcs.

Le problème avec une source s et une destination d s’énonce alorscomme suit :

f(x, y)

{y N | (x, y) A}

- f(y, x)

{y N | (y, x) A}

v si x = s

0 si x s, d-v si x = d

L(x, y) f(x, y) K(x, y), (x, y) A.

On désigne aussi parK(x, y) : capacité maximale de l’arc (x, y), (x, y) A,f(x, y) : quantité de flot passant par l’arc (x, y), (x, y) A.

Note : Sauf avis contraire par la suite, L(x, y) = 0 (x, y) A.

Problème de programmation linéaire

En ajoutant un arc fictif (d, s) de capacité infinie, le problème devient :

MAX f(d, s)

f(x, y)

{y N | (x, y) A'}

- f(y, x)

{y N | (y, x) A'}

= 0 x N.

L(x, y) f(x, y) K(x, y), (x, y) A' où A' = A {(d, s)}.

Note :

Cela nous ramène à un problème de flot à coût minimum.

La méthode du simplexe peut être utilisée :- membre de droite nul,- vecteur de coût nul excepté pour la variable f(d, s).

un algorithme spécialisé plus efficace que la méthode du simplexe.

Exemple :

(12, 12)

(8, 8)(3, 9)

(6, 11)

(6, 6)

(0, 3)

(6, 6)

(8, 8)

(9, 9)

(0, 4)

(f(x, y), K(x, y))

La valeur du flot passant dans ce réseau est v = 29.

Définition de coupe

Si X et Y sont 2 sous-ensembles de N, (X, Y) désigne {(x, y) A | x X, y Y}.

On peut aussi définir une fonction g sur A et à valeurs réelles,comme suit :

g(X, Y) = g(x, y)(x, y) (X, Y)

Notation :

Définition :

Soit X N, un sous-ensemble de sommets contenant la source s,mais ne contenant pas la sortie d, la partition X, X = N – X génèreune coupe C [X, X ] = (X, X) (X, X ) séparant la source s de ladestination d.

Définition :

La capacité de la coupe C [X, X ] est égale à K(X, X) – L(X, X).

Exemple :

Soit X = {s, 1}, alors C = {(s, 2), (1, 3), (1, d), (1, 2), (3, s), (d, s)}.

Note : Toute chaîne reliant s à d doit nécessairement contenir un arcdans chaque coupe [X, X ].

Note :

Si l’on enlève du réseau tous les arcs de la coupe [X, X ], il ne peuty avoir de chaînes reliant s à d.

La valeur du flot pouvant passer dans le nouveau réseau ainsi obtenuest nulle.

Étant donné qu’une coupe bloque toutes les chaînes reliant s à d,il s’ensuit que la valeur du flot f passant dans le réseau ne peut pasexcéder la capacité d’une coupe, quelque soit celle-ci.

Lemme :

Soient un flot f de s à d dans le réseau R = (N, A) et v la valeur dece flot. Si [X, X ] est une coupe dans R séparant s et d, alors

v = f(X, X) – f(X, X) K(X, X) – L(X, X).

La valeur v d’un flot quelconque de s à d est inférieure ouégale à la capacité de toute coupe séparant s et d.

Démonstration du lemme :

Étant donné que f est un flot, f satisfait les équations :

f(s, N) – f(N, s) = v

f(d, N) – f(N, d) = - v

f(x, N) – f(N, x) = 0 si x s et x d.

Additions ces équations pour x X, vu que s X et d X, on a :

v = (f(x, N) – f(N, x) ) = f(X, N) – f(N, X).x X

Sachant que N = X X, on obtient :

v = f(X, X X) – f(X X, X)

v = f(X, X) + f(X, X) – f(X, X) – f(X, X) = f(X, X)– f(X, X).

Puisque f(X, X) L(X, X) et f(X, X) K(X, X), alors v = f(X, X) – f(X, X) K(X, X) – L(X, X).

Corollaire du lemme :

vmax = Max v(f) Min K(X, X) – L(X, X){f est un flot réalisable de s à d} X N

s X, d X

c’est-à-dire, que la valeur maximale du flot est toujours inférieure ouégale à la coupe minimale des capacités.

Exemple :

(f(x, y), K(x, y))

L(x, y) = 0 (x, y) A.

v = 3.

La coupe C = {(s, 1), (2, 1), (2, d), (1, 2)} a aussi une capacité égaleà 1 + 1 + 1 - 0 = 3.

D’après ce qui précède, le flot est maximal et la coupe est minimale.

Théorème (flot max – coupe min) :

Pour n’importe quel réseau donné, la valeur maximale du flot reliantla source s à la destination d est égale à la capacité minimale descoupes séparant s et d dans le réseau.

Démonstration :

Laissée en exercice.

Les définitions suivantes et les corollaires de ce théorème vont nouspermettre d’élaborer un procédé pour parvenir à un flot maximal.

Définition :

Une chaîne W reliant la source s à la destination d est dite une chaîned’augmentation par rapport au flot f si

f(x, y) < K(x, y) (x,y) de cette chaîne tel que (x,y) Aet

f(x, y) > L(x, y) (x,y) de cette chaîne tel que (y,x) A.

Les arcs de W parcourusdans le sens de leur orientation.

Les arcs de W parcourusdans le sens inverse de leur orientation.

(f(x, y), K(x, y))

Exemple :

Il existe une chaîned’augmentation :

(s,2) - (1,2) – (1,d).

On peut faire passer une unitéde flot à travers cette chaîne.

Définition :

Un arc (x, y) est saturé par rapport à f si f(x, y) = K(x, y).

Un arc (u, v) est dit minimal par rapport à f si f(u, v) = L(u, v).

Corollaire :

Un flot f est maximal si et seulement si il n’existe pas de chaîned’augmentation par rapport à celui-ci.

Corollaire :

Une coupe [X, X] est minimale si et seulement si, pour tout flotmaximal f, les arcs de (X, X) sont saturés par rapport à f et ceux de(X, X) sont minimaux par rapport à f.

Appliquons maintenant ces résultats à l’exemple suivant où à chaqueitération, nous tenterons de construire une chaîne d’augmentation.

Exemple :

0,30,2

0,20,1

Déterminons d’abord un flot au jugé en saturant le plus grand nombrepossible de chemins reliant s à d.

I. s - 2 - 3 - d : 3 unités pour obtenir une saturation.

0,30,2

0,20,1

II. s - 2 - 3 - 4 - d : déjà saturé.

III. s - 2 - 4 - 3 - d : 2 unités pour obtenir une saturation.

0,32,2

2,20,1

IV. s - 2 - 4 - d : déjà saturé.

V. s - 3 - d : 2 unités pour obtenir une saturation.

0,32,2

2,20,1

7 72,6

VI. s - 3 - 4 - d : 1 unité pour obtenir une saturation.

0,32,2

2,21,1

8 83,6

VII. s - 4 - 2 - 3 - d : déjà saturé.

VIII. s - 4 - 3 - d : déjà saturé.

IX. s - 4 - d : 4 unités pour obtenir une saturation.

0,32,2

2,21,1

12 123,6

Pour déterminer une chaîne d’augmentation reliant s à d (si elle existe),on doit opter pour une procédure de marquage :

Soit Z = {(s, pred(s) = •, = +)},pour chaque sommet (x, pred(x), ) Z non traité,

si f(x, y) < K(x, y)ajouter (y, x, min{, K(x, y) – f(x, y)}) à Z

sinon si f(y, x) > L(y, x)ajouter (y, x, min{, f(y, x) – L(y, x)}) à Z.

0,32,2

2,21,1

12 123,6

Z = {(s, •,+)}

Z = {(s, •,+), (2, s, 1), (3, s, 3)}

Z = {(s, •,+), (2, s, 1), (3, s, 3), (4, 3, 2)}

Z = {(s, •,+), (2, s, 1), (3, s, 3), (4, 3, 2), (d, 4, 2)}

Il existe une chaîne d’augmentation reliant s à d où l’on peut faire passer2 unités de flot. À l’aide de Z, on peut retracer la chaîne d’augmentation.

0,32,2

0,21,1

14 145,6

Répétons la procédure de marquage :

Z = {(s, •,+)}

Z = {(s, •,+), (2, s, 1), (3, s, 1)}

Il n’est pas possible d’atteindre la sortie d;par conséquent, le flot est maximal.

0,32,2

0,21,1

14 145,6

X = {s, 2, 3}

(X, X) = {(s, 4), (2, 4), (3, 4), (3, d)}(X, X) = {(4, 2), (4, 3)}

v = 14 = f (X, X) - f (X, X) = K(X, X) – L(X, X).

Donc, le flot est optimal.

Algorithme de Ford & Fulkerson

Étape A Marquage des sommets

Cela conduit soit : à la fin de l’algorithme,à la découverte d’une chaîne d’augmentation.

Un sommet peut être dans l’un des 3 états suivants :non marquémarqué et examinémarqué et non encore examiné

À chaque sommet x marqué est associé un quadruplet(x, pred(x), m(x), p(x)).

Le sommetqui a permis le

le marquagede x.

La qté de flot supplém.que l’on peut faire passerdans la chaîne de s à x.

+ ou – selon que x a étémarqué grâce à l’arc(pred(x), x) ou (x, pred(x)).

Étape B Modifie le flot le long de la chaîne d’augmentation.

Description complète de l’algorithme de Ford & Fulkerson

Étape A

1. Initialisation.

La source s est marquée et non encore examinée : (s, •, •, ).

Les autres sommets sont non marqués.

2. Marquage.

Choisir un sommet x marqué et non encore examiné :(x, pred(x), m(x), p(x)).

sommet y non marqué tel que (x, y) A,si f(x, y) < K(x, y), alors marquez y non encore examiné :

(y, x, +, min{p(x), K(x, y) – f(x, y)})

sommet y non marqué tel que (y, x) A,si f(y, x) > L(y, x), alors marquez y non encore examiné :

(y, x, -, min{p(x), f(y, x) – L(y, x)})x est maintenant marqué et examiné.

Si la destination d est marquée et non encore examinée,aller à l’étape B.

Si tous les sommets marqués ont été examinés, c’est terminé(il n’y a pas de chaînes d’augmentation et le flot est maximal).

Autrement, répéter cette opération de marquage avec un nouveausommet marqué et non encore examiné.

Étape B Changement de flot dans une chaîne d’augmentation.

La destination d a été marquée : (d, pred(d), m(d), p(d)).

Si m(d) = + alors f(pred(d), d) = f(pred(d), d) + p(d)sinon f(d, pred(d)) = f(d, pred(d)) – p(d).

Posons y = pred(d).

Tant et aussi longtemps que y est différent de s{ soit le quadruplet associé à y : (y, pred(y), m(y), p(y)),

si m(y) = + alors f(pred(y), y) = f(pred(y), y) + p(d)sinon f(y, pred(y)) = f(y, pred(y)) – p(d);

poser y = pred(y).}.

On efface les marques des sommets et on retourne à l’étape A.

Construction d’une coupe minimale

À la fin de l’algorithme de Ford & Fulkerson, on peut construireune coupe minimale comme suit :

Poser U = {i N| le sommet i est marqué},V = {j N| le sommet j est non marqué},

Alors la coupe minimale est [U, V] et v = K(U, V) – L(V, U).

Exemple :

0,50,2

0,90,3

0,20,100,8

0,40,2 0,1

Effectuons un premier marquage.

0,50,2

0,90,3

0,20,100,8

0,40,2 0,1

(•,•,)

(1,+,4)

(1,+,3)

(1,+,8)

(1,+,10)

(1,+,4)

(5,+,6)

Ajoutons 6 unités dans la chaîne d’augmentation.

0,50,2

0,90,3

0,20,106,8

0,40,2 0,1

Effectuons un 2ième marquage.

0,50,2

0,90,3

0,20,106,8

0,40,2 0,1

(•,•,)

(1,+,4)

(1,+,3)

(1,+,2)

(1,+,10)

(7,+,3)

0,50,2

0,90,3

0,20,106,8

0,40,2 0,1

0,50,2

0,90,3

0,20,106,8

0,40,2 0,1

(•,•,)

(1,+,4)

(1,+,2)

(1,+,4)

(1,+,10)

(5,+,2)

(7,+,2)

0,50,2

0,90,3

0,20,108,8

0,40,2 0,1

0,50,2

0,90,3

0,20,108,8

0,40,2 0,1

(•,•,)

(1,+,4)

(1,+,10)

(1,+,4)

(3,+,9)

(3,+,2)

(4,+,2)

0,52,2

0,90,3

0,22,108,8

0,40,2 0,1

0,52,2

0,90,3

0,22,108,8

0,40,2 0,1

(•,•,)

(1,+,4)

(1,+,4)(1,+,8)

(6,+,4)

(6,+,2)

(7,+,4)

0,52,2

0,90,3

0,22,108,8

4,40,2 0,1

0,52,2

0,90,3

0,22,108,8

4,40,2 0,1

(•,•,)

(1,+,4)

(1,+,8)

(2,+,3)

(5,+,3)

(7,+,3)

0,52,2

0,93,3

0,22,108,8

4,40,2 0,1

0,52,2

0,93,3

0,22,108,8

4,40,2 0,1

(•,•,)

(1,+,1)

(1,+,8)

(3,+,8)

(5,+,3)

(5,+,1)

(7,+,3)

0,52,2

3,93,3

0,25,108,8

4,40,2 0,1

0,52,2

3,93,3

0,25,108,8

4,40,2 0,1

(•,•,)

(1,+,5)

(1,+,1)

(3,+,5)

(5,+,1)

(6,+,1)

(7,+,1)

Ajoutons 1 unité dans la chaîne d’augmentation.

0,52,2

4,93,3

0,26,108,8

4,40,2 1,1

0,52,2

4,93,3

0,26,108,8

4,40,2 1,1

(•,•,)

(1,+,1)

(1,+,4)

(3,+,4)

Il n’est pas possible d’atteindre le sommet 8; le flot est donc optimal.En prenant X = {1, 2, 3, 5}, la coupe minimale des capacités est [X, X]et la valeur du flot est 24.

Théorème d’intégrité

Si les capacités K(x, y) et les bornes inférieures L(x, y) sont toutesentières, il existe toujours un flot maximal à valeurs entières.

Si le flot initial est à valeurs entières et que les capacités le sontaussi, le flot maximal obtenu de l’algorithme sera aussi àvaleurs entières car la découverte d’une chaîne d’augmentationentraîne un changement de flot conduisant à un minimum denombres entiers.

Extension au cas de plusieurs sources et / ou destinations

On peut toujours se ramener au cas d’une source et d’une destination.

Supposons que les sommets N du réseau R = (N, A) sont partitionnéscomme suit :

S : l’ensemble des sources,

D : l’ensemble des destinations,

X : l’ensemble des sommets intermédiaires.

Le problème s’énonce comme suit :

Max vf(x, N) – f(N, x) = 0 x XL(x, y) f(x, y) K(x, y) (x, y) Af(S, N) – f(N, S) = vf(D, N) – f(N, D) = - v

Prolongeons le réseau R = (N, A) en un réseau R = (N, A) où

N = N {s, d},

S = {s}, D = {d},

X = N,

A = A tous les arcs correspondants à (s, S) tous les arcs correspondants à (D, d).

De plus,

L(s, x) = 0 et K(s, x) = x S

L(x, d) = 0 et K(x, d) = x D

L(x, y) = L(x, y) et K(x, y) = K(x, y) (x, y) A.

Théorème :Le problème de flot maximal de S à D dans le réseau R estéquivalent au problème de flot maximal de s à d dans R.

Extension au cas où chaque sommet x est soumis à une capacitémaximale (x)

Exemple :

Il est naturel et même nécessaire pour le réseau téléphonique denotre exemple d’introduction de supposer que chaque poste Ti

de retransmission des appels ne peut pas traiter plus de (Ti)appels par minute.

Théorème :

Le problème de flot maximal dans un réseau soumis à descontraintes de capacité sur ses arcs et sur ses sommets estéquivalent à un problème de flot maximal dans un nouveauréseau soumis à des contraintes de capacité sur ses arcsseulement.

Hypothèse non restrictive :

Tous les arcs admettant la source s à une de leurs extrémités sont dela forme (s, •) uniquement.

Tous les arcs admettant la destination d à une de leurs extrémitéssont de la forme (•, d) uniquement.

Note : S’il en est autrement, il s’agit de considérer 2 sommetssupplémentaires s et d de même que les arcs (s , s) et(d, d).

s et d joueront le rôle de source et de destination resp.

Le problème s’énonce comme suit :

Max f(s, N) f(x, N) – f(N, x) = 0 x N, x s, dL(x, y) f(x, y) K(x, y) (x, y) Af(x, N) (x) x N, x df(N, d) (d).

Pour ramener ce problème au cas de capacités maximales associées àdes arcs seulement, définissons un nouveau réseau R = (N, A).

x N, on fait correspondre 2 sommets x' et x'' N.

(x', y'') A (x, y) A.

(x'', x') A x N.

L(x', y'') = L(x, y), K(x', y'') = K(x, y), (x, y) A.

L(x'', x') = 0, K(x'', x') = (x), x N.

Exemple :

Les arcs incidents à x sont maintenant incidents à x'' tandis queceux issus de x sont maintenant issus de x'.

La capacité maximale (x) est imposée comme une capacitémaximale sur l’arc reliant x'' à x'.

Tout flot f satisfaisant , conduit à un flot équivalent f de s'' à d'dans R = (N, A) en définissant :

f(x', y'') = f(x, y) (x, y) A,

f(x'', x') = f(x, N) x d et f(d'', d') = f(N, d).

Comment déterminer un flot réalisable initial lorsque les bornesinférieures ne sont pas toutes nulles ?

Lorsque les bornes inférieures L(x, y) ne sont pas toutes nulles, ilpeut y avoir un sérieux problème pour déterminer un flot au jugépuisque le flot nul n’est pas admissible comme flot de départ.

Pour déterminer un flot réalisable initial, s’il existe,

on ajoute un arc « artificiel » (d, s) avec L(d, s) = 0, K(d, s) = .

on obtient le graphe G' = (N, A') où A' = A {(d, s)}.

Si f est un flot réalisable pour G avec une valeur de flot v, posons :

f '(d, s) = v et f '(x, y) = f(x, y) (x, y) A.

Ainsi, f ' est un flot réalisable sur G ' et la quantité nette de flots’écoulant à la source est nulle.

Définition :

f ' est une circulation réalisable sur G' si la qté nette de flot s’écoulantà n’importe quel sommet du réseau est nulle.

Rechercher un flot réalisable de départ sur G est donc équivalent àrechercher une circulation réalisable sur G' car, étant donné unecirculation réalisable sur G', en enlevant l’arc (d, s) du réseau, onobtient un flot réalisable sur G.

Transformons maintenant le problème de trouver une circulationréalisable sur G' en un problème de flot maximal sur un réseauaugmenté G" = (N", A").

Procédé :

Ajoutons une nouvelle source s" et une nouvelle destination d" :

N" = N {s", d"}.

Ajoutons les arcs (s", x) et (x, d") x N :

A" = A' (s", N) (N, d").

Ajoutons des bornes inférieures nulles :

L"(x, y) = 0 (x, y) A".

Ajoutons un nouveau vecteur de capacités :

K"(x, y) = K(x, y) – L(x, y) (x, y) A'

K"(s", y) = L(x, y) y Nx tel que (x, y) A

K"(x, d") = L(x, y) x Ny tel que (x, y) A

Il s’agit alors de trouver un flot maximal f" de s" à d" en partant avecle flot nul comme flot au jugé.

Soit la valeur de flot v" du flot f" sur G",

v" < L(x, y)(x, y) A

Il n’existe pas de flot réalisable sur G.

v" = L(x, y)(x, y) A

Le vecteur f suivant est réalisable surG : f(x, y) = f "(x, y) + L(x, y).

Exemple :

3,122,8

2,41,3

Note :

Les données sur l’arc(x, y) sont :

L(x, y), K(x, y).

Le problème de trouver un flot réalisable sur G est équivalent auproblème de trouver une circulation réalisable sur G' :

3,122,8

2,41,3

Sur le réseau augmenté G", le flot maximal f" de s" à d" est :

0,20,2

3,35,5

5,50,0

Réseau G" avec sur chaque arc : f"(x, y), K"(x, y).

Tous les arcs issus de s" sont saturés; alors, v" = L(x, y) = 11.(x, y) A

Le problème initial est réalisable et un vecteur de flotréalisable sur G est :

(f12, f13, f23, f32, f24, f34) = (3, 4, 1, 2, 4, 3).

Problème de flot maximal Problème de flot maximal dans un réseau Formulation du problème de flot...

Documents

Problème de flot

MOTEUR CABINE SYSTEME DE FREINAGE - isuzu.be Technique 3.5-5.5... · Poids maximal de la remorque non freinée 750 750 750 750 Poids maximal de la remorque avec frein 3500 3500 3500

Chapitre 1: Chiffrement Symétrique: par flot et par blocs

Médicaments soumis à un prix maximal payable (PMP) · Médicaments soumis à un prix maximal payable (PMP) DIN Dénomination commune Forme Teneur Marque de commerce Fabricant 15229

Court Flot Maximal

CODE 2 février 2021 - OECD · 2021. 1. 29. · CODE 2 – février 2021 6 2.6 Effort maximal de traction à la barre Effort maximal moyen soutenu que le tracteur peut maintenir à

Départ : Pessac Centre > Direction : Bassins à Flot ou ...tram.bordeaux.free.fr/docs/tram b_0.pdf · Départ : Claveau ou Bassins à Flot > Direction : Pessac Centre Pour tout savoir

Effets immédiats d'un effort concentrique quasi maximal

Rendement maximal avec volumes d’air importants · 158 CALFLO Rendement maximal avec volumes d’air importants Mark CALFLO est un système de chauffage avec brûleur en veine d’air

M2 MPRO Optimisation dans les Graphes 2014-2015cedric.cnam.fr/~bentzc/Files/OG_2014-2015.pdf · Le problème du flot maximum Problème emblématique de la RO et de l'optimisation

Flot contre ebolaFLOT Contre Ebola

Problème de flot, d’affectation et de transport · PDF filenotamment la recherche opérationnelle, à cause de leur niveau de complexité

LA RÉVOLUTION DE L’ENTRETIEN À FLOT

Photo-problème 3 Photo-problème 4

Médicaments soumis à un prix maximal payable (PMP) · Loi sur l’assurance médicaments permet au ministre d’imposer un prix maximal payable (PMP) sur ces médicaments. Dans

ET LE FLOT MITAIT MF0R1ATI0HS EÉIEMLËS

7. Problème de flot à coût minimum. 7.1 Graphes, graphes orientés, réseaux Un graphe G =(V, E) est constitué dun ensemble non vide fini de sommets V et

Un algorithme de chiffrement a flot base sur le probleme des 3 corps

WICLINE 75 MAX Design maximal Durabilité maximale

SCIENCES INDUSTRIELLES - ccp.scei-concours.frccp.scei-concours.fr/cpge/sujet/2012/MP/MP-SI.pdf · Débit maximal 400 m3/h Couple maximal que peut transmettre le moteur 1000 N.m