Problème de flot, d’affectation et de transport 173695

Extrait / Introduction

Extrait / Introduction :

Toute entreprise qu’elle que soit sa taille, son domaine d’activité est amenée à faire face à des problèmes de gestion au quotidien. Parmi ces problèmes, on cite les problèmes de flot, d’affectation et de transport qui nécessitent la mise en oeuvre d’un procédé de prise de décision rationnel, notamment la recherche opérationnelle, à cause de leur niveau de complexité particulièrement élevé et à cause des coûts supplémentaires qu’ils génèrent s’ils sont mal gérés. Ce qui souligne l’importance qu’occupe ce type de problème dans la gestion quotidienne de l’entreprise. C’est pour cette raison que le but de notre travail est de présenter des méthodes faciles de formulation et de résolution de ce genre de problème. Et pour cela, nous avons divisé notre travail en trois parties, où nous allons aborder dans un premier temps le problème de flot et plus précisément le problème de flot maximal à coût minimal, et ensuite nous allons présenter le problème de transport ainsi que des algorithmes de résolution appropriés. Et enfin nous allons traiter les problèmes d’affectation.

Plan

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

Signaler un abus