Nouvelle Méthode de Résolution du Problème de Transport à Capacité par décomposition.
Keywords:
Problèmes linéaires à variables bornées, Méthodes Révisée du Simplexe, Méthode de décomposition, Problèmes de Transport à capacitéAbstract
Dans cet article, nous présentons une nouvelle méthode de résolution du problème de transport à capacité
(PTC). Cette méthode est basée sur deux principes fondamentaux : une généralisation de l’écriture de l’inverse de la
matrice de base courante de la méthode révisée du simplexe et une adaptation de la méthode de décomposition des
programmes linéaires de Dantzig-Wolfe. Dans certains problèmes de programmation linéaire dont les matrices des
contraintes sont creuses (ce qui est le cas du PTC), nous arrivons à faire entrer simultanément deux ou plusieurs variables
dans la base, en une seule itération. Nous démontrons ensuite que l’inverse de la matrice de la base résultant de l’entrée de
certains types de variables est obtenue automatiquement sans effectuer des produits de matrices ni d’inversion de matrices.
L’adaptation de la méthode de décomposition est réalisée pour tenir en compte l’entrée simultanée de variables dans la
base. C’est ainsi qu’elle évite les calculs de coûts réduits de certaines variables et diminue considérablement le nombre
d’itérations.
