Plan :
Problème de flot de valeur maximale à coût minimal Notion de base : Réseau de transport : Flux : Flot : Exemple de flot sur un réseau de transport : Problème de flot de valeur maximale à coût minimal : Présentation : Formulation : Méthode de résolution Définition graphe d’écart : Théorème d’optimalité : Construction du graphe d’écart : Exemple : Algorithme calculant un flot maximal de coût minimal : Déroulement de l’algorithme : Problème de transport Présentation : Formulation : Exemple : Méthode de résolution: recherche d’une solution de base réalisable : Solution de base Méthode du COIN NORD-OUEST : Application de la méthode du coin nord-ouest Méthode de BALAS – HAMMER : Application de l’algorithme de Balas-Hammer Optimisation d’une solution de base : Algorithme du STEPPING-STONE. Présentation de l’algorithme : Calcul des couts marginaux à l'aide des potentiels : Calcule des gains marginaux de la solution de base donnée par l’algorithme de Balas-Hammer.31 Vérification du résultat par le logiciel Solveur d’Excel Problème d’affectation Problème de flot, d’affectation, et de transport Présentation : Formalisation : La méthode Hongroise : Résolution d’un problème d’affectation par l’algorithme hongrois : Résultat donné par la méthode Hongroise : . Vérification par le logiciel Solveur d’Excel