Résolution Du Problème De Flot A Coût Minimum Par La Méthode De Support Réseau

Abstract

Le problème de flot à coût minimum est l’un des problèmes classiques d’optimisation dans les réseaux. Ce dernier modélise diverses situations pratiques et qui sont résolues efficacement par la méthode du simplexe réseau. Le but de notre travail est d’appliquer la méthode directe de support à ce problème, et ce en tenant compte de la spécificité du problème traité. L’algorithme du support réseau proposé est itératif et permet de résoudre des problèmes d’optimisation dans les réseaux. Le schéma de l’algorithme est donné, puis illustré par un exemple pratique en logistique. Ce cas concret est modélisé comme étant un problème de flot à coût minimum, puis il est résolu par l’algorithme de support que nous avons implémenté sur Matlab The minimum-cost flow is one of the classic network optimization problems. It models a variety of practical situations that are efficiently solved by the network simplex method. The aim of our work is to apply the direct support method to this problem, taking into account the specificity of the problem at hand. The proposed network support algorithm is iterative and can be used to solve optimization problems in networks. A description of the algorithm is given, followed by a practical example in logistics. This concrete case is modeled as a minimum-cost flow problem, then solved by the support algorithm that we have implemented on Matlab.