TP Cours - Optimisation Réseaux Bouras 3 [PDF]

Zitiervorschau

Résolution des problèmes du plus court chemin et du flot maximal 1.

P l us cou rt c h e m i n

Les problèmes de plus court chemin apparaissent naturellement comme modélisation de problèmes opérationnels (trajet le plus rapide, ou le moins cher, gestion optimale de stock...). On suppose dans la suite qu’on dispose d’un graphe orient D = (V,A) pondéré par une fonction poids p : A → R. Les poids peuvent représenter des longueurs, des durées, mais aussi des coˆuts ou des bénéfices. C’est pour cela qu’ils peuvent prendre des valeurs positives ou négatives. Dépendamment du signe de p et de l’existence ou pas de circuitsdans le graphe, on dispose de différents algorithmes. Le poids d’un chemin est la somme des poids de ses arcs. On cherche le chemin de poids le plus petit. L e s p o i d s s o n t positifs: a l g o r i th m e d e Di j ks t ra On suppose dans cette section que la fonction w = p prend des valeurs strictement positives. On considère un sommet de départ a. L’algorithme de Dijkstra va donner le poids du chemin le plus court de a à tous les autres sommets. Pendant l’algorithme, on maintiendra les variables suivantes: • Q: vecteur de taille n, le nombre de sommets du graphe. • λ : V → R + : fonction qui à chaque sommet v donne l’évaluation courante du poids du plus court chemin de a à v. Décrivons maintenant l’algorithme. 1. Initialisation: • Q (a) = 1 et Q (v) = 0 sinon, • λ (a) = 0 et λ (v) = + ∞ sinon. 2.

Boucle sur v tel que Q(v) = 1: (on choisit v qui minimise λ) • Q (v) = 0. • Boucle sur tous les v ′ successeurs de v: – Si λ(v ′) = + ∞ , Q (v ′) = 1. – Si λ(v) + w (vv ′) < λ(v ′), alors λ(v ′) = λ(v) + w(v,v ′).

3. Critère d’arrêt: On s’arrête quand Q = 0. La fonction λ donne alors les poids des plus courts chemin du sommet a aux autres sommets. Un poids égal à +∞ signifie que le sommet n’est pas atteignable à partir de a.

1

Exemple 1. On considère le graphe suivant.

Déterminer les PCC de s vers les autres sommets. 1. Initialisation: • Q = { s} , • λ (s) = 0 et λ (v) = + ∞ sinon. 2.étape 1: v = s • Q = ∅. • S (s) = { a,d,f } . – v′ = a. λ(a) = 3. Q = {a}. – v ′ = d. λ (d ) = 3. Q = { a,d} . – v ′ = f . λ (f ) = 5. Q = { a,d,f } . 3.étape 2: v = a • Q = { d,f } . • S (a) = {b}. – v ′ = b. λ(b ) = 5. Q = {d,f,b} . 4.étape 3: v = d • Q = {b,f }. • S(s) = {b}. – v ′ = b. λ(b) = 4. Q = {b,f }. 5.étape 4: v = b 2

• Q = {f }. • S (s) = { c} . – v ′ = c . λ (c ) = 5. Q = { f,c} . 6.étape 5: v = c • Q = {f }. • S (s) = { e} . – v ′ = e. λ (e) = 8. Q = {e,f } . 7.étape 6: v = f • Q = {e} . • S (s) = { e,t} . – v ′ = e. λ (e ) = 7. – v ′ = t. λ (t) = 12 . Q = { e,t} . 8.étape 7: v = e • Q = { t} . • S (s) = { d,t} . – v ′ = d. λ(d) = 3 < λ(e) + 1 = 9. – v ′ = t. λ (t) = 9. 9.étape 8: v = t • Q = ∅. • S (s) = { c} . – v ′ = c. λ(c) = 5 < λ(t) + 6 = 15. 10. Critère d’arrêt: On s’arrête car Q = ∅. Les différentes valeurs de λ sont représentées dans le tableau suivant.

Proposition 1. La complexité de l’algorithme de Dijkstra est O(n 2 ).

3

Programmation de l’algorithme Dijkstra Nous disposons d’un graphe orienté pondéré. Nous souhaitons trouver le plus court chemin entre chaque 2 sommets de ce graphe à l’aide de l’algorithme de Dijkstra. Le but de cet exercice est de programmer l’algorithme de Dijkstra sous Scilab et l’utiliser pour trouver le plus court chemin du point s = 1 au point t = 8 du graphe de la figure 1.

Figure 1: Graphe orienté.

1. Créer un répertoire de travail “PCC”. Dans ce répertoire, créer un fichier “Graphe.sce” et un fichier “Dijkstra.sce”. 2. Lancer Scilab et se placer dans le répertoire “PCC”. 3. Nombre de sommets: dans le fichier “Graphe.sce”, introduire une variable n qui représente le nombre de sommets dans le graphe. 4. Arcs et poids: dans le fichier “Graphe.sce”, introduire une matrice A telle que A ij = 0 si l’arc ij n’appartient pas au graphe et A ij = w(ij) le poids de l’arc ij si l’arc ij appartient au graphe. 5. Sommet de départ: dans le fichier “Graphe.sce”, introduire une variable s qui donne l’indice du sommet de départ. 6. Exécuter le fichier “Graphe.sce”. On implémentera dorénavant les commandes dans le fichier “Dijkstra.sce”.

4

7. La fonction: définir une fonction PCC qui prend en argument un graphe A et un sommet de départ s et dont le résultat est un vecteur λ qui donne les poids des plus courts chemins de s aux autres sommets du graphe. Introduire une variable n qui donne le nombre de sommets du graphe et le vecteur Q qui donne les sommets à explorer. 8. Initialisation: initialiser Q et λ. 9. Sommets à explorer: faire une boucle sur les éléments de Q tant que Q n’est pas vide.à chaque itération, définir i, l’indice du sommet de Q qui minimise λ. On peut utiliser les commandes min et find. 10. Exploration du sommet: faire une boucle sur les sommets j successeurs de i. Pour chaque j implémenter les deux commandes suivantes: • Si λ(j) = + ∞ , Q = Q ∪ {j}. • Si λ(i) + w (ij) < λ(j), alors λ (j) = λ(i) + w (ij). Exécuter le fichier “Dijkstra.sce”. 11. Application: appliquer la fonction PPC à la matrice définie précédemment et donner le poids du plus court chemin entre s et t. 12. Envoyer les fichiers “Graphe-votrenom.sce” et “Dijskstra-votrenom.sce” à l’adresse abdelghani.bouras@@centrale-casablanca.ma à la fin de la séance.

5

2.

Flo t maxi mal

Soit D = (V,A) un graphe orienté de capacité c et deux sommets particuliers s,t ∈ V problème de flot maximal est de trouver un s − t-flot f sur D de valeur maximale. Le problème du flot maximal peut être formulé sous forme d’un programme linéaire:

(**)

. Le

• Les variables de décision: fa flot passant par l’arc a (card(A) variables) • Les contraintes: ∀a ∈ A, 0 ≤ f (a) ≤ c(a). Pour tout v = s,t,

Σ

f(a ) −

a∈ δ + (v)

Σ f(a) =

0

a∈δ− (v )

• Objectif: Max

Σ f (a) − Σ f (a)

a∈ δ + (v)

a∈δ− (v )

L’algorithme le plus célèbre pour résoudre le problème du flot maximal est l’algorithme de Ford-Fulkerson. Il se base sur la notion de capacité résiduelle et de chaîne augmentante. Définition 1 (Capacité résiduelle). Soit f un s−t flot sur D. La capacité résiduelle de D par rapport à f est une fonction sur V × V définie par • δ(e) := c(e) − f (e) si e ∈ A, • δ(e) := f (e) si e ∈ A −1 , où on rappelle A −1 = {ji, ij ∈ A}. Définition 2 (Chaîne augmentante). Le capacité résiduelle d’une chaine C est définie par δ(C) = min δ(e). e∈C C est une chaîne f -augmentante si sa capacité résiduelle δ est non nulle.

_____________________________________________________________________________________________________ (**) On suppose dans une première lecture que si ij ∈ A alors ji ∈ A 6

Théorème 1. Soit f un s − t-flot sur D. S’il existe une chaîne augmentante entre s et t alors f n’est pas maximal. L’algorithme a la structure suivante: 1. Initialisation: on se donne un flot initial f . 2. Tant que le critère d’arrêt n’est pas atteint • Trouver une chaîne augmentante C de s à t • Améliorer le flot sur cette chaîne comme suit: – si a ∉ C, 𝑓(𝑎) =𝑓(𝑎) – si a ∈ C ∩ A, 𝑓 (𝑎) = 𝑓(𝑎) + δ(C)

– si a ∈ C ∩ A −1 , 𝑓 (𝑎) = 𝑓(𝑎) − δ(C) 3. Critère d’arrêt: On s’arrête quand il n’y a plus de chaînes augmentantes.

Pour trouver une chaîne augmentante, on se base sur une procédure de marquage direct et indirect. Pendant l’algorithme, on garde les variables suivantes: • Un vecteur P qui donne le prédécesseur de chaque sommet de la chaîne. • Un vecteur γ qui donne la valeur courante de la capacité résiduelle de la chaîne. • Un vecteur Q qui donne les sommets à explorer

Voici les étapes de l’algorithme. • Initialisation: – On pose P (s) = s et P (v) = +∞ sinon. – γ = +∞. – Q(s) = 1 et Q(v) = 0 sinon. • Boucle sur i tel que Q(i) = 1: alors Q(i) = 0 et on fait une boucle sur les successeurs j de i. Si δ(ij) > 0 et P (j) = +∞ alors – Q(j) = 0,

– on pose P (j) = i, – on pose γ(j) = min(δ(ij),γ(i)) • Critère d’arrêt: on s’arrête quand Q = 0 ou quand on a marqué t (P (t) ≠ 0). Dans ce dernier cas, la chaîne augmentante est donnée récursivement par

Chaine(v) =

{

v si P (v) = v, (Chaine(P (v)), v)sinon.

7

Programmation de l’algorithme de Ford-Fulkerson Nous disposons d’un graphe orienté pondéré avec une capacité c : A → R+. Nous souhaitons trouver le flot maximal entre 2 sommets particuliers de ce graphe (s et t) à l’aide de l’algorithme de Ford-Fulkerson. Le but de cet exercice est de programmer l’algorithme de Ford-Fulkerson sous Scilab et l’utiliser pour trouver le flot maximal du point s = 1 au point t = 8 du graphe de la figure 2.

Figure 2: Graphe orienté. 1. Créer un répertoire de travail “FF” et y copier le fichier “Graphe.sce”. Créer un fichier “FF.sce”. Lancer Scilab et se placer dans le répertoire “FF”. 2. La fonction: dans le fichier “FF.sce”, définir une fonction FF qui prend en argument un graphe A, un sommet source s et un sommet puits t, et dont les résultats sont: une matrice f qui donne le flot sur chaque arc ij, et la valeur du flot F . Introduire une variable n qui donne le nombre de sommets du graphe. 3. Flot: introduire une matrice f qui représente le flot courant. f (i,j) = λ si le flot sur l’arc ij est égal à λ. Initialiser le flot à 0. 4. Capacités résiduelles: introduire une matrice δ qui représente les flots résiduels sur chaque arc. 5. Critère d’arrêt: introduire un indicateur FA qui vaut 1 si le critère d’arrêt est atteint et 0 sinon. 6. Recherche d’une chaîne augmentante: • Initialiser les capacités résiduelles. • Introduire et initialiser les vecteurs Q, P et γ qui représentent re- spectivement: les sommets à explorer, les prédécesseurs des som- mets marqués et le marquage. • Explorer les sommets non encore marqués, jusqu’aux critères d’arrêt. 8

• Si aucune chaîne augmentante n’est trouvée, mettre l’indicateur FA à 1. 7. Amélioration du flot: Si une chaîne augmentante est détectée, améliorer le flot suivant cette chaîne. 8. Valeur du problème: Introduire une variable F qui donne la valeur du flot maximal. Exécuter le fichier “FF.sce”. 9. Application: Appliquer la fonction FF au graphe défini précédemment et donner le flot maximal entre s et t et sa valeur. 10. Envoyer les fichiers “Graphes-votrenom.sce” et “FF-votrenom.sce” à l’adresse [email protected] à la fin de la séance.

9