Recherche opérationnelle avec les raisonnements

Thèmes abordés

Recherche opérationnelle, école de l'innovation technlogique, ESIEE Paris, algorithme de Dijkstra, capacité d'un réseau routier, routage, algorithme de Ford et Fulkerson, débit horaire

Résumé du document

Le graphe est connexe, car pour chaque couple de points, il existe bien une chaîne les reliant.
Le chemin E-b-c-g-S a la valuation la plus élevée (7). On va saturer ce chemin en augmentant le flot courant de 7.

Extraits

[...] Chemin Valuation min. S-A-B-T 0 S-C-B-T 0 S-A-B-D-T 2 S-C-B-D-T 1 S-A-D-T 2 S-C-D-T 1 S-B-T 0 S-C-D-A-B-T 0 S-B-D-T 1 Deux chemins ont la valuation la plus élevée On choisit arbitrairement le chemin S-A-B-D-T. On va saturer ce chemin en augmentant le flot courant de 2 : La branche S-A est saturée. Etape 3 : on recommence à nouveau: Chemin Valuation min. Chemin Valuation min. S-A-B-T 0 S-C-B-T 0 S-A-B-D-T 0 S-C-B-D-T 1 S-A-D-T 0 S-C-D-T 1 S-B-T 0 S-C-D-A-B-T 0 S-B-D-T 1 Trois chemins ont la valuation la plus élevée On choisit le chemin S-C-D-T car celui-ci ne va saturer qu'une branche. [...]

[...] On commence par transformer la matrice des capacités de connexions entre nœuds en un graphe connexe équivalent : On applique ensuite par étapes l'algorithme de Ford et Fulkerson : Etape 1 : on cherche parmi tous les chemins de E vers S disponibles, celui ou ceux avec la valuation minimale la plus élevée : Chemin Valuation min. Chemin Valuation min. S-A-B-T 2 S-C-B-T 1 S-A-B-D-T 2 S-C-B-D-T 1 S-A-D-T 2 S-C-D-T 1 S-B-T 5 S-C-D-A-B-T 1 S-B-D-T 3 Le chemin S-B-T a la valuation la plus élevée On va saturer ce chemin en augmentant le flot courant de 5 : La branche B-T est saturée. Etape 2 : on recommence comme à l'étape 1 en tenant compte du nouveau flot courant : Chemin Valuation min. [...]

[...] Chemin Valuation min. E-a-c-g-S 0 E-b-e-d-S 1 E-a-d-S 0 E-b-e-d-f-S 1 E-a-d-f-S 0 E-b-e-d-g-S 1 E-a-d-g-S 0 E-b-e-f-S 1 E-b-c-g-S 0 E-e-d-S 1 E-b-d-S 1 E-e-d-f-S 2 E-b-d-f-S 2 E-e-d-g-S 2 E-b-d-g-S 2 E-e-f-S 4 Le chemin E-e-f-S a la valuation la plus élevée On va saturer ce chemin en augmentant le flot courant de 4 : La branche e-f est saturée. Etape 4 : on recommence de nouveau : Chemin Valuation min. Chemin Valuation min. E-a-c-g-S 0 E-b-e-d-S 1 E-a-d-S 0 E-b-e-d-f-S 1 E-a-d-f-S 0 E-b-e-d-g-S 1 E-a-d-g-S 0 E-b-e-f-S 0 E-b-c-g-S 0 E-e-d-S 1 E-b-d-S 1 E-e-d-f-S 2 E-b-d-f-S 2 E-e-d-g-S 2 E-b-d-g-S 2 E-e-f-S 0 On a plusieurs chemins avec la valuation 2. [...]

[...] S-A-B-T 0 S-C-B-T 0 S-A-B-D-T 0 S-C-B-D-T 0 S-A-D-T 0 S-C-D-T 0 S-B-T 0 S-C-D-A-B-T 0 S-B-D-T 1 Il ne reste que le chemin S-B-D-T avec valuation de 1. On ajoute donc 1 au flot courant. On obtient finalement le graphe suivant : Au fil des étapes on a ajouté et 1 au flot courant (en partant de 0). Le flot maximal est donc de 5+2+1+1=9. Le débit maximal est donc de 9 Mbit/s. Le routage proposé est représenté par la figure précédente. [...]

[...] Chemin Valuation min. E-a-c-g-S 5 E-b-e-d-S 1 E-a-d-S 5 E-b-e-d-f-S 1 E-a-d-f-S 2 E-b-e-d-g-S 1 E-a-d-g-S 4 E-b-e-f-S 1 E-b-c-g-S 7 E-e-d-S 2 E-b-d-S 2 E-e-d-f-S 2 E-b-d-f-S 2 E-e-d-g-S 2 E-b-d-g-S 2 E-e-f-S 4 Le chemin E-b-c-g-S a la valuation la plus élevée On va saturer ce chemin en augmentant le flot courant de 7 : La branche c-g est saturée. Etape 2 : on recommence comme à l'étape 1 en tenant compte du nouveau flot courant : Chemin Valuation min. [...]