Nouvelle Méthode de Résolution du Problème de Transport à Capacité par décomposition.

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.
In this paper, we present a new resolution method of the capacitated transportation problem (CTP). This method is based on two fundamental principles: a generalization of the inverse of the current basis matrix and an
adaptation of the decomposition method of Dantzig-Wolfe [6]. In some linear programming problem where the matrix of constraint is sparse (it is the case of the CTP), we prove that two or several variables can simultaneously enter the basis in a single iteration. Then, we show that the inverse of the matrix of the current basis resulting from the entry of some types of variables is automatically obtained without making products or inversion of matrices. The adaptation of the decomposition method is realized to hold in account the simultaneous entry of multiple variables to the basis. And so it avoids the
computation of the reduced costs of certain variables and decreases considerably the number of iterations.
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é; bounded linear Programs, revised simplex method, decomposition methods, capacitated transportation problems.

Journal des Sciences Pour l\'Ingénieur. Vol. 8 2007: pp. 52-61