Exposé flot maximum ford fulkerson 62120

Exemple de page de Exposé flot maximum ford fulkerson

1. Introduction :

La recherche opérationnelle est une discipline dont le but est de fournir des méthodes pour répondre à un type précis de problème, c’est-à-dire à élaborer une démarche universelle pour un type de problème qui aboutit à la ou les solutions les plus efficaces.

En recherche opérationnelle on a des problèmes connu comme le problème du flot de coût minimum, le problème du sac à dos, le problème du voyageur de commerce, le problème du chemin le plus court ou le plus long, ainsi que le problème du flot maximum auquel on s’intéressera dans cet exposé.

On peut décrire le problème du flot maximum en ces exemples :

Soit des châteaux d’eau ayant un débit constant. Ils desservent un certain nombre de villes, chacune ayant des besoins quantifiés constants. L’eau est acheminée à travers des conduits dont le débit maximum est connu. Le problème est de trouver un moyen de satisfaire au mieux les demandes de chaque ville. En d’autres termes, essayer d’apporter le plus d’eau possible vers les villes.

Pour un réseau de transport, déterminer le flot maximum de voitures qu’il peut supporter avant d’arriver à saturation. Étant donné des capacités des arcs on veut maximiser le flot entre les sources et les puits. Si l’on rejoint toutes les sources à une source unique et tous les puits à un puits unique, et que l’on trace l’arc de retour entre le puits unique et la source unique, cela revient à maximiser le flux dans l’arc retour.

On a utilisez des termes techniques peu compréhensible comme puit, source... etc. On éclairera ces termes dans leurs définitions.

Les applications du flot maximum sont multiples et dans diverses domaines on citera :

• Problèmes de réseaux impliquant une limite sur la capacité (pipelines, télécommunications (bande passante), . . .)

• Ordonnancement de la production (jobs/machines, programmes/processeurs, . . .)

Énormément d’applications comme sous problèmes dans d’autres algorithmes.

2. Définitions :

1. Réseau de transport :

Un réseau de transport est un graphe sans boucle, où chaque arc est associé à un nombre c (u) ? 0, appelé "capacité de l’arc u". En outre, un tel réseau vérifie les hypothèses suivantes.

• Il existe un seul noeud s qui n’a pas de prédécesseurs, tous les autres en ont au moins un. Ce noeud est appelé l’entrée du réseau, ou la source.

• Il existe également un seul noeud p qui n’a pas de successeurs, tous les autres en ont au moins un. Ce noeud est appelé la sortie du réseau, ou le puits.