Sur les flots a-flots maximaux et les flots à taux de sécurité maximal
BIENA ; LETROUIT
Type de document
CHAPITRE D'OUVRAGE (CO)
Langue
francais
Auteur
BIENA ; LETROUIT
Résumé / Abstract
Nous abordons, dans cet article, une généralisation de la théorie classique des flots permettant de résoudre des problèmes particuliers liés à la sécurité et à la fiabilité des réseaux. En 1976, M. Minoux introduit la notion d'a-flot dans son article intitule 'flots équilibrés et flots avec sécurité'[3]. Dans la partie 1 nous présentons les a-flots maximaux et les flots à taux de sécurité maximal. Dans la partie 2, nous traitons les a-flots maximaux. Nous montrons que l'algorithme proposé dans [3] pour obtenir un a-flot maximal ne converge pas toujours vers la solution optimale. Nous présentons les dysfonctionnements de l'algorithme [3]. Nous proposons un algorithme fortement polynomial, basé sur la méthode de Newton couplée avec l'algorithme classique de flot maximum et nous montrons l'efficacité des méthodes dichotomiques classiques pour ce problème. Dans la partie 3 nous traitons les flots à taux de sécurité maximal. Nous signalons que l'algorithme proposé dans [3] pour obtenir un flot à taux de sécurité maximal ne converge pas toujours vers la solution optimale. Nous présentons un algorithme fortement polynomial du même type que pour les a-flots maximaux et nous signalons aussi l'efficacité des méthodes dichotomiques pour ce problème.
